Python의 계산 기하학: 이론에서 응용으로

사람들이 계산 기하학을 생각할 때 내 경험에 따르면 일반적으로 다음 두 가지 중 하나를 생각합니다.

1. 와, 복잡하게 들립니다.
2. 오 그래, 볼록 껍질.

이 포스트에서 나는 내 자신의 경험을 바탕으로 한 실용적인 조언으로 넘어가기 전에 주제에 대한 간략한 개요로 시작하여 계산 기하학에 대해 약간의 설명을 드리고자 합니다.

무슨 소란이야?

볼록 껍질 계산 기하학 알고리즘은 일반적으로 입문 알고리즘 과정에 포함되지만 계산 기하학은 일반 개발자/컴퓨터 과학자로부터 거의 충분한 관심을 받지 못하는 훨씬 더 풍부한 주제입니다(게임 등을 만들지 않는 한).

이론적으로 흥미로운…

이론적 관점에서 계산 기하학에 대한 질문은 종종 매우 흥미롭습니다. 설득력 있는 답변; 그리고 그들이 도달하는 경로는 다양합니다. 이러한 자질만으로도 제 생각에는 공부할 가치가 있는 분야입니다.

예를 들어, 미술관 문제를 생각해 보십시오. 우리는 미술관을 소유하고 있으며 우리 작품을 보호하기 위해 보안 카메라를 설치하려고 합니다. 그러나 우리는 예산이 부족하므로 가능한 한 적은 수의 카메라를 사용하고 싶습니다. 얼마나 많은 카메라가 필요합니까?

이것을 계산적 기하학적 표기법으로 번역하면 갤러리의 '평면도'는 단순한 다각형입니다. 그리고 약간의 윤활유를 사용하면 아무리 지저분하더라도 n 개의 정점에 있는 다각형에 대해 n/3개의 카메라가 항상 충분하다는 것을 증명할 수 있습니다. 증명 자체는 이중 그래프, 일부 그래프 이론, 삼각 측량 등을 사용합니다.

여기에서 우리는 영리한 증명 기법과 그 자체로 높이 평가될 만큼 호기심을 불러일으키는 결과를 봅니다. 그러나 이론적 관련성이 충분하지 않다면…

그리고 실전에서 중요한

앞서 언급했듯이 게임 개발은 계산 기하학의 적용에 크게 의존합니다(예를 들어 충돌 감지는 종종 개체 집합의 볼록 껍질 계산에 의존함). 지리 데이터를 저장하고 계산을 수행하는 데 사용되는 지리 정보 시스템(GIS)도 마찬가지입니다. 및 로봇도 있습니다(예: 가시성 및 계획 문제).

왜 그렇게 힘든가요?

매우 간단한 계산 기하학 문제를 살펴보겠습니다. 한 점과 다각형이 주어졌을 때 그 점이 다각형 내부에 있습니까? (이를 point-in-polygon 또는 PIP 문제라고 합니다.)

PIP는 계산 기하학이 (기만적으로) 힘들 수 있는 이유를 잘 보여줍니다. 인간의 눈에는 어려운 질문이 아닙니다. 다음 다이어그램을 보고 포인트가 폴리곤에 있음을 즉시 알 수 있습니다.

비교적 복잡한 다각형의 경우에도 1~2초 이상 답을 찾지 못합니다. 그러나 이 문제를 컴퓨터에 제공하면 다음이 표시될 수 있습니다.

 poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point)

인간의 두뇌에 직관적인 것은 컴퓨터 언어로 그렇게 쉽게 번역되지 않습니다.

더 추상적으로(그리고 이러한 것들을 코드로 표현할 필요성을 무시하면), 이 분야에서 볼 수 있는 문제는 계산 기하학 알고리즘에서 엄격하게 처리('엄격하게 만들기')하기가 매우 어렵습니다. 'A point is inside the polygon if it is inside the polygon'과 같은 동어반복 언어를 사용하지 않고 point-in-polygon 시나리오를 어떻게 설명할 수 있습니까? 이러한 속성의 대부분은 너무 기본적이고 너무 기본적이어서 구체적으로 정의하기 어렵습니다.

어렵지만 불가능한 것은 아닙니다. 예를 들어 다음 정의를 사용하여 point-in-polygon을 엄격하게 지정할 수 있습니다.

