欧几里德最小生成树和 Delaunay 三角剖分
Euclidean Minimal Spanning Tree and Delaunay Triangulation
我想根据二维平面上一组点之间的欧式距离计算最小生成树。我当前的代码存储所有边，然后执行 Prim 算法以获得最小生成树。但是，我知道这样做需要 O(n^2) space 用于所有边缘。
经过一些研究，很明显，如果我先在这组点上计算 delaunay 三角剖分，然后通过 运行 Prim 或 Kruskal 算法获得最小生成树，则可以优化内存和运行时间在三角测量的边缘。
这是编程竞赛 (https://prologin.org/train/2017/qualification/taxi_des_neiges) 的一部分，所以我怀疑我能否使用 scipy.spatial。有没有其他方法可以简单地获取 Delaunay 三角剖分中包含的边？
提前致谢。
模块有帮助吗？以下是一些可能有效的方法：
自己动手？这两个描述的都是增量算法，Wikipedia好像说的是O(n log n):
- http://www.geom.uiuc.edu/~samuelp/del_project.html
- http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_1.pdf
这里 an ActiveState recipe 可能有助于开始，但看起来还没有完成。
看起来 Scipy 使用 QHull，它..在此文件夹中的某处...具有执行 delaunay 三角剖分和获取边的代码（尽管是在 C 中实现的）
https://github.com/scipy/scipy/tree/master/scipy/spatial/qhull/src
我想根据二维平面上一组点之间的欧式距离计算最小生成树。我当前的代码存储所有边，然后执行 Prim 算法以获得最小生成树。但是，我知道这样做需要 O(n^2) space 用于所有边缘。
经过一些研究，很明显，如果我先在这组点上计算 delaunay 三角剖分，然后通过 运行 Prim 或 Kruskal 算法获得最小生成树，则可以优化内存和运行时间在三角测量的边缘。
这是编程竞赛 (https://prologin.org/train/2017/qualification/taxi_des_neiges) 的一部分，所以我怀疑我能否使用 scipy.spatial。有没有其他方法可以简单地获取 Delaunay 三角剖分中包含的边？
提前致谢。
模块有帮助吗？以下是一些可能有效的方法：
自己动手？这两个描述的都是增量算法，Wikipedia好像说的是O(n log n):
- http://www.geom.uiuc.edu/~samuelp/del_project.html
- http://graphics.stanford.edu/courses/cs368-06-spring/handouts/Delaunay_1.pdf
这里 an ActiveState recipe 可能有助于开始，但看起来还没有完成。
看起来 Scipy 使用 QHull，它..在此文件夹中的某处...具有执行 delaunay 三角剖分和获取边的代码（尽管是在 C 中实现的）
https://github.com/scipy/scipy/tree/master/scipy/spatial/qhull/src