does not produce convex hull

[qqwa]

The Delaunay triangulation should produce a triangulation with a convex hull.

To fix it you would need to check if some of the triangles that have a point of the supertriangle need to have an edge flipped, before removing them from the triangulation.

Don't know if it matters to you, but just leaving it here in case someone wants to use this implementation and needs a convex hull.

[moritzbeck]

I guess it should matter for users of this crate as this means the function doesn't compute a (complete) Delaunay triangulation.

I stumbled across a set of 3 points for which triangulate returns an empty Vec:

use rtriangulate::{TriangulationPoint, triangulate};
fn main() {
	let points = [
		TriangulationPoint::new( 4., 11.),
		TriangulationPoint::new( 6., 10.),
		TriangulationPoint::new(10.,  8.)
	];
	// Do the triangulation.
	let triangles = triangulate(&points).unwrap();

	println!("{:?}", triangles); // Empty :-(
}

[tynril]

@moritzbeck: These three points are collinear, so they can't form a triangle. What would be your expected output there?

[moritzbeck]

D'oh, you're right. I should have checked that. (These points have "minimized" coordinates.)

My use case is the following: I want to compute the Euclidean minimum spanning tree of a set of points. For this I compute a Delaunay triangulation, create a graph out of it (I am really only interested in the edges of the triangulation, not the triangles themselves.) and then compute the minimum spanning tree on that graph.

So for my use case I'd like the output to contain the degenerated triangle with those three vertices.

Having said that, the triangulation remains empty if I change the first point from (4, 11) to (4, 12) or even (4, 12.9). With (4, 13) it does produce a triangle, so there might be a problem with float stability.