각 교차점에 대한 세그먼트와 교차 된 세그먼트 목록 찾기

Question

2D에서 세그먼트 목록에서 "모든 교차점"과 "교차점마다 교차 된 세그먼트"를 찾기 위해 CGAL을 사용하려고합니다. 몇 가지 이유로 Bentley-Ottmann 알고리즘을 사용하고 싶습니다. CGAL 라이브러리에는 Sweepline 2이라고하는이 알고리즘의 C++ 구현이 있지만 교차점 만 찾을 수 있습니다. CGAL에 다른 구현이 있습니까? 또는이 문제를 어떻게 해결할 수 있습니까?

Answer 1

편집 : 진짜로 빠른 수정은 생성 된 모든 교차점을 통해 스윕 라인 2, 루프를 사용하여 모든 교차점을 생성하기 위해, 그리고 것입니다 각 교차점 레코드 점의 좌표 것을 포함하는 모든 선분 모두 원하는 구조를 가리킨다. 당신이 당신의 다른 교차로를 모두 저장할 수 있도록

//Probably start off with a struct to store your information 
struct intersection{ 
    //This stores the x and y position of the intersection. 
    int[2] xyCoords; 
    //This stores the segment ids or indexes of the intersection line segments. 
    //For example, if the 1st and 5th line segment intersect, you would store 1 and 5 in here. 
    int[2] segmentIDs; 
} 

가 그럼 그냥 교차로 구조체의 벡터를 만들 :

---

빠른 해결책은 (이기는하지만 가장 효율적이지)이다.

vector<intersection> intersectionVector; 

그런 다음 다음과 유사한에있는 선분의 ​​모든 통해 단지 루프 :

for (int i = 0; i < numSegments; i++){ 
    for (int j = 0; j < numSegments; j++){ 
     //Don't look at the same points.   
     if (i == j) 
      continue; 
     //See below for pseudocode for this part. 
    } 
} 

지금 대신 How do you detect where two line segments intersect?을 참조 아무것도 개혁의, 그 블록을 작성합니다.

위의 링크에서와 같이 r × s 및 (q - p) × r의 값을 계산합니다. 여기서 x는 벡터 교차 곱입니다. 거기에서, if/else 블록을 사용하여 네 가지 사례 (ctrl f는 "네 가지 경우가 있습니다 :")를 설명합니다. 질문에 윤곽을 나타 내기만하면 케이스 3의 유효성을 확인하십시오. 유효하면 벡터 및 x/y 좌표뿐만 아니라 사용중인 구조에 선분의 색인을 저장하십시오 .

당신이해야 할 추가 작업은 u를 계산하여 교차점의 x 좌표를 저장하기 위해 검사중인 두 번째 선분에 적용하는 것입니다.