Triangulation fails if there are almost colinear points in input

[ubruhin]

This test:

TEST_CASE( "Delaunay triangulation should be able to handle 3 almost colinear points", "[DelaunayTest]" ) {
	std::vector<Vector2<double>> points;
	points.push_back(Vector2<double>{0.0, 0.0});
	points.push_back(Vector2<double>{1000.0, 0.0});
	points.push_back(Vector2<double>{2000.0, 40.0});
	Delaunay<double> triangulation;
	const std::vector<Triangle<double>> triangles = triangulation.triangulate(points);
	REQUIRE(1 == triangles.size());
}

Fails because no triangle is found. Note that this is just one example - it's very easy to interactively generate arbitrary input data which doesn't get triangulated properly. It also happens with more than three points, then some triangles are generated, but some of the points are left unconnected.

Although three colinear points are not a valid triangle, I still see two critical issues:

1. Compared to floating point accuracy, these points are not really almost a triangle. It's even obvious for a human eye that this is a totally valid triangle:
2. The library does not report any failure if it did not connect some of the input points. Depending on the use case, it is extremely important to know if the triangulation failed (e.g. to use an alternative fallback algorithm to still handle all points somehow). But the library silently ignores some of the input points so the user is not able to detect and handle this situation properly.

[bl4ckb0ne]

I tested against pyDelaunay2D, delaunay-cpp and scipy.spatial.Delaunay.

The first two are implementations of Bowyer-Watson, just like my code, and the last one is based on Qhull. The first two fail to triangulate the three points you gave me, but the last one succeeded.

For me it seems that this case is not made for the Bowyer-Watson algorithm. I invite you to try with other implementations of the Delaunay triangulation (as my time is limited these days), and see if you can find a Bowyer-Watson implementation that succeeds.

If Bowyer-Watson is indeed the problem, we'll have to find a solution.