유클리드 최소 스패닝 트리 및 들로네 삼각

Question

나는 2 차원 평면에 점 세트 사이의 유클리드 거리에 따라 최소 스패닝 트리를 계산할

. 내 현재 코드는 모든 가장자리를 저장 한 다음 Prim의 알고리즘을 수행하여 최소 스패닝 트리를 얻습니다. 그러나, 나는 이것을 수행하는 것이 모든 가장자리에 대해 O(n^2) 공간을 차지한다는 것을 알고 있습니다.

몇 가지 조사를 한 후 처음으로 delaunay 삼각 측량을 계산하면 메모리와 런타임을 최적화 할 수 있으며 그 다음에 Prim 또는 Kruskal의 알고리즘을 실행하여 최소 스패닝 트리를 얻습니다. 삼각 측량.

이 프로그래밍 대회 (https://prologin.org/train/2017/qualification/taxi_des_neiges)의 일부입니다, 그래서 내가 scipy.spatial 사용할 수있을 거라고 의심한다. Delaunay 삼각 측량에 포함 된 가장자리를 단순히 얻는 다른 방법이 있습니까?

미리 감사드립니다.

Answer 1

모듈 도움이겠습니까? 여기에 몇 가지 작동을 생각하고있다 :

• delaunator
• poly2tri
• triangle
• matplotlib?

롤 자신의?

• http://www.geom.uiuc.edu/~samuelp/del_project.html
• http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_1.pdf

여기 시작하는 데 도움이 될 an ActiveState recipe하지만 그것은 본다 :이 두 가지 (N 로그 n) Wikipedia 말 것 O입니다 증분 알고리즘을 설명 끝나지 않은 것처럼.

Answer 2

Scipy이 QHull를 사용하는 것처럼 보이는 .. 곳이 폴더에 ...이 조언을

https://github.com/scipy/scipy/tree/master/scipy/spatial/qhull/src