Segmentation fault in determining closest pair

[noob15]

I'm trying to code the closest pair algorithm...but when the distribution of points is too close, it is giving segmentation fault. My algorithm is right as for points sparsely placed it is giving same answer with bruteforce...th e problem is most probably when the line dividing points into two halves contain more than one point(not sure though) whose probability inc. with more and more points in picture. Here's my code
http://pastebin.com/ZbDtC9dq

the segmentation fault is in line
double d1 = closestPair(ppx , ll, lenL);
//checked with debugger

here's quickSortCloses tPair.c
http://pastebin.com/jCYd8dr8

help !!

[Banfa]

If you want help with your code you are going to have to post your code.

[noob15]

here's the code

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<assert.h>
#include<string.h>


#define POINTS 1000 

struct point{
	double x;
	double y;
};

#include"quickSortClosestPair.c"

double gaussrand();
void generatePoints(struct point *pp[]);
double closestPair(struct point *ppx[], struct point *ppy[], int n);
double bruteForceClosest(struct point *ppx[], struct point *ppy[], int n );
double distance(struct point *p1, struct point *p2);
void print(struct point *pp[]);
int isLeft(struct point *p, struct point *bisect);


int main()
{
	//array of points whose min. closest pair we have to find
	struct point *pp1[POINTS];
	generatePoints(pp1);
	
	//copy of pp1
	struct point *pp2[POINTS];
	int i;
	for(i=0; i<POINTS; i++){
		pp2[i] = malloc(sizeof(struct point));
		assert(pp2[i] != NULL);
		pp2[i]->x = pp1[i]->x;
		pp2[i]->y = pp1[i]->y;
	}
//	print(pp1);
//	printf("hiiiii\n");
	QuickSort(pp1, 0, POINTS-1, 'x');
	QuickSort(pp2, 0, POINTS-1, 'y');
	print (pp1);
	//d gives the closest distance
	double d = closestPair(pp1, pp2, POINTS);

	printf("the distance between closest pair of point is %f\n", d);

	d = bruteForceClosest(pp1, pp2, POINTS);
	printf("the distance between closest pair of point by brute force is %f\n", d);
	

	return 0;
}


void print(struct point *pp[])
{
	int i=0;
	while(i< POINTS){
		printf("%f %f\n",pp[i]->x, pp[i]->y);
		i++;
	}
}


void generatePoints(struct point *pp[])
{
	int i;
	srand(time(0));
	for(i=0; i<POINTS; i++){
		pp[i] = malloc(sizeof(struct point));
		assert(pp[i] != NULL);
		pp[i]->x = rand()%100 + gaussrand();
		pp[i]->y = rand()%100 + gaussrand();

	}
}


double closestPair(struct point *ppx[], struct point *ppy[], int n)
{
	if(n <= 3){
		return bruteForceClosest(ppx, ppy, n);
	}
	
	//compute separation line L such that half points are
	//on one side nd half on other side
	struct point *bisect = ppx[n/2];
	
	struct point **ll = malloc(sizeof(struct point*)*n);
	struct point **rr = malloc(sizeof(struct point*)*n);
	
	int lenL = 0;
	int lenR = 0;

	int i,j;
	for(i=0; i<n; i++){
		if(isLeft(ppy[i], bisect)){
			ll[lenL] = ppy[i];
			lenL++;
		}else if(!(isLeft(ppy[i], bisect))){
			rr[lenR] = ppy[i];
			lenR++;
		}
	}

	double d1 = closestPair(ppx, ll, lenL);
	double d2 = closestPair(ppx+n-lenR, rr, lenR);
	double min1 = (d1 <= d2) ? d1 : d2;

	//delete all points further than min1 from separation line L
	int stripLen = 0;
	struct point *striped[POINTS];
	for(i=0; i<n; i++){
		if((ppy[i])->x >= (bisect->x - min1) || (ppy[i])->x <= (bisect->x + min1)){
			striped[stripLen] = ppy[i];
			stripLen++;
		}
	}

	//check the next 7 points till the end 
	for(i=0; i<stripLen; i++){
		for(j=i+1; j-i<8 && j<stripLen; j++){
			if(distance(striped[i], striped[j]) < min1){
				min1 = distance(striped[i],striped[j]);
			}
		}
	}
	
	return min1;
}
	

int isLeft(struct point *p, struct point *bisect)
{
	if(p->x < bisect->x){
		return 1;
	}else if(p->x == bisect->x && p->y < bisect->y){
		return 1;
	}
	return 0;

}


double distance(struct point *p1, struct point  *p2)	
{
	double distance1 = sqrt((p1->x - p2->x) * (p1->x - p2->x) + (p1->y - p2->y) * (p1->y - p2->y));
//	assert(distance1 != 0);
	return distance1;
}


