세그먼트가 다각형 안에 완전히 있는지 알아보십시오

Question

P의 경계에서 A 점에서 시작하여 P의 경계에서 B로 끝나는 세그먼트가 P 내부에 완전히 포함되어 있는지 어떻게 알 수 있습니까?

편집 :이 경우에는 다각형의 경계에서 다른 세그먼트와 세그먼트의 교차점을 확인할 필요가 없습니다. 나중에 수행 될 예정입니다.

일정한 시간 내에이 작업을 수행 할 수 있습니까?

Answer 1

편집 된 설명에 따라 다각형은 간단하며 시계 반대 정렬 순서로 세그먼트 목록으로 표시되고 쿼리 세그먼트의 내부는 다각형의 경계와 교차하지 않으며 쿼리 세그먼트의 끝점 중 어느 하나의 끝점을 포함하는 폴리곤 세그먼트를 알 수 있습니다.

끝점이 다각형 정점이면 두 가지 상황이 발생할 수 있습니다. 이들은 정점에 대한 각도를 2D 결정자 테스트와 비교하여 일정 시간 동안 구별 할 수 있습니다. 엔드 포인트가 다각형 세그먼트의 내부에 놓여있는 경우

Case 1: segment not in polygon 

     \ query segment 
     \ 
*<--------*<--------* 
    polygon 
    interior 


Case 2: segment in polygon 

*<--------*<--------* 
    polygon \ 
    interior \ query segment 

는 다음 유사한 테스트있다 (이 정점있다 척).

다음은 각도 테스트의 세부 사항입니다. 폴리곤 정점이 (0,0)이되도록 모든 것을 해석하십시오. 그런 다음 우리는

(e,f)  (0,0)  (c,d) 
    *<--------*<--------* 
    polygon \ 
    interior \ query segment 
       * 
      (a,b) 

쿼리 세그먼트가 x 축에 놓 이도록 모든 것을 회전 (및 중요하지는 않음)합니다. 이것은 새도 우리 축퇴 가정함으로써

 * (ac+bd,ad-bc) = (p,q) 
    /
    /
    |_  query 
    *-----------* (a^2+b^2,0) 
/
/
|_ 
* (ae+bf,af-be) = (r,s). 

, (p,q) != (0,0)를 얻기 위해 매트릭스

[ a b] 
[-b a] 

곱하여 이루어진다. 이제 (p,q)은 q>0 || (q==0 && p>0) 인 경우 상반부 평면에 있습니다. 그렇지 않은 경우 하단 평면에 있습니다. (r,s)에 대해서도 마찬가지입니다.

(p,q)이 위쪽 평면에 있고 (r,s)이 더 낮은 경우 쿼리 세그먼트가 안에 있습니다. 반대의 경우 반대쪽에 있습니다. 그렇지 않은 경우, 점들은 동일한 평면에 있습니다. 결정 요인 테스트는 ps-qr > 0 (내부) 또는 ps-qr < 0 (외부)인지 여부입니다. 다각형은 단순하기 때문에 평등 할 수 없습니다.

아마 저보다 지식이 많은 사람이이 테스트의 정도를 4 분위로 줄일 수 있습니다. 내가 제대로 질문을 이해한다면

Answer 2

, 다음 이가지 경우를 구별하려고 :

• AB는 전적으로 다각형 엔드 포인트를 제외하고
• 내에는, AB는 다각형의 외부 전적으로

AB가 각면과 교차하는지 이미 테스트했기 때문에 AB가 부분적으로 다각형 내부에있는 경우를 제외했습니다.

귀하의 질문은 AB의 중간 점이 다각형 내에 포함되어 있는지 묻는 것과 같습니다. Wikipedia에는 ​​이것을 결정하는 방법을 설명한 괜찮은 기사가 있습니다 : http://en.wikipedia.org/wiki/Point_in_polygon. 나는 당신이 일들을 수치 적으로 안정시키기를 원한다면 와인딩 숫자 접근법을 제안 할 것이다.