Delaunay 삼각 측량 알고리즘 최적화

Question

안녕하세요, 커뮤니티 회원 들께,

저는 최근에 cpp에서 Delaunay 삼각 측량을 구현하기 위해 노력해 왔습니다. 알고리즘이 작동하는 동안 .. 매우 느립니다 (약 100 초 객체는 약 16 초 내에 계산됩니다).

알고리즘은 무차별 대입 방식을 기반으로합니다. 점의 유한 집합을 감안할 때 :

• 내가
  그 점에서 삼각형을 만들 수 있는지를 점검, 각 지점을 통해 세 번 반복하고 있습니다;
• 이 세 가지 점에서 나는 그 점들을 통과하는 원을 만듭니다.
• 생성 된 원이 있는지 확인하고 네 번째 점 전체 집합을 반복합니다. 위의 세 점과 다른 점이 포함되어 있습니다.
• 원 안에 추가 점이 없으면이 세 점에서 생성 된 삼각형이 유효하다고 가정합니다.

앞서 언급 한 것처럼 알고리즘은 여기에 설명 된 Delaunay 삼각 측량의 직접 구현입니다. https://en.wikipedia.org/wiki/Delaunay_triangulation. 그것은 "완벽하게"작동하지만 느리다.

(가능한 경우 논리를 완전히 변경하지 않고) 속도를 높일 수있는 논리에 대한 아이디어 나 제안 사항이 있습니까?

Answer 1

빠른 피드백을 보내 주셔서 감사합니다.

나는 약간의 추가 연구를했으며 슬프게도 시간 복잡성을 줄이는 가장 좋은 방법은 기존 알고리즘을 완전히 재 작성하는 것입니다. 비슷한 문제가있을 수있는 다른 사람을 위해

는 샘플 접근 방법이 여기에 설명되어 있습니다 https://people.eecs.berkeley.edu/~jrs/274/proj.html