0

辺が等しい不規則な多面多角形が与えられます。それを6つの等しいサイズの合同領域に分割するアルゴリズムはありますか??

4

1 に答える 1

5

いいえ。そのような細分化は常に可能であるとは限りません。

2つの正多角形を結合し、異なる非常に多数の辺とを使用してP得られた多角形について考えてみます。このポリゴンは、円盤のペアを任意の精度で近似します。P1P2N1N2C1C2

その細分化を6つの合同な領域と考えてください。

の頂点のセットを考えてみましょうP1。少なくとも(N1)/6頂点を含む領域が必要です。頂点V1と領域を呼び出しR1ます。少なくとも(N2)/6の頂点を含む領域が必要ですP2。頂点V2を領域と呼びR2ます。

の場合、へR1 != R2の合同マッピングが必要です。の場合、そのようなマッピングは不可能です。N1よりもはるかに大きくなるようにN2を選択します。R2R12*N1 < N2

したがって、R1 == R2。V1との両方を含む領域がありV2ます。各領域の直径は、の直径よりも大きくする必要がありますP2。

2円近似を使用します。各領域には、の周囲長の少なくとも1/6のC1弧と、の周囲長の少なくとも1/6の弧が含まれている必要がありますC2。また、両方の円の内側に少なくとも1つの領域があり、小さい方の円の内側に完全にある領域はありません。

の可能な一致を考慮してくださいR1。合同は、1）主軸に沿った反射であるか、2）P1またはP2のいずれかをPの外側にマップするか、3）周囲の一部をPの内部にマップします。反射は十分ではないため、サブディビジョンには合同が含まれている必要があります。これは、P1の一部をP1の内部にマップします。

したがって、各領域の境界には、直径が。の凹状の円弧が含まれている必要があります12。直感的には、これはそのような細分化が存在できないことを示しています。

検出できるポリゴンには多くのクラスがあります。

  • 次数6回転対称C6。これらは、回転対称性を尊重する任意の方法で細分化できます。
  • 次数3の二面体対称性D6（次数3の回転+ミラー）。鏡に沿って切ります。
  • 頂点で交わる4つのポリゴンで平行移動して平面を並べて表示する形状。これらは、一致する反対のパスの2つのペアを持つ形状です。刃先を一方向に複製し、他の方向に三重にします。
  • 一部の形状には反射対称性があり、個々の半分には3次の回転対称性があります。これらも検出してカットすることができます。
  • 一部の形状は2次回転対称であり、3次回転対称の2つの合同領域で切断できます。境界に沿って繰り返されるパターンを探します。
  • 一部の形状は3次の回転対称性を持ち、対称性を持って3つの領域に分割できます。そのような形を確実に検出できるかどうかはわかりません（検出C3は簡単ですが、その後の切断は簡単ではありません）。私は人間です。
  • ..。
  • ポリオミノは正方形で作られた形であり、ポリヘックスは六角形で作られた形であり、ポリイアモンドは三角形で作られた形です。それらは簡単に検出でき、細分化されているものもあります。サブディビジョンが存在する場合、それも検出が難しい場合がありますが、少なくとも、正しいサイズで整列されたグリッドを尊重するすべてのサブディビジョンを列挙して、それらが合同であるかどうかを確認できます。
  • ..。

問題の複雑さを示すために：目標が2つの合同な領域で複雑な形状（60の正方形）を分割することである論理パズルの特定のクラスがあります。人間がポリオミノを2つの合同な領域に分割するのが容易でない場合、コンピューターが一般的な形状を6つの合同な領域に分割することをどのように期待しますか？

細分化が可能なほとんどのケースを検出したい場合は、プログラミング時間（ますます多くの特殊なケースをサポートするため）とテスト強度の間でトレードオフを行う必要があります。手始めに、に固執しC6, D3 and checkerboard tiles => easy to subdivide; polyforms => maybe possible; the rest => probably no subdivisionます。

于 2012-10-28T08:57:38.783 に答える