2

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.

fisch
  • 23
  • 3
  • You don't inflate all polygons at once, you do it one at a time. then you look for intersections make a straight connection between the two points where the shapes intersect and remove the part that peeks into the other polygon. That's imo. the simplest and best solution. – Thomas Jun 06 '23 at 16:06
  • What does "fair" mean, in the case where an offset vertex from one shape intersects an offset edge from another shape? (and in particular where the generating edge and vertex are NOT coincident, as they are in all your examples.) – Sneftel Jun 06 '23 at 16:09
  • Note that non-convex polygons can become self-intersecting when you inflate them. Also multiple polygons can join to enclose an area. You'll need to decide what you want to do about that. – Matt Timmermans Jun 06 '23 at 17:47
  • In a previous question [Fastest polygon union...](https://stackoverflow.com/questions/75355917/fastest-polygon-union-when-all-polygons-are-rectangles), I proposed a solution that works even if polygons are intersecting. – Graffito Jun 07 '23 at 09:25
  • @Thomas I was thinking along the same lines. It certainly works for the triangle case in the example. But I think it fails in other cases. – fisch Jun 07 '23 at 21:09
  • @Sneftel that's a good point, I am not sure. I can try to draw what would be my ideal outcome (something like roughly half of the overlapping area is assigned to each original polygon. But when it comes to an algorithm I guess the simplest the better. – fisch Jun 07 '23 at 21:18
  • @MattTimmermans that's fair. For the self-intersecting bit I would try to simplify the polygon after inflation if possible. And I am okay if multiple polygons end up enclosing an area. – fisch Jun 07 '23 at 21:18
  • @Graffito in my case I am trying to keep the polygons separate. – fisch Jun 07 '23 at 21:18
  • *fisch* : I didn't fully understood the problem that is much more complex than the polygon union, which itself is not an easy task. @sneftel : "fairly" means that the points belonging to the limit separating 2 overlaps are at equal distances to the 2 initial polygons. – Graffito Jun 07 '23 at 22:56

1 Answers1

1

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.

Sneftel
  • 40,271
  • 12
  • 71
  • 104
  • The use case is related to origami: given an SVG file that represents an unfolded piece of paper where each polygon in the SVG represents a face that will be visible once the origami is folded, and the polygons are used as clip paths to clip different images, enlarge each clip path so that the origami creases do not need to be perfect to show the image and no "neutral" space. I will need to convert these shapes back to SVG and I might try to avoid complex arcs and split shapes. I think this is a good steer in the right direction so thanks! – fisch Jun 08 '23 at 09:49
  • Okay a friend suggested that since the final output needs to be printed and rasterized I do not necessarily need to convert back to SVG and I could just determine to which polygon each final pixel belongs to and therefore which clipped image I should clone the pixel from. So, using pixels might help compute the equivalent of the Voronoi diagram in an efficient way. – fisch Jun 08 '23 at 10:19