algorithm - 找到顶点边缘（多边形）的最佳算法

Question

我有大量顶点，其中一些是边，一些是多余的（在形状内部），我想删除它们。

我能想到的最简单的算法是一一检查它们是否碰到了其他人形成的形状。但它应该是一个非常慢的算法。

我考虑过从边缘选择一个（每个示例离原点最远的一个）并计算从这个开始的最长路径......应该得到边缘路径，对吗？

有什么建议吗？

Answer 1

多面体算法的诀窍是选择一个适合您的输入和所需输出的算法，因为表示多面体的方法不止一种，并且表示之间的转换可能很昂贵。在这种情况下，您从点开始并希望以顶点结束，因此计算凸包顶点的格雷厄姆扫描算法应该可以解决问题，尽管可能需要一些努力才能将其扩展到二维情况。输入顶点的数量为O( n log n )。

Answer 2

我不知道找到该多边形的最佳算法是什么，但您正在寻找的多边形称为“凸壳”。

通过搜索，您应该找到匹配算法。

Answer 3

凸壳是计算几何中研究较多的问题之一。格雷厄姆扫描是最简单的凸包算法之一，但肯定不是唯一的。礼品包装算法，也称为 Jarvis' March，是我所知道的最简单的算法。Stony Brook 算法存储库有几种 C 和 C++ 中凸包算法的实现。Geometry in Action主要展示了凸包的应用。这是一个低维和任意维凸包计算程序的集合。