Selecting the nearest grid vertices with Delaunay triangulation

Processing.py
1

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.

oLeC22o.png605×653 113 KB

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.

zNtgLnt.png622×667 129 KB

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

l9FP4Zc.png1336×640 195 KB 

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.

Would really appreciate your help.

code (in Python)

Summary 

add_library('triangulate')
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):
            allpList.add(PVector(x, y))
         
            
    #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))
        allpList.add(p)
        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)
3 Likes
2

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
  PVector ur = ul.copy().add(unit, 0);
  PVector ll = ul.copy().add(0, unit);
  PVector lr = ul.copy().add(unit, unit);
  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
3

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.

LWEgZoz.jpg1488×888 116 KB

Thank you !

3 Likes
4

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

1 Like