algorithm - マップ上のゼロのクラスターを 8 つ以下の頂点を持つポリゴンで囲みます

Question

画像マップ (500 x 500) では、0 と 1 しかありません。ほとんどすべてが 1 ですが、ゼロのクラスターがいくつかあります (これは障害物を表すため、丘のようにプレイヤーが越えることはできません)。障害物は任意の形状を持つ可能性があるため、単純化する必要があるため、そのような障害物をすべて、頂点が 8 つ以下のポリゴンで囲む方法を見つけることにしました (周囲のポリゴンは内部に 1 をいくつか持つことができますが、障害物のすべての 0 は内部にある必要があります)。そのポリゴン）。すべての障害物に対して、1 つのポリゴンを生成する必要があります。障害物の外側の境界ですべての 0 を接続できますが、n ( n >> 8 ) 個の頂点を持つポリゴンが生成されます。これを行う方法や同様のアルゴリズムの名前について提案を求めています。

Answer 1

最初にクラスターの凸包を構築する必要があります。この後、次の戦略を使用して頂点の数を 8 に減らすことができます。

接続されたポイントの任意のペアのクロスポイントを見つけます。提供された画像では、ポイント 8 と 9 が 10 に置き換えられましたが、ポリゴン サイズが大きくなりました。

注:このアプローチは、このポリゴンが別の「ゼロ」のクラスターと重ならないことを保証するものではありません。場合によっては、8 つの頂点を持つポリゴンが、別のクラスターの交差なしにクラスターをカバーできないことがあります。

Answer 2

S、SW、W、NW、N、NE、E、および SE の最も遠い点を障害物と見なし、これらの点を垂直方向に通過するセグメントによって設定された八角形を作成できます。すなわち適切に: WE、NW-SE など。それが最速で最も簡単なアルゴリズムであり、@Толяのソリューションとは逆に、余分な長い星の光線のような頂点が得られることは決してないと思います。