I cannot find a way to connect all points of a grid to form triangles, without any crossing

In order to solve this I’ve tried many things but they all ended up failing because I couldn’t come up with ways to not have past points used or lines crossing… So I don’t have any code to show appart from the list of points used.

points = [
    (5, 6, 'A'),
    (5, -8, 'B'),
    (-2, 2, 'C'),
    (-10, 4, 'D'),
    (8, 1, 'E'),
    (-8, 8, 'F'),
    (2, 7, 'G')
]

I would want a list containing the points of all triangles possible, like this:

triangles = [[A, B, C], [B, C, D], ...]

I only want a suggestion on how to achieve this
I hope this is clear enough to get an idea of what I’d like to achieve…

>Solution :

The simplest way to do this is to use scipy.spatial.Delaunay. The following example computes the Delaunay triangulation of four points (taken directly from linked page):

points = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1]])
from scipy.spatial import Delaunay
tri = Delaunay(points)

import matplotlib.pyplot as plt
plt.triplot(points[:,0], points[:,1], tri.simplices)
plt.plot(points[:,0], points[:,1], 'o')
plt.show()

I won’t pretend to understand what’s actually going on, but if you know more about np/scipy you should be able to get something useful out.