# 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