closest pair algorithm

[modulo_crt]

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

#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;
}

[Adak]

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.

[modulo_crt]

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)

[Adak]

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:

#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;
}

[stahta01]

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.

[Adak]

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.

[EVOEx]

@Adak:
abs(x)*abs(x) == x*x

for anything but imaginary x.

[Adak]

Thanks, EVOEx. Obvious once you think for a sec. /facepalm

[modulo_crt]

thanx adak
but it seems to have problems in case you want to input the cordinates of the points

[Adak]

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.)

[modulo_crt]

yesssss it seems to work just fine
thanx again

[Adak]

Thank You Tim S!

You Rascal!