구속 삼각형 삼각형을 사용하여 다각형 삼각형을 그리기

Question

필자는 구속 삼각법 (CDT) 알고리즘을 사용하고 있으며 입력으로 다각형 (오목 또는 볼록일 수 있음)이 있습니다. 어떻게 그 제약 delaunay 삼각 측량 알고리즘을 사용하여 새로운 점을 도입하지 않고 다각형을 삼각형으로 분해 할 수 있습니까?

편집 : 모든 삼각형의 합집합은 다각형과 동일해야합니다. 그래서 삼각형을 생성하기 위해 경계를 경계로 삼아 CDT를 취할 수는 없습니다. 입력이 오목하거나 볼록한 것인지 여부에 관계없이 볼록한 다각형을 생성 할 수 있기 때문입니다.

Answer 1

포인트 클라우드가 아닌 다각형을 가지고 있기 때문에 가장 쉬운 방법은 순진한 삼각형을 그리는 것입니다. 그런 다음 각 모서리를 방문하여 간단한 선 - 다각형 교차 테스트를 사용하여 원래의 다각형 밖에 있는지 테스트하십시오.

알고리즘에 따라이 테스트를 삼각형 세분화의 일부로 수행하고 끝에 통과를 건너 뛸 수 있습니다. 약간 더 나은 방법이있을 것이라고 확신하지만 이것이 마음에 가장 먼저 떠오르는 첫 번째 방법입니다.

편집 :

내 삼각 분 할부에서이 구현 내가 구현 제약이 없기 때문에 잘못 결과를 주었다. 모든 다각형 모서리가 사용된다면 나는 그것이 작동한다고 믿습니다.