title: Triangular mesh in python
body: <p>I have points in a plane. I want each point to be a vertex of at least one triangle. I also want to fill the plane confined within the vertices with no overlapping triangles. Something like:</p>
  
  <p><a href="https://i.stack.imgur.com/1LjyG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/1LjyG.png" alt="enter image description here"></a></p>
  
  <p>Note that for each pair of points in any triangle, the line connecting them consists of points that are also in some triangle.</p>
  
  <p>I want to get the list of all vertices triplets from which a triangle can be defined. In the picture, there would be 6 such triplets.</p>
  
  <p>My attempt is this one:</p>
  
  <pre><code>indices = range(locs.shape[0])
  visited = []
  ind_list = []
  for ind in indices:
      if ind not in visited:
          visited.append(ind)
          nearest_idx = np.argsort(distances[ind])[1:3]
          for ni in nearest_idx:
              visited.append(ni)
          ind_list.append([ind]+list(nearest_idx))
  </code></pre>
  
  <p>where <code>locs</code> is a Nx2 array containing the (x,y) coordinates of each vertex, <code>distances</code> is a NxN matrix whose i,j component is the euclidean distance between the i-th vertex and the j-th vertex. Note that <code>ind_list</code> is a list of indices that allow me to get the vertices by <code>locs[ind_list]</code>. What I want is the correct <code>ind_list</code>. In my case I clearly omit some of the triplets. An example of this failure can be seen in this figure:</p>
  
  <p><a href="https://i.stack.imgur.com/Zxko5.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Zxko5.png" alt="enter image description here"></a></p>
  
  <p>where there are blank regions. Instead I want all the space to be filled with no overlapping triangles. Any idea of how to achieve this? Thanks a lot!</p>