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.

Lovash

How are your data stored ? Do you have a set of pixels (or a discretized grid storing values) ? Do you have a set of coordinates for the squares ? Do you have any adjacency information (half-edges etc.) ?... – Sprint

What kind of input format is in your problem? Is it a set of 1x1 rectangles? – Airiness

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

Amerigo

I'll try this - it would actually replace the convex hull, correct ? – Lovash

Yes, indeed. The convex hull would not be computed. – Amerigo

I asked whether there were any adjacency information, because looking at the data, it rather looks like a polygon soup : some quads are just next to each other without touching while the expected result seems to assume they are connected...! – Sprint

yeah... sorry about my sketch ! (reality is sort of the same way, I mostly use an epsilon just in case. – Lovash