I need to find "near" neighbors among a set of points.
There are 10 points in the above image. Red lines are edges from the Delaunay Triangulation, black stars mark the mid-lines of the edges, blue lines are the Voronoi tesselation. Point 1 has three "near" neighbors, i.e. 4, 6, and 7, but not 2 and 3, who are almost in line with the edge 1-7, but much further away.
What is a good way to identify the near neighbors (or "good" edges)? Looking at the figure, it seems to me that either selecting edges whose mid-point falls onto the intersection with the Voronoi lines, or considering as "near" neighbors those with touching Voronoi cells could be a good solution (the classification of 3-5 can go either way). Is there an efficient way of implementing either of the solutions in Matlab (I'd be happy to get a good general algorithm that I can then translate to Matlab, btw)?
You can implement your first idea of selecting edges whose mid-points fall on the intersection with the Voronoi lines by making use of the
DelaunayTri
class and itsedges
andnearestNeighbor
methods. Here's an example with 10 random pairs ofx
andy
values:And now
edgeIndex
is an N-by-2 matrix where each row contains the indices intox
andy
for one edge that defines a "near" connection. The following plot illustrates the Delaunay triangulation (red lines), Voronoi diagram (blue lines), midpoints of the triangulation edges (black asterisks), and the "good" edges that remain inedgeIndex
(thick red lines):How it works...
The Voronoi diagram is comprised of a series of Voronoi polygons, or cells. In the above image, each cell represents the region around a given triangulation vertex which encloses all the points in space that are closer to that vertex than any other vertex. As a result of this, when you have 2 vertices that aren't close to any other vertices (like vertices 6 and 8 in your image) then the midpoint of the line joining those vertices falls on the separating line between the Voronoi cells for the vertices.
However, when there is a third vertex that is close to the line joining 2 given vertices then the Voronoi cell for the third vertex may extend between the 2 given vertices, crossing the line joining them and enclosing that lines midpoint. This third vertex can therefore be considered a "nearer" neighbor to the 2 given vertices than the 2 vertices are to each other. In your image, the Voronoi cell for vertex 7 extends into the region between vertices 1 and 2 (and 1 and 3), so vertex 7 is considered a nearer neighbor to vertex 1 than vertex 2 (or 3) is.
In some cases, this algorithm may not consider two vertices as "near" neighbors even though their Voronoi cells touch. Vertices 3 and 5 in your image are an example of this, where vertex 2 is considered a nearer neighbor to vertices 3 or 5 than vertices 3 or 5 are to each other.