algorithm analysis : Finding the nearest point pair problem (c++)

1, Preparation part :
For the nearest point problem , Problems need to be coded , So create a point class first , To make the calculation more comprehensive ,
class Points // Point class { public: float x; float y; };
Because the distance will be calculated many times , We need a function to calculate the distance between two points .
float Distance(Points p1,Points p2)// Find the distance function of two points { return sqrt((p1.x-p2.x)*(p1.x-p2
.x)+(p1.y-p2.y)*(p1.y-p2.y)); } But the improvement here is to put the root number outside, which can reduce the amount of calculation . float Distance(Points
p1,Points p2)// Find the distance function of two points { return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
2, Exhaustive law
Algorithmic idea :
Traverse every point , Distance each point from all other points , Then find the shortest distance , Keep point pair return at the same time .

Implementation code :

Traverse every point , Use two cycles , Sum every time , The first i Only and i+1 reach n To compare , Because the previous numbers have been compared , No need to double calculate . At first, the minimum value is infinite , The calculated distances are compared one by one , If smaller than the minimum , Replace its value , Save point pair .
for (int i=0; i<length-1; i++) { for(int j=i+1; j<length; j++) { float temp =
Distance(p[i],p[j]);if (temp < min_dis) { min_dis = temp; a = p[i]; b = p[j]; }
} }
3, Divide and conquer
Function name :
float merge_distance(Points* po,int len,Points &a,Points &b)
parameter :
po Ordered point set ,len Is the number of points ,a Save first point ,b Save the second point .

Algorithm idea and code interpretation :
Consider two dimensions as one dimension array first , according to x Axis sort all points .
code implementation :
sort(p, p+length, CmpX); // sort min_dis = merge_distance(p, length, a, b);
// Call function
Less points .

code implementation :
if(len < 2) return na_n;// Infinity if(len == 2) { a = po[0]; b = po[1]; dis =
Distance(po[0],po[1]); }
point |S|>3 Time , Set plane points S Split into two subsets of approximately equal size SL and SR, Pick a vertical line mid As split line .

code implementation :
else //len>=3 { Points *p1 = new Points[len/2+1]; // Left dot Points *p2 = new
Points[len/2+1]; // Right point float mid = po[(len-1)/2].x; int i=0, j=0, k1=0, k2=0;
for(i=0; i<len/2; i++) // Get the left point p1[i] = po[j++]; // Get the right point for(i=0; i<len/2; i++)
p2[i] = po[j++]; d1 = merge_distance(p1,len/2, a1, b1);// Left recursion d2 =
merge_distance(p2,len-len/2, a2, b2);// Right recursion
Use two recursive calls to find the shortest distance between the regions on both sides , by d1,d2,d=min{d1,d2}

code implementation :
if (d1 < d2) { dis = d1; a = a1; b = b1; } else { dis = d2; a = a2; b = b2; }
Consider the distance between cross-border areas , According to the above d, Draw on both sides of the center line 2d Area of , Because it's beyond this area , The left to right point must exceed d Distance of , To reduce computation , Right first x Shaft cutting .

code implementation :
Points *p3 = new Points[len/2]; //d Area left Points *p4 = new Points[len-len/2];
//d District friendship for(i=0, k1=0; i<len/2; i++) //x Axis left cut if((mid - po[i].x) <= dis)
p3[k1++] = po[i];for(i=0, k2=0; i<(len-len/2); i++) //x Week right cut if((po[i].x - mid)
>= dis) p4[k2++] = po[i];
In order to reduce the calculation , On the left side of traversal d At all points in , opposite side d Point processing in , Put it y Shaft cutting , Also press d To draw out d*2d Area of . Because it's impossible to compare d Small .

