폴리곤 삼각 측량

Polygon triangulation
이 주제에 대한 자세한 내용은 삼각측량(기하학)을 참조하십시오.
폴리곤 삼각 측량

계산기하학에서, 폴리곤 삼각 측량(polygon triangulation)[1]은 다각형 영역(단순 폴리곤) P를 삼각형 세트로 분할하는 것이다. 즉, 결합이 P인 쌍방향 비교차 내부 삼각형의 집합을 찾는 것이다.

삼각측량은 평면 직선 그래프의 특수한 경우로 볼 수 있다.구멍이나 추가된 점이 없으면 삼각 측량이 최대 외부 평면 그래프를 형성합니다.

추가 정점이 없는 다각형 삼각 측량

시간이 지남에 따라 폴리곤을 삼각측량하기 위한 여러 알고리즘이 제안되었습니다.

특수한 경우

볼록한 헵타곤(7면 볼록한 다각형)에 대해 42개의 가능한 삼각 측량입니다.이 번호는 카탈로니아 5번째 번호로 지정됩니다.

한 정점에서 다른 모든 정점에 대각선을 추가하여 선형 시간에 볼록 폴리곤을 팬 삼각측량으로 삼각측량하는 것은 간단합니다.

교차하지 않는 대각선으로 볼록한 n-곤을 삼각 측량하는 총 방법 수는 다음과 같은 (n-2)번째 카탈로니아 수이다.

레온하르트 [2]오일러가 발견한 공식

단조 폴리곤은 A의 알고리즘 중 하나로 선형 시간 내에 삼각 측량할 수 있다. Fournier와 D.Y. 몬투노 [3]또는 [4]고드프리드 투생 알고리즘.

귀 클리핑 방법

다각형 귀

간단한 다각형을 삼각 측량하는 한 가지 방법은 두 개의 귀 정리에 기초한다. 구멍이 없는 적어도 4개의 정점을 가진 모든 단순 다각형은 적어도 두 개의 '귀'를 가지고 있다는 사실, 즉 두 개의 변이 다각형 가장자리이고 [5]세 번째 변이 완전히 내부에 있는 삼각형이기 때문이다.알고리즘은 그런 귀를 찾아 폴리곤에서 제거하고(여전히 조건을 충족하는 새 폴리곤을 생성함) 삼각형이 하나만 남을 때까지 반복하는 것으로 구성됩니다.

이 알고리즘은 구현이 쉽지만 다른 알고리즘보다 느리고 구멍이 없는 폴리곤에서만 작동합니다.볼록한 정점과 오목한 정점의 개별 목록을 유지하는 구현은 O()n2 시간에 실행됩니다.이 방법은 귀 클리핑과 때로는 귀 트리밍으로 알려져 있다.Hossam ElGindy, Hazel Everett, Godfried Toussaint에 [6]의해 귀를 잘라내는 효율적인 알고리즘이 발견되었다.

모노톤 폴리곤 삼각 측량

폴리곤을 모노톤 폴리곤으로 분할

L에 직교하는 선이 최대 두 번 폴리곤과 교차하는 경우, 단순 폴리곤은 선 L에 대해 단조롭다.모노톤 폴리곤은 두 개의 모노톤 체인으로 분할할 수 있습니다.y축에 대해 단조로운 폴리곤을 y-모노톤이라고 합니다.N개의 정점이 있는 단조 폴리곤은 O()n 시간으로 삼각 측량할 수 있습니다.주어진 폴리곤이 y-모노톤이라고 가정하면,[1] 탐욕 알고리즘은 폴리곤의 한 체인을 위에서 아래로 걸으면서 가능한 한 대각선을 추가하는 것으로 시작됩니다.알고리즘이 모든 단조 폴리곤에 적용될 수 있음을 쉽게 알 수 있습니다.

비 모노톤 폴리곤 삼각 측량

폴리곤이 모노톤이 아닌 경우 스위프라인 어프로치를 사용하여 O(nlog) 시간 내에 모노톤 서브폴리곤으로 분할할 수 있습니다.이 알고리즘은 폴리곤이 단순할 필요가 없으므로 구멍이 있는 폴리곤에 적용할 수 있습니다.일반적으로 이 알고리즘은 O()n[1] 공간을 사용하여 O(nlog) 시간 내에 정점과 평면 분할을 삼각 측량할 수 있습니다.

삼각 측량 이중 그래프

폴리곤의 삼각 측량과 자주 관련된 유용한 그래프는 이중 그래프입니다.의 삼각형을 지정하면 그래프()TP는 두 개의 꼭지점(삼각형)이 대각선을 공유하는 경우에만 인접한 의 삼각형이 되는 그래프입니다.()TP은 최대 도수가 3인 트리임을 쉽게 알 수 있습니다.

계산의 복잡성

1988년까지 간단한 폴리곤이 O(nlog) 시간보다 더 빨리 삼각측량될 수 있는지 여부는 컴퓨터 [1]기하학에서 미해결 문제였습니다.그 후, Tarjan & Van Wyk(1988)는 [7]삼각측량을 위한 nO(log log)-time 알고리즘을 발견하였고, 나중에 Kirkpatrick, Klawe & Tarjan(1992)[8]에 의해 단순화되었다.복잡도 O(nlog*)를 가진 몇 가지 개선된 방법([9][10][11]실제로 선형 시간과 구별할 수 없음)이 뒤따랐다.

버나드 샤젤은 1991년에 제안된 알고리즘은 매우 [12]복잡하지만, 어떤 단순한 다각형도 선형 시간에 삼각 측량할 수 있다는 것을 보여주었다.선형 예상 시간을 갖는 더 간단한 랜덤화 알고리즘도 [13]알려져 있습니다.

