Lossless path simplification (only simplifying outwards)

[sponsoredlinks]

Hi, just another quick question about a recommended approach. When solving coverage problems it is of interest to simplify the subject contour as much as possible while also ensuring that no coverage is missed - so basically only ever expanding any (closed) subject polygon outwards

I've had a bit of a look around the internet and can't really find any description or implementation of this, which is strange as it would seem to be a reasonably logical extension of general path simplification algos

Anyway I was thinking that a way to do this might be:

• Apply Ramer–Douglas–Peucker to the polygon to simplify (both inwards and outwards)
• Take the union of the subject and the RDP output, to eliminate inward simplifications

Does this appear to be correct (and optimal)? I actually wonder too if it is worth adding this as a parameter to the RamerDouglasPuecker() function if so - eg as bool:OnlyExpand (or even as an enum OnlyExpand / OnlyContract / NoRestriction)

[AngusJohnson]

Anyway I was thinking that a way to do this might be:
Apply Ramer–Douglas–Peucker to the polygon to simplify (both inwards and outwards)
Take the union of the subject and the RDP output, to eliminate inward simplifications

That'd work but it'd be relatively time costly.
Alternatively, if you were confident of the orientation of your paths, you could modify the RDP function so that it only removed vertices that were angling inwards (and test for this using CrossProduct).

[sponsoredlinks]

Thanks, yes this sounds like the closest solution to what I was thinking. Will test..

[alexisnaveros]

It doesn't seem like a difficult problem, are you trying to get a convex or mostly-convex shape that contains a polygon?

I would:

• Pick a "most" vertex (bottom-most, right-most, whatever)
• Iterate over the other vertices, find the vertex with the steepest angle (most outward vertex)
• Trace a line segment between the two, and repeat the step from that new vertex, until you have closed the shape

The steps above are going to give you a convex polygon, but you can limit to search to a certain distance (but always including the direct neighbor, no matter the distance) to allow some concave angles. I guess I would also do a final postprocessing step: remove tiny edges from the final result by joining the two neighbor edges (connected to the tiny edge) at a distant vertex, the intersection point of these two neighbor edges (removing the tiny edge, turning two vertices into one).

If you have millions of edges, the step "Iterate over the other vertices" will have to be a little smarter, but that's not too complicated.

[AngusJohnson]

Convex hull.

[sponsoredlinks]

Hi guys, yes not strictly convex - as Angus has surmised above just not simplifying (removing) any concave vertices. Convex hull works for this but wildly expands the polygon area in certain cases (eg for a very-convex polygon), so ends up being inefficient.