0

I am looking for algorithm that will let me thicken given polyline -- or algorithm that will create a second polyline, which could be thought as left/right boundary of the "thick line".

The input is sequence of points in 2D (polyline) and width. Width is the distance between segments from original polyline and the created one (it can vary locally on "turns", i.e. vertices).

Conditions -- this algorithm should not create arcs on vertices, it should also not create new vertices. It can only reduce number of vertices.

Example:

    --
   /  \
  /    \
 A      B

Consider creating "outer" polyline from A to B, we had 3 vertices and we will have 3 vertices:

    ---
   /   \
  /     \
 /       \
A         B

But when creating "inner" polyline it could happen that number of vertices is reduced:

    /\
   /  \
  A    B

Of course you can think of several special conditions (like, does original polyline cross itself or not -- in my case not) but any helpful direction, idea, tip, name of the algorithm, or entire algorithm is welcome and I am grateful in advance.

greenoldman
  • 16,895
  • 26
  • 119
  • 185

1 Answers1

3

The basic solution is to construct the bissectors at every vertex (in the direction of the sum of the unit normal vectors), and to locate the point at the desired location along it (the distance to the vertex is the desired offset over the sine of the half-angle).

You will obtain a polyline parallel to the original one. There is a technical difficulty, unfortunately, as the polyline can be self-crossing inside sharp turns. This is a global problem (requires to know the whole configuration to be solved - in an extreme case the whole offset polyline could be in a self-crossing configuration, and invisible), not so easy to handle.

If you just need to render the thick line, a quick & dirty way is to ignore the self-crossings and use a polygon filling algorithm that supports the "non-zero" winding number rule.