欧几里得最小生成树和德劳内三角剖分

Question

4

我想基于平面上一组点之间的欧几里得距离计算最小生成树。我的当前代码存储所有边，然后执行Prim算法以获得最小生成树。然而，我意识到这样做需要O(n^2)的空间来存储所有的边。

经过一些研究，我发现如果我先在这组点上计算Delaunay三角形，然后通过运行Prim或Kruskal算法在三角形的边缘上获取最小生成树，可以优化内存和运行时间。

这是编程比赛的一部分(https://prologin.org/train/2017/qualification/taxi_des_neiges)，所以我怀疑我能否使用scipy.spatial。有没有其他方法简单地获取Delaunay三角形中包含的边缘？

提前感谢。

- Jingjie Yang

2个回答

3

似乎Scipy使用QHull，在这个文件夹中...有用于执行Delaunay三角剖分和获取边缘的代码（虽然是用C实现的）。 https://github.com/scipy/scipy/tree/master/scipy/spatial/qhull/src

- Marviel

没问题，希望wildwilhelm的回答能有所帮助！看起来他找到了算法的抽象描述。 - Marviel

1

是的，你们两个的回答都帮了我很多，所以这里有一个赞来表示感谢！ - Jingjie Yang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- wildwilhelm · Accepted Answer

需要模块来帮助吗？以下是几个可能适用的模块：

自己编写？这两个都描述了增量算法，维基百科似乎说它是O(n log n)：

这里有一个ActiveState的配方，可能会有所帮助，但看起来它还没有完成。