outline - 给定非凸多边形中的大量顶点，我如何找到边缘？

Question

我有一组顶点（称为 A），我想找到所有的边界顶点，使得这个边界顶点集是形状的轮廓。

A 中的许多顶点都是多余的，因为它们在形状内部，我想摆脱这些顶点。

我的问题类似于查找顶点边缘（多边形）的最佳算法，但我需要它来处理非凸多边形情况。

编辑：澄清：下图是一个凹多边形。这就是我所说的非凸的。如果我在其上运行凸包算法，它不会保留多边形的凹面部分。（除非我弄错了）。

我在多边形的边界内和边界上有一组顶点： [[x1,y1], [x2,y2]...] 我想减少集合，使顶点只是形状的边框轮廓。

score 5 · Accepted Answer

score 0 · Accepted Answer

您的描述有些含糊，但您可能正在寻找构造一组点的凸包的算法。简单地说，凸包就是在所有顶点周围放上橡皮筋所得到的形状。
在 2D 中编写凸包算法并不是非常困难，并且有一些库可以像qhull

（您链接到的问题中也给出了该答案，这似乎是您问题的特例）

score 0 · Accepted Answer

这是一个古老的，可能被遗弃的问题，但它让我开始思考。您不是在寻找凸包，而是要保持多边形形状，而只是摆脱沿线位于“边缘”之间的点。

解决方案可以是遍历相邻点并计算第一个和第二个的线性斜率，然后保存该斜率值，如果 pt1-pt2 的斜率等于 pt2-pt3 的斜率，则计算第二个和第三个的斜率那么 pt2 在形成线时是多余的，因此可以被删除。继续循环，直到回到 pt1。

这将确保您的凹形保持不变，但不相关的额外点会被删除。

score 0 · Accepted Answer

您正在寻找的术语是凹壳。

问题的最简单形式不像凸包那样定义明确，因为覆盖给定点的凹多边形不是唯一的。但是有很多好的方法。

最简单的方法之一是，您使用礼品包装算法，但不是考虑每一步的所有点，而是只考虑当前顶点的k最近邻。

这里k是你要调整的超参数。如果k太高，你会得到凸包。如果k太低，则生成的多边形有很多凹面。

以下是一些相关链接：

4 回答 4