mapnik/mapnik — pull request #1269 by lightmare (2012-06-25 18:08:28+00:00)
Title: offset_converter rewrite, refs #927

I've rewritten the line-offset algorithm. First it traverses all input vertices, computes new vertices in the given distance (not caring for self-intersections) and stores them in a vector. For each bend it computes the end-point of the preceding segment's parallel, the start-point of the next segment's parallel, and connects them by either a straight line (inner turn) or a bulge made of several vertices along the arc (outer turn). This raw line can be seen in the image below marked with (*) (I also left a commented //break enabling this in the code). When vertex(&x,&y) is called, it checks whether the line segment from previous to current vertex intersects the rest of the line - if it does, the intersection point is returned instead, and all vertices preceding it on the line are skipped.

http://i48.tinypic.com/33pen1s.png (red: old algo, blue: postgis)
http://i48.tinypic.com/2ihtocz.png (red: new algo)
http://i49.tinypic.com/zjhs7k.png (red: new algo, simplified geom)

Sample pictures in several zoom levels. The black line is original geom, blue is PostGIS ST_OffsetCurve, red and green are mapnik line-offset with the new algorithm:
http://i47.tinypic.com/eze3qd.png - looks bad where separate linestrings meet, would need some preprocessing for this zoom
http://i50.tinypic.com/2z5ouio.png - there's a glitch with the upper green line, it's caused by how the algo works
http://i45.tinypic.com/2iubye.png - this one looks good, in the bottom left corner there's a little space between two separate linestrings
http://i45.tinypic.com/2cxizib.png (*) - the above picture with intersection detection turned off, showing how the algorithm works

From the silly sharpy line I added above the real-world geometry you can see that postgis (libgeos actually) cuts out the whole two-sided buffer around the line, splitting the offset line in pieces. Maybe it won't be difficult to do - we can compute both parallels at the beginning and check intersections with both - but that's twice as many computations, and we're satisfied with one-side checks for now.

I'd like to see how this works with other people's data, please post pictures if you find some quirks.