중첩 라인 세그먼트를 찾는 알고리즘

StackOverflow https://stackoverflow.com/questions/1424923

문제 

n4------------------n3--------------------n2--n1
|                    |                    |    |
|                    |                    | P1 |
|                    |                    |    |
|                    |                    n6--n5
|                    |                    |
|              n11--n10                   |
n17      P4     |    |         P2         |
|               | P3 |                    n7
|              n12---n9                   |
|               |                         n8
|               |                         |
n16------------n15---------n14------------n13

위의 ASCII 아트에는 정확히 랩핑 라인 세그먼트가있는 4 개의 다각형 (P1, P2, P3, P4)이 있습니다. 예를 들어, 다각형 P2 (노드 N3, 10, 9, 12, 14, 13, 8, 7, 6) 및 P1 (N1, 2, 5 및 6) 사이의 라인 세그먼트에 의해 형성됩니다. N2와 N6 사이의 라인 세그먼트.

정확히 겹치는 라인 세그먼트를 찾는 가장 빠른 방법은 무엇입니까?

도움이 되었습니까?

해결책

각 모양이 가장자리 목록 인 경우 :

initialize map<edge, list of shapes> map
for each Shape s
  for each Edge e in s
    list l = map.get(e)
    if(l == null) 
      l = new list()
    l.add(s)
    map.put(e, l)

for each <edge, list> in map.entries
  if(list.size > 1)
    do something with this common edge

그것의 O (가장자리), 그리고 당신은 그것보다 더 잘할 수 없습니다. 이 솔루션은 구체적으로 수행하려는 작업에 따라 만족스럽지 않을 수 있습니다.

다른 팁

N 라인 세그먼트가 주어지면 최악의 경우 O (n^2) 교차점이있을 수 있습니다. 각 다각형이 동일한 가장자리를 공유하는 n 다각형이있는 경우를 생각해보십시오. 이 상황이 발생하는 것을 막기위한 추가 제약이 없다면 (추가하기 위해 생략) 최악의 알고리즘은 최악의 경우 O (n^2)가 될 것입니다. 교차로를 나열하는 것은 O (n)입니다. ^2).

실제로, 라인 세그먼트의 교차점을 찾기위한 계산 형상에서 가장 효율적인 알고리즘은 스윕 라인 알고리즘입니다. 모든 교차로를 찾기위한 최악의 경우 실행 시간은 O (k log n)입니다. 여기서 k는 교차의 수입니다 (이것은 n^2 일 수 있지만 드물게는 거의 없습니다.)

필요한 알고리즘에 대한 설명을 찾을 수 있습니다. Thomas H Cormen의 알고리즘 소개 계산 형상 섹션에서.

Twolfe18의 알고리즘이 좋아 보입니다. 그러나 일치하는 가장자리가 동일하게 설명되지 않은 경우 합병증이 추가 될 수 있습니다. 예에서 P1과 P2는 모두 N2-N6 에지를 공유합니다. 그러나 P2의 가장자리는 대신 N2-N7 세그먼트에 의해 설명 될 수있다 (N2-N6 및 N6-N7이 Colinear 인 경우). 그런 다음 두 개의 가장자리가 겹치는지 여부를 결정하려면 더 복잡한 해싱 방법이 필요합니다. 세그먼트를 라인에 매핑하여 두 개의 가장자리가 겹치고 해시 테이블의 선을 찾은 다음 라인의 매개 변수 공간에서 간격 트리를 사용하여 라인의 두 세그먼트가 교차하는지 여부를 테스트 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top