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

I thought I might briefly mention my own polygon clipping and offsetting libraryClipper.

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.

Polygon offsetting styles

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:

vCgNf

And this is the straight skeleton for another polygon:

lETWh

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:

enter image description here

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:

enter image description here

Leave a Comment