1. 問題描述：

問題: 對于平面上n個點，找包圍它們的最小凸多邊形；

2. 思路：

蠻力算法: 對于每對點 p1和p2 ，判斷是否所有其他點都在連接 p1和p2 的直線的同一側；
思路：兩點確定一條直線，如果剩余的其它點都在這條直線的同一側，則這兩個點是凸包上的點，否則就不是。步驟如下：
（1）將點集里面的所有點兩兩配對，組成 n(n-1)/2 條直線。
（2）對于每條直線，再檢查剩余的 (n-2) 個點是否在直線的同一側。
那么現在出現了一個問題，我們怎樣判定一個點在直線的哪一側呢？方法有兩種：
（1）（坐標：p1(x1,y1)，p2(x2,y2)，p3(x3,y3)）行列式求面積 (也就是我們常說的"叉積")

當上式結果為正時，p3在直線 p1p2 的左側；當結果為負時，p3在直線 p1p2 的右邊
（2）將兩點構造成直線，將第三點坐標代入，≥0則表示在上方，≤0則表示在下方。

// 算法：蠻力法求解凸包問題 BruteForceConvexHull (P) // 輸入：一個n個(n≥2)的點的列表P,Pi=(Xi,Yi) // 輸出：能夠組成凸包的點的列表Qi=(Xi,Yi) for i ? 1 to n - 1 dofor j ? i + 1 to n dosign1 ? 0; sign2 ? 0;a = Yj - Yi; b = Xi - Xj; c = Xi * Yi - Yi * Xj;for k ? 1 to n doif k = i || k = j continue;if a * Xk + b * Yk - c ≥ 0 sign1++;if a * Xk + b * Yk - c ≤ 0 sign2++;if sign2 = 2 - n || sign1 = n - 2record the pole retutn OK

總結

以上是生活随笔為你收集整理的蛮力法求解凸包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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