Parallel Curve Similar to Chart Algorithm

Question

Is there a well-known algorithm for computing a "parallel graph"? where, by a parallel graph, I mean the same thing as a parallel curve, vaguely called a "displacement curve", but with a graph instead of a curve. In the best case, this will allow you to vary the distance for each segment (connection).

Given the following image, where the coordinates of the nodes associated with the red segments are known, as well as the desired distance (thickness)

offset chart http://3.bp.blogspot.com/_MFJaWUFRFCk/TAEFKmfdGyI/AAAAAAAACXA/vTOBQLX4T0s/s320/screenshot2.png

How can I calculate the points of black outlined polygons?

Answer 1

Check out Straight Seleton . Below is an example implementation here . The complexity of the algorithm is documented here .

In addition, several other methods are described here, Overview of Polygon Shift Strategies .

There is also a theme in GameDev .

Edit: CGAL also has an implementation on this, since v3.3, see the API . Nice introduced a test file . (Not an implementation.) However, you can check the source.