查找顶点边(多边形)的最佳算法

Question

我有一大堆顶点,其中一些是边,一些是冗余的(在形状内),我想删除它们.

我能想到的最简单的算法是,如果它们碰到其他人形成的形状,则逐个检查.但它应该是一个非常慢的算法.

我想过从边缘挑选一个(距离每个例子最远的一个)并计算从这个开始的最长路径...应该得到边缘路径,对吗？

有什么建议吗？

Answer 1

多面体算法的技巧是选择一个适合您的输入和所需输出的技巧,因为有多种方法来表示多面体,并且表示之间的转换可能很昂贵.在这种情况下,您从点开始并希望以顶点结束,因此用于计算凸包顶点的Graham扫描算法应该可以解决问题,尽管可能需要花费一些精力才能将其扩展到2-D情况.它是输入顶点数量的O(n log n).

Answer 2

我不知道找到该多边形的最佳算法是什么,但您正在寻找的多边形称为"凸壳".

通过搜索,您应该找到匹配的算法.