我有一组顶点（称为A），我想找到所有边界顶点，使得这些边界顶点集合是该形状的轮廓。
A中许多顶点是冗余的，因为它们在形状内部，我想摆脱这些顶点。
我的问题类似于Best Algorithm to find the edges (polygon) of vertices，但我需要它适用于非凸多边形情况。
编辑： 澄清：下面的图像是一个凹多边形。这就是我所说的非凸性。如果我在它上面运行凸包算法，它将无法保留多边形的凹部（除非我弄错了）。
我有一组多边形内部和边界上的顶点：[[x1,y1]，[x2,y2] ...]，我想缩小该集合，使得顶点仅为形状的边界轮廓。
这是一个可能被遗弃的老问题，但它让我思考。你不是在寻找凸包，而是想要保持多边形的形状，只是摆脱沿着线条的“边缘”之间的点。
解决方法可以是逐步通过相邻点并计算第一点和第二点的线性斜率，然后保存该斜率值，计算第二个点和第三个点的斜率，如果pt1-pt2的斜率等于pt2-pt3的斜率，则pt2在形成该线路中是多余的，因此可以被删除。继续循环直到回到pt1。
这将确保保持您的凹形状，但无关的额外点将被移除。
您要查找的术语是凸包。
与凸包不同，覆盖给定点的凹多边形并不唯一，因此最简单形式的问题并没有像凸包那样被很好地定义。然而，有许多好的方法。
其中最简单的方法之一是使用礼品包装算法，但在每个步骤中只考虑当前顶点的k个最近邻点，这里的k是您要调整的超参数。如果k太高，则会得到凸包。如果k太低，则所得到的多边形具有许多凹度。