자이델의 분해 알고리즘과 샤젤의 삼각 측량 방법은 Li & Klette(2011)[14]에 자세히 설명되어 있다.

구멍이 있는 -vertex 폴리곤의 삼각측정의 시간 복잡도는 [1]계산의 대수 계산 트리 모델에서 하한 δ(nlog)를 가진다.동적 프로그래밍을 사용하여 다항식 시간에 단순 폴리곤의 고유한 삼각측량 수를 계산할 수 있으며, (이 계수 알고리즘에 기초하여) 다항식 [15]시간에 균일하게 랜덤 삼각측량을 생성할 수 있습니다.그러나 구멍이 있는 다각형의 삼각 측량을 세는 것은 #P-완료이므로 다항식 시간 내에 [16]수행될 수 없습니다.

관련 오브젝트 및 문제

  • 삼각 측량 문제 모두 삼각 측량(기하학)의 특수한 경우이고 폴리곤 분할의 특수한 경우입니다.
  • 최소 가중치 삼각 측량이란 총 모서리 길이를 최소화하는 것이 목표인 삼각 측량입니다.
  • 점 세트 삼각 측량이란 점 세트의 볼록 선체에 대한 다각형 삼각 측량입니다.Delaunay 삼각 측량은 점 집합을 기반으로 삼각 측량을 만드는 또 다른 방법입니다.
  • 정점은 볼록 다각형의 삼각측량에 해당하는 다면체이다.
  • 폴리곤 삼각형 피복. 이 경우 삼각형이 겹칠 수 있습니다.
  • 폴리곤별 타일링. 목표는 전체 평면을 미리 지정된 모양의 폴리곤으로 덮는 것입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), "3: Polygon Triangulation", Computational Geometry (2nd ed.), Springer-Verlag, pp. 45–61, ISBN 3-540-65620-0{{citation}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  2. ^ Pickover, Clifford A. (2009), The Math Book, Sterling, p. 184
  3. ^ Fournier, Alain; Montuno, Delfin Y. (1984), "Triangulating simple polygons and equivalent problems", ACM Transactions on Graphics, 3 (2): 153–174, doi:10.1145/357337.357341, ISSN 0730-0301, S2CID 33344266
  4. ^ Toussaint, Godfried T. (1984), "A new linear algorithm for triangulating monotone polygons", Pattern Recognition Letters, 2 (3): 155–158, doi:10.1016/0167-8655(84)90039-4
  5. ^ Meisters, Gary Hosler (1975), "Polygons have ears", American Mathematical Monthly, 82 (6): 648–651, doi:10.2307/2319703, JSTOR 2319703
  6. ^ ElGindy, Hossam; Everett, Hazel; Toussaint, Godfried T. (1993), "Slicing an ear using prune-and-search", Pattern Recognition Letters, 14 (9): 719–722, doi:10.1016/0167-8655(93)90141-y
  7. ^ Tarjan, Robert E.; Van Wyk, Christopher J. (1988), "An O(n log log n)-time algorithm for triangulating a simple polygon", SIAM Journal on Computing, 17 (1): 143–178, CiteSeerX 10.1.1.186.5949, doi:10.1137/0217010, MR 0925194
  8. ^ Kirkpatrick, David G.; Klawe, Maria M.; Tarjan, Robert E. (1992), "Polygon triangulation in O(n log log n) time with simple data structures", Discrete & Computational Geometry, 7 (4): 329–346, doi:10.1007/BF02187846, MR 1148949
  9. ^ Clarkson, Kenneth L.; Tarjan, Robert; van Wyk, Christopher J. (1989), "A fast Las Vegas algorithm for triangulating a simple polygon", Discrete & Computational Geometry, 4 (5): 423–432, doi:10.1007/BF02187741
  10. ^ Seidel, Raimund (1991), "A Simple and Fast Incremental Randomized Algorithm for Computing Trapezoidal Decompositions and for Triangulating Polygons", Computational Geometry, 1: 51–64, doi:10.1016/0925-7721(91)90012-4
  11. ^ Clarkson, Kenneth L.; Cole, Richard; Tarjan, Robert E. (1992), "Randomized parallel algorithms for trapezoidal diagrams", International Journal of Computational Geometry & Applications, 2 (2): 117–133, doi:10.1142/S0218195992000081, MR 1168952
  12. ^ Chazelle, Bernard (1991), "Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 6 (3): 485–524, doi:10.1007/BF02574703, ISSN 0179-5376
  13. ^ Amato, Nancy M.; Goodrich, Michael T.; Ramos, Edgar A. (2001), "A Randomized Algorithm for Triangulating a Simple Polygon in Linear Time", Discrete & Computational Geometry, 26 (2): 245–265, doi:10.1007/s00454-001-0027-x, ISSN 0179-5376
  14. ^ Li, Fajie; Klette, Reinhard (2011), Euclidean Shortest Paths, Springer, doi:10.1007/978-1-4471-2256-2, ISBN 978-1-4471-2255-5
  15. ^ Epstein, Peter; Sack, Jörg-Rüdiger (1994), "Generating triangulations at random", ACM Transactions on Modeling and Computer Simulation, 4 (3): 267–278, doi:10.1145/189443.189446, S2CID 14039662
  16. ^ Eppstein, David (2019), "Counting polygon triangulations is hard", Proc. 35nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl, pp. 33:1–33:17, arXiv:1903.04737, doi:10.4230/LIPIcs.SoCG.2019.33, S2CID 75136891

외부 링크