폴리곤의 점

Point in polygon
단순 다각형 예제

계산 지오메트리에서 PIP(Point-in-Polygon) 문제는 평면의 특정 점이 폴리곤의 내부, 외부 또는 경계에 있는지 여부를 묻습니다.점 위치 문제의 특수한 경우이며 컴퓨터 그래픽, 컴퓨터 비전, 지리 정보 시스템(GIS), 모션 계획, 컴퓨터 지원 설계(CAD) 등 기하학적 데이터를 처리하는 영역에서 응용 프로그램을 찾습니다.

컴퓨터 그래픽의 문제에 대한 초기 설명은 1974년 [1]초에 사용 중인 두 가지 일반적인 접근법(레이 캐스팅과 각도 합산)을 보여준다.

문제의 이력과 해결 방법을 추적하기 위한 컴퓨터 그래픽 전문가의 시도는 Ray Tracing News [2]호에서 확인할 수 있습니다.

레이캐스팅 알고리즘

폴리곤 외부에서 임의의 점으로 통과하는 광선의 교차점 수. 홀수인 경우 점이 폴리곤 내부에 있음을 나타냅니다.짝수인 경우 점은 폴리곤 외부에 있으며 이 테스트는 3차원에서도 작동합니다.

점이 단순한 폴리곤의 안쪽에 있는지 외부에 있는지 확인하는 간단한 방법 중 하나는 해당 점에서 시작하여 고정된 방향으로 가는 광선이 폴리곤의 가장자리를 교차하는 횟수를 테스트하는 것입니다.점이 폴리곤 외부에 있는 경우 광선이 모서리와 짝수 횟수 교차합니다.점이 폴리곤 내부에 있는 경우 점이 모서리와 홀수 횟수 교차합니다.폴리곤 가장자리의 점 상태는 광선 교차 알고리즘의 세부 정보에 따라 달라집니다.

이 알고리즘은 교차수 알고리즘 또는 짝수 규칙 알고리즘이라고도 불리며 [3]1962년부터 알려져 있었습니다.이 알고리즘은 점이 무한대에서 프로브 포인트로 광선을 따라 이동하고 폴리곤의 경계를 여러 번 교차하면 외부에서 내부로, 그리고 내부에서 외부로 교대로 이동하는 단순한 관찰에 기초하고 있습니다.그 결과, 두 번의 "국경 통과" 후에 이동 지점은 밖으로 나간다.이 관찰은 조던 곡선 정리를 사용하여 수학적으로 증명될 수 있다.

한정된 정밀도

유한 정밀 산술이 있는 컴퓨터에 실장되어 있는 경우, 반올림 오차로 인해 점이 그 경계에 매우 가까운 경우 결과가 부정확할 수 있습니다.대부분의 컴퓨터 [dubious – discuss]그래픽스 응용 프로그램에서는 속도가 완전한 정확도보다 훨씬 중요하기 때문에 이것은 일반적으로 문제가 되지 않습니다.그러나 공식적으로 올바른 컴퓨터 프로그램의 경우, 수치 공차 θ를 도입하여 P(점)가 L(선)의 θ 내에 있는지 검사해야 하며, 이 경우 알고리즘은 정지하고 "P는 경계에 매우 가깝다"고 보고해야 한다.

레이 캐스팅 알고리즘의 대부분의 구현은 연속적으로 폴리곤의 모든 변과 레이의 교차점을 확인합니다.이 경우 다음과 같은 문제를 해결해야 합니다.광선이 폴리곤의 정점을 정확히 통과하면 끝점에서 2개의 세그먼트와 교차합니다.예제의 맨 위 정점의 경우 또는 교차점 4와 5 사이의 정점의 경우 정상이지만, 알고리즘이 올바르게 작동하려면 맨 오른쪽 정점의 경우 1개의 교차점을 셀 필요가 있습니다.광선에 떨어지는 수평 세그먼트에서도 비슷한 문제가 발생합니다.이 문제는 다음과 같이 해결됩니다.교차점이 테스트된 다각형 변의 정점인 경우 변의 다른 정점이 광선 아래에 있는 경우에만 교차점이 카운트됩니다.이는 사실상 광선의 정점을 광선의 약간 위에 있는 것으로 간주하는 것과 같습니다.

