5

いくつかの閉じた任意の形状/ポリゴンを表す線分の配列として与えられたデータを解析しています。これらの形状は凹状にすることができます。これが私が見ているものの簡単な例です：

ここに画像の説明を入力

ただし、提供されたデータには、セグメントが任意の順序で含まれています。例によると、私のデータは次のようになります{V,E,D,X,U,A,Z,C,B,W,Y}。したがって、セグメントをプロットすると正しい形状が表示されますが、形状に対して操作を行うのは簡単ではありません。

上記の配列を並べ替えて、閉じた各形状のセグメントが接続順に続き、各形状のセグメントがグループ化されるようにしようとしています。

そう

{V,E,D,X,U,A,Z,C,B,W,Y}

になるだろう

[ {A,B,C,D,E} , {X,Y,Z} , {U,V,W} ]

線分の各グループの順序は重要ではなく、個々の線分が順番に並べられているだけです。また、各グループの特定の開始セグメントも気にしません。

となることによって

[ {Y,Z,X} , {C,D,E,A,B} , {W,U,V} ]

同等に有効な結果です。

私は幾何学をたどる経験がなく、初歩的な試みと大ざっぱなオンライン検索では、迅速な解決策が得られませんでした。凹型ハルを調べましたが、データがポイント間の接続を既に知っていることを考えると、それはやり過ぎのようです。

4

2 に答える 2

2

頭を悩ませ、ここでの提案を試し、いくつかのヘルパー クラスを作成した後、かなり一般的なものを思いつきました。大まかな疑似コードでは、私の解決策は次のとおりです。

create group list;

while (line segments exist in pool)
{
    create new group;
    remove one segment from pool and place into group;

    while (endpoint of last line in group != startpoint of first line in group)
    {
        get the endpoint of the last line in group;
        search pool for line segment whose startpoint = that endpoint;
        remove that segment from the pool and place into group;
    }

    store group in group list;
}

このコードは、データに閉じた形状のみが含まれている (つまり、各形状のデータが正確に同じ座標できちんと終了している) という前提と、すべてのデータが孤立した線だけでなく形状を作成するという前提に依存しています。これがどれほど効率的かはわかりませんが、これが前処理ステップとして 1 回使用されることを考えると、それで十分です。

于 2016-12-27T13:38:13.760 に答える
1

各セグメントの始点と終点 (ノードと呼びましょう) を知っていて、ポリゴンに別のセグメントと共通のノードがないと仮定できる場合は、次のことができます。

  • ノードのリストを作成します。各ノードは、接続する 2 つのセグメントによって定義されます。たとえば、ノード 1 はセグメント A と E を接続するノード、ノード 2 は A と B を接続するノードなどです。

  • ノードをポリゴンにグループ化します。つまり、共通のセグメントを共有するすべてのノードをまとめます。

  • あなたは終わった

于 2016-12-26T12:40:17.687 に答える