겹치는 선 세그먼트를 찾는 알고리즘

 
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, 15, 14, 13, 8, 7, 6 및 2 사이의 선분과 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 (가장자리), 그리고 그것보다 더 잘하지 않을 각 형태는 다음 가장자리의 목록 인 경우

출처

2009-09-15 magneticMonster

예 설명이 잘못되었습니다. P1에는 노드 1,2,5,6가 있고 P2에는 노드 2,3,10,9,12,15,14,13,8,7,6이 있습니다. – perimosocordiae

@perimosocordiae 감사합니다. 나는 그 설명을 고쳤다 고 생각한다. – magneticMonster

대답하기 전에 도형이 어떻게 저장되는지 언급해야합니다. 그런 종류의 대답은 해답에 영향을줍니다. – twolfe18

. 이 솔루션은 당신이 구체적으로하고 싶은 것에 따라 만족스럽지 않을 수도 있습니다.

출처

2009-09-15 03:52:52 twolfe18

+1이 겹치지 않을 것입니다. 추가 메모로 모양이 점 목록으로 저장되는 경우 점을 쌍으로 훑고 가장자리가 정렬 된 쌍 (p1, p2)으로 표시되도록 할 수 있습니다. 여기서 p1 < p2 => p1.x

N 개의 선분이 주어지면 최악의 경우 O (n^2) 개의 교차점이있을 수 있습니다. 각 다각형이 같은 가장자리를 공유하는 N 개의 다각형이있는 경우를 생각해보십시오. 이 상황이 발생하지 않도록 추가 제약 조건이 없으면 (추가하지 않으므로) 최악의 경우 O (N^2)가 될 수있는 최상의 알고리즘은 단순히 교차를 나열하는 것이 O^2).

사실상 선분의 교차점을 찾기위한 계산 기하학에서 가장 효율적인 알고리즘은 스윕 라인 알고리즘입니다. 모든 교차점을 찾기위한 최악의 경우의 실행 시간은 O (k log n)이며 여기서 k는 인터셉 션 수입니다 (N^2 일 수는 있지만 거의 없습니다.)

정확하게 알고리즘에 대한 설명을 찾을 수 있습니다 계산 기하학에 관한 섹션에서 Introduction to algorithms by Thomas H Cormen이 필요합니다.

출처

2009-09-15 05:21:23 ldog

어떻게 O (n^2)를 얻습니까? m 개의 모서리를 가진 n 개의 도형이 있다면 O (n * m)가됩니다. 모든면을 검사해야하기 때문에 분명히 잘할 수 없습니다. 내 알고리즘은 O (n * m)입니다. 또한 질문에 답변하지 않았습니다. – twolfe18

나는 선분을 말했다 *. 폴리곤으로 준 예제는 일러스트레이션 일뿐입니다.O (n^2) 알고리즘은 분명하고 사소한 알고리즘입니다. 실제로, sweepline 알고리즘은 사소한 알고리즘을 크게 수행합니다. – ldog

twolfe18의 알고리즘이 좋아 보인다. 그러나 일치하는 가장자리가 동일하게 설명되지 않으면 추가되는 복잡성이있을 수 있습니다. 귀하의 예에서 P1과 P2는 모두 n2-n6 에지를 공유합니다. 그러나 P2의 에지는 세그먼트 n2-n7에 의해 대신 설명 될 수 있습니다 (n2-n6 및 n6-n7이 동일 직선 인 경우). 그런 다음 두 개의 가장자리가 겹치는 지 확인하기 위해보다 복잡한 해싱 방법이 필요합니다. 세그먼트를 행에 매핑하고 해시 테이블에서 행을 찾은 다음 행의 두 세그먼트가 행의 매개 변수 공간에있는 간격 트리를 사용하여 교차하는지 테스트하는 방법으로 두 개의 가장자리가 겹치는 지 여부를 알 수 있습니다.

출처

2009-10-11 03:41:46

겹치는 선 세그먼트를 찾는 알고리즘

답변

관련 문제