GiftWrapping算法解決二維凸包問題

一.問題描述         凸集(Convex Set): 任意兩點的連線都在這個集合内的集合就是一個凸集.             ⒈對于一個集合D，D中任意有限個點的線性組合的全體稱為D的凸包。             ⒉對于一個集合D，所有包含D的凸集之交稱為D的凸包(由此定義可以想到分治算法)。         可以證明，上述兩種定義是等價的。點集Q的凸包（convex hull）是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其内。下圖中由紅色線段表示的多邊形就是點集Q={p0,p1,...p12}的凸包。一組平面上的點，求一個包含所有點的最小的凸多邊形，這就是凸包問題了，這可以形象地想象成在地上放置一些不可移動的木樁，用一根繩子把他們盡量緊地圈起來，并且為凸邊形，這就是凸包了。

二.GiftWrapping算法         又叫卷包裹算法，複雜度O(n*h)，n表示共幾個點，h表示極點個數。 理論準備                 向量叉積：也被稱為矢量積、叉積（即交叉乘積）、外積，是一種在向量空間中向量的二進制運算。與點積不同，它的運算結果是一個僞向量而不是一個标量，并且兩個向量的叉積與這兩個向量垂直，方向由右手法則确定。兩個向量a和b的叉積寫作a×b（有時也被寫成a∧b，避免和字母x混淆）。 a×b=(aybz-azby)i+(azbx-axbz)j+(axby-aybx)k,為了幫助記憶，利用三階行列式，寫成 |  i    j   k| |ax ay az| |bx by bz|。         b×a= -a×b，三角形ABC的面積=1/2*abs(AB×AC)(這個公式可以解決一些精度問題)，不滿足結合律，但滿足雅可比恒等式：a× (b×c) +b× (c×a) +c× (a×b) =0和拉格朗日公式a× (b×c) =b(a·c) -c(a·b),可以簡單地記成“BAC - CAB”。這個公式在實體上簡化向量運算非常有效，需要注意的是，這個公式對微分算子不成立。 算法描述

        卷包裹算法從一個必然在凸包上的點開始向着一個方向依次選擇最外側的點，當回到最初的點時，所選出的點集就是所要求的凸包。這裡還有兩個問題不是很清楚:         1.怎麼确定一個肯定在凸包上的點?         這個問題很好解決，取一個最左邊的也就是橫坐标最小的點（或最下邊的點，縱坐标最小的），如果有多個這樣的點， 就取這些點裡縱坐标（橫坐标）最小的，這樣可以很好的處理共線的情況。         2.如何确定下一個點(即最外側的點)?         向量的叉積是不滿足交換律的，向量A乘以向量B， 如果為正則為A逆時針旋轉向B，否則為順時針，當然這裡A轉向B的角總是考慮一個小于180度以内的角。 三.算法的Java實作         看完這段代碼，直接把POJ1113AC了吧。

         遺留問題：做完POJ1113時，想起了怎麼求所得凸多邊形的外接圓，也就是最小覆寫圓問題，那麼又怎麼求内切圓呢？

​