An algorithm for inflating/deflating (offsetting,

Question

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

Answer 1

I never used Clipper (developed by Angus Johnson) but 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:

Answer 2

Here is an alternative solution, see if you like this better.

1. Do a triangulation, it don't have to be delaunay -- any triangulation would do.

2. Inflate each triangle -- this should be trivial. if you store the triangle in the anti-clockwise order, just move the lines to right-hand-side and do intersection.

3. Merge them using a modified Weiler-Atherton clipping algorithm

Answer 3

In the GIS world one uses negative buffering for this task: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

The JTS library should do this for you. See the documentation for the buffer operation: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

For a rough overview see also the Developer Guide: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Answer 4

Each line should split the plane to "inside" and "outline"; you can find this out using the usual inner-product method.

Move all lines outward by some distance.

Consider all pair of neighbor lines (lines, not line segment), find the intersection. These are the new vertex.

Cleanup the new vertex by removing any intersecting parts. -- we have a few case here

(a) Case 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by one, you got this:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 and 4 overlap.. if you see this, you remove this point and all points in between.

(b) case 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by two, you got this:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

to resolve this, for each segment of line, you have to check if it overlap with latter segments.

(c) case 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

expend by 1. this is a more general case for case 1.

(d) case 4

same as case3, but expend by two.

Actually, if you can handle case 4. All other cases are just special case of it with some line or vertex overlapping.

To do case 4, you keep a stack of vertex.. you push when you find lines overlapping with latter line, pop it when you get the latter line. -- just like what you do in convex-hull.

Answer 5

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.