Create offset line contours from a line set with arbitrary topology

Question

Example image:

Given a set of connected lines (see thick black lines in example image), how can you generate a set of offset contour lines that form loops (see thin blue lines)? The offset is constant across all lines, and the contours are always parallel to its associated lines.

The input line topology is arbitrary: i.e. it may contain cycles. Note that the number of contour loops is equal to the number of cycles plus one. A solution that just deals with tree topologies only (no cycles) could also be of interest.

Any papers or relevant algorithms out there that tackle this problem?

"Note that the number of contour loops is equal to the number of cycles plus one": not always. The inner loops smaller than the offset width vanish. — , Nov 24 '17 at 15:11
see [draw outline for some connected lines](https://stackoverflow.com/a/22068534/2521214) — Spektre, Nov 26 '17 at 09:34

score 0 · Accepted Answer · 2017-11-24T15:48:31.333

0

The basic method is to construct the bissectrix of the angles (on the right side) and draw on it a length such that it achieves the desired offset (a little of trigonometry). And to link them in the loop traversal order. Different capping rules can be used at free endpoints.

For this to be possible, you need a representation of the geometry as a planar graph (quad-edge for instance). Maybe have a look here: https://mathoverflow.net/q/23811.

Anyway, this method will not avoid the overlaps that can arise, nor self-intersecting offsets. These are much more difficult problems that require a global approach, and are similar to the polygon union problem.

edited Nov 24 '17 at 15:48

answered Nov 24 '17 at 15:38

Thanks for your reply, Yves. It makes sense to place the points along the bisectrix. But once you know where the points end up, you still need to figure out in what order to connect them. Traversal order sounds plausible, but I think it's more complicated than that because you need to generate several loops simultaneously on both sides of each input edge. Perhaps it's be easier to just generate partial polygons per input line (using your suggested bisectrix methor) and them fuse them together by throwing away edges shared by two polygons. Eventually that will leave only the boundary edges. – drtommertens Nov 24 '17 at 16:33
You need to enumerate all simple cycles of the planar graph exactly once, including the "outer" loop. – Nov 24 '17 at 17:15

Create offset line contours from a line set with arbitrary topology

1 Answers1