Delaunay의 직사각형 구속 조건 내 가장자리없는 삼각 분할

Question

삼각형 라이브러리를 사용하여 큰 경계 내에서 직사각형 집합의 구속 된 Delaunay 삼각 측량을 계산합니다. 알고리즘은 모든 가장자리를 반환하지만 구속 조건을 정의하는 사각형 내부에 가장자리를 추가합니다.

제약 조건 인 사각형 내에서 가장자리가없는 그래프를 만들 수 있지만 (물론 큰 경계는 예외), 삼각형 분할에서 이러한 가장자리를 제거하는 것이 더 오래 걸립니다. O (nlog (n)) 시간보다 길어서 내가 필요한 것에는 좋지 않습니다.

내가 묻는 것은 가장자리가 일부 다각형 안에 나타나지 않도록 CDT를 얻는 빠른 방법이 있습니까? 직사각형에 가장자리가 없기를 원하지만 신속하게 처리하는 방법을 모르겠습니다.

이 경우에 도움이되는 라이브러리는 Marcello Kallmann의 TriPath이며 C++ (http://graphics.ucmerced.edu/software/tripath/)로 작성되었습니다. 내 응용 프로그램은 Java이고 JNI를 사용하고 있습니다.

편집 : 요청에 따라 설명 할 내용을 시각화하는 데 도움이되는 몇 가지 이미지가 있습니다. 이 CDT는 검은 선이 제약 조건으로 만들어졌습니다. 보시다시피 각 구속 된 모서리는 사각형의 일부입니다. 파란색 선은 제한되지 않은 Delaunay 가장자리입니다. 검정 제한 사각형 내에서 파란색 제약되지 않은 Delaunay 가장자리를 제거하려고합니다.

Answer 1

경우 제약 사각형 내가 모든 원래의 사각형 안에 약간 작은 사각형을 넣어 제안, 겹치거나 서로를 포함 할 수 없습니다. 안쪽 사각형과 원래 사각형 사이의 틈은 충분히 작아서 구속되지 않은 가장자리가 작은 직사각형과 교차하지 않고 원래 사각형 안에 들어갈 수 있습니다. 그런 다음, 삼각형 분할이 완료된 후, 작은 사각형의 정점에 인접한 모든 모서리를 삭제하십시오. 그렇게하면 가장자리가 O (1) 시간에 삭제되어야하는지 여부를 알 수 있으므로 전체 절차에 O (E)가 적용됩니다.

작은 간격을 선택하는 한 가지 방법은 작은 사각형없이 삼각형을 평가하고, 최소 길이의 가장자리를 찾고, 그 길이의 1/3을 간격으로 사용하는 것입니다.