무작위로 나열된 모서리에서 다각형 감지

Question

많은 폴리곤 모서리가 포함 된 벡터 드로잉이 있습니다. 각 가장자리는 시작점과 끝점으로 표시됩니다. 모서리 사이의 연결은 명시 적으로 표시되지 않습니다. 이 데이터에서 다각형을 추출해야합니다. 이를 수행하는 확실한 방법은 각 에지의 하나의 정점을 취하여 모든 다른 에지에서 일치하는 정점을 검색하고 폐 루프가있을 때까지 에지의 다음 정점으로이를 반복하는 것입니다. 그러나 이것은 매우 비효율적입니다.

가장자리의 시작점과 끝점을 특별한 순서없이 지정하여 추출한 좋은 알고리즘은 무엇입니까? 이 (파이썬 - 의사)와 같은

Answer 1

시도 뭔가 :

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) 

지금 당신은 모든 정점과 각 꼭지점에서 나오는 모든 가장자리를 가지고있다. 알고리즘에 대한 초기 아이디어를 이제 할 수 있지만, 일치하는 정점에 대한 모든 에지를 검색하는 대신, 그 룩업은 즉각적입니다. 그것을 할 수

Answer 2

쉬운 방법 중 하나는 다음과 같습니다 당신이 완료하면

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)} 

있지만, 반드시이 순서이다. 두 번째 가장자리가 {(10, 0), (10, 10)}으로 주어지면 (즉 시작과 끝이 뒤집 혔을 때), 문제는 다소 어렵습니다.

해시 맵과 직접 검색으로 똑같은 작업을 수행 할 수 있습니다. 이진 검색보다 빠릅니다.

또한 하나의 점에 두 개 이상의 가장자리가 연결되어 있지 않은 것으로 가정합니다.