평면 스위프 알고리즘 : 교차점 이후에 세그먼트를 정렬하는 방법

Question

이 책에 기반한 세그먼트 교차점에 대한 평면 스윕 알고리즘을 C++ 코드로 구현하려고합니다 : http://www.cs.uu.nl/geobook/. 이들은 균형 이진 검색 트리를 사용하여 평면 스윕의 상태 구조를 구현할 것을 제안합니다.

상태 구조를 구현하기 위해 std :: set 구조를 사용하고 있지만 지점 "p"가 포함 된 세그먼트를 재정렬하는 데 문제가 있으며 상위 끝점은 "p"지점입니다. 그들은 동일한 좌표 점을 가지고 있습니다. 즉, 반복적 인 값을 허용하지 않기 때문에 std :: set에 삽입 할 수 없습니다 ... 더 낮은 끝점과 함께 삽입하려고했으나 그 다음에 순서를 잃을 것입니다. 그들은 "p"바로 밑의 스윕 라인과 교차합니다. 책에

의사 코드는 다음 말한다 :

U (P) 타오에 ∪C (P)의
1. 삽입 세그먼트. Tao의 세그먼트 순서는 에 의해 p 아래에 스윕 라인이 교차되는 순서와 일치해야합니다. 수평 세그먼트가있는 경우 p가 포함 된 모든 세그먼트 중에서 마지막으로 이됩니다.
2. 는 (* 삭제 및 C (P)의 세그먼트를 재 삽입하는 순서를 반전시킵니다. *)

나는 세그먼트를 삽입으로 나는 그들이 .. 자신의 순서를 반대로가는 방법을 모르는 상태 구조에서 x 위 종점 좌표로 정렬합니다. 나는 교차로 후에 그들의 순서를 교환하는 방법을 모른다.

아이디어가 있으십니까?

업데이트 :이 책은 https://books.google.com/books?id=C8zaAWuOIOcC에 있지만 일부 페이지는 나타나지 않습니다. 이 페이지는 24, 25, 26 희망은 어떤 상황

보다도,

Answer 1

로 작동해야 평면 스윕 상태 데이터 구조로서 사용되는 std::set 대한 분류 술어는 다음과

가

1. 그것은 (동적)을 스윕 라인과 소정의 세그먼트의 교점의 좌표를 계산해야 스윕 라인의 현재 위치를 나타냅니다.

2. 동점의 경우 (두 세그먼트가 같은 좌표에서 스윕 라인과 교차하는 것처럼 보일 때) 두 세그먼트의 각도도 비교해야합니다. 이렇게하면 상태의 세그먼트 순서를 찾을 수 있습니다 스윕 라인의 향후 위치를 나타냅니다. 요건 (1) 위는 스윕 라인 진보로 정확하게 세그먼트를 비교할 수 있도록 술어 객체 스윕 라인 위치 변수에 대한 참조를 보유해야한다는 것을 의미한다는

참고. 스윕 라인 위치는 알고리즘에서 업데이트 할 수 없기 때문에 술어 자체에 저장할 수 없습니다 (std::set은 참조로 술어에 대한 액세스를 제공하지 않습니다).std::set 이러한 술어 자동 요소를 재정렬되지 - (필요에 따라 교환 즉) 세트 내의 세그먼트의 정확한 순서를 유지하는 책임이 알고리즘 여전히 있음

EDIT

참고.

Answer 2

주요 종류가 Y에 그래서 비교 함수를 작성, 배에 작은을 제공하는 데 도움이, 제 2 장에 있습니다. 그런 다음 x가 다른 한 중복 된 y 값을 가진 세그먼트를 삽입 할 수 있습니다. (두 개의 동일한 세그먼트가 있다면 어쨌든 교차로 테스트를 위해 특별히 처리해야합니다.)

는

Answer 3

당신이 std::set에 대한 피팅 비교기를 사용하는 가정, 문제가되지 않습니다 std::set공통의 y 값에 두 개 이상의 항목의 모양을 사용하여. y 값 외에 을 비교하고 기울임차순으로 정렬하는 것이 좋습니다 (). (std::set에 대한 비교기의 예)

std :: set을 사용하지 말고 std :: vector와 같은 것을 사용하는 것이 좋습니다. std :: vector를 사용하면 특정 선분에 대한 참조를 스왑 (std :: swap) 할 수 있고 선분 시작/끝내기 O (log n) 시간에 삽입/제거 할 수 있습니다. 여기서 n은 선분 수입니다. 교차로에 해당하는 선분을 교체하여 회선 스윕 전체에서 상태의 올바른 순서를 유지한다는 것이 아이디어로, 이벤트 대기열 만 우선 순위 대기열입니다. 은 (통찰력을 위해, @Sneftel의 코멘트로 인해 감사를 제거되었습니다.)

스윕 라인 알고리즘에 대한 일반적인 접근 방식에 대해서 : 특정에 (sweep line status)는 선 세그먼트의 순서를 나타낸다 않는 상태 (현재) 시간을 표시합니다. 스윕 라인 상태의 경우, 필자는 @Sneftel에 의해 언급 된 바와 같이 밸런스 이진 트리를 사용해야한다. 그런 다음 교차로에 해당하는 선분을 교체하여 회선 스윕 전체에서 상태의 올바른 순서를 유지할 수 있습니다. event queue 만 우선 순위 대기열이어야합니다.