coordinates - 平面を分割する方法

Question

たとえば、特定の平面内の座標など、固定数 (X) の点があるとします (2-D 点群と呼ぶことができると思います)。

これらのポイントは、Y < X の Y ポリゴンに分割する必要があります。ポリゴンはオーバーラップしてはなりません。ポリゴンがコンベックス（ボロノイ図のようなもの）だったら最高です。

国を形成する場所のように想像してみてください。たとえば、12 個のポイントがあり、それぞれ 4 個のポイントを持つ 3 つのポリゴンを作成したいとします。

ポイントをカバーするグリッドを作成することを考えました。次に、点を反復処理して、最も近いグリッド セルに割り当てます。

多分私は明白なことを見逃していますか？より良い解決策があると確信しています。

ありがとう、ダニエル

最適化 (kmeans++)を見つけました。おそらくこれにより、より良い結果が得られるでしょう..

Answer 1

ボロノイ図について言及されましたが、関連するテッセレーション アルゴリズムを見たことがありますか? もしそうなら、なぜそれらがあなたにとってうまくいかないのかを強調していただけますか?

Answer 2

おそらく、ポリゴン パーティションを作成するために使用する基準をより適切に定義する必要があります。たとえば、近接の場合は、次のことができます。

• ボロノイ図を作成します。
• 隣接する 2 つのポリゴンに隣接するポリゴンがある場合は、それらを 1 つのポリゴンにマージします。
• 必要な数のポリゴンが得られるまで繰り返します

ポリゴンごとのポイント数が等しい場合、目的のポイント数が満たされるまで、隣接するポリゴンをマージすることに基づいて、同様のことを行うことができます。

編集:凸状が最も重要な問題である場合は、雲の真ん中にポイントを取り、放射状を端に投影して、雲を放射状の三角形の配列に分割することができます。