algorithm - 2D 空間で 2 つのポイント セットを分離するポリゴンを検​​出するアルゴリズム

Question

2D 空間に点のセットがあります。ポイントには 2 つの異なるタイプがあります (いくつかのポイントは色が黒で、残りは白であるとします)。ポイントの 2 つのサブセットを分離するポリゴンを見つけるアルゴリズムを見つける必要があります。多角形の頂点は、2 種類の点のいずれかになります。

グーグルで調べてみましたが、適切なアルゴリズムが見つかりませんでした。それを行うアルゴリズムはありますか？

Answer 1

あなたの質問はあまり明確ではありませんが、存在を求めているだけだと思います。次のアルゴリズムを考慮します。

1. 特定の色を選んでください、たとえば黒
2. 直線を使用して、この頂点を黒色の他のすべての頂点に結合します。おそらく、パス上に白い頂点があってはなりません。
3. 白い頂点が直線上にある場合は、無限に迂回します。
4. 黒いノードで形成されたこの「スター」ネットワークの周りに多角形を描きます。

最後のステップは、多角形を「スター」ネットワークの非常に近くに描画する限りいつでも実行できるため、2D で黒点と白点を分離する多角形が得られます。