We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpPrograms › seeking fastest method to find the closest vector
Page Index Toggle Pages: 1
seeking fastest method to find the closest vector (Read 925 times)
seeking fastest method to find the closest vector
May 16th, 2009, 12:32pm
 
I have an algorithm which has a part where I need to find the closest vector from a list to another given vector. Does anyone know of any examples or patterns that do this? I guess I am basically looking to sort the list by distances and choose the first one - but I'm not sure how to do this....

thanks for the help in advance
Re: seeking fastest method to find the closest vector
Reply #1 - May 16th, 2009, 1:57pm
 
how do you make an array of floats (the distances between each vector) that keeps the index value of each float paired with it?
Re: seeking fastest method to find the closest vector
Reply #2 - May 16th, 2009, 2:07pm
 
You should make a class implementing the Comparable interface (or using a Comparator -- search the forum). Allows to sort without pain while keeping necessary relationships.
Re: seeking fastest method to find the closest vector
Reply #3 - May 16th, 2009, 2:30pm
 
yeah, i was even involved in one that you helped out with.

still, I am a little lost. I get the sense that comparator wants objects as its arguments but mine, in this case would be simple floats, not associated with objects. Do you know of any examples that would do this?

My scenario is this I have a vector v1 and I want to get the distances between v1 and v[] (an array of vectors). When I sort them to get the closest, I need to know which of the vectors - its indices - it was from the original list...
Re: seeking fastest method to find the closest vector
Reply #4 - May 17th, 2009, 1:38am
 
oompa_l wrote on May 16th, 2009, 2:30pm:
I get the sense that comparator wants objects as its arguments but mine, in this case would be simple floats, not associated with objects.

The idea was to encapsulate floats in objects. Even a simple vector is an object.
Re: seeking fastest method to find the closest vector
Reply #5 - May 17th, 2009, 2:09pm
 
any tips on optimizing the pattern - maybe I am creating objects where I don't need them...

for(int i = 0; i<hairs.length; i++){
 
 for(int j=0; j<hairs[i].cPts.length; j++){
   PVector ptA = new PVector(hairs[i].cPts[j].position.x, hairs[i].cPts[j].position.y, hairs[i].cPts[j].position.z);

   PVector[] closestPts = new PVector[0];
   
    for(int k = 0; k<hairs.length; k++){
     
      if(k!=i){
          for(int l=0; l<hairs[k].cPts.length; l++){
       PVector ptB = new PVector(hairs[k].cPts[l].position.x, hairs[k].cPts[l].position.y, hairs[k].cPts[l].position.z);
       
        PVector ptDifference = PVector.sub(ptA, ptB);
        if(i ==0 && j == 0 && k == 1){
        println(ptDifference.mag());
      }
        closestPts = (PVector[]) append(closestPts, ptDifference);
      }
       if(i ==0 && j == 0 && k == 1){
        println(closestPts);
      }
      Arrays.sort(closestPts, new AComparator());
      if(i ==0 && j == 0 && k == 1){
        println(closestPts);
      }
    }
 }
}
}
}

class AComparator implements Comparator {
int compare(Object o1, Object o2) {
  Float d1 = new Float(((PVector) o1).mag());
   Float d2 = new Float(((PVector) o2).mag());
   return d1.compareTo(d2);
//      return (d1<d2) ? -1 : (d1==d2) ? 0 : 1;
}
}
Re: seeking fastest method to find the closest vector
Reply #6 - May 17th, 2009, 2:14pm
 
Indeed, I think this is enough:
Code:
class AComparator implements Comparator {
int compare(Object o1, Object o2) {
float d1 = ((PVector) o1).mag();
float d2 = ((PVector) o2).mag();
return (d1<d2) ? -1 : (d1==d2) ? 0 : 1;
}
}
Page Index Toggle Pages: 1