팬 삼각측량

볼록 폴리곤의 팬 삼각측량

고유한 오목한 정점을 가진 오목한 다각형의 팬 삼각 측량.

팬 삼각형은 다각형의 정점을 선택하고 다각형의 다른 모든 정점에 대각선을 그려 삼각형을 이루는 간단한 방법이다.모든 다각형이 이런 식으로 삼각측량될 수 있는 것은 아니기 때문에 이 방법은 보통 볼록한 다각형에만 사용된다.^[1]

특성.

팬 삼각형은 모든 삼각형 속성과 별도로 다음과 같은 속성이 있다.

• 모든 볼록한 폴리곤(모든 폴리곤은 아님)은 팬 삼각측정이 가능하다.
• 오목한 꼭지점이 하나만 있는 다각형은 오목한 꼭지점에서 대각선을 그리는 한 항상 부채 삼각형으로 측량할 수 있다.
• 폴리곤의 모든 지점에서 보이는 정점이 적어도 하나 이상 있는지 판단하기 위해 아트 갤러리 문제를 해결함으로써 폴리곤을 팬 삼각형으로 측정할 수 있는지 여부를 알 수 있다.
• 정점이$$ $n{\displaystyle }$ ${\displaystyle n}$인 다각형의 삼각형은 n${\displaystyle }$- ${\displaystyle 3}$ ${\displaystyle n-3}$개의 대각선을$$ 사용하고 n -${\displaystyle 2}$ ${\displaystyle n-2}$개의 삼각형을$$ 생성한다.^[2]
• 정점의 순서 목록을 사용할 수 있는 경우 삼각형 목록을 생성하는 것은 사소한 일이며, 선형 시간으로 계산할 수 있다.이와 같이 삼각형 목록을 명시적으로 저장할 필요가 없으므로, 많은 그래픽 라이브러리는 이 삼각형을 바탕으로 다각형을 나타내기 위해 원시형을 구현한다.^[3]
• 이 삼각측량은 래스터라이제이션이나 충돌탐지 등 특정 문제를 해결하는 데 적합하지만, 원점 정점에는 이웃이 많이 쌓이고, 삼각측량의 내부 각도가 고르지 않게 분포되어 있기 때문에 다른 작업에 부적합할 수 있다.

참고 항목

• 삼각팬

참조