"EdgeEvent - null triangle" from valid but not-quite-collinear points

[roystgnr]

It took a while for me to hit this in a real use case, but once I did it was surprisingly easy to boil down:

#include <poly2tri.h>

#include <numeric> 

int main(void)
{
  const double eps = 1e-15; // This gives EdgeEvent - null triangle
  // const double eps = 0;  // This (or negative eps) succeeds

  std::vector<p2t::Point> outer_boundary
    {{0,0},{0.5,eps},{1,0},{1,1},{0,1}};

  std::vector<p2t::Point *> api_shim(outer_boundary.size());
  std::iota(api_shim.begin(), api_shim.end(), outer_boundary.data());

  p2t::CDT cdt(api_shim);

  cdt.Triangulate();

  return 0;
}

A stack trace shows us dying 3 levels of p2t::Sweep::EdgeEvent deep, lines 114,151,120. I'm afraid I don't really understand it, though. The EPSILON tolerance in Orient2D puts us in the o2 == COLLINEAR block, which should be true for all practical purposes and should be the same block we reach in the eps = 0 case, so why are we then failing for positive eps?

Hope you can help find a fix for this. My user code that first tripped the error does adaptive refinement of boundary edges, which combined with FP roundoff means it's going to be generating not-quite-collinear points all the time. I could try pushing those new boundary points outward a little bit so that they end up in the working convex-by-eps case rather than the failing concave-by-eps case, but that doesn't sound like a robust workaround.

[roystgnr]

I could try pushing those new boundary points outward a little bit so that they end up in the working convex-by-eps case

This works for a single cycle of boundary refinement, but I hit the same error after many cycles. In hindsight it's hard to come up with a value of X in "perturb outward by X" that doesn't make it possible for the addition of a new node to create a slight concavity at its neighbors, even if it's always itself a slight convexity.

the failing concave-by-eps case

Interestingly, poly2tri is okay with clear concavity. If I bump eps up to 1e-12 or so (I guess that's enough to get us out of the COLLINEAR detection?) we seem to be working fine.