# Selecting the nearest grid vertices with Delaunay triangulation

Hi all,

I’m displaying random points on a 2D canvas and would like (for each one of them) to get the coordinates of the nearest grid vertices.

To find the nearest vertices I’m using Delaunay triangulation.

• I put all the points (grid vertices + random points) in an array list (`allpList`) and use the Triangulate library to operate the triangulation. I end-up with a new array list (`triangles`) containing all the triangles and their vertices.

• Then, I look for the triangles with at least one vertex placed at the random point locations.

The problem occurs when I try to sort-out the nearest grid points.

• Out of the 3 vertices of each selected triangle, I keep the 2 that are not placed at the location of the random point (in red)

However, for some reason, that sorting part doesn’t work well and my final array list (`nearestpList`) is still filled with (some, not all) random points

``````for t in triangles: #list of triangles
for i, p in enumerate(rdmpList): #list of random points

#if the triangle 1st vertex == a random point location, then select 2nd and 3rd vertex
if t.p1 == p:
nearestpList.append(PVector(t.p2.x, t.p2.y))
nearestpList.append(PVector(t.p3.x, t.p3.y))

#if the triangle 2nd vertex == a random point location, then select 1st and 3rd vertex
if t.p2 == p:
nearestpList.append(PVector(t.p1.x, t.p1.y))
nearestpList.append(PVector(t.p3.x, t.p3.y))

#if the triangle 3rd vertex == a random point location, then select 1st and 2nd vertex
if t.p3 == p:
nearestpList.append(PVector(t.p1.x, t.p1.y))
nearestpList.append(PVector(t.p2.x, t.p2.y))
``````

I suspect the logic of that final sorting step to be flawed (some triangles may have 2 vertices corresponding to random points location, not only one like I stated) but cannot figure out how to fix it.

code (in Python)

Summary
``````
from java.util import ArrayList

allpList, rdmpList, nearestpList = ArrayList(), [], []
step, edge = 20, 60

def setup():
size(1000, 1000, P2D)
background(255)
smooth(8)

#Adding grid points (vertices) to array list
for y in range(edge, width, step):
for x in range(edge, height, step):

#Adding random points to array list
#Also adding them to a seperate list (rdmpList)
for e in range(256):
p = PVector(random(edge, width-edge), random(edge, height-edge))
rdmpList.append(p)

#Triangulating all the points in the array list
triangles = Triangulate.triangulate(allpList)

#Sorting-out nearest grid vertices
for t in triangles:
for i, p in enumerate(rdmpList):
if t.p1 == p:
nearestpList.append(PVector(t.p2.x, t.p2.y))
nearestpList.append(PVector(t.p3.x, t.p3.y))
if t.p2 == p:
nearestpList.append(PVector(t.p1.x, t.p1.y))
nearestpList.append(PVector(t.p3.x, t.p3.y))
if t.p3 == p:
nearestpList.append(PVector(t.p1.x, t.p1.y))
nearestpList.append(PVector(t.p2.x, t.p2.y))

strokeWeight(5)
for p in nearestpList: point(p.x, p.y)
``````
2 Likes

Is there are specific reason you are using this method (Delaunay) to achieve this goal?

I may be misunderstanding what you are trying to do, but if you want the four closest grid points to a point, that is a grid-aligned unit square, and you can find it with `%`. Once you have the nearest upper-left point you know what the other three are.

``````float unit = 20;

void setup() {
size(400, 400);
ellipseMode(CENTER);
noStroke();
}
void draw() {
background(255);
fill(204);
// draw grid
for (int j=0; j<=height; j+=unit) {
for (int i=0; i<=width; i+=unit) {
ellipse(i, j, 3, 3);
}
}
fill(255,92,92);
// draw point
ellipse(mouseX, mouseY, 5, 5);
// draw nearest grid points
PVector[] pts = boundpoints(mouseX, mouseY, unit);
for(PVector vec : pts){
ellipse(vec.x, vec.y, 5, 5);
}
}

PVector[] boundpoints(float x, float y, float unit){
// find the upper left point by rounding down to the nearest grid unit
PVector ul = new PVector(x - x%unit, y - y%unit);
// find the other three points by adding units
return new PVector[]{ul, ur, ll, lr};
}
``````

Edit: note this simple code assumes that 1) the grid has equal x and y units, and 2) the grid is centered on (0,0). If that isn’t the case, you need more parameters than `unit`, but the approach is the same.**

2 Likes

Very clever tip @jeremydouglass !

This is exactly what I was looking for. Elegant solution that makes me save at least 20 lines of unecessary code.

The red points are specific sound frequencies that I display randomly on a 2D grid. The script you provided makes possible to locate the four closest grid points (in pink) that I want to displace along the Z-axis (here the height is the amplitude of the selected frequency).

The goal was to instantly build a 3D terrain from a sound file at a specific moment of a song. Thing that is usually not possible with a standard spectrogram/sonogram.

Thank you !

3 Likes

So glad it was useful – and that is beautiful looking work, best of luck with it.

1 Like