我有一个大的顶点数组，其中一些是边缘，一些是冗余的（在形状内部），我想删除它们。
我能想到的最简单的算法是逐个检查它们是否与其他顶点形成的形状相交。但这应该是非常慢的算法。
我考虑选择一个边缘（例如，距离原点最远的边缘）并计算从此起点开始的最长路径... 应该获得边缘路径，对吗？
有什么建议吗？
寻找顶点的多边形边缘的最佳算法
5
- mrlinx
2
你想要一个覆盖所有点的多边形，还是想要覆盖所有点的面积最小的多边形？ - sykora
@sykora，一个覆盖所有点的多边形。格雷厄姆扫描算法似乎可行。谢谢。 - fabiopedrosa
3个回答
8
多面体算法的关键是选择适合您输入和期望输出的算法，因为有不止一种表示多面体的方法，而在不同的表示方式之间转换可能很昂贵。在这种情况下，您从点开始，并希望以顶点结束，因此使用Graham scan算法计算凸包的顶点应该可以解决问题，尽管将其扩展到2-D案例可能需要一些努力。它的时间复杂度为O(n log n)，其中n是输入顶点的数量。
- Chris Conway
1
Graham扫描基本上为您提供凸包。 - shoosh
6
我不知道找到该多边形的最佳算法是什么，但你要找的多边形被称为“凸包”。
通过搜索它，你应该能找到一个匹配的算法。
通过搜索它，你应该能找到一个匹配的算法。
- Timbo
4
我认为他不是在寻找凸包，因为他想要由他的顶点形成的多边形的边缘。凸包甚至可能会排除他想要的一些内容。 - sykora
有些是多余的（在形状内部），我想把它们删除。 - Timbo
我不是想减少边缘……我正在考虑从顶点集合中构建一个多边形，其中一些顶点是冗余的。 - fabiopedrosa
你好，我该如何获取我用于将多边形插入MySQL数据库的顶点？ - shasi kanth
4
凸包问题是计算几何中研究较多的问题之一。凸包算法中，Graham扫描是较为简单的一种，但并不是唯一的一种。礼品包装算法，也称为Jarvis' March，是我所知道的最简单的一种。Stony Brook算法库提供了C和C++语言实现的多种凸包算法。Geometry in Action主要展示凸包的应用场景。这里有一些低维和任意维凸包计算程序。
- Yuval F
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接