다시 한 번, 정점을 통과하는 광선의 경우는 유한 정밀 산술에서 수치 문제를 일으킬 수 있다. 같은 정점에 인접한 두 변에 대해 광선을 사용한 교점의 간단한 계산은 두 경우 모두에서 정점을 제공하지 않을 수 있다.폴리곤이 꼭지점에 의해 지정된 경우, 실제로 교차점을 계산하기 전에 광선의 y 좌표와 테스트된 폴리곤 측의 끝을 확인하여 이 문제를 제거합니다.다른 경우 폴리곤 변을 다른 유형의 데이터로 계산할 때 알고리즘의 수치적 견고성을 위해 다른 트릭을 적용해야 합니다.

권선수 알고리즘

점이 폴리곤 내부에 있는지 확인하는 데 사용되는 또 다른 기술은 폴리곤에 대해 주어진 점의 와인딩 수를 계산하는 것입니다.권선 번호가 0이 아닌 경우 점은 폴리곤 내부에 있습니다.이 알고리즘은 비제로 규칙 알고리즘이라고도 합니다.

와인딩 수를 계산하는 한 가지 방법은 [4]폴리곤의 각 변에 의해 부분 처리된 각도를 합산하는 것입니다.그러나 여기에는 비용이 많이 드는 역삼각함수가 포함되므로 일반적으로 이 알고리즘은 레이캐스팅 알고리즘에 비해 성능이 비효율적입니다(느림).다행히 이러한 역삼각함수는 계산할 필요가 없습니다.그 결과 이후 모든 각도의 합계 0또는 2π로 제한하기로 했지만 그것은 꼬불꼬불한 번호 알고리즘 속도의 경계 교차 계수 비견될 만하지 시험 지점 주변을 보는 다각형 winds,[5]quadrants을 통해 추적하는 것으로 충분하다{2\pi\displaystyle}(2π의 또는 배수{\displaystyle 2\pi})를 할 수 있다.에서gs.

댄 선데이의 와인딩 넘버 알고리즘 시각화.권선 번호 0은 점이 폴리곤 외부에 있음을 의미하며, 다른 값은 점이 폴리곤 내부에 있음을 나타냅니다.

와인딩 수를 계산하기 위한 개선된 알고리즘은 2001년 [6]댄 선데이에 의해 개발되었습니다.계산에서 각도나 삼각법을 사용하지 않으며 위에서 설명한 레이 캐스팅 알고리즘과 정확히 동일하게 기능합니다.일요일 알고리즘은 체크되는 지점에서 무한 수평 광선을 캐스트하는 것으로 동작합니다.이 광선이 폴리곤의 가장자리를 통과할 때마다 후안 피네다의 가장자리 교차 알고리즘(1988)[7]을 사용하여 교차선이 와인딩 수에 어떤 영향을 미칠지 결정합니다.일요일이 설명한 바와 같이 가장자리가 "상향"으로 가는 광선과 교차하면 권선 번호가 증가하고, "하향"으로 교차하면 번호가 감소합니다.일요일 알고리즘은 단순하지 않은 다각형에 대한 정답을 제공하지만,[6] 이 경우 경계 교차 알고리즘은 실패합니다.

실장

SVG

다양한 도형(경로, 폴리선, 폴리곤, 텍스트 등)으로 채우는 방법을 정의하기 위해 SVG에서도 유사한 방법이 사용됩니다.[8]채우기 알고리즘은 'fill-rule' 속성의 영향을 받습니다.값은 다음 중 하나입니다.nonzero또는evenodd 예를 들어, 볼록하지 않은 오각형 표면에는 중앙의 "구멍"(보이는 배경)이 있습니다.evenodd, 및 none with는 없습니다.nonzero속성을 [9]지정합니다.

