# Selecting the nearest grid vertices with Delaunay triangulation

**URL:** <https://discourse.processing.org/t/selecting-the-nearest-grid-vertices-with-delaunay-triangulation/3370>\
**Category:** Processing.py\
**Created:** [September 8, 2018, 3:41pm UTC](https://discourse.processing.org/t/selecting-the-nearest-grid-vertices-with-delaunay-triangulation/3370 "2018-09-08T15:41:21Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [September 8, 2018, 3:41pm UTC](https://discourse.processing.org/t/selecting-the-nearest-grid-vertices-with-delaunay-triangulation/3370/1 "2018-09-08T15:41:21Z")

</div>

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.

 ![](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/4/40dd16c0868bacb395fb586c0ee428bd98b3536b.png)

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](http://n.clavaud.free.fr/processing/triangulate/triangulate-20100628.zip) 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.

 ![](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/b/beda352a1bb5821ce14363ffc742a701c57ccb28.png)

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

 ![](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/0/056d30eae30959428658bcef0e06b03a55209db0.png)

```auto
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**
>
> ```auto
> 
> 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)
> 
> ```

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [September 9, 2018, 10:11pm UTC](https://discourse.processing.org/t/selecting-the-nearest-grid-vertices-with-delaunay-triangulation/3370/2 "2018-09-09T22:11:49Z")

</div>

> [@solub](#):
>
> 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.**

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.

```auto
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.\*\*

---

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [September 11, 2018, 12:00am UTC](https://discourse.processing.org/t/selecting-the-nearest-grid-vertices-with-delaunay-triangulation/3370/3 "2018-09-11T00:00:39Z")

</div>

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](https://streamable.com/czmza) from a sound file at a specific moment of a song. Thing that is usually not possible with a standard spectrogram/sonogram.

 ![](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/61690a3702a78d3a63b168b6d3601436843e1331.jpeg)

Thank you !

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [September 11, 2018, 4:14am UTC](https://discourse.processing.org/t/selecting-the-nearest-grid-vertices-with-delaunay-triangulation/3370/4 "2018-09-11T04:14:30Z")

</div>

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