一晩中私を悩ませた質問があります。
一連のポイントが与えられた場合、次のように言います。
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
最大のポリゴンは 4x4 の正方形です。このため：
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
最大のものは台形ですが、不規則な形やその他のバリエーションがあります...
可能な限り最大のものを決定する方法は？(最大のものは、他の多角形で囲むことができないことを意味します) どのようなアルゴリズムを使用すればよいですか?
また、面積、周長、凸(t/f)、不変回転数などの他の属性も必要です...
これは説明書に記載されていますが、それが正確に何についてのものであるかはよくわかりません...
サイズが 2x2 から 50x50 の間の任意の 2 次元配列をエンコードして呼び出します(両方の次元は異なる場合があります)。その要素はすべて 0 または 1 です。配列の最大 8 つのメンバーのいずれかをエンコードするメンバーの隣人
mを呼び出します。の値は 1 であり、両方のインデックスのそれぞれが の対応するインデックスと最大で 1 異なります。特定のエンコーディングが与えられると、次のように、すべての自然数について (このエンコーディングの)深さのポリゴンのセットmを帰納的に決定します。dd自然数
dが与えられ、すべての d 0 < d に対して、深さ d 0のポリゴンのセットが決定されたとします。これらのポリゴンを決定するすべての 1 を 0 にエンコードするように変更します。次に、深さ d のポリゴンのセットは、次のような方法で 1 を隣接するものと接続することにより、そのエンコードから取得できるポリゴンのセットとして決定されます。最大多角形 (つまり、1 を隣接するいくつかの多角形と 1 を接続することによって、そのエンコードから得られる他のどの多角形にも含まれない多角形)。