3D 모델에서 사용하기 위해 다각형을 삼각형으로 삼으려고하는 임. 아래 점이있는 점이있는 다각형에서 귀 메소드를 사용하려고하면 빨간색 선이있는 삼각형이 표시됩니다. 이 삼각형 안에는 다른 점이 없기 때문에 아마도 맞을 것입니다. 하지만 나는 검은 선 안의 영역을 삼각형 화하기를 원한다. 누구든지이 작업을 수행 할 수있는 알고리즘을 알고 있습니까? 당신은 모노톤 다각형에 다각형을 나눌다각형의 삼각 측량
먼저 모노톤 폴리곤으로 분할 할 필요가없는 다각형을 삼각형 화하는 알고리즘이 많이 있습니다. 하나는 필자의 교과서 Computational Geometry in C에 설명되어 있으며이 코드는 링크 (C 또는 Java)에서 자유롭게 다운로드 할 수 있습니다. 먼저 경계 순회에 해당하는 순서로 점을 가져야합니다. 내 코드는 반 시계 방향으로 가정하지만 물론 변경하기 쉽습니다. Wikipedia article을 참조하십시오. 아마도 당신의 문제입니다. 경계 지점을 일관되게 조직하지 않았습니까?
당신의 책인 Joseph을 좋아하십시오. 저의 두 판을 제 뒤에 놓아 두십시오. Edelsbrunner, Shamos & Perparata, Hjelle & Daehlen 사이에 자리 잡고 있습니다. TIN으로 작업하는 사람은 반드시 실제 있어야합니다. –
@Shane : 친절한 말에 감사드립니다! :-) –
답변에 해당 코드를 포함시킬 수 있습니까? – Jonny
Wikipedia suggest. 모든 각도가 180도 미만인지 확인하여 다각형이 오목한 모양이 아닌지 확인합니다. 180 이상의 각도를 가진 모든 모서리가 오목하고, 그 모서리에서 파손될 필요가 있습니다.
일반적인 방법은 사다리꼴 분해를 사용하여 단순 다각형을 단조 다각형으로 분할 한 다음 단조 다각형을 삼각형 화하는 것입니다. 첫 번째 부분은 스윕 라인 알고리즘을 사용하여 수행 할 수 있습니다. 올바른 데이터 구조 (예 : 이중 연결된 에지 목록)로 속도를 높일 수 있습니다. 제가 알고있는 가장 좋은 설명은 Computational Geometry입니다. This 및 this도 도움이되는 것 같습니다.
Delaunay가 아니라 EarClipping 알고리즘을 사용해야합니다. 다음 백서를 참조하십시오. http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
그림을 볼록 부분으로 자르고 삼각형화할 수 있습니다. 복잡한 복잡한 인물의 경우 지저분해진다. –
삼각 측량에 제약이 있습니까 (Delaunay?) 아니면 시간 제약이 있습니까? 그렇지 않으면 대답은 다소 광범위합니다. – pmr
제약이 없으므로 모델이 한 번 생성되므로 시간이 큰 문제는 아닙니다. – user978281