Finding the closest neighbour between PVector objects in an array

Processing Coding Questions
1

Hi ive created an array which holds PVectors of points on a sketch, when mouse is pressed a point is created at mouseX and mouseY. im trying to connect each point to its closest neigbour in order to make a planar graph with one face. which should look something like

image
image.png967×824 92.3 KB

ive managed to store each of the locations of the cordinates of the points but im stuck and i cant seem to link them to their closest neighbor.


PVector[] position = new PVector[100];
int pointNum;

void setup() {
  size(600, 600);
  background(255);
  for (int x = 0; x < position.length; x++) {
    position[x] = new PVector(0, 0);
  }
}

void draw() {
  fill(255);
  fill(0);

}


void mousePressed() {
  {
    pointNum++;
    position[pointNum]= new PVector(mouseX, mouseY);
    circle(position[pointNum].x, position[pointNum].y, 20);
    if (pointNum > 1) {
      line(position[pointNum].x, position[pointNum].y, position[pointNum-1].x, position[pointNum-1].y);
    }
  }
}
2

Remark: no use to draw circle in mousePressed when you use background

Instead for loop over all points in draw and use circle there

(Say background at start of draw because you want lines to disappear when they are obsolete)

For the lines:

essentially you want to have a for loop i=0;i< position.length-1; i++) { that calls a for loop with j = i+1; j…

Thus you compare each distance to each other distance (but only once for each pair)

Say float currentDist = dist(position[i].x,
position[i].y,
position[j].x, position[j].y);

if(currentDist<minDist){
minDist=currentDist;
min_i=i;
min_j=j;

line (position[i].x,
position[i].y,
position[j].x, position[j].y) ;

}

That’s all inside the nested for loops

Improvement

It can be improved by storing the lines in two new PVector arrays from and to, so you only have to check distance for the new position

then for loop lineIndex over from and say

line(from[lineIndex].x,
from[lineIndex].y,
to[lineIndex].x,
to[lineIndex].y);

Chrisir

3

Unfortunately this statement does not match the diagram if we take

connect each point to its closest neigbour

We get the following graph
polygon1

make a planar graph with one face

This is ambiguous because a planar graph would allow for lines to intersect but the ‘one face’ and the diagram suggests that what you want is a polygon i.e. a closed shape without intersecting lines.

A problem must be clearly defined if we are to devise a good algorithm to solve it :smile:

Please restate the problem more clearly.

2 Likes
4

Might just be missing something but why don’t you just loop round the array, and connect, the last item to the first item? Problem solved no?

Also I can see a possible problem in your approach, your seeking the closest neighbour, which is fine, but from your first diagram you can see that the first and lat point counting clockwise from top left are not closest neighbours.