An algorithm for inflating/deflating (offsetting, buffering) polygons

How would I "inflate" a polygon? That is, I want to do something similar to this:

The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the example picture they are not, since then it would have to use arcs for inflated vertices, but let's forget about that for now ;) ).

The mathematical term for what I'm looking for is actually inward/outward polygon offseting. +1 to balint for pointing this out. The alternative naming is polygon buffering.

Results of my search:

Here are some links:

• A Survey of Polygon Offseting Strategies
• Polygon offset, PROBLEM
• Buffering Polygon Data

I thought I might briefly mention my own polygon clipping and offsetting library - Clipper.

While Clipper is primarily designed for polygon clipping operations, it does polygon offsetting too. The library is open source freeware written in Delphi, C++ and C#. It has a very unencumbered Boost license allowing it to be used in both freeware and commercial applications without charge.

Polygon offsetting can be performed using one of three offset styles - squared, round and mitered.

The polygon you are looking for is called inward/outward offset polygon in computational geometry and it is closely related to the straight skeleton.

These are several offset polygons for a complicated polygon:

And this is the straight skeleton for another polygon:

As pointed out in other comments, as well, depending on how far you plan to "inflate/deflate" your polygon you can end up with different connectivity for the output.

From computation point of view: once you have the straight skeleton one should be able to construct the offset polygons relatively easily. The open source and (free for non-commercial) CGAL library has a package implementing these structures. See this code example to compute offset polygons using CGAL.

The package manual should give you a good starting point on how to construct these structures even if you are not going to use CGAL, and contains references to the papers with the mathematical definitions and properties:

CGAL manual: 2D Straight Skeleton and Polygon Offsetting

For these types of things I usually use JTS. For demonstration purposes I created this jsFiddle that uses JSTS (JavaScript port of JTS). You just need to convert the coordinates you have to JSTS coordinates:

function vectorCoordinates2JTS (polygon) {
  var coordinates = [];
  for (var i = 0; i < polygon.length; i++) {
    coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
  }
  return coordinates;
}

The result is something like this:

Additional info: I usually use this type of inflating/deflating (a little modified for my purposes) for setting boundaries with radius on polygons that are drawn on a map (with Leaflet or Google maps). You just convert (lat,lng) pairs to JSTS coordinates and everything else is the same. Example:

Sounds to me like what you want is:

• Starting at a vertex, face anti-clockwise along an adjacent edge.
• Replace the edge with a new, parallel edge placed at distance d to the "left" of the old one.
• Repeat for all edges.
• Find the intersections of the new edges to get the new vertices.
• Detect if you've become a crossed polygon and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'm not sure whether there's a better way to detect this than just to compare every pair of non-adjacent edges to see if their intersection lies between both pairs of vertices.

The resulting polygon lies at the required distance from the old polygon "far enough" from the vertices. Near a vertex, the set of points at distance d from the old polygon is, as you say, not a polygon, so the requirement as stated cannot be fulfilled.

I don't know if this algorithm has a name, example code on the web, or a fiendish optimisation, but I think it describes what you want.