7.26 简单计算几何

向量加减法,长度,数乘

代码实现

Pt operator - (Pt a,Pt b){
return Pt(a.x-b.x,a.y-b.y);}
Pt operator + (Pt a, Pt b){
return Pt(a.x + b.x, a.y + b.y); }
double Length ( Point q){
return sqrt (q.x*q.x+q.y*q.y); }
Pt operator * ( double A, Pt p){
return Pt(p.x*A, p.y*A); }

 

点积

double dot (Pt a, Pt b) {
return a.x * b.x + a.y * b.y; }
double Angle ( Vector A, Vector B) {
return acos ( dot(A,B)/ Length (A)/ Length (B ));}

叉积

double det (Pt a, Pt b) {
return a.x * b.y - a.y * b.x; }

 

点在直线上的判断,直线间的关系

点在线段上的判断

bool PtOnSegment (Pt s, Pt t, Pt a) {
return ! det (a-s,a-t)&& min (s.x,t.x)<=a.x &&
a.x <= max(s.x,t.x)&& min(s.y, t.y) <= a.y &&
a.y <= max(s.y, t.y);
}
bool PtOnSegment (Pt p, Pt a, Pt b) {
return ! sgn (det (p-a,b-a ))&& sgn (dot (p-a,p-b)) <=0;
}

线段间的关系

点到线段的距离

求点P到线段AB的最短距离
1.判断线段PA和AB所成的夹角，如果是钝角，那么jPAj是
点到线段的最短距离。
2.判断线段PB和AB所成的夹角，如果是钝角，那么jPBj是
点到线段的最短距离。
3.线段PA和线段PB与AB所成的夹角都不为钝角，那么
点P到线段AB的距离是点P到直线AB的距离，这个距离可
以用面积法直接算出来。

求三角形的面积

判断点是否在三角形内

重心

Pt triangleMassCenter (Pt a, Pt b, Pt c) {
return (a+b+c) / 3.0;}

求多边形的面积

//代码实现多边形的有向面积,这里返回正值
double PolygonArea (Pt* p,int n){
double area =0;
for (int i=1;i<n -1; i++)
area += det (p[i]-p[0] ,p[i+1] -p [0]);
return fabs ( area /2);
}

多边形内格点数

Pick公式

//代码实现：求多边形边界上的点数：可以当成伪代码来看
int polygon_border_point_cnt ( const Polygon &p) {
int ans = 0;
int n = p. size ();
for (int i = 0; i < n; ++i)
ans += gcd (Abs (int (p[ next (i)].x-p[i].x)),
Abs(int(p[ next (i)].y-p[i].y )));
return ans ;
}

凸包 

定义：凸包就是把给定点包围在内部的、面积最小的凸多边形

算法：Andrew算法

首先把所有点按照从小到大排序（如果x相同，按照y从小到大排
序），删除重复点后得到序列p1; p2; :::，然后把p1和p2放到凸包
中。从p3开始，当新点在凸包“前进”方向的左边时继续，否则
依次删除最近加入凸包的点，直到新点在左边。
注意：从左到右和从右到左各扫描一次