Inflate a polyline so that the 2D band can be triangulated without self-intersections

Question

Introduction

I have simple polylines as sequences of points. I need a triangulation with a configurable width. The goal is to get a 2D 'band' from the input polyline without self-intersections.

Description:

Input is a 2D point sequence {P1, ..., Pn} (Polyline) and a target width of the triangulated band. Output is the triangulation without self intersection:

In the current implementation I move the segments formed by {P1, .., Pn} in both perpendicular directions. The outline points to be triangulated are calculated by intersection of the translated segments (red dots in the image above).

The problem with this approach is that in sharp angles the resulting intersection points generate self-intersecting triangles:

Question

Is there a robust algorithm to triangulate a band from a polyline without generating self-intersections?

References:

• this approach seems to be similar but also does not solve the self intersection problem
• Clipper2 has an InflatePath method that does the offset but I don't know how to triangulate the resulting path
• An approach would be to just triangulate the outline points with Delaunay but I don't know how to restrict the result to triangles inside the 'Band'
• A very nice explanation of Constrained Delaunay Triangulation

Answer 1

I think your "inflated polyline" can be correctly defined as a union of "inflated line segments". Each such "inflated line segment" will be a rectangle with half-disks on its two opposite ends, describing all points $p \in \Bbb R^2$, such that their distance from the segment is not more than a (configurable) constant $W$:

However you'll get an area with circular arcs on its boundary, so it'll be not easy to triangulate it. Probably you don't need all this heavy artillery, like the Delaunay triangulation - a couple of simple heuristics will do the job for you.

For example, to solve the problem with intersecting triangles in case of sharp turns you need to consider not only pairs of adjacent segments - you need to analyze longer chains of segments and skip segments, which don't contribute to the boundary. Please see below - the segment $s2$ doesn't contribute to the boundary, because it's located too deep inside the "inflated polyline". The point, marked by red color, belongs to the boundary of the union of two "inflated line segments" $s1$ and $s3$, so this point should be the triangulation vertex:

Please note, that this segment $s2$ can't be ignored on the other side of the polyline. These ignored segments can appear in groups, and be on both sides of the polyline. As a result, this triangulation won't be so simple and regular compared to your one.