我使用了convexHull 算法来找到一些……不规则形状的轮廓。虽然还不够好...
很可能是因为我不能保证我的形状是凸的......
我有一组矩形，我希望能够获得轮廓外部的所有点 - 但不要抛出任何轮廓点。
凸包算法效果很好 - 但它就像右边的例子一样，所以我丢失了一些关于轮廓的信息。
我想要更接近左边版本的东西，保留外角，只消除里面的点......
有这样的算法吗？
或者，有没有办法将这样的形状（多边形）分解成凸形，以便凸包算法可以正确处理它？
从一个链接到另一个链接，我一直在试图弄清楚如何设置某种算法，比如 Hertel-Mehlhorn 算法——但我不知道在这种情况下使用相交线会做什么......
谢谢你的任何建议。
如果您的非凸多边形如您所展示的那样（即一组四边形元素的并集），您所要做的就是找到位于边界上的四边形的边缘。
这可以通过注意这些“外部”边缘仅出现在一个元素中来实现，而“内部”边缘对于两个相邻元素是共有的。这意味着以下简单算法：
edge_list = {}
for (i = all elements in mesh)
for (j = all edges in element(i))
edge_list <- push jth edge of ith element
endfor
endfor
edge_list <- sort
edge_list <- remove_duplicates
剩余的独特边形成多边形的外部轮廓。这个简单的算法O(N*log(N))及时运行。
您可以通过使用合适的哈希表进行边缘比较来提高复杂性，从而将复杂性降低到O(N).