code implementation :
for(i=0; i<k1; i++) { for(j=0; j<k2; j++) { if( abs(p3[i].y - p4[j].y) < dis)
//y Shaft cutting { float temp = Distance(p3[i],p4[j]); if(temp < dis) { dis = temp; a =
p3[i]; b = p4[j]; } } } }
Complete code display ( Optimized ), The root of the distance to be calculated , Get it out there
#include <iostream> #include <time.h> #include <cmath> #include <sys/timeb.h >
#include <windows.h> #include <limits> #include <algorithm> #define Example_num
2 using namespace std; class Points // Point class { public: float x; float y; }; bool
CmpX(Points a, Points b) {return a.x < b.x; } class Handles { public: int
length;float min_dis; float na_n; double p_time; Points *p; Handles(){} Handles(
int n) { na_n = numeric_limits<float>::max(); min_dis = na_n; length = n; p =
new Points[length]; set_points(); } void set_points() { struct timeb timeSeed;
ftime(&timeSeed); srand(timeSeed.time *1000 + timeSeed.millitm); for(int i=0;
i<length; i++) { p[i].x = rand()/10.00000000; p[i].y = rand()/10.00000000; } }
float Distance(Points p1,Points p2) { return
((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); }float exhaustion_Distance()
{ Points a,b; LARGE_INTEGER li, freq; QueryPerformanceCounter(&li);long long
p_start = li.QuadPart; QueryPerformanceFrequency(&freq);for (int i=0; i<length-1
; i++) {for(int j=i+1; j<length; j++) { float temp = Distance(p[i],p[j]); if
(temp < min_dis) { min_dis = temp; a = p[i]; b = p[j];/*if (min_dis ==0)
cout<<p[i].x<<' '<<p[i].y<<' '<<p[j].x<<' '<<p[j].y<<endl;*/ } } }
QueryPerformanceCounter(&li);long long p_end = li.QuadPart; p_time = (p_end -
p_start)*1000./freq.QuadPart; cout<<" The shortest distance is "<<sqrt(min_dis)<<' '; cout<<'('
<<a.x<<','<<a.y<<')'<<','<<'('<<b.x<<','<<b.y<<')'<<' '; cout<<p_time<<"ms"<<' '
<<endl;return min_dis; } float merge_dis() { Points a,b; LARGE_INTEGER li,
freq; QueryPerformanceCounter(&li);long long p_start = li.QuadPart;
QueryPerformanceFrequency(&freq);// computing time sort(p, p+length, CmpX); // sort min_dis =
merge_distance(p, length, a, b);// Call function QueryPerformanceCounter(&li); long long
p_end = li.QuadPart; p_time = (p_end - p_start)*1000./freq.QuadPart; cout<<
" The minimum distance is "<<sqrt(min_dis)<<' '; cout<<'('<<a.x<<','<<a.y<<')'<<','<<'('<<b.x<<','
<<b.y<<')'<<' '; cout<<p_time<<"ms"<<' '<<endl; } float merge_distance(Points*
po,int len,Points &a,Points &b) { float dis; float d1,d2; Points a1,b1,a2,b2; if
(len <2) return na_n; // There is only one point infinite if(len == 2) // Direct calculation of two points { a = po[0]; b = po[1];
dis = Distance(po[0],po[1]); } else //len>=3 { Points *p1 = new Points[len/2+1];
// Left dot Points *p2 = new Points[len/2+1]; // Right point float mid = po[(len-1)/2].x; int
i=0, j=0, k1=0, k2=0; for(i=0; i<len/2; i++) // Get the left point p1[i] = po[j++]; // Get the right point
for(i=0; i<len/2; i++) p2[i] = po[j++]; d1 = merge_distance(p1, len/2, a1, b1);
// Left recursion d2 = merge_distance(p2, len-len/2, a2, b2);// Right recursion if (d1 < d2) { dis =
d1; a = a1; b = b1; }else { dis = d2; a = a2; b = b2; } Points *p3 = new
Points[len/2]; //d Area left Points *p4 = new Points[len-len/2]; //d District friendship for(i=0, k1=0;
i<len/2; i++) //x Axis left cut if((mid - p[i].x) <= dis) p3[k1++] = po[i]; for(i=0, k2=0
; i<(len-len/2); i++) //x Week right cut if((po[i].x - mid) <= dis) p4[k2++] = po[i]; for
(i=0; i<k1; i++) { for(j=0; j<k2; j++) { if( abs(p3[i].y - p4[j].y) < dis)//y Shaft cutting
{float temp = Distance(p3[i],p4[j]); if(temp < dis) { dis = temp; a = p3[i]; b
= p4[j]; } } } }delete []p1; delete []p2; delete []p3; delete []p4; } return
dis; } ~Handles() {delete []p; } }; int main() { int x = 0; bool key = true;
while(x<2) { int n = 10; if(key) {cout<<" Exhaustive law "<<endl;cout<<" Sample size :"
<<Example_num<<endl;}else {cout<<" Divide and conquer "<<endl;cout<<" Sample size :"<<Example_num<<endl;}
for(int i=0; i<4; i++) { double time_ave = 0; n = n*10; cout<<" The scale is "<<n<<endl;
for(int k=0; k<Example_num; k++) { Handles h(n); if (key)
h.exhaustion_Distance();else h.merge_dis(); time_ave += h.p_time; } cout<<
" The average time is "<<time_ave/Example_num<<"ms"<<endl; cout<<endl; } x++; key = false; } cin
>>x;return 0; }

Technology
©2019-2020 Toolsou All rights reserved,
JS How to operate java Realize the function of grabbing red packets C Language programming to find a student's grade The United Nations 《 Glory of Kings 》 Please go to the studio : To save the earth Dialogue between apple and Nissan suspended ,Apple Car How's it going ?CSS architecture design China's longest high speed rail officially opened ! The fastest way to finish the race 30.5 hour First knowledge MySQL Comprehensive review ( dried food )2021 year 1 Monthly programmer salary statistics , average 14915 element How to use it quickly html and css Write static page