3

多くのポリゴンのエッジを含むベクトル描画があります。各エッジは、始点と終点で表されます。エッジ間の接続は明示的に示されません。このデータからポリゴンを抽出する必要があります。これを行う明白な方法は、各エッジの 1 つの頂点を取得し、他のすべてのエッジで一致する頂点を検索し、エッジの次の頂点でこれを繰り返して、閉じたループができるようにすることです。しかし、これは非常に非効率的です。

特定の順序でエッジの開始点と終了点のみを指定してポリゴンを抽出するための優れたアルゴリズムは何ですか?

4

2 に答える 2

2

次のようなものを試してください (python-pseudocode):

vertices = {} #map (x, y) coords to a list of all edges containing that vertex

for edge in edges:
    #add start & end vertices
    if edge.start not in vertices:
        vertices[edge.start] = []
    if edge.end not in vertices:
        vertices[edge.end] = []
    vertices[edge.start].append(edge)
    vertices[edge.end].append(edge)

これで、すべての頂点と、各頂点から出ているすべてのエッジができました。これで、アルゴリズムの最初のアイデアを実行できますが、一致する頂点をすべてのエッジで検索する代わりに、その検索は瞬時に行われます。

于 2013-03-14T14:53:59.490 に答える
1

それを行う簡単な方法の1つは次のとおりです。

Sort the list of edges by end point. Call that array edges
Create a new array, polygon, size is num_edges 
edgeIndex = 0
copy edge from edges[0] to polygon[0]
count = 1
while (count < number_of_edges)
{
    starting_point = edges[edgeIndex].endpoint
    // do a binary search to find the segment that starts
    // at this edge's end point
    newIndex = binary_search(edges, starting_point)
    copy edge[newIndex] to polygon[count]
    ++count
    edgeIndex = newIndex
}

これが完了すると、polygon配列にはエッジが順番に含まれているはずです。

上記は、エッジポイントが合理的に出力されることを前提としています。つまり、頂点が '[(0, 0), (10, 10), (10, 0)]' の三角形がある場合、辺は次のように与えられます。

{(0, 0), (10, 10)}
{(10, 10), (10, 0)}
{(10, 0), (0, 0)}

必ずしもその順序ではありませんが。2 番目のエッジが次のように指定されている場合{(10, 0), (10, 10)}(つまり、開始と終了が逆になっている場合)、問題はやや難しくなります。

ハッシュ マップと直接検索を使用して同じことを行うことができます。これは、二分探索よりも高速です。

また、これは、1 つの点に 2 つ以上のエッジが接続されていないことを前提としていることにも注意してください。

于 2013-03-14T17:18:35.270 に答える