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

Question

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

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

我的问题类似 最佳算法找到顶点的边缘（多边形） 但是我需要它用于非凸多边形案例。

编辑：澄清：下图是凹形多边形。这就是我的意思。如果我在上面运行凸壳算法，它不会保留多边形的凹点。（除非我错误地）。

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

Answer 1

这似乎是一个热门话题。https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

本文似乎是最好的。Duckham，M.，Kulik，L.，Worboys，MF，Galton，A。（2008）有效地生成简单多边形，以表征飞机中一组点的形状。模式识别v41，3224-3236

Answer 2

您的描述有些模糊，但是您可能正在寻找算法来构建一个 凸壳 一组点。简而言之，如果在所有顶点上放置橡皮筋，凸壳是您获得的形状。
在2D中编写凸壳算法并不难，有些图书馆像这样 QHULL

（您链接到的问题也给出了这个答案，这似乎是您问题的特殊情况）

Answer 3

这是一个古老的，也许是被废弃的问题，但这让我想到了。您不是在寻找凸船体，而是要保持多边形的形状，而只是摆脱沿线“边缘”之间的点。

该解决方案可能是跨过相邻点并计算第一和第二的线性斜率，然后保存该斜率值，如果PT1-PT2的斜率等于PT2-PT3的斜率，则计算第二和第三的斜率然后，PT2在形成线路时是多余的，因此可以去除。继续循环遍历，直到您在PT1处弯曲为止。

这将确保保持您的凹形形状，但要删除无关紧要的额外点。

Answer 4

您要寻找的一词是 凹面船体.

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

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

这里 k 是您的超参数调音。如果 k 太高了，您会得到凸壳。如果 k 太低了，您产生的多边形有很多凹面。

---

以下是一些相关链接：

• https://github.com/mapbox/concaveman
• https://gis.stackexchange.com/questions/1200/what-are-definition-algorithms-and-practical-solutions-for-concave-hull
• 凹面船体：k-neart邻居的方法来计算一组点所占用的区域（关联)