스윕 알고리즘

Question

이중 데이터에 대해 좋은 결과를 얻을 수있는 좋은 스윕 알고리즘을 누가 추천 할 수 있습니까? 몇 가지 문서, 방법 등.

2 차원 공간에서 그래프의 교점을 검출하는 스윕 알고리즘입니다. 그래프는 항상 닫힙니다.

Answer 1

http://www.amazon.com/Computational-Geometry-Algorithms-Applications-Second/dp/3540656200의 하나가 꽤 좋습니다.

교차로 테스트를위한 스위프 라인은 매우 간단합니다. 시작을위한 자료 : http://www.cs.umd.edu/~mount/Papers/crc-intersect.pdf.

Answer 2

나는 평면 ​​폐 그래프의 교차점을 검출하기위한 스윕 알고리즘에 대해 지금까지 3 가지 변형을 구현했습니다. 그래프를 나타내는 커다란 데이터를 가지고 있습니다 (예를 들어 200 개 이상의 가장자리가 있습니다. 정점은 2D에서 점들의 쌍입니다. 모서리는 두 개의 정점의 한 쌍입니다. 하나는 소스가되고 다른 하나는 대상이됩니다). 다른 목적을위한 C++ 라이브러리.

문제는 3 구현이 정수 나 두 배 길이의 데이터에서는 잘 작동하지만 그래프를 나타내는 데이터에 이러한 3 가지 구현 중 하나를 시도 할 때 매번 다른 결과를 얻었지만 좋은 결과는 아닙니다. 사람.

• 나는 모든 내가 원하는 교차하지만, 다른 점 그래프에서 (교차하지)

• 나는 결과 그래프에서 몇 가지 포인트가 있는지 여부를하지만 내가 필요로하는 일부 교차로가 있는지 여부 내가 가진 여부 계산 된 결과

• 에서 누락 된 단지 교차로

이 모든 depe 필요 nds는 내가 본 것과 다른 것 위에있는 정렬 함수에 있지만, 나는 그것을 이해할 수 없다. 분명히 어떤 경우에만 작동하고 나는 이런 종류의 기능이 monoticity과 다른 경우에 대한 좋은 생각

x.E1.Vstart<x.E2.Vstart or 
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart<y.E2.Vstart or 
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart==y.E2.Vstart and slope(E1)<slope(E2) 

하지만 :

을 감안할 때 두 가장자리 E1(Vstart,Vend), E2(Vstart,Vend)로 다음과 같이 정렬 기능은 그래프의 가장자리를 주문한다 규칙적인 교차점 외에도 다른 교차점도 감지합니다. 어떤 경우에는 모든 교차점을 계산하지 않고 그래프의 일부 지점 만 계산한다는 점에서 전혀 작동하지 않습니다.