Nearest point to problem

There are many points in two-dimensional space. The coordinates of each point are (x, y). Find the coordinates and distances of the two closest points

Solution

Consider two methods. The first method, violence solution, is easy to understand, but time complexity is high, when the number of points is large, it is difficult to run. The second method uses the idea of divide and conquer to solve the nearest point pair problem recursively.

Violence law

float baoli(Point points[], int length, Point &a, Point &b){
	float min = 99999;
	for(int i=0;i<length;i++){
		for(int j=0;j<i;j++){
			double temp = sqrt(pow(points[i].x-points[j].x,2)+pow(points[i].y-points[j].y,  2));
			if(temp<min){
				min = temp;
				a = points[i];
				b = points[j];
			} 
		}
	}
	return min;
}

The idea of violence law is very simple, so there is no more explanation here

Divide and conquer

The idea of divide and conquer method to solve the nearest problem is as follows:
First, the point pairs are sorted according to the size of the abscissa, which are divided into the left half and the right half. Recursively call the function to find the nearest point pair and the minimum distance d1, d2 of the left and right half, and then find the nearest point pair and the minimum distance of the min (D1, d2) neighborhood of the middle point. Compare with min (D1, d2), the smallest is taken.
The code is as follows.

#include <stdio.h>
#include <math.h> 

//Point is the structure of a point, x, y is the abscissa and ordinate 
typedef struct Point{
	float x;	
	float y;
}Point;
//The function of finding the distance between two points 
float distance(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//Quick row 
int partition(Point a[],int begin,int end){
	Point key = a[end];
	int i = begin-1;
	for(int j=begin;j<end;j++){
		if(a[j].x<=key.x){
			i++;
			Point temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	i++;
	a[end] = a[i];
	a[i] = key;
	return i;
}
void quiksort(Point a[],int begin,int end){
	if(begin<end){
		int middle = partition(a,begin,end);
		quiksort(a,begin,middle-1);
		quiksort(a,middle+1,end);
	}
}
//Solving distance by divide and conquer method 
float closest (Point* points,int n,Point &a, Point &b){
	//Exit of recursive function, two points directly return distance, one point returns a maximum value 
	if(n==2){
		a = points[0];
		b = points[1];
		return distance(a,b);
	} 
	else if(n<2){
		return 99999;
	}
	//Divide and conquer 
	else{
		int n1 = n/2;
		int n2 = n-n1;
		float d1,d2,dis,mid;
		Point points1 [n1];
		Point points2 [n2];
		Point a1,a2,b1,b2;
		//Arrange point pairs according to x coordinate 
		quiksort(points,0,n-1);
		mid = points[n1].x;
		for(int i=0;i<n1;i++){
			points1[i] = points[i];
		}
		for(int i=0;i<n2;i++){
			points2[i] = points[i+n1];
		}
		//Left and right partitions 
		d1 = closest(points1,n1,a1,b1);
		d2 = closest(points2,n2,a2,b2);
		if(d1<=d2){
			a = a1;
			b = b1;
			dis = distance(a,b);
		}
		else{
			a = a2;
			b = b2;
			dis = distance(a,b);
		}
		//Middle area
		Point points3[n];
		int k = -1;
		for(int i=0;i<n;i++){
			if(abs(points[i].x-mid)<=dis){
				points3[++k] = points[i];
			}
		}
		for(int i=0;i<n;i++){
			for(int j=i+1;j<i+7&&j<k;j++){
				if(distance(points3[i],points3[j])<dis){
					a = points3[i];
					b = points3[j];
					dis = distance(a,b);
				}
			}
		} 
		return dis;
		
	}
}
int main(void){
	Point points[7] = {{1.0,2.0},{1.1,6.2},{5.0,7.0},{15.0,12.5},{2.6,2.5},{5.9,4.6},{9.1,15.8}};
	for(int i=0;i<7;i++){
		printf("(%f,%f)\n",points[i].x,points[i].y);
	}

	Point a,b;
	float dis = closest(points,7,a,b);
	printf("distance%f，spot a(%f，%f)，spot b(%f，%f)",dis,a.x,a.y,b.x,b.y);
}