Ncollide::transformation::triangulate behavior?


#1

I think the docs for this functions could be a bit more clear - it says it’s going to triangulate a set of points, but what exactly does that mean? I had assumed that it would create a filled polygon given a set of points representing that polygon’s boundary, but it seems more like it is creating triangles that connect all points.

I’m happy to submit a PR to update the docs once I understand what it’s supposed to be doing.


#2

The result of this triangulation will be a planar triangulation, i.e., each point will be a vertex of some triangles (and only triangles). So, as you pointed out, this just connects a set of points without considering any topological constraint (i.e. without assuming they represent the boundary of a polygon. Such a triangulation would be called a constrained triangulation because we would see the polygon edges as constraints between points).

The implemented algorithm is incremental, i.e., each point provided is added one-by-one to an existing triangulation and it is ensured that this point does not lie on any other existing triangle’s circumcircle. But this circumcircle property is valid only when the point is added, so it might be violated later when other points are added. In other words, the result will be a topologically well-formed triangulation (and with triangles that should not be too disproportionate), but it won’t be a Delaunay triangulation unfortunately (which I would like to add in the future).


#3

Ok! Got it. That’s a great explanation. I’d suggest adding some of it to the docs for the function so future users can figure it out a bit easier than I did :slight_smile: