非凸多边形-预处理以使用凸包算法 [英] Non-convex polygon - preprocess to use convex hull algorithm

问题描述

我使用了凸包算法来找到某些不规则形状的轮廓.但这还不够好...

很可能是因为我不能保证我的形状是凸的...

我有一组矩形，我希望能够将所有点都放在轮廓的外部，但不能将任何轮廓点都扔掉.

凸包算法很好用-但是它的工作方式类似于右侧的示例，因此我在轮廓上会丢失一些信息.

我想要一个更接近左侧版本的东西，保留外部角落，只消除内部的点...

有这样的算法吗?

或者，有没有办法将这样的形状(多边形)分解为凸形，所以凸包算法可以正确处理它?<​​/p>

从一个链接到另一个链接，我一直在尝试找出如何设置某种算法，例如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).

I used the convexHull algorithm to find the contour for some... irregular shape. It is not good enough though...

Quite possibly because I can't guarantee that the shape I have is convex...

I have a set of rectangles, and I would like to be able to get all points on the outside of the contour - but not throw any of the contour points out.

The convex hull algorithm works great - but it works like the example on the right, so I lose some information on the contours.

I want something that works closer to the version on the left, preserving the outside corners, and only eliminating the points inside...

Is there such an algorithm ?

Or, is there any way to break a shape (polygon) like this into convex shapes, so the convex hull algorithm can process it properly ?

From link to link, I have been trying to figure out how to set up some sort of algorithm, like Hertel-Mehlhorn Algorithm - but I don't know what use intersecting lines would do in this situation...

Thank you for any suggestion.

解决方案

If your non-convex polygon is as you've shown it (i.e. the union of a set of quadrilateral elements) all you have to do is find the edges of the quadrilaterals that lie on the boundary.

This can be achieved by noting that these "external" edges only appear in one element, while the "internal" edges are common to two adjacent elements. This implies the following simple algorithm:

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

The remaining unique edges form the external contour of your polygon. This simple algorithm runs in O(N*log(N)) time.

You can improve the complexity by making use of a suitable hash table for the edge comparisons, reducing the complexity to O(N).

这篇关于非凸多边形-预处理以使用凸包算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！