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

Question

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

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

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

有什么建议吗？

Answer 1

与多面体算法诀窍是选择一个与您输入和所需输出适合，由于存在表示一个多面体一种以上的方式与表示之间转换可能是昂贵的。在这种情况下，您从开始点和希望与顶点结束，所以格雷厄姆扫描算法计算凸包应该做的伎俩的顶点，虽然它可能需要一些努力扩大它经过2-d的情况。这是O（ N日志Ñ）中输入的顶点的数量。

Answer 2

我不知道什么是最好的算法来找到多边形，但你正在寻找的被称为“凸包”。

多边形

通过搜索，你应该找到一个匹配算法。

Answer 3

凸包 是计算几何研究较多的问题之一。格雷厄姆扫描是最简单的扫描之一 凸包算法, ，但肯定不是唯一的。 礼物包装算法, ，也称为贾维斯进行曲，是我所知道的最简单的。 Stony Brook 算法存储库 有几种用 C 和 C++ 实现的凸包算法。 几何在行动 主要展示了凸包的应用。这是一个集合 低维 和 任意维 凸包计算程序。