有没有一种算法可以告诉您在给定一组点的情况下连接哪些点以形成三角形？没有一条连接线可以相交，但是三角形可以在其他三角形的内部。
问问题
1757 次
3 回答
1
给定Delaunay 三角剖分R^d中的一组一般点通常是曲面细分的最佳选择。
具体来说，Delaunay 三角剖分会将点集的凸包细分为一组不重叠的元素，确保最大圆周球的半径最小化——这意味着三角剖分在其“紧凑性”方面是最优的，或者换句话说，生成了具有良好纵横比的元素。
构建 Delaunay 三角剖分的高效算法并非易事，但有许多优秀的库 - 我可以推荐Triangle、CGAL或Qhull（用于高维问题） ， JDT显然是 Java 中的一种实现，尽管我从未使用过它。
于 2013-05-31T05:06:22.940 回答
0
我也在尝试解决这个问题。这是一个为游戏 Ingress 工作的人的 github 分支的链接，这就是我对解决方案感兴趣的原因。但是，据我所知，最佳解决方案是通过蛮力找到的（我可能对此错了），并且还有其他因素可以最大化和最小化。此外，我认为有些东西，例如采用 E6 纬度/经度并投影到 Gnomonic 投影上以确定最短路线，但是我认为这在通过代码时可以打折扣。我认为此代码中没有您的解决方案，但对于您、我和其他任何研究此问题的人来说，这可能是一个很好的起点。
于 2014-11-12T22:02:22.780 回答
0
我不确定它是否正是您正在寻找的，但它可能会有所帮助：Graph Theory
于 2013-05-31T04:09:13.397 回答