演算法:
給一些平面上的點，找出這些相距最近的兩個點
1. 如果只有一點，回傳距離為無限大
2. 找一直線L垂直X軸並且分割S成一樣大小的兩半SL and SR
持續分割，直到剩下兩點或一點就進行比較
3. merge時 找出SL 與 SR 兩點之中最小的距離，紀錄為d
並且在L-d 與 L 裡找所有點a 看有沒有點在 L 與 L+d 裡並且Y值要介於 ay + d 與 ay - d
如果有判斷它與a 的距離d'是否小於d， 如果小於，則d = d'
程式碼實作如下
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct vertex //座標資料
{
float x; //紀錄X位置
float y; //紀錄Y位置
};
struct min_pair //紀錄最短距離pair的資料
{
float x1;
float y1;
float x2;
float y2;
float min_len; //紀錄最短距離
};
float len(float x1,float y1,float x2,float y2) //計算兩點間的距離函式
{
float result;
result = sqrt( fabs(x2-x1)*fabs(x2-x1) + fabs(y2-y1)*fabs(y2-y1) );
return result;
}
void per( struct vertex *vertex_arr1, int init, int end, struct min_pair *pair1) //per函式將所有點一分為二 init為初始注標 end為結尾注標
{
int i,j;
float result,middle;
if( init == end - 1 ) //分割到剩兩點 直接計算距離
{
result = len(vertex_arr1[init].x, vertex_arr1[init].y, vertex_arr1[end].x, vertex_arr1[end].y);
if( result < pair1->min_len )
{
pair1->x1 = vertex_arr1[init].x;
pair1->y1 = vertex_arr1[init].y;
pair1->x2 = vertex_arr1[end].x;
pair1->y2 = vertex_arr1[end].y;
pair1->min_len = result;
}
}
else if(init == end)
return;
else
{
per(vertex_arr1, init, (init + end )/2, pair1); //分割後 前半段帶入遞迴
per(vertex_arr1, (init + end )/2+1, end, pair1); //分割後 後半段帶入遞迴
//開始merge
middle = ( vertex_arr1[(init+end)/2].x + vertex_arr1[(init+end)/2+1].x )/2; //middle紀錄要merge兩區域的中間X值
for(i=init;i<=(init+end)/2;i++)
{
if( vertex_arr1[i].x <= middle && vertex_arr1[i].x >= middle - pair1->min_len ) //左點的X值位在middle與middle-min_len之間
{
for(j=(init + end)/2+1;j<=end; j++)
{
if( vertex_arr1[j].x >= middle && vertex_arr1[j].x <= middle + pair1->min_len ) //右點的X值位在middle+min_len之間
{
if( vertex_arr1[i].y + pair1->min_len >= vertex_arr1[j].y && vertex_arr1[i].y - pair1->min_len <= vertex_arr1[j].y ) //右點的Y值位在位在左點的Y值+min_len 與y值-min_len之間
{
result = len( vertex_arr1[i].x, vertex_arr1[i].y, vertex_arr1[j].x, vertex_arr1[j].y);
if( result < pair1->min_len )
{
pair1->x1 = vertex_arr1[i].x;
pair1->y1 = vertex_arr1[i].y;
pair1->x2 = vertex_arr1[j].x;
pair1->y2 = vertex_arr1[j].y;
pair1->min_len = result;
}
}
}
}
}
}
}
}
int main()
{
int i,max=0,j,temp;
char c[10];
FILE *fp;
fp = fopen("input.txt","r+");
i=0;
while(1) //讀檔 計算有幾個點
{
i++;
if( fgets(c,10,fp) == NULL )
break;
}
max = i-1; // 共有max個點
fseek(fp,0L,SEEK_SET); //移回檔頭
struct vertex *vertex_arr = malloc( max * sizeof(struct vertex) );
struct min_pair *pair = malloc( sizeof(struct min_pair) );
//初始化
pair->min_len = 1000;
i=0;
while(1) //讀檔 並放入vertex 結構
{
fscanf( fp,"%f,%f",&(vertex_arr[i].x) ,&(vertex_arr[i].y) );
i++;
if( (getc(fp)) == EOF )
break;
}
//先按照X值由小到大排列
for(i=0;i<max;i++)
{
for(j=i+1;j<max;j++)
{
if( vertex_arr[i].x > vertex_arr[j].x )
{
temp = vertex_arr[i].x;
vertex_arr[i].x = vertex_arr[j].x;
vertex_arr[j].x = temp;
temp = vertex_arr[i].y;
vertex_arr[i].y = vertex_arr[j].y;
vertex_arr[j].y = temp;
}
else if( vertex_arr[i].x == vertex_arr[j].x && vertex_arr[i].y > vertex_arr[j].y )
{
temp = vertex_arr[i].y;
vertex_arr[i].y = vertex_arr[j].y;
vertex_arr[j].y = temp;
}
}
}
per(vertex_arr,0,max-1,pair); //開始遞迴
printf("%.0f,%.0f\n",pair->x1,pair->y1);
printf("%.0f,%.0f\n",pair->x2,pair->y2);
printf("min_len = %.2f\n",pair->min_len);
system("pause");
return 0;
}
輸入請以讀入檔案方式。
例如：以下檔案內容，代表5個平面座標點
2,3
4,5
6,7
8,9
10,11
