非凸多边形 - 预处理以使用凸包算法

Question

非凸多边形 - 预处理以使用凸包算法

algorithmgeometryconvex-hullgraph-drawingnon-convex

4

我使用凸包算法来寻找一些不规则形状的轮廓。但是这并不够好，可能是因为我无法保证我的形状是凸的。

我有一组矩形，并且想要能够获得轮廓外部的所有点 - 但不丢弃任何轮廓点。

凸包算法非常有效，但它像右侧的示例，所以我损失了一些轮廓信息。我希望有一个更接近左侧版本的算法，保留外部角落，并仅消除内部点...

是否有这样的算法？

或者，是否有一种将这样的形状（多边形）分解成凸形状的方法，使得凸包算法可以正常处理它？

通过各种链接，我一直在试图找出如何设置某种算法，例如Hertel-Mehlhorn算法-但我不知道在这种情况下相交线的用途是什么...

谢谢任何建议。

- Thalia

你的数据是如何存储的？你有一组像素（或存储值的离散化网格）吗？你有正方形的一组坐标吗？你有任何相邻信息（半边等）吗？... - nbonneel

你的问题采用何种输入格式？是一组1x1的矩形吗？ - songlj

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Darren Engwirda · Accepted Answer

如果您的非凸多边形如您所示（即由一组四边形元素组成），则您只需找到位于边界上的四边形的边缘。

可以通过注意到这些“外部”边缘仅出现在一个元素中，而“内部”边缘则共同出现在两个相邻元素中来实现此目标。这意味着以下简单算法：

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)。