python - 欧几里德最小生成树和 Delaunay 三角剖分

Question

我想根据二维平面上一组点之间的欧式距离计算最小生成树。我当前的代码存储所有边，然后执行 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?

自己动手？这两个都描述了增量算法，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这可能有助于开始，但看起来还没有完成。