How to find all neighbors of a given point in a delaunay triangulation using scipy.spatial.Delaunay?

Question

I have been searching for an answer to this question but cannot find anything useful.

I am working with the python scientific computing stack (scipy,numpy,matplotlib) and I have a set of 2 dimensional points, for which I compute the Delaunay traingulation (wiki) using scipy.spatial.Delaunay.

I need to write a function that, given any point a, will return all other points which are vertices of any simplex (i.e. triangle) that a is also a vertex of (the neighbors of a in the triangulation). However, the documentation for scipy.spatial.Delaunay (here) is pretty bad, and I can't for the life of me understand how the simplices are being specified or I would go about doing this. Even just an explanation of how the neighbors, vertices and vertex_to_simplex arrays in the Delaunay output are organized would be enough to get me going.

Much thanks for any help.

Answer 1

I figured it out on my own, so here's an explanation for anyone future person who is confused by this.

As an example, let's use the simple lattice of points that I was working with in my code, which I generate as follows

import numpy as np
import itertools as it
from matplotlib import pyplot as plt
import scipy as sp

inputs = list(it.product([0,1,2],[0,1,2]))
i = 0
lattice = range(0,len(inputs))
for pair in inputs:
    lattice[i] = mksite(pair[0], pair[1])
    i = i +1

Details here not really important, suffice to say it generates a regular triangular lattice in which the distance between a point and any of its six nearest neighbors is 1.

To plot it

plt.plot(*np.transpose(lattice), marker = 'o', ls = '')
axes().set_aspect('equal')

Now compute the triangulation:

dela = sp.spatial.Delaunay
triang = dela(lattice)

Let's look at what this gives us.

triang.points

output:

array([[ 0.        ,  0.        ],
       [ 0.5       ,  0.8660254 ],
       [ 1.        ,  1.73205081],
       [ 1.        ,  0.        ],
       [ 1.5       ,  0.8660254 ],
       [ 2.        ,  1.73205081],
       [ 2.        ,  0.        ],
       [ 2.5       ,  0.8660254 ],
       [ 3.        ,  1.73205081]])

simple, just an array of all nine points in the lattice illustrated above. How let's look at:

triang.vertices

output:

array([[4, 3, 6],
       [5, 4, 2],
       [1, 3, 0],
       [1, 4, 2],
       [1, 4, 3],
       [7, 4, 6],
       [7, 5, 8],
       [7, 5, 4]], dtype=int32)

In this array, each row represents one simplex (triangle) in the triangulation. The three entries in each row are the indices of the vertices of that simplex in the points array we just saw. So for example the first simplex in this array, [4, 3, 6] is composed of the points:

[ 1.5       ,  0.8660254 ]
[ 1.        ,  0.        ]
[ 2.        ,  0.        ]

Its easy to see this by drawing the lattice on a piece of paper, labeling each point according to its index, and then tracing through each row in triang.vertices.

This is all the information we need to write the function I specified in my question. It looks like:

def find_neighbors(pindex, triang):
    neighbors = list()
    for simplex in triang.vertices:
        if pindex in simplex:
            neighbors.extend([simplex[i] for i in range(len(simplex)) if simplex[i] != pindex])
            '''
            this is a one liner for if a simplex contains the point we`re interested in,
            extend the neighbors list by appending all the *other* point indices in the simplex
            '''
    #now we just have to strip out all the dulicate indices and return the neighbors list:
    return list(set(neighbors))

And that's it! I'm sure the function above could do with some optimization, its just what I came up with in a few minutes. If anyone has any suggestions, feel free to post them. Hopefully this helps somebody in the future who is as confused about this as I was.