Search code examples
algorithmgeometrypolygoncomputational-geometry

An algorithm for offsetting multiple polygons without overlaps

Given a list of polygons that are guaranteed to be not intersecting each other (and also guaranteed to not be self-intersecting), I would like to write an algorithm (or use a library) that generates an outward polygon offset "where possible" with the following characteristics:

  • No generated offset area can overlap with an area defined by one of the original polygons
  • Where generated offset areas from two or more polygons would overlap, the overlap area should be assigned "fairly" among the polygons

The picture below should give an idea of what I am looking for.
The picture is not accurate.
I do not think the term "fairly" is correct and there might be multiple strategies.
Ideally I would like to apply a strategy that is close to the one in the picture.

Image link

I found different questions on how to offset polygons (e.g. An algorithm for inflating/deflating (offsetting, buffering) polygons). But I cannot find anything around offsetting multiple polygons at the same time.

Solution

  • Your proposed rules:

    • Offset the boundary of each shape by a constant radius...
    • But do not allow the resultant shapes to intersect...
    • ...and each point which could be assigned to two or more shapes, should be assigned to the closest shape.

    Under these rules, a few weird things happen:

    • Boundaries consist of straight lines and parabolic arcs. Some corners appear "unfairly truncated".
    • A shape can have an "inflated" version which is in multiple pieces, even if all the original shapes are convex and nonintersecting.

    You stuck your medial axis in my straight skeleton!

    Nevertheless, the way to accomplish this is to find the "segment Voronoi diagram" of the shapes (its set of boundaries is also known as the "medial axis"), and find the intersection of each shape's boundaries with that shape's inflated version. CGAL or a similar geometry library should be able to do this straightforwardly.

    You haven't talked about your use case, so it's not clear what your actual needs are, but in this situation I would use "dilation" (aka "buffering"), not boundary offsetting, so that the rules and computation would be simpler (basically just a Voronoi diagram with truncated distances) and acute corners wouldn't give me so much grief. The resultant shapes would have circular arcs corresponding to original vertices.

    Incidentally, you'll find the most interest in this sort of problem in the GIS community.