1
$\begingroup$

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: enter image description here

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:

enter image description here

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
$\endgroup$
8
  • 3
    $\begingroup$ It is not clear how the outline should look like. Please be specific. (One method is to build the outline, then triangulate it.) $\endgroup$
    – user16034
    Dec 12, 2022 at 11:18
  • $\begingroup$ Thank for the comment. I added an image with input and output, I hope that helps to clarify the issue. I'm currently looking at constrained Delaunay triangulation $\endgroup$
    – anhoppe
    Dec 12, 2022 at 12:33
  • $\begingroup$ That does not address my question. I said outline. $\endgroup$
    – user16034
    Dec 12, 2022 at 12:44
  • 1
    $\begingroup$ Also, why have you rejected the approach Yves Daoust suggests of building the outline, then triangulating it? What does "suffer from self-intersections" mean and why is that a problem? What does "robust" mean in this context? What approaches have you already considered and why have you rejected them? Are you asking how to build the outline? $\endgroup$
    – D.W.
    Dec 12, 2022 at 18:04
  • $\begingroup$ The outline the result of translating the points of the inner polygon {P1, ... Pn} to the outside. This is where the self-intersection is coming in, since it is has the same problem as a polygon offset. So the outline points are not really reliable. Using these outline points leads to a triangulation with self-intersections $\endgroup$
    – anhoppe
    Dec 13, 2022 at 7:11

1 Answer 1

1
$\begingroup$

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$:

Inflated-polyline

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:

Skipped-segment

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much, your answer is indeed helpful. I will consider such an 'heuristic' approach and drop the idea of using CDT. As far as I understand it it is not the right use case for CDT anyways. $\endgroup$
    – anhoppe
    Jan 2, 2023 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.