计算几何学习
凸包
凸组合， λ = < λ 1 , λ 1 , . . . , λ n > T \lambda = <\lambda_1,\lambda_1,...,\lambda_n>^T λ=<λ1,λ1,...,λn>T
其中 λ 1 + λ 2 + . . . + λ n = 1 \lambda_1+\lambda_2+...+\lambda_n = 1 λ1+λ2+...+λn=1,且 λ i ≥ 0 \lambda_i\ge0 λi≥0
凸包，充要条件所有极点不被包含到任何三角形。
极点，所有最外侧的点
InTriangle
三角形测试，判断点是否在一个三角形内。
伪代码
void extremePoint(Point s[],int n){for(int s = 0; s < n; s++) S[s].extreme = true;for(int p = 0; p < n; p++)for(int q = p+1; q < n ; q++)for(int r = q+1; r < n; r++)for(int s = 0 ; s < n ; s++){if( s == p || s == q || s== r|| !S[s].extreme) continue;if(InTriangle(S[p],S[q],S[r],S[s])){S[s].extreme = false;}}
}
naïve 版本， O ( n 4 ) O(n^4) O(n4)
toLeft
判断点是否在向量的左侧或右侧
在三角形内，当且仅当点在三条边的左侧。
bool ToLeft(Point p, Point q, Point s)return Area2(p,q,s) > 0;int Area2(Point p, Point q, Point s)return p.x * q.y - p.y * q.x+ q.x * s.y - q.y * s.x+ s.x * p.y - s.y * p.x;
极边
对凸包有贡献的边。
极边的判断，所有的点都在极边的左侧。
基于极边的判断算法，
Let EE = 空集
for each directed segment pqif points in S/{p,q} lie to the same side of pq then let EE = EE 并 {pq}
复杂度 O ( n ∗ ( n − 1 ) ∗ ( n − 2 ) ) O(n*(n-1)*(n-2)) O(n∗(n−1)∗(n−2))
void markEE(Point s[] ,int n){for(int k = 0 ; k < n ; k++)S[k].extreme = False;for(int p = 0; p < n ; p++){for(int q = p + 1 ; q < n ; q++){checkEdge(S,n,p,q);// 判断是否在边的一侧}}
}void checkEdge(Point s[],int n , int p, int q){bool LEmpty = true, REmpty = true;for(int k = 0; k < n && (LEmpty || REmpty) ; k++){if(k != p && k != q)ToLeft(S[p],S[q],S[k])?LEmpty = false : REmpty = false;}if(LEmpty || REmpty)S[p].extreme = S[q].extreme = true;
}
分治算法
典型例子，插入排序