Member Avatar for AndrewYY

I've got a large array of coordinates (a struct containing x and y, among other things) and for each pair of coordinates, I'm trying to find another pair that's closest to it from that array.

int i, j, d = 0, cd = 0, closest;
for(i=0;i<size;i++){
  closest = 0;
  for(j=0;j<size;j++){
    if (i != j){
      //find distance bewteen i and j
      cd = sqrt(pow(coords[i].x-coords[j].x,2)+pow(coords[i].y-coords[j].y,2))
      if(cd < d){
        d = cd;
        closest = j;
      }
    }
  }
  //do stuff with the 'closest' variable
}

The problem is, this code runs really slowly, as it has to execute size^2 times, and I'm constantly running this code because the x and y coordinates are always changing.

Is there a faster way to do what I'm trying to do? I know that I could potentially cut calculation time by 2, because if a is closest to b, then b is closest to a, but beyond that, I can't think of any optimizations.

Edited by AndrewYY because: n/a
  • 2 Contributors
  • 1 Reply
  • 110 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by mrnutty
Member Avatar for mrnutty

don't use the sqrt function. compare the squared distance.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.