1. 分治法步驟

1.按x對點對數組進行從小到大排序
2.找出x中間值，按中間值劃分數組為左右兩部分
3.不斷細分，找出左右兩部分的最近點對
4.重復步驟1.2.3，得到最終左右兩部分的最近點對的距離d
5.找出 |X - Xmid| < d ,部分的點對，此部分左邊的點對集合我們設為p1,右邊設為p2，對p1,p2中的點按y的大小從小到大排序
6.對P1中所有點p，對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者，對P1中每一點最多只要檢查P2中排好序的相繼6個點，具體證明見：這位仁兄的帖子

2.實現

頭文件

#ifndef _CLOSESTPAIR_H_ #define _CLOSESTPAIR_H_typedef struct Point {int x;int y; }Point;void setPoints(Point points[], int pointsLength); int Distance(Point point1, Point point2); void sort(Point points[], int s, int e, char z); void merge(Point points[], int s, int e, int mid, char z); void divideByMid(int mid, Point points[], Point pointsL[], Point pointsR[], int n); int getClosestInSides(Point points[], int pointsLength); int getClosest(Point points[], Point result[2], int pointsLength);#endif

C文件

#include "ClosestPair.h" #include <graphics.h> #include <stdio.h> #include <math.h> #include <time.h>#define LENGTH 100 #define MYINFINITE 100000;int main() { initgraph(960, 540);setcolor(WHITE);Point points[LENGTH] = { 0,0 };Point result[2] = { 0,0 };int distance = 0;setPoints(points, LENGTH);for (int i = 0; i < LENGTH; i++){circle(points[i].x, points[i].y, 1);}distance = getClosest(points, result, LENGTH);setlinecolor(GREEN);line((int)result[0].x, (int)result[0].y, (int)result[1].x, (int)result[1].y);setcolor(RED);circle((int)result[0].x, (int)result[0].y, 1);circle((int)result[1].x, (int)result[1].y, 1);outtextxy(5, 5, "distance: ");char distanceText[20];_itoa_s(distance, distanceText, 10);outtextxy(70, 5, distanceText);system("pause");getchar();return 0; } //在畫面生成內不重復的一定數量的點 void setPoints(Point points[],int pointsLength) {srand((unsigned)time(0));for (int i = 0; i < pointsLength; i++){points[i].x = rand() % 960;points[i].y = rand() % 540;for (int j = 0; j < i; j++){if (points[j].x == points[i].x && points[j].y == points[j].x){i--;}}}return; } //獲得兩點距離 int Distance(Point point1, Point point2) { int distance = sqrt(pow(point1.x - point2.x, 2) + pow(point1.y - point2.y, 2));return distance; } //歸并排序 void sort(Point points[], int s, int e,char z) {if (s < e){int mid = (s + e) / 2;sort(points, s, mid, z);sort(points, mid + 1, e, z);merge(points, s, e, mid, z);return;} } //歸并 void merge(Point points[], int s, int e, int mid, char z) {int length1 = mid - s + 1;int length2 = e - mid;Point *AL = (Point*)malloc(sizeof(Point)*length1);Point *AR = (Point*)malloc(sizeof(Point)*length2);int i = 0, j = 0, k = s;for (i = s; i <= mid; i++){AL[i - s] = points[i];}for (j = mid + 1; j <= e; j++){AR[j - mid - 1] = points[j];}switch (z){//對橫坐標x進行排序case 'x':i = 0; j = 0;while (i < length1&&j < length2){if (AL[i].x < AR[j].x){points[k++] = AL[i++];}else points[k++] = AR[j++];}while (i < length1){points[k++] = AL[i++];}while (j < length2){points[k++] = AR[j++];}break;//對縱坐標y進行排序case 'y':i = 0; j = 0;while (i < length1&&j < length2){if (AL[i].y < AR[j].y){points[k++] = AL[i++];}else points[k++] = AR[j++];}while (i < length1){points[k++] = AL[i++];}while (j < length2){points[k++] = AR[j++];}break;default:free(AL);free(AR);break;}return; } //按中心劃分左右兩部分點對 void divideByMid(int mid, Point points[], Point pointsL[], Point pointsR[], int n) {int i = 0, j = 0, k = 0;for (i = 0; i < n; i++){if (points[i].x > mid) {pointsR[j++] = points[i];}else {pointsL[k++] = points[i];}}return; } //在左右點集中獲得最近點對 int getClosestInSides(Point points[], int pointsLength) {int distance;if (pointsLength < 2){distance = MYINFINITE;}else if (pointsLength == 2){distance = Distance(points[0], points[1]);}else{Point * pointsL = (Point*)malloc(sizeof(Point)*(pointsLength));Point * pointsR = (Point*)malloc(sizeof(Point)*(pointsLength));//初始化數組中各點坐標for (int i = 0; i < pointsLength; i++){if (i < pointsLength / 2){pointsL[i].x = 0;pointsL[i].y = 0;}else{pointsR[i - pointsLength / 2].x = 0;pointsR[i - pointsLength / 2].y = 0;}}//按x排序sort(points, 0, pointsLength - 1, 'x');//分治divideByMid(points[pointsLength/2].x, points, pointsL, pointsR,pointsLength);//分治后求解int distance_L = getClosestInSides(pointsL, pointsLength / 2);int distance_R = getClosestInSides(pointsR, pointsLength - pointsLength / 2);if (distance_L > distance_R){distance = distance_L;}else distance = distance_R;free(pointsR);free(pointsL);}return distance; } //獲取全局最近點對 int getClosest(Point points[], Point result[2], int pointsLength) {int distance = getClosestInSides(points, pointsLength);sort(points, 0, pointsLength - 1, 'y');Point * pointsCenter = (Point *)malloc(sizeof(Point)*pointsLength);int pointsCenterLength = -1;for (int i = 0; i < pointsLength; i++){if (fabs(points[i].x - points[pointsLength/2].x) < distance){pointsCenter[++pointsCenterLength] = points[i];}}for (int i = 0; i < pointsCenterLength; i++){for (int j = i + 1; j <= i + 7 && j < pointsCenterLength; j++){if (Distance(pointsCenter[i], pointsCenter[j]) < distance){distance = Distance(pointsCenter[i], pointsCenter[j]);result[0] = pointsCenter[i];result[1] = pointsCenter[j];}}}free(pointsCenter);return distance; }

3.結果

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的分治法实现最近点对问题——C语言可视化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。