6

ポリゴンを形成するポイントを取得して、色で塗りつぶそうとしています。一連の点があり、それに対してボロノイ図を計算します。結果は次のとおりです。

ボロノイ図

緑色の点は私が定義した点で、青色の点はボロノイ図の計算された頂点です。特定の緑色の点によって生成された多角形を塗りつぶしたいので、多角形を形成して塗りつぶすために、その周りにある点を知る必要があります。

Gift Wrapping AlgorithmConvex Hullについて読みましたが、必要なものではないようです。このニーズに合うアルゴリズムはありますか? 私は C++ でプログラミングしていますが、Java または C# のヘルプがあれば役に立ちます。

4

2 に答える 2

1

ギフト ラッピング アルゴリズム (凸包アルゴリズム) は、平面内の点のセットを含む最小の凸多角形を見つけるためのものです。それはあなたがここで望むものではありません。

Fortune のアルゴリズムは、ボロノイ図の実際の境界を見つけるための優れたソリューションです。これは単純なアルゴリズムではありませんが、完全な疑似コードがリンクされたウィキペディアのページで提供されています。ウィキペディアのページの下部に、いくつかの異なる言語でのフォーチュンのアルゴリズムの実装へのリンクがあります。

于 2013-05-28T17:25:15.297 に答える
0

フォーチュンのアルゴリズムの実装は、顔のエッジ リストを抽出するために使用できる自然な埋め込みを計算するように見えます。これが重要なデータ構造です。

struct Halfedge 
{
    struct  Halfedge    *ELleft, *ELright;
    struct  Edge    *ELedge;
    int     ELrefcnt;
    char    ELpm;
    struct  Site    *vertex;
    float   ystar;
    struct  Halfedge *PQnext;
};

ELleft特定の頂点または面に付随するエッジを角度別に並べた、二重にリンクされたリストのようにELright見えます。それが顔なら、あなたは金色です。それ以外の場合は、ハーフエッジ e を次のハーフエッジの反転に (反) 時計回りの順序で目的の頂点を中心に (つまり の反転ELleft) 更新することで、面の周りを反復処理できます。

于 2013-05-29T22:49:47.137 に答える