我有一组顶点（称为A），我想要找到所有边界顶点，以便此边界顶点集是该形状的轮廓。给定非凸多边形中的一大组顶点，我如何找到边？
A中的许多顶点都是多余的，因为它们在形状内部，我想摆脱这些顶点。
我的问题类似Best Algorithm to find the edges (polygon) of vertices，但我需要它为一个非凸多边形的情况下工作。
编辑： 说明：下图是一个凹多边形。这就是我的意思是非凸的。如果我在它上面运行凸包算法，它不会保留多边形的凹形部分（除非我错了）。
我有一组顶点的内部和多边形的边界：[[X1，Y1]，[X2，Y2] ...] 我想降低设定使得顶点只是形状的边框轮廓。
您的描述有些模糊，但可能您正在寻找构建一组点的Convex Hull的算法。简而言之，如果在所有顶点周围放置橡皮筋，凸包就是您的形状。
写作二维凸包算法是不是非常困难的，也有一些库，做到像qhull
（即答案在问题也给了你链接到这似乎是一个特殊的情况下，你问题）
凸包不会排除某些点，因为它只会跟踪凸多边形？我在答案中添加了一张图片来澄清形状。 – 2010-04-30 17:28:27
它会但你怎么能告诉哪个边缘要分开把这两个额外的边缘？ – shoosh 2010-04-30 19:05:18
这是一个古老的，也许是遗弃的问题，但它让我思考它。你不是在寻找一个凸包，你想要保持多边形的形状，但只是摆脱沿着一条线的“边缘”之间的点。
解决方案可以是逐步通过相邻点并计算第一个和第二个线性斜率，然后保存该斜率值，计算第二个和第三个斜率，如果pt1-pt2的斜率等于该斜率的pt2-pt3，那么pt2在形成线路中是多余的，因此可以删除。继续循环直到你回到pt1。
这将确保您的凹形状保持不变，但不相关的加点被删除。
你是指“为非凸多边形案件工作”是什么意思？你链接的问题包括输入顶点形成一个凹多边形的情况，所以我没有看到你的问题有什么不同。 – outis 2010-04-30 00:56:20
如何区分多边形内的哪些顶点以及边上的哪些顶点？ – 2010-07-14 20:22:22