• 점 에서 시작하는 무한 광선이 홀수개의 다각형 가장자리와 교차하는 경우 점은 다각형 내부에 있습니다(짝수-홀수 규칙이라고 함).
• 0이 아닌 굴곡 횟수(다각형을 정의하는 곡선이 포인트 주위를 이동하는 횟수로 정의됨)가 있는 경우 포인트는 폴리곤 내부에 있습니다.

계산 기하학에 대한 경험이 없다면 이러한 정의는 아마도 기존 어휘의 일부가 아닐 것입니다. 그리고 그것은 아마도 계산 기하학이 어떻게 당신이 다르게 생각 하도록 밀어붙일 수 있는지를 상징적으로 보여줍니다.

CCW 소개

이제 우리는 계산 기하학 문제의 중요성과 어려움에 대해 이해했으므로 이제 손을 적셔야 할 때입니다.

주제의 중추에는 믿을 수 없을 정도로 강력한 원시 작업이 있습니다. 즉, 반시계 방향 또는 줄여서 'CCW'입니다. (지금 경고하겠습니다: CCW는 계속해서 나타날 것입니다.)

CCW는 세 점 A, B, C를 인수로 사용하여 다음과 같이 질문합니다. 이 세 점은 시계 반대 방향 회전(대 시계 방향 회전)을 구성합니까? 즉, A -> B -> C는 반시계 방향 각도입니까?

예를 들어, 녹색 점은 CCW이고 빨간색 점은 그렇지 않습니다.

CCW가 중요한 이유

CCW는 우리가 구축할 수 있는 기본 작업을 제공합니다. 그것은 우리에게 계산 기하학 문제를 엄격화하고 해결하기 시작할 장소를 제공합니다.

그 힘에 대한 이해를 돕기 위해 두 가지 예를 살펴보겠습니다.

볼록도 결정하기

첫 번째: 다각형이 주어졌을 때 볼록한 것인지 결정할 수 있습니까? 볼록성은 매우 중요한 속성입니다. 폴리곤이 볼록한 경우가 많다는 사실을 알고 있으면 성능을 몇 배나 향상시킬 수 있습니다. 구체적인 예로서 볼록 다각형에 대해서는 Log(n) 시간에 실행되지만 많은 오목 다각형에 대해서는 실패하는 상당히 간단한 PIP 알고리즘이 있습니다.

직관적으로 이 간격은 의미가 있습니다. 볼록한 모양은 '좋은' 반면 오목한 모양은 안팎으로 날카로운 모서리가 돌출되어 있을 수 있습니다. 동일한 규칙을 따르지 않을 뿐입니다.

볼록성을 결정하기 위한 단순하지만 분명하지 않은 계산 기하학 알고리즘은 연속 정점의 모든 삼중항이 CCW인지 확인하는 것입니다. 이것은 단지 몇 줄의 Python 기하학 코드를 사용합니다( points 시계 반대 방향 순서로 제공된다고 가정합니다. points 시계 방향 순서인 경우 모든 삼중항이 시계 방향이 되기를 원할 것입니다):

 class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True

몇 가지 예를 들어 종이에 이것을 시도하십시오. 이 결과를 사용하여 볼록성을 정의 할 수도 있습니다. (좀 더 직관적으로 만들기 위해 A -> B -> C의 CCW 곡선은 볼록성을 정의하는 널리 알려진 방법인 180도 미만의 각도에 해당합니다.)

선 교차점

두 번째 예로 CCW만 사용하여 해결할 수도 있는 선분 교차를 고려하십시오.

 def intersect(a1, b1, a2, b2): """Returns True if line segments a1b1 and a2b2 intersect.""" return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1)

왜 이런 일이 발생합니까? 선분 교차점은 다음과 같이 표현할 수도 있습니다. 끝점 A와 B가 있는 선분에서 다른 선분의 끝점 C와 D는 AB의 같은 쪽에 있습니까? 즉, A -> B -> C와 A -> B -> D의 턴이 같은 방향이면 세그먼트가 교차할 수 없습니다. 우리가 이러한 유형의 언어를 사용할 때 그러한 문제가 CCW의 빵과 버터라는 것이 분명해집니다.

엄격한 정의

