Jin*_*ANG 3 python delaunay minimum-spanning-tree euclidean-distance
我想根据2D平面上一组点之间的欧氏距离计算最小生成树.我当前的代码存储了所有边,然后执行Prim的算法以获得最小的生成树.但是,我知道这样做会O(n^2)占用所有边缘的空间.
在做了一些研究之后,如果我首先在这组点上计算delaunay三角剖分,然后通过在三角剖分的边缘上运行Prim或Kruskal算法来获得最小生成树,那么很明显可以优化内存和运行时.
这是编程竞赛的一部分(https://prologin.org/train/2017/qualification/taxi_des_neiges),所以我怀疑我能否使用scipy.spatial.有没有其他方法可以简单地获得Delaunay三角剖分中包含的边缘？
提前致谢.
模块会有帮助吗？这里有一些可行的方法:
滚你自己？这两个都描述了增量算法,维基百科似乎说是O(n log n):
这是一个可能有助于入门的ActiveState配方,但它看起来还没有完成.
| 归档时间： |
|
| 查看次数： |
695 次 |
| 最近记录： |