Near-degenerate edge causes infinite loop

[gkjohnson]

Hello! Thanks again for this project. I've been using it to triangulate a resulting polygon generated by intersections from polygon intersections (for the three-bvh-csg project) and I'm seeing that the project can fall into a infinite loop in cases possibly when a very short constrained edge is in the graph. It should be good to know, if possible, what the tolerances should be used for the project and throw an error if an infinite loop is reached.

Here's a simplified example case derived from the data:

import Delaunator from 'delaunator';
import Constrainautor from '@kninnug/constrainautor';

const coords = [
  0,0,
  0.05626429153399996,0,
  0.024093852080076722,4.80267923973791e-18,
  0.01379050745122589,0.1463775332929564,
  0.05177587092034522,0.015468457826306506,
  0.024093852080076705,-5.204170427930421e-18
];
const indices = [
  [0,5],
  [5,2]
];

const del = new Delaunator( coords );
const cons = new Constrainautor( del, indices );
// infinite loop

[kninnug]

Hi! I'm glad you like the project! (Less so that it's causing you this issue ;)

With the given coordinates I can indeed reproduce the issue, and it appears to go away when the values are scaled up. In principle there are not supposed to be limitations on the scale of the coordinates, as both this project and Delaunator use robust predicates for the geometrical tests. But maybe there are limits to that.

In any case, I'll try to at least turn the infinite loop into a thrown error, however, this may take a while due to external circumstances

[gkjohnson]

Thanks I appreciate the response. For some more context I've been using the cdt2d project for now, which seems to be robust to some of these cases but it seems to be no longer maintained and is fairly slow in some cases (though I understand that may just be the nature of the algorithm). I'm not sure if you've done any benchmarks compared to that project? I'd be happy to move over to this project if it looks like some of these issues can be ironed out.

[kninnug]

I managed to find the cause of the infinite loop: apparently, when two or more points are very close to each other, Delaunator only triangulates one of them. Un-triangulated points have no existing edges, and Constrainautor cannot constrain an edge if one or both end-points have no incoming/outgoing half-edges.

From version 4.1.0, this scenario is now detected, and an error is thrown when trying to constrain between points that are not triangulated. Additionally there is a method, untriangulatedPoints that can be called after constructing, but before constraining, that will return a list of ids of points that were not triangulated by Delaunator. You could use this to maybe re-map those to a nearby point that is present in the triangulation, or filter out those edges entirely, depending on your use-case.

Regarding performance, the repository also contains a simple benchmarking script (npm run bench) that compares this library with cdt2d. That project is slower in almost all cases, but is indeed much more robust