How to calculate Polygon points from a simple line for a specific width?

Question

I currently develop an application that creates polygons from lines and I experience a small problem:

I have a set of points, representing a line. I would like to create a polygon that displays the line with a specific width (e.g. for a street). I have several ideas how to calculate the outer polygon points, but I think they are too complicated...

My best idea was the one pictured below: Every point of the line must be projected to at least two points: Both points must be 90° to the following line segment and have a distance half of the preferred polygon width.

This works good, as you can see at the end and start points of the pictured polygon. Now the complicated part: With this method, at a corner, each point gets four points. But these points are not correct for the outer polygon, because they are in the shape. The lines intersected and created an ugly polygon.

How can I find the correct points for such a polygon? I think my method is far too complicated for solving this problem.

Can anybody help me with this (propably very common) problem?

Info: I tagged this with openstreetmap because renderer like Mapnik have this problem, too.

Answer 1

What you are looking for is a polygon (or line) offsetting algorithm. This is not necessarily an easy problem to solve, by the way: An algorithm for inflating/deflating (offsetting, buffering) polygons.

For the last couple of weeks I've been working on a line offsetting algorithm for Maperitive. In my case I only needed to offset the line so I wasn't looking for a solution to create a buffered polygon around it, but I guess the algorithm could be extended further in the future:

Basic flow (roughly, but the devil is in the details):

1. For each polyline point find a point that has an L distance from the original point and lies on a line that's orthogonal to the original line and goes through the original point.
2. Now draw an offset line through that new point. The line must be parallel to the original line.
3. For corner angles you must extend the two neighbouring offset lines and find the intersection point, which will be the next point of the offset line.

Some things to observe:

• Notice the miter limit applied on concave angles to the right of the picture.
• Before calculating the offset line you need to simplify the original polyline to exclude segments that are too small to hold the offset (the results can be seen at the center left of the picture).
• I only implemented support for miter joins, but a good algorithm should be able to render round joins, too (using arcs).