Non-convex polygon - preprocess to use convex hull algorithm

Question

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.

Answer 1

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