给定一个非凸多边形中的一大组顶点,如何才能找到边?

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

这篇论文似乎是最好的。 Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

您的描述有些模糊,但您可能正在寻找构造 Convex Hull 一组点。简单地说,如果在所有顶点周围放置橡皮筋,凸面外壳就是你得到的形状。
在2d中编写凸壳算法并不太困难,而且有一些库可以做到这一点。 qhull

(该答案也在您所链接的问题中给出,而您所链接的问题似乎是您问题的特殊情况)

这是一个古老的,也许被抛弃的问题,但它让我开始思考。你不是在寻找一个凸面外壳,你想保持多边形的形状,但只是摆脱点之间的“边缘”沿一条线。

解决方法可以是跨过相邻点,计算第一和第二的线性坡度,然后保存该坡度值,计算第二和第三个坡度,如果pt1-pt2的坡度等于pt2-pt3的坡度,则pt2在形成线时是多余的,因此可以是r。情绪激动。一直循环直到你回到PT1。

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

你要找的术语是 凹形船体 .

这个问题最简单的形式并不像凸壳那样定义得很好,因为覆盖给定点的凹多边形不是唯一的。然而,有许多好的方法。

最简单的方法之一是,使用礼品包装算法,而不是只考虑每个步骤中的所有点 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近邻方法。( link )