가장 빠른 수평 라인 <-> 볼록한 다각형 교차로 알고리즘?

Question

비교적 간단한 것을 해결해야합니다. N-VENTERICE CONVEX 2D 다각형과 'Y'좌표가있는 수평 (!) 라인이 있습니다. 한 가지만 필요합니다. 다각형 이이 줄과 교차하는지 확인하려면 (즉, 2 개의 교차로가 있습니다)

내가 생각할 수있는 가장 빠른 것은 다각형 내에서 최소/최대 Y 좌표를 찾는 것입니다 (2 개의 비교와 2 개의 상점에서 루프 반복 N 회 반복).

어쨌든 나는 이것이 더 "수학적으로"해결 될 수 있다고 생각하지만 항상 느린 코드로 끝납니다 (예 : 벡터 웨이 - n [i] 및 n [i+1]에 대한 차이를 계산 한 다음 곱하고 추가 등 - - 2 cmps+상점보다 훨씬 느려집니다).

Answer 1

다각형에 y1 <y와 y2> y가있는 지점이 있는지 확인하면됩니다. 그러한 두 가지 점을 발견하자마자 끝났습니다. Y 좌표로 포인트를 색인 할 수 있다면 빠른 조회가되어야합니다.

Answer 2

수평 2D 라인이라면 예, 설명한 방법이 가장 빠릅니다. 마치 수표를 통해 파 부분을 얻고 최소 + 최대의> 및 y 값을 갖는 것처럼 교차로가 있습니다.

Answer 3

매번 RAW에서해야한다면 아마도 그보다 더 빨리 만들기위한 트릭을 찾지 못할 것입니다.

다각형으로 Min/Max Y 값을 캐시 할 수 있다면 테스트를 수행 할 때마다 각 정점을 반복하지 않아 시간을 절약 할 수 있습니다.

다각형에 관련된 경계 박스가있는 경우 다각형 대신 상자 범위에 대해 테스트하고 동일한 결과를 더 빨리 얻을 수 있습니다.

Answer 4

또 다른 접근법은 여기에 설명되어 있습니다.최적의 알고리즘 라인이 볼록 다각형이 교차하는 경우. 그러나 직교 라인으로 처리하고 있기 때문에 조금 단순화 할 수 있습니다 :). 따라서 총 복잡성은 값을 저장하지 않고 로그 N입니다.