이제 CCW의 중요성을 맛보았으므로 CCW가 어떻게 계산되는지 봅시다. 주어진 점 A, B, C:

 def ccw(A, B, C): """Tests whether the turn formed by A, B, and C is ccw""" return (Bx - Ax) * (Cy - Ay) > (By - Ay) * (Cx - Ax)

이 정의가 어디에서 왔는지 이해하려면 벡터 AB와 BC를 고려하십시오. 외적 AB x BC를 취하면 z축을 따라 벡터가 됩니다. 그러나 어느 방향으로(즉, +z 또는 -z)? 결과적으로 외적이 양수이면 회전은 시계 반대 방향입니다. 그렇지 않으면 시계 방향입니다.

이 정의는 선형 대수, 오른손 법칙 등에 대해 잘 이해하지 않는 한 직관적이지 않은 것처럼 보일 것입니다. 그러나 이것이 우리가 추상화를 사용하는 이유입니다. CCW를 생각할 때 계산보다는 직관적인 정의를 생각하십시오. 값이 즉시 지워집니다.

Python을 사용한 계산 기하학 및 프로그래밍에 대한 나의 다이빙

지난 한 달 동안 저는 Python에서 여러 계산 기하학 알고리즘을 구현하는 작업을 했습니다. 다음 몇 섹션에서 이를 바탕으로 그림을 그릴 것이므로 잠시 시간을 내어 GitHub에서 찾을 수 있는 계산 기하학 응용 프로그램에 대해 설명하겠습니다.

참고: 내 경험은 제한적입니다. 내가 몇 년이 아니라 몇 달 동안 이 일을 해왔기 때문에 소금 한 알과 함께 내 충고를 받아들이십시오. 즉, 나는 그 몇 달 동안 많은 것을 배웠으므로 이 팁이 유용하기를 바랍니다.

커크패트릭의 알고리즘

내 작업의 핵심은 포인트 위치에 대한 Kirkpatrick의 알고리즘 구현이었습니다. 문제 설명은 다음과 같을 것입니다. 평면 세분화(평면에서 겹치지 않는 다각형 묶음)와 점 P가 주어지면 어떤 다각형에 P가 포함됩니까? 단일 다각형 대신 스테로이드의 point-in-polygon을 생각하십시오. 평면 전체가 있습니다.

사용 사례로 웹 페이지를 고려하십시오. 사용자가 마우스를 클릭하면 웹 페이지는 사용자가 무엇 을 클릭했는지 최대한 빨리 파악해야 합니다. 버튼A였나? 링크B였나? 웹 페이지는 겹치지 않는 다각형으로 구성되어 있으므로 Kirkpatrick의 알고리즘이 도움이 될 것입니다.

알고리즘에 대해 자세히 설명하지는 않겠지만 여기에서 더 자세히 알아볼 수 있습니다.

최소 경계 삼각형

하위 작업으로 선형 시간에 최소 둘러싸기/경계 삼각형(즉, 볼록한 점 집합을 둘러싸는 가장 작은 삼각형 찾기)을 계산하기 위한 O'Rourke의 알고리즘도 구현했습니다.

참고: 최소 경계 삼각형을 계산하는 것은 계산 자체가 선형 시간이므로 Kirkpatrick 알고리즘의 점근적 성능을 돕거나 손상시키지 않지만 미학적 목적에는 유용합니다.

실용적인 조언, 적용 및 우려 사항

이전 섹션에서는 계산 기하학이 엄격하게 추론하기 어려운 이유에 중점을 두었습니다.

실제로 우리는 완전히 새로운 문제에 대처해야 합니다.

CCW를 기억하십니까? 좋은 segue로, 부동 소수점 오류의 위험으로부터 우리를 보호하는 또 다른 장점을 살펴보겠습니다.

부동 소수점 오류: CCW가 왕인 이유

계산 기하학 과정에서 내가 셀 수 있는 것보다 더 많은 논문을 발표한 존경받는 교수인 Bernard Chazelle는 알고리즘이나 솔루션을 설명할 때 각도를 언급할 수 없다는 규칙을 만들었습니다.

왜요? 각도가 엉망입니다. 각도는 "더티"입니다. 각도를 계산해야 하는 경우 일부 근사(예: Pi와 관련된 모든 것) 또는 일부 삼각 함수를 나누거나 사용해야 합니다.

