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

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

Answer 2

Based on advice from @JoshO'Brian, it appears the rGeos package in the R language implements this algorithm. See rGeos::gBuffer .

Answer 3

One further option is to use boost::polygon - the documentation is somewhat lacking, but you should find that the methods resize and bloat, and also the overloaded += operator, which actually implement buffering. So for example increasing the size of a polygon (or a set of polygons) by some value can be as simple as:

poly += 2; // buffer polygon by 2

Answer 4

Big thanks to Angus Johnson for his clipper library. There are good code samples for doing the clipping stuff at the clipper homepage at http://www.angusj.com/delphi/clipper.php#code but I did not see an example for polygon offsetting. So I thought that maybe it is of use for someone if I post my code:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        foreach (var point in originalPath)
        {
            polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
        }

        ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
        co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);

        List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        co.Execute(ref solution, offset);

        foreach (var offsetPath in solution)
        {
            foreach (var offsetPathPoint in offsetPath)
            {
                resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
            }
        }

        return resultOffsetPath;
    }

Answer 5

There are a couple of libraries one can use (Also usable for 3D data sets).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

One can also find corresponding publications for these libraries to understand the algorithms in more detail.

The last one has the least dependencies and is self-contained and can read in .obj files.

Best wishes, Stephan

Answer 6

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 polynomial 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.