double bruteForceClosest(struct point *ppx[], struct point *ppy[], int n )
{
	double min1 = INFINITY;
	double distance1;
	int i,j;
	for(i=0; i<n-1; i++){
		for(j=i+1; j<n; j++){
			distance1 = distance(ppx[i],ppx[j]);
			if(min1 > distance1){
				min1 = distance1;
			}
		}
	}
	return min1;
}	
	

double gaussrand()
{
	static double V1, V2, S;
	static int phase = 0;
	double X;
	if(phase == 0) {
		do{
			double U1 = (double)rand() / RAND_MAX;
			double U2 = (double)rand() / RAND_MAX;
			V1 = 2 * U1 - 1;
			V2 = 2 * U2 - 1;
			S = V1 * V1 + V2 * V2;
		}while(S>=1 || S==0);
		
		X = V1 * sqrt(-2 * log(S) / S);

	}else{
		X = V2 * sqrt(-2 * log(S) / S);
	}
	
	phase = 1 - phase;
		
	return X;
}

[noob15]

here's the code

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<assert.h>
#include<string.h>


#define POINTS 1000 

struct point{
	double x;
	double y;
};

#include"quickSortClosestPair.c"

double gaussrand();
void generatePoints(struct point *pp[]);
double closestPair(struct point *ppx[], struct point *ppy[], int n);
double bruteForceClosest(struct point *ppx[], struct point *ppy[], int n );
double distance(struct point *p1, struct point *p2);
void print(struct point *pp[]);
int isLeft(struct point *p, struct point *bisect);


int main()
{
	//array of points whose min. closest pair we have to find
	struct point *pp1[POINTS];
	generatePoints(pp1);
	
	//copy of pp1
	struct point *pp2[POINTS];
	int i;
	for(i=0; i<POINTS; i++){
		pp2[i] = malloc(sizeof(struct point));
		assert(pp2[i] != NULL);
		pp2[i]->x = pp1[i]->x;
		pp2[i]->y = pp1[i]->y;
	}
//	print(pp1);
//	printf("hiiiii\n");
	QuickSort(pp1, 0, POINTS-1, 'x');
	QuickSort(pp2, 0, POINTS-1, 'y');
	print (pp1);
	//d gives the closest distance
	double d = closestPair(pp1, pp2, POINTS);

	printf("the distance between closest pair of point is %f\n", d);

	d = bruteForceClosest(pp1, pp2, POINTS);
	printf("the distance between closest pair of point by brute force is %f\n", d);
	

	return 0;
}


void print(struct point *pp[])
{
	int i=0;
	while(i< POINTS){
		printf("%f %f\n",pp[i]->x, pp[i]->y);
		i++;
	}
}


void generatePoints(struct point *pp[])
{
	int i;
	srand(time(0));
	for(i=0; i<POINTS; i++){
		pp[i] = malloc(sizeof(struct point));
		assert(pp[i] != NULL);
		pp[i]->x = rand()%100 + gaussrand();
		pp[i]->y = rand()%100 + gaussrand();

	}
}


double closestPair(struct point *ppx[], struct point *ppy[], int n)
{
	if(n <= 3){
		return bruteForceClosest(ppx, ppy, n);
	}
	
	//compute separation line L such that half points are
	//on one side nd half on other side
	struct point *bisect = ppx[n/2];
	
	struct point **ll = malloc(sizeof(struct point*)*n);
	struct point **rr = malloc(sizeof(struct point*)*n);
	
	int lenL = 0;
	int lenR = 0;

	int i,j;
	for(i=0; i<n; i++){
		if(isLeft(ppy[i], bisect)){
			ll[lenL] = ppy[i];
			lenL++;
		}else if(!(isLeft(ppy[i], bisect))){
			rr[lenR] = ppy[i];
			lenR++;
		}
	}

	double d1 = closestPair(ppx, ll, lenL);
	double d2 = closestPair(ppx+n-lenR, rr, lenR);
	double min1 = (d1 <= d2) ? d1 : d2;

	//delete all points further than min1 from separation line L
	int stripLen = 0;
	struct point *striped[POINTS];
	for(i=0; i<n; i++){
		if((ppy[i])->x >= (bisect->x - min1) || (ppy[i])->x <= (bisect->x + min1)){
			striped[stripLen] = ppy[i];
			stripLen++;
		}
	}

	//check the next 7 points till the end 
	for(i=0; i<stripLen; i++){
		for(j=i+1; j-i<8 && j<stripLen; j++){
			if(distance(striped[i], striped[j]) < min1){
				min1 = distance(striped[i],striped[j]);
			}
		}
	}
	
	return min1;
}
	

