closest pair algorithm

This is a discussion on closest pair algorithm within the C Programming forums, part of the General Programming Boards category; Hello Forum I'm trying to implement the closest pair algorithm but when i run it i get wrong pairs anyone ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    9

    closest pair algorithm

    Hello Forum
    I'm trying to implement the closest pair algorithm but when i run it i get wrong pairs
    anyone help ?
    here is the code in c

    Code:
    #include <stdio.h>
    #include <math.h>
    
    
    double getDistance (double x1,double y1, double x2, double y2)
    {
    	return (sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)));
    }
    
    int main(){
        int i,j=0;
        const int NUMBER_OF_POINTS = 3;
        double points[NUMBER_OF_POINTS][2];
        printf ("Enter %d points: " , NUMBER_OF_POINTS );
    	   for(i=0; i< NUMBER_OF_POINTS;i++)
    	   scanf ("%lf", &points[i][0]);
        scanf ("%lf", &points[i][1]);
    
    
        int p1=0,p2=1;
        double shortestDistance = getDistance( points[p1][0], points[p1][1], points[p2][0], points[p2][1]);
        for ( i=0;i<NUMBER_OF_POINTS;i++){
    		for ( j=i+1;j<NUMBER_OF_POINTS;j++){
    			double distance=getDistance(points[i][0],points[i][1],points[j][0],points[j][1]);
    
    			if(shortestDistance > distance){
    				p1=i;
    				p2=j;
    				shortestDistance = distance;
    			}
    		}
    	}
    
        printf ("The closest two points are (%lf", points[p1][0]);
        printf (", %lf", points[p1][1]);
        printf (") and ("); 
        printf ("%lf", points[p2][0]);
        printf (",%lf\n" ,points[p2][1]);
    
        system("pause");
        return 0;
    }
    Last edited by modulo_crt; 10-19-2010 at 12:22 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I used that formula recently and found that I needed to be sure I was dealing with positive distances, only.

    So I used abs() around anything that gave me negative values.

    Just a quick study, but I didn't see anything wrong with what's there.
    Last edited by Adak; 10-19-2010 at 11:19 AM.

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    9
    let me give a quick example
    when i input the points (1,1) , (4,2) , (5,3)
    the output should be the point (4,2) , (5,3) as they are closer
    but the output i take is
    (1,0) , (1,0)

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Well point 1,0 is VERY CLOSE to point 1,0, for sure.

    Let me put it into the oven, see what cooks up.

    I had to change a few things (working in Turbo C right now), but this works fine:
    Code:
    #include <stdio.h>
    #include <math.h>
    #define NUMBER_OF_POINTS 3
    
    double getDistance (double x1,double y1, double x2, double y2)
    {
    	return (sqrt((x2-x1)* (x2-x1) + (y2-y1) *(y2-y1)));
    }
    
    int main(){
      int i,j=0, p1=0,p2=1;   
        //	const int NUMBER_OF_POINTS = 3;
    	double points[NUMBER_OF_POINTS][2]={ {1,0}, {4,3}, {5,2} };
    //    printf ("Enter %d points: " , NUMBER_OF_POINTS );
    //	for(i=0; i< NUMBER_OF_POINTS;i++)
    //	scanf ("%lf", &points[i][0]);
    //    scanf ("%lf", &points[i][1]);
    
    	double shortestDistance = getDistance( points[p1][0], points[p1][1], points[p2][0], points[p2][1]);
    	for ( i=0;i<NUMBER_OF_POINTS;i++){
    		for ( j=i+1;j<NUMBER_OF_POINTS;j++){
    			double distance=getDistance(points[i][0],points[i][1],points[j][0],points[j][1]);
    
    			if(shortestDistance > distance){
    				p1=i;
    				p2=j;
    				shortestDistance = distance;
    			}
    		}
    	}
    
    	printf ("The closest two points are (%lf", points[p1][0]); 
      printf (", %lf", points[p1][1]);
      printf (") and ("); 
    	printf ("%lf", points[p2][0]);       
      printf (",%lf)\n" ,points[p2][1]);
    
    	//system("pause");
      (void) getchar();
    	return 0;
    }
    Last edited by Adak; 10-19-2010 at 12:44 PM.

  5. #5
    Registered User
    Join Date
    May 2009
    Posts
    2,569
    Suggestion 1: Format your code so it is readable.
    Suggestion 2: After reading in the point values; display then all to confirm you read them in right.
    Suggestion 3: Always use braces ("{", "}") around loops.

    Tim S.
    Last edited by stahta01; 10-19-2010 at 12:15 PM. Reason: Grammer

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    As a way to debug, Tim's point can't be stressed enough. Test each block of code for accuracy in what you need it to do.

    You can work for hours looking for a bug in your processing, only to find out it's been a bug in your earlier input function, the whole time! That's a real 4 letter word, moment!

    btw, I tried 1,1 also, and it worked fine with it. Using abs() did not help or hinder here - both worked.

  7. #7
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    @Adak:
    abs(x)*abs(x) == x*x

    for anything but imaginary x.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Thanks, EVOEx. Obvious once you think for a sec. /facepalm
    Last edited by Adak; 10-19-2010 at 12:45 PM.

  9. #9
    Registered User
    Join Date
    Jun 2009
    Posts
    9
    thanx adak
    but it seems to have problems in case you want to input the cordinates of the points

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Bingo! Nice catch. you need to add braces around the two scanf() lines of code - right now only the first one gets executed in each loop.

    I'll bet that's what Tim was suggesting, don't you think so?

    (I took it as a general suggestion, as well.)

  11. #11
    Registered User
    Join Date
    Jun 2009
    Posts
    9
    yesssss it seems to work just fine
    thanx again

  12. #12
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Thank You Tim S!



    You Rascal!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Polynomials and ADT's
    By Emeighty in forum C++ Programming
    Replies: 20
    Last Post: 08-19-2008, 08:32 AM
  2. search algorithm
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 09-17-2007, 02:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21