코드 에서 각도를 계산해야 할 때 거의 항상 근사합니다. 평등을 테스트할 때 중요한 약간의 부동 소수점 정밀도로 벗어날 수 있습니다. 두 가지 다른 방법을 통해 평면의 어떤 점을 풀 수 있으며 물론 p1.x == p2.x and p1.y == p2.y 예상할 수 있습니다. 그러나 실제로 이 검사는 자주 실패합니다. 더 나아가(그리고 분명히), 이러한 포인트는 다른 해시를 갖게 됩니다.

설상가상으로 작은 차이가 계산을 통해 전파됨에 따라 오류의 정도가 증가합니다. (좀 더 과학적인 예를 위해 이 문서에서는 볼록 껍질 또는 들로네 삼각분할을 계산할 때 무엇이 ​​잘못될 수 있는지 살펴봅니다.)

그래서 우리는 이것에 대해 무엇을 할 수 있습니까?

거의 같음

파이썬 계산 기하학 문제의 일부는 사물이 거의 정확하지 않은 세상에서 정확성 을 요구한다는 것입니다. 이것은 각도를 다룰 때보다 더 자주 문제가 됩니다. 다음을 고려하세요:

 # Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print "Error!" # Error!

사실, 이 코드는 "Error!"를 출력할 것입니다. 시간의 대략 70%(경험적으로). 우리는 평등에 대한 정의를 조금 더 관대하게 함으로써 이 문제를 해결할 수 있습니다. 즉, 정확도를 희생함으로써.

내가 사용한 한 가지 접근 방식(예: 일부 OpenCV 모듈에서 본)은 작은 값 엡실론만 다른 경우 두 숫자를 동일한 것으로 정의하는 것입니다. Python에서는 다음이 있을 수 있습니다.

 def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) < EPSILON class Point(object): ... def __eq__(self, that): return (almostEqual(self.x, that.x) and almostEqual(self.y, that.y))

실제로 이것은 매우 유용합니다. 1e-5 미만으로 차이가 나는 두 점을 실제로 다른 점으로 간주하는 경우는 드물지만 계산하시겠습니까? 이 유형의 재정의를 구현하는 것이 좋습니다. 유사한 방법을 라인에 사용할 수 있습니다. 예를 들면 다음과 같습니다.

 class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept))

물론 더 고급 솔루션이 제안되었습니다. 예를 들어, '정확한 기하학적 계산' 학파(이 백서에서 설명)는 프로그램의 모든 결정 경로가 정확한 수치 값보다는 일부 계산의 부호 에만 의존하도록 하여 관련된 많은 우려를 없애는 것을 목표로 합니다. 부동 소수점 계산에. 우리의 거의 평등 접근 방식은 표면을 긁는 것일 뿐 실제로는 충분할 때가 많습니다.

CCW는 왕이다

더 높은 수준에서, 우리가 우리의 솔루션을 각도나 점 좌표와 같은 정확한 계산량으로 정의 하는 것조차 문제가 됩니다. 증상만 해결하는 것보다(즉, 거의 Equal 을 사용하여 부동 소수점 오류를 almostEqual ) 원인을 해결하지 않는 이유는 무엇입니까? 해결책: 각도의 관점에서 생각하는 대신 CCW 관점에서 생각 하십시오. 그러면 부동 소수점 계산과 관련된 문제를 추상화하는 데 도움이 됩니다.

다음은 구체적인 예입니다. 볼록한 다각형 P , 꼭짓점 v , 다각형 외부에 있는 점 u 가 있다고 가정해 보겠습니다. 일정한 시간에 선 uv 가 v 위 또는 아래에서 P 와 교차하는지 또는 전혀 교차하지 않는지 어떻게 알 수 있습니까?

무차별 대입 솔루션(일정한 것이 아니라 선형 시간인 것 외에)은 정확한 선 교차점을 계산해야 하므로 문제가 될 수 있습니다.

내가 본 한 가지 일정 시간 접근 방식은 다음과 같습니다.

• arctan2 를 사용하여 일부 각도 계산하기.
• 180/Pi를 곱하여 이러한 각도를 각도로 변환합니다.
• 이러한 다양한 각도 사이의 관계를 조사합니다.

운 좋게도 작성자는 부동 소수점 오류를 부드럽게 하기 위해 위의 almostEqual 기술을 사용했습니다.

제 생각에는 부동 소수점 오류 문제를 완전히 피하는 것이 좋습니다. 몇 분 정도 시간을 내어 문제를 종이로 보면 완전히 CCW를 기반으로 하는 솔루션을 얻을 수 있습니다. 직관: v 에 인접한 정점이 uv 의 같은 쪽에 있으면 선이 교차하지 않습니다. 그렇지 않으면 u 와 v 가 인접한 정점 사이의 선의 같은 쪽에 있는지 확인하고 결과에 따라 높이를 비교합니다.

다음은 v 위의 교차를 테스트하기 위한 Python 코드입니다(아래 교차는 비교 방향을 반대로 합니다).

 def intersectsAbove(verts, v, u): """ Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. """ n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return uy > verts[v].y else: return uy < verts[v].y

솔루션은 육안으로 즉시 명확하지 않지만 계산 기하학 알고리즘의 언어 로 되어 있습니다. '같은 면'은 신뢰할 수 있는 알고리즘의 고전적인 요소입니다.

완료는 완벽보다 낫다

계산 기하학 문헌에는 겉보기에 단순한 연산과 관련된 상당한 양의 마법이 종종 있습니다. 이것은 당신에게 선택권을 줍니다: 당신은 그다지 발전되지 않은 문제에 대한 믿을 수 없을 정도로 진보된 솔루션을 정의하는 일부 문서에 따라 어려운 방법으로 일을 할 수 있습니다. 또는 약간의 무차별적인 힘으로 쉬운 방법으로 일을 할 수 있습니다.

다시 한 번 예를 사용하겠습니다. 임의의 다각형에서 임의의 내부 점을 샘플링합니다. 다시 말해서, 저는 여러분에게 간단한 폴리곤을 제공하고 여러분은 그 내부에 임의의 점을 제공합니다(다각형 전체에 균일하게 분포됨).

종종 테스트를 위해 내부 포인트가 필요합니다. 이 경우 (이유 내에서) 생성하는 계산 기하학 알고리즘에 대한 특정 런타임 요구 사항이 없습니다. 구현하는 데 2분이 소요되는 빠르고 더러운 솔루션은 다각형이 포함된 상자 내에서 임의의 점을 선택하고 점 자체가 다각형 내에 있는지 확인하는 것입니다.

예를 들어, 두 번 놓치고 세 번째 지점에서만 유효한 샘플을 찾을 수 있습니다.