int isLeft(struct point *p, struct point *bisect)
{
	if(p->x < bisect->x){
		return 1;
	}else if(p->x == bisect->x && p->y < bisect->y){
		return 1;
	}
	return 0;

}


double distance(struct point *p1, struct point  *p2)	
{
	double distance1 = sqrt((p1->x - p2->x) * (p1->x - p2->x) + (p1->y - p2->y) * (p1->y - p2->y));
//	assert(distance1 != 0);
	return distance1;
}


double bruteForceClosest(struct point *ppx[], struct point *ppy[], int n )
{
	double min1 = INFINITY;
	double distance1;
	int i,j;
	for(i=0; i<n-1; i++){
		for(j=i+1; j<n; j++){
			distance1 = distance(ppx[i],ppx[j]);
			if(min1 > distance1){
				min1 = distance1;
			}
		}
	}
	return min1;
}	
	

double gaussrand()
{
	static double V1, V2, S;
	static int phase = 0;
	double X;
	if(phase == 0) {
		do{
			double U1 = (double)rand() / RAND_MAX;
			double U2 = (double)rand() / RAND_MAX;
			V1 = 2 * U1 - 1;
			V2 = 2 * U2 - 1;
			S = V1 * V1 + V2 * V2;
		}while(S>=1 || S==0);
		
		X = V1 * sqrt(-2 * log(S) / S);

	}else{
		X = V2 * sqrt(-2 * log(S) / S);
	}
	
	phase = 1 - phase;
		
	return X;
}

quickSortCloses tPair.c

// quicksort, if char==c then it sorts points acc. to x coordinate otherwise it sorts according to y coordinate
void Swap(struct point **a, struct point **b);
void QuickSort(struct point *aa[], int p, int r, char c);
int Partition1(struct point *aa[], int p, int r);
int Partition2(struct point *aa[], int p, int r);

//sorts array of struct point according to index given by c
void QuickSort(struct point *aa[], int p, int r, char c)
{
	if(p<r && c=='x'){
		int q = Partition1(aa, p, r);
		QuickSort(aa, p, q-1, 'x');
		QuickSort(aa, q+1, r, 'x');
	}

	if(p<r && c=='y'){
		int q = Partition2(aa, p, r);
		QuickSort(aa, p, q-1, 'y');
		QuickSort(aa, q+1, r, 'y');
	}
}

int Partition1(struct point *aa[], int p, int r)
{
	int x=aa[r]->x;
	int y=aa[r]->y;
	int i=p-1;
	int j;
	for(j=p; j<r; j++){
		if(aa[j]->x < x){
			i++;
			Swap(&aa[i], &aa[j]);
		}else if(aa[j]->x == x && aa[j]->y < y){
			i++;
			Swap(&aa[i], &aa[j]);
		}
	}
	Swap(&aa[i+1], &aa[r]);
	return (i+1);
}


int Partition2(struct point *aa[], int p, int r)
{
	int x=aa[r]->y;
	int y=aa[r]->x;
	int i=p-1;
	int j;
	for(j=p; j<r; j++){
		if(aa[j]->y < x){
			i++;
			Swap(&aa[i], &aa[j]);
		}else if(aa[j]->y == x && aa[j]->x < y){
			i++;
			Swap(&aa[i], &aa[j]);
		}

	}
	Swap(&aa[i+1], &aa[r]);
	return (i+1);
}

void Swap(struct point **a, struct point **b)
{
	struct point *tmp = *a;
	*a = *b;
	*b = tmp;
}

[Banfa]

Line 15, you should never, NEVER include code files. If its meant to be included then it should be a header file (.h) if it is a code file then you should compile it separately and link it into your program.


Its tricky, closestPair has recursed over 500 times by the time the segmentation fault occurs. On my machine it seems to happen inside malloc suggesting a memory allocation issue but I estimate it wont have more than 4 Mbytes of data on the heap and rather less on the stack which should be ok.

[noob15]

Line 15, you should never, NEVER include code files. If its meant to be included then it should be a header file (.h) if it is a code file then you should compile it separately and link it into your program.


Its tricky, closestPair has recursed over 500 times by the time the segmentation fault occurs. On my machine it seems to happen inside malloc suggesting a memory allocation issue but I estimate it wont have more than 4 Mbytes of data on the heap and rather less on the stack which should be ok.

yupp....both heap and stack memory should not be a problem as the same program is running fine with larger number of points but points being distributed relatively apart from each other(changing %100 of rand to bigger value) !!

Btw thanks for pointing out line 15 thing...'ll avoid such a thing in future.

[Banfa]

I found that changing the %100 to a larger value made no difference.

I'm not sure however you are also using over 1Mbyte of stack space. I suspect if you re-wrote this routine to run iteratively rather than recursively and avoided the recursion into closestPair>500 times it might work better.