Simple polygon
기하학(geometry)에서, 단순 다각형(simple polygon /ˈpɒlɪɡɒn/)은 자신과 교차(intersect)하지 않고 구멍을 가지지 않는 다각형(polygon)입니다. 즉, 그것은 단일 닫힌(closed) 경로를 형성하기 위해 쌍별 결합되는 똑바른, 비-교차하는 선분(line segment) 또는 "변"으로 구성된 평평한 모양입니다. 만약 변이 교차하면 다각형은 단순이 아닙니다. 수식어 "단순"은 자주 생략되며 위의 정의는 일반적으로 다각형을 정의하기 위해 이해됩니다.
위에 제공된 정의는 다음 속성을 보장합니다:
- 다각형은 항상 측정-가능 넓이(area)를 가지는 영역(region) (내부라고 불림)을 둘러쌉니다.
- 다각형을 구성하는 선분 (변 또는 가장자리라고 불림)은 꼭짓점 또는 덜 형식적으로는 "모서리"라고 불리는 오직 끝점에서 만납니다.
- 정확하게 둘의 가장자리가 각 꼭짓점에서 만납니다.
- 가장자리의 수는 항상 꼭짓점의 수와 같습니다.
모서리에서 만나는 둘의 가장자리는 보통 똑바른 것 (180°)이 아닌 각도(angle)를 형성하기 위해 요구됩니다; 그렇지 않으면 공선형(collinear) 선분은 한 변의 일부로 고려될 것입니다.
수학자들은 전형적으로 "다각형"을 닫힌 영역이 아닌 오직 선분에 의해 만들어진 모양을 참조하기 위해 사용하며, 어쨌든 일부는 "다각형"을 유한 선분의 수열로 구성된 (즉, 닫힌 다각형 체인(closed polygonal chain)에 의해) 닫힌 경로에 의해 경계진 평면(plane) 그림(figure)을 참조하기 위해 사용될 수 있습니다. 사용 중인 정의에 따르면, 이 경계는 다각형 자체의 일부를 형성하거나 형성하지 않을 수 있습니다.[1]
단순 다각형은 역시 조르당 다각형(Jordan polygons)이라고 불리는데, 왜냐하면 조르당 곡선 정리(Jordan curve theorem)는 그러한 다각형이 평면을 두 영역, 그것을 내부 영역과 외부 영역으로 나누는 것을 입증하기 위해 사용될 수 있기 때문입니다. 평면에서 다각형이 단순인 것과 그것이 토폴로지적으로 원(circle)과 동등한 것은 필요충분 조건입니다. 그것의 내부는 토폴로지적으로 디스크(disk)와 동등합니다.
Weakly simple polygon
만약 비-교차하는 선분의 모음이 토폴로지적으로 디스크와 동등한 평면의 영역의 경계를 형성하면, 이 경계는 약하게 단순 다각형(weakly simple polygon)이라고 불립니다.[2] 왼쪽 이미지에서, ABCDEFGHJKLM은 이 정의에 따라 약하게 단순 다각형이며, 파란색이 그것의 경계 영역을 표시합니다. 이러한 유형의 약하게 단순 다각형은 컴퓨터 그래픽과 CAD에서 구멍을 갖는 다각형적 영역의 컴퓨터 표현으로 나타날 수 있습니다: 각 구멍에 대해 "절단"이 외부 경계에 그것을 연결하기 위해 생성됩니다. 위의 이미지를 참조하면, ABCM은 구멍 FGHJ를 갖는 평면 영역의 외부 경계입니다. 절단 ED는 구멍을 외부와 연결하고 약하게 단순 다각형 표현을 초래하는 것에서 두 번 횡단됩니다.
약하게 단순 다각형의 대안적이고 보다 일반적인 정의에서, 그것들은 프레셰 거리(Fréchet distance) 아래에서 수렴을 갖는 같은 조합론적 유형의 단순 다각형의 수열의 극한입니다.[3] 이것은 그러한 다각형이 선분에 닿는 것을 허용하지만 교차하는 것을 허용하지 않는 개념을 공식화합니다. 어쨌든, 이러한 유형의 약하게 단순 다각형은 영역의 경계를 형성할 필요가 없는데, 왜냐하면 "내부"가 빈 것일 수 있습니다. 예를 들어, 위의 이미지를 참조하면, 다각형 체인 ABCBA는 이 정의에 따라 약하게 단순 다각형입니다; 그것은 다각형 ABCFGHA의 "조임"의 극한으로 보일 수 있습니다.
Computational problems
계산 기하학(computational geometry)에서, 몇 가지 중요한 계산적 임무는 단순 다각형의 형식에서 입력을 포함합니다; 이들 각각의 문제에서, 내부와 외부의 구별은 문제 정의에서 매우 중요합니다.[4]
- 다각형에서 점(point in polygon) 테스팅은 단순 다각형 P와 질의 점 q에 대해, q가 P의 내부에 있는지 여부를 결정하는 것을 포함합니다.[5]
- 단순 공식은 다각형 넓이(polygon area); 즉, 다각형 내부의 넓이를 계산하는 것에 대해 알려져 있습니다.[6]
- 다각형 분할(Polygon partition)은 겹치지 않고 그것들의 합집합은 다각형과 같은 원시 단위 (예를 들어, 정사각형)의 집합입니다. 다각형 분할 문제는 어떤 의미에서 최소인 파티션: 예를 들어, 가장 작은 단위의 숫자 또는 가장 작은 총 변 길이의 단위를 가진 분할을 찾는 문제입니다.[7]
- 다각형 분할의 특별한 경우는 다각형 삼각분할(Polygon triangulation)입니다: 간단한 다각형을 삼각형으로 나누는 것입니다. 비록 볼록 다각형이 삼각분할하기 쉬울지라도, 일반적인 단순 다각형을 삼각분할하는 것은 보다 어려운데 왜냐하면 우리는 다각형 외부와 교차하는 가장자리를 더하는 것을 피해야 하기 때문입니다. 그럼에도 불구하고, 베르나르 샤젤르(Bernard Chazelle)는 1991년에 n 꼭짓점을 갖는 단순 다각형이 최적인 Θ(n) 시간에 삼각분할될 수 있음을 보였습니다. 같은 알고리듬은 역시 닫힌 다각형 체인이 단순 다각형을 형성하는지 여부를 결정하는 데 사용될 수 있습니다.
- 또 다른 특별한 경우는 최소한의 별-모양된 다각형(star-shaped polygon)으로 분할로 동등하게 다시 공식화될 수 있는 아트 갤러리 문제(art gallery problem)입니다.[7]
- 다각형에 대한 부울 연산(Boolean operations on polygons): 다각형 영역에 의해 정의된 점의 집합에 대한 다양한 부울 연산.
- 단순 다각형의 볼록 껍질(convex hull)은 접 집합의 볼록 껍질과 같은 다른 유형의 입력의 볼록 껍질보다 더 효율적으로 계산될 수 있습니다.
- 단순 다각형의 보로노이 다이어그램(Voronoi diagram)
- 단순 다각형의 중점 축/토폴로지적 뼈대/직진 뼈대
- 단순 다각형의 오프셋 곡선
- 단순 다각형에 대해 민코프스키 합
References
- ^ Grünbaum, B.; Convex Polytopes 2nd Ed, Springer, 2003
- ^ Dumitrescu, Adrian; Tóth, Csaba D. (2007). "Light orthogonal networks with constant geometric dilation". In Thomas, Wolfgang; Weil, Pascal (eds.). STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings (illustrated ed.). Springer. p. 177. ISBN 978-3540709176.
- ^ Hsien-Chih Chang; Jeff Erickson; Chao Xu (2015). Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15). Soda '15. pp. 1655–1670.
- ^ The comp.graphics.algorithms FAQ, which lists solutions to mathematical problems with 2D and 3D polygons.
- ^ Haines, Eric (1994). "Point in polygon strategies". In Heckbert, Paul S. (ed.). Graphics Gems IV. San Diego, CA, USA: Academic Press Professional, Inc. pp. 24–46. ISBN 0-12-336155-9.
- ^ Bart Braden (1986). "The surveyor's area formula" (PDF). The College Mathematics Journal. 17 (4): 326–337. doi:10.2307/2686282. JSTOR 2686282. Archived from the original (PDF) on 2012-11-07.
- ^ a b Lee, D. T. (1998). "Chapter 19: Computational Geometry I". In Atallah, Mikhail J. (ed.). Algorithms and Theory of Computation Handbook. Chapman & Hall/CRC Applied Algorithms and Data Structures series. CRC Press. ISBN 9781420049503. See "Other decompositions", p. 19-25.
External links