코드는 다음과 같습니다.

 class Polygon(object): ... def interiorPoint(self): """Returns a random point interior point""" min_x = min([px for p in self.points]) max_x = max([px for p in self.points]) min_y = min([py for p in self.points]) max_y = max([py for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True

이를 거부 샘플링 이라고 합니다. 기준을 충족할 때까지 임의의 점수를 얻습니다. 기준을 충족하는 지점을 찾기 위해 여러 샘플이 필요할 수 있지만 실제로는 테스트 제품군에서 그 차이는 무시할 수 있습니다. 그렇다면 왜 더 열심히 일합니까? 요약: 상황이 필요할 때 더러운 길을 가는 것을 두려워하지 마십시오.

그건 그렇고: 만약 당신이 무작위 샘플링을 위한 정확한 알고리즘을 원한다면, 여기에 제가 아래에 구현한 영리한 알고리즘이 있습니다. 그것의 요지:

1. 다각형을 삼각형으로 만듭니다(즉, 삼각형으로 나눕니다).
2. 면적에 비례하는 확률을 갖는 삼각형을 선택하십시오.
3. 선택한 삼각형 내에서 임의의 점을 가져옵니다(일정 시간 작업).

이 알고리즘을 사용하려면 다각형을 삼각 측량해야 하므로 알고리즘에 다른 런타임 경계가 즉시 적용되며 임의의 다각형을 삼각 측량하기 위한 라이브러리 가 있어야 합니다(Python 바인딩과 함께 poly2tri 사용).

 from p2t import CDT class Triangle(object): ... def area(self): return abs((Bx * Ay - Ax * By) + (Cx * By - Bx * Cy) + (Ax * Cy - Cx * Ay)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(tax, tay) B = Point(tbx, tby) C = Point(tcx, tcy) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint()

바라건대, 추가 노력은 코드에서 분명합니다. 기억하십시오. Facebook에서 "완벽한 것보다 낫다"고 말합니다. 계산 기하학 문제도 마찬가지입니다.

시각적 및 자동화된 테스트

계산 기하학에서 작업하는 많은 문제는 쉽게 시각화할 수 있는 품질이나 양으로 정의되므로 시각적 테스트는 그 자체로는 충분하지 않지만 특히 중요합니다. 이상적인 테스트 제품군에는 시각적 테스트와 무작위 자동화 테스트가 결합되어 있습니다.

다시, 우리는 예를 들어 진행합니다. Kirkpatrick 알고리즘의 구현을 테스트하는 것을 고려하십시오. 한 단계에서 알고리즘은 주어진 다각형을 삼각형으로 묶고 다각형과 외부 삼각형 사이의 영역을 삼각측량해야 합니다. 다음은 녹색 실선이 초기 다각형을 정의하고 파선이 삼각형 영역을 정의하는 시각적 예입니다.

이 삼각 측량이 올바르게 실행되었는지 확인하는 것은 코드를 통해 확인하는 것이 매우 어렵지만 사람의 눈에는 즉시 분명합니다. 참고: 시각적 테스트에 도움이 되도록 Matplotlib를 사용하는 것이 좋습니다. 여기에 좋은 가이드가 있습니다.

나중에 알고리즘이 점을 올바르게 찾는지 확인하려고 합니다. 무작위로 자동화된 접근 방식은 모든 폴리곤에 대해 많은 내부 포인트를 생성하고 원하는 폴리곤을 반환하는지 확인하는 것입니다. 코드에서:

 class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target))

그런 다음 서로 다른 폴리곤 세트에 대해 runLocator 메서드를 사용하여 잘 다양한 테스트 제품군을 제공할 수 있습니다.

오픈 소스 솔루션

계산 기하학에는 선택한 프로그래밍 언어에 관계없이 사용할 수 있는 멋진 오픈 소스 라이브러리 및 솔루션 제품군이 있습니다(C++ 라이브러리가 불균형적인 양을 자르는 것처럼 보이지만).

기존 오픈 소스 솔루션(Python의 과학 컴퓨팅에서와 같이)을 사용할 때의 이점은 잘 알려져 있고 광범위하게 논의되었으므로 여기에서 계속 설명하지 않겠습니다. 하지만 유용하다고 생각되는 몇 가지 Python 중심 리소스를 언급할 생각입니다.

• poly2tri: 폴리곤의 빠른 삼각 측량을 위한 훌륭한 라이브러리입니다. 또한 구멍 이 있는 폴리곤을 지원합니다(이것은 종종 중요합니다). C++로 작성된 poly2tri에도 Python 바인딩이 있으며 시작하고 실행하기가 매우 쉽습니다. 함수 호출에 대한 맛을 보려면 위의 triangulate 방법을 참조하십시오.
• scipy.spatial: 볼록 껍질, 들로네 삼각분할 등을 계산하기 위한 함수를 포함합니다. 빠르고(항상 그렇듯이), 안정적입니다. 참고: toNumpy 메서드와 함께 내 고유한 Point 데이터 유형을 사용하는 것이 유용하다는 것을 알았습니다. def np(self): return [self.x, self.y] . 그런 다음 scipy.spatial 메서드를 쉽게 호출할 수 있습니다. 예: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: 오픈 소스 컴퓨터 비전 라이브러리에는 멋진 독립형 계산 기하학 모듈이 있습니다. 특히, 필자는 직접 구현하기 전에 최소한의 둘러싸는 삼각형 기능을 잠시 사용했습니다.

결론

이 게시물이 Python 개발자로서 계산 기하학의 아름다움에 대한 맛을 보았기를 바랍니다. 이 주제는 매혹적인 문제와 마찬가지로 매혹적인 응용 프로그램이 풍부한 주제입니다.

실제로, 기하학적 계산 구현은 새롭고 흥미로운 문제 해결 기술을 연습하도록 하는 고유한 과제를 제시합니다.

더 자세히 알고 싶거나 질문이 있는 경우 [email protected]으로 연락할 수 있습니다.