ConvexHull(凸包)

凸包是什么

凸包是計算幾何一個非常基礎核心的概念。我理解的凸包就是給定一個點集合, 最外圍的點的包圍體就是凸包。如下所示:

極點(ExtremityPoint)

給定的點集合中, 如果一個點存在一條直線, 讓其他所有點都在于該直線的同一側, 則該點為極點。

非極點

和極點性質相反, 經過該點任一直線都無法做到讓其他所有點位于同一側

凸集合

給定一個點集合S = [P1, P2...Pn], 給每個點分配一個權重rx,? 滿足條件:

[1]rx >= 0 &&rx <= 1,?

[2]r1 + r2 +? ...... rn = 1.0

由 P = r1 * P1 + ..... + Pn * rn 計算公式,? 得到新的點集合，成為S的凸組合.

我理解的是點S構成的凸包內部的點集合就是凸組合。

凸相關

給定一個點集合S, 加入一個點A后，凸組合沒變化的，就稱點A和點集合S是凸相關的。

換一個說法就是, 點A包含在集合S里的凸組合里。

比如給定點S = {1, 4}, 點2或者點3和集合S是凸相關。

凸無關

給定一個點集合S, 加入一個點A后，凸組合發生變化,?就稱點A和點集合S是凸無關。

對于點集合S(1, 2, 3), 點4是凸無關.

給定點集合求極點

分解問題

極點滿足： 不在點集合構成的所有三角形內部的點, 則為極點。反之為非極點。

偽代碼實現

算法復雜度為O(n4)

算法實現

In-Trianle-Test

In-Trianle-Test: 判斷一個點是否在一個三角形內.

如果點S在三角形三條邊的同一側, 則在三角形內. 分解為三次ToLeft測試，即點和三角形的三條邊的測試.

ToLeft測試

ToLeft測試就是用于判斷點是否在一條邊的左側.

叉積面積正負來判斷左側 or 右側

(CCW 的時候ToLeft 世界左側返回True,?CW的時候ToLeft 世界左側返回False)

代碼實現

給定點集合

代碼實現

#include <iostream>
#include <vector>using namespace std;struct Point
{float x;float y;
};float Area2(const Point& inPointA, const Point& inPointB, const Point& inPointC)
{float value =inPointA.x * inPointB.y - inPointA.y * inPointB.x+ inPointB.x * inPointC.y - inPointB.y * inPointC.x+ inPointC.x * inPointA.y - inPointC.y * inPointA.x;return value;
}bool IsLeftTest(const Point& inPointA, const Point& inPointB, const Point& inPointC)
{return Area2(inPointA, inPointB, inPointC) > 0;
}bool IsInTrianle(const Point& inPoint, const Point& triangleA, const Point& triangleB, const Point& triangleC)
{bool bLeftA = IsLeftTest(triangleA, triangleB, inPoint);bool bLeftB = IsLeftTest(triangleB, triangleC, inPoint);bool bLeftC = IsLeftTest(triangleC, triangleA, inPoint);return (bLeftA == bLeftB) && (bLeftB == bLeftC);
}void GetConvexPointSet(const vector<Point>& inPoints, vector<Point>& outPoints)
{int pointNum = inPoints.size();vector<bool> extrmeFlags;extrmeFlags.resize(pointNum);for (int index = 0; index < pointNum; index++){extrmeFlags[index] = true;}// O(n4)for (int idxA = 0; idxA < pointNum; idxA++){for (int idxB = idxA + 1; idxB < pointNum; idxB++){for (int idxC = idxB + 1; idxC < pointNum; idxC++){for (int s = 0; s < pointNum; s++){if (s == idxA || s == idxB || s == idxC || !extrmeFlags[s])continue;if (IsInTrianle(inPoints[s], inPoints[idxA], inPoints[idxB], inPoints[idxC])){extrmeFlags[s] = false;}}}}}for (int index = 0; index < pointNum; index++){if (extrmeFlags[index]){outPoints.push_back(inPoints[index]);}}}int main()
{std::cout << "Hello World!\n";// point set contructvector<Point> inPoints ={{0, 0},{-1, -1},{5, 2},{4, 5},{3, 3},{-1, 3},{2, 2},{-3, 2},};vector<Point> outPoints;GetConvexPointSet(inPoints, outPoints);for (int index = 0; index < outPoints.size(); index++){printf("(%f, %f)\n", outPoints[index].x, outPoints[index].y);}}

運行結果

很顯然漏掉了 (-1, -1, -1, -1)

原因是(-1, -1), (0, 0) (2, 2), (3, 3)四點共線導致ToLeft測試失效，誤認為也在三角形內部。所以得改進檢測算法。

改進In-Trianle-Test

在進行In-Trianle-Test的時候先判斷是否四點共線， 然后在進行ToLeftTest

bool IsInTrianle(const Point& inPoint, const Point& triangleA, const Point& triangleB, const Point& triangleC)
{float a_area2 = Area2(triangleA, triangleB, inPoint);float b_area2 = Area2(triangleB, triangleC, inPoint);float c_area2 = Area2(triangleC, triangleA, inPoint);if (a_area2 == 0 && b_area2 == 0 && c_area2 == 0)return false;bool bLeftA = a_area2 > 0;bool bLeftB = b_area2 > 0;bool bLeftC = c_area2 > 0;// 取決于CCW/CWreturn (bLeftA == bLeftB) && (bLeftB == bLeftC);
}

運行結果

參考資料

[1]清華計算幾何?P1-P12