The ComputationalGeometry
package has a DelaunayTriangulation[]
function. It returns a list of points connected to each point, ordered counterclockwise.
Example:
showTriangulation[tri_, opt : OptionsPattern[]] :=
Graphics[GraphicsComplex[points, Line /@ Thread /@ tri], opt]
points = Tuples[Range[0, 5, 1], 2];
tri = DelaunayTriangulation[points];
showTriangulation[tri]
Question: How can I obtain a list of all triangles instead?
My first naive first try doesn't work correctly:
makeTriangles[points_] :=
Flatten[Function[{p, list},
Prepend[#, p] & /@ Partition[list, 2, 1, {1, 1}]] @@@
DelaunayTriangulation[points], 1] (* doesn't work *)
GraphicsComplex[points, Line@makeTriangles[points]] // Graphics
Why does it give an incorrect result?
This function simply takes all points $\{A, B, C, D, \ldots\}$ connected to a point $P$, and constructs the triangles $PAB, PBC, PCD, \ldots$. Since $A,B,C,...$ are in counterclockwise order, I assumed all these would be valid triangles. But take the following case:
$PAB$ will not be a valid triangle, even though $ABC$ are in counterclockwise order.