단순한 폴리곤의 경우 알고리즘은 동일한 결과를 제공합니다.그러나 복잡한 폴리곤의 경우 폴리곤이 자체와 교차하는 영역의 점, 즉 폴리곤의 내부와 외부에 명확하게 정의되지 않은 점에 대해 알고리즘이 다른 결과를 제공할 수 있습니다.짝수 규칙을 사용하는 한 가지 해결책은 교차로 [10]검사 전에 (복잡한) 폴리곤을 짝수 등가인 단순한 폴리곤으로 변환하는 것입니다.그러나 이것은 계산상 비용이 많이 든다.폴리곤이 겹치더라도 정확한 결과를 얻을 수 있는 0이 아닌 빠른 와인딩 수 알고리즘을 사용하는 것이 저렴합니다.

폴리곤 쿼리 포인팅

폴리곤 문제의 점은 일반적인 반복 기하학적 쿼리 설정에서 고려할 수 있습니다. 즉, 단일 폴리곤과 일련의 쿼리 포인트를 지정하면 각 쿼리 포인트에 대한 답을 빠르게 찾을 수 있습니다.평면 점 위치에 대한 일반적인 접근법 중 하나를 사용할 수 있습니다.일부 특수 폴리곤에 대해 더 간단한 솔루션을 사용할 수 있습니다.

특수한 경우

단조 폴리곤, 별 모양의 폴리곤, 볼록 폴리곤 및 삼각형의 경우 보다 간단한 알고리즘이 가능합니다.

삼각형의 경우는 중심 좌표계, 파라메트릭 방정식 또는 [11]점곱을 사용하여 쉽게 풀 수 있습니다.도트 곱법은 모든 볼록 폴리곤으로 자연스럽게 확장됩니다.

레퍼런스

  1. ^ Ivan Sutherland et al., "10개의 숨겨진 표면 알고리즘의 특성화" 1974, ACM Computing Surveies vol.6 No.1.
  2. ^ "Point in Polygon, One More Time..." Wayback Machine, Ray Tracing News, vol.3 no.4, 1990년 10월 1일자에 보관.
  3. ^ Shimrat, M., "알고리즘 112: 폴리곤에 대한 점의 위치" 1962, ACM 제5권 제8호, 1962년 8월 8일
  4. ^ Hormann, K.; Agathos, A. (2001). "The point in polygon problem for arbitrary polygons". Computational Geometry. 20 (3): 131. doi:10.1016/S0925-7721(01)00012-8.
  5. ^ Weiler, Kevin (1994), "An Incremental Angle Point in Polygon Test", in Heckbert, Paul S. (ed.), Graphics Gems IV, San Diego, CA, USA: Academic Press Professional, Inc., pp. 16–23, ISBN 0-12-336155-9
  6. ^ a b Sunday, Dan (2001). "Inclusion of a Point in a Polygon". Archived from the original on 26 January 2013.
  7. ^ Pineda, Juan (August 1988). A Parallel Algorithm for Polygon Rasterization (PDF). SIGGRAPH'88. Computer Graphics. Vol. 22, no. 4. Atlanta. Retrieved 8 August 2021.
  8. ^ "Painting: Filling, Stroking, Colors and Paint Servers – SVG Tiny 1.2". www.w3.org. Retrieved 2021-07-24.
  9. ^ "Painting: Filling, Stroking, Colors and Paint Servers – SVG Tiny 1.2". www.w3.org. Retrieved 2021-07-24.
  10. ^ Michael Galetzka, Patrick Glauner (2017). A Simple and Correct Even-Odd Algorithm for the Point-in-Polygon Problem for Complex Polygons. Proceedings of the 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017), Volume 1: GRAPP.
  11. ^ 삼각 테스트의 정확한 포인트...가장 유명한 해결 방법"

「 」를 참조해 주세요.

Wikibooks는 다음과 같은 토픽에 관한 책을 가지고 있습니다.카테고리:Point-in-Polygon 문제