分治法在求解凸包問題中的應用（JAVA）

之前寫過一篇蠻力法在求解凸包問題中的應用（JAVA）還算簡單易懂，沒有基礎的讀者最好先去閱讀以下。 這里用分治法來求解凸包問題，由于這個算法和快速排序十分相似，因此又被稱為“快包”。 在平面上有n>1個點構成的集合，定義為S，為簡化思考，假定這些點按照x軸、y軸升序排列。有一個幾何事實就是，最左邊的一個點p1和最右邊的一個點pn一定是集合的凸包頂點。我們連接p1與pn，這條直線將所有的點分成了兩個子集合S1，S2。如果p1，p2，p3構成一個逆時針回路，我們稱p3為與直線p1-p2的左側；反之，稱為p3為與直線p1-p2的右側。另外S集合中位于p1-p2直線上的點，肯定不是凸包的頂點，直接忽略不考慮。
S的凸包邊界是有上下兩條多角形鏈條組成的，“上”邊界稱為上包，上包由p1、S1（如果S1不為空）中的一些點、p2為端點組成，“下”邊界稱為下包，下包由p1、S2（如果S2不為空）中的一些點、p2為端點組成。上下端點用同樣的方法構造而成，采用分治法思路更為清晰。下面以上包為例，分析所謂的快包算法：

由于一些下標不好表示，這里截取了《算法設計與分析基礎》中的文字講解部分。 知道了原來，我們該如何實現呢？假設我們有三個點p1（x1, x1）, p2(x2, y2)，p3(x3, y3)，這三點圍成的三角形的面積可以用下面的公式計算：
當且僅當p3位于直線p1-p2左側時，該表達式符號為正。 和快速排序一樣，該算法的最差時間復雜度為O(n^2)，但是平均效率好很多！ 下面的代碼在精度上由于采用double類型，但是沒有做判斷上的處理，比如比較大小的時候，所以對于高精度的數據并不適用。 import java.util.Arrays; import java.util.Comparator; import java.util.Scanner;class Point {double x;double y;public Point(double x, double y) {this.x = x;this.y = y;} } public class Main {static Point[] point;static double[] s = new double[6];static Scanner in = new Scanner(System.in);public static void main(String[] args) {int n = in.nextInt();point = new Point[n]; // for (int i = 0; i < n; i++) { // int a = in.nextInt(); // int b = in.nextInt(); // point[i] = new Point(a, b); // }point[0] = new Point(1,3);point[1] = new Point(2,1);point[2] = new Point(3,5);point[3] = new Point(4,4);point[4] = new Point(5,2);point[5] = new Point(3,2);Arrays.sort(point,0, n, new Comparator<Point>() {@Overridepublic int compare(Point o1, Point o2) {if (o1.x - o2.x == 0) {return (int) (o1.y - o2.y);}return (int) (o1.x - o2.x);}});System.out.println(point[0].x + "," + point[0].y);hull(1, n-1,point[0],point[0]);}private static void hull(int l,int r,Point p1,Point p2){int x=l;int i=l-1,j=r+1;/*** 找出距離直線p1-p2最遠的點p3* */for (int k = l; k <= r; k++){if (s[x] - s[k] <= 0) {x=k;}}Point p3 = point[x];/*** p1-p3左側的點* */for (int k = l; k <= r; k++) {s[++i] = cross(point[k], p1, p3);if (s[i] > 0) {Point temp = point[i];point[i] = point[k];point[k] = temp;} else {i--;}}/*** 直線p3-p2右側的點* */for (int k=r;k>=l;k--) {s[--j]=cross(point[k], p3, p2);if (s[j] > 0) {Point temp = point[j];point[j] = point[k];point[k] = temp;} else {j++;}}/*** 分治，并中序輸出* */if (l <= i) {hull(l, i, p1, p3);}System.out.println(p3.x + "," + p3.y);if (j <= r) {hull(j, r, p3, p2);}}private static double cross (Point a, Point b, Point c) {return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);} }

總結

以上是生活随笔為你收集整理的分治法在求解凸包问题中的应用（JAVA）--快包算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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