Study - 几何计算总结

---

一、点与向量

在二维坐标系中，我们可以将点的坐标转换为向量的坐标；假设坐标原点$O(0,0)$ , 如 $P(x,y)$：
$$P(x,y)=\overrightarrow{OP},\overrightarrow{OP}=(x,y)$$

1.1. 两点之间的距离

• 二维平面的点用坐标$P(x,y)$表示:

struct Point
{
    
	float x,y;
	Point(){
    }
	Point(float x,float y):x(x),y(y){
    }
};

• 两点间的距离

1. 用库函数hypot()计算三角形 [A,B与原点O组成的三角形] 的斜边长; 需要添加头文件#include <math.h>

float Distance(Point A, Point B)
{
    
    return hypot(A.x - B.x, A.y - B.y);
}

• 直接两点间的距离公式 $A(x_1,y_1),B(x_2,y_2)$
  $$\overrightarrow{AB}=\overrightarrow{OB}-\overrightarrow{OA},|\overrightarrow{AB}{|}^2=(x_2-x_1{)}^2+(y_2-y_1{)}^2$$

---

struct Point
{
    
	float x,y;
	Point(){
    }
	Point(float x,float y):x(x),y(y){
    }
	float Distance(Point A, Point B)
	{
    
    	return hypot(A.x - B.x, A.y - B.y);
	}
};

---

1.2. 向量的运算

我们把向量也用点表示，但需注意，向量可以平移。

typedef Point Vector;

两个点确定一个向量

Point (Point A,Point B)
{
    
	return Point(A.x - B.x, A.y - B.y);
}

向量运算需要对运算符进行重载。

• 加法

Point operator +(Point B)
{
    
	return Point(x + B.x, y + B.y);
}

• 减法

Point operator -(Point B)
{
    
	return Point(x - B.x, y - B.y);
}

• 乘法和除法用来等比例放大或缩小向量

Point operator *(float k)
{
    
	return Point (x * k, y * k);
}
Point operator /(float k)
{
    
	return Point (x / k, y / k);
}

• 判等
  判等涉及到运算的精度，所以需要先定义浮点数的判等函数。

const float eps=1e-8;    //偏差值，有时用1e-10
int sgn(float x)		//判断x是否等于0：0为等于，1为大于，-1为小于
{
    
	if(abs(x)<eps)
		return 0;
	else
		return x < 0 ? -1 : 1;
}
int dcmp(float x, float y)	//判断x是否等于y：0为等于，1为大于，-1为小于
{
    
	if(abs(x-y)<eps)
		return 0;
	else
		return x < y ? -1 : 1;
}

所以向量的判等可以调用上面的sgn()函数或dcmp()函数。

bool operator ==(Point B)
{
    
	return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;
}

---

typedef Point Vector
struct Point
{
    
	float x,y;
	Point(){
    }
	Point(float x,float y):x(x),y(y){
    }
	Point (Point A,Point B){
    return Point(A.x - B.x, A.y - B.y);}
	float Distance(Point A, Point B)
	{
    
    	return hypot(A.x - B.x, A.y - B.y);
	}
	const float eps=1e-8;    //偏差值，有时用1e-10
	int sgn(float x)		//判断x是否等于0：0为等于，1为大于，-1为小于
	{
    
		if(abs(x)<eps)
			return 0;
		else
			return x < 0 ? -1 : 1;
	}
	int dcmp(float x, float y)	//判断x是否等于y：0为等于，1为大于，-1为小于
	{
    
		if(abs(x - y)<eps)
			return 0;
		else
			return x < y ? -1 : 1;
	}

	Point operator +(Point B){
    return Point(x + B.x, y + B.y);}
	Point operator -(Point B){
    return Point(x - B.x, y - B.y);}
	Point operator *(double k){
    return Point (x * k, y * k);}
	Point operator /(double k){
    return Point (x / k, y / k);}
	bool operator ==(Point B){
    return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
};

1.3. 向量的点积与叉积

1. 点积
   数学公式：
   $$\mathbf{A}\cdot \mathbf{B}=\left|A\right|\left|B\right|\cos \theta =A.x\cdot B.x+A.y\cdot B.y$$
   代码如下：

double Dot(Vector A,Vector B)
{
    
	return A.x * B.x + A.y * B.y;
}

点积的正负可判断向量的夹角是锐角还是钝角.
点积为0代表向量垂直.

---

2. 叉积
   数学公式：
   $$\mathbf{A}\times \mathbf{B}=\left|A\right|\left|B\right|\sin \theta =A.x\cdot B.y-A.y\cdot B.x$$

代码如下：

double Cross(Vector A,Vector B)
{
    
	return A.x * B.y - A.y * B.x;
}

A与B逆时针叉乘为正数，反之为负数。
如果叉积为0，则向量共线，可能同向，也可能反向。

---

1.4. 叉积的应用

• 计算三角形面积
  我们知道，三角形的面积公式可表示为$S=\frac{1}{2}ab\sin C$
  而$a\times b=|a||b|sinC$
  所以$S=\frac{1}{2}(a\times b)$

---

• 判断两个向量是否平行
  叉积为0代表向量平行

bool Parallel(Vector A,Vector B)
{
    
	return sgn(Cross(A, B)) == 0;
}

---

• 向量旋转
  假如我们需要将向量$(x,y)$旋转$\theta$度，则数学关系表达式为：
  $$x^{\prime }=xcos\theta -ysin\theta ,y^{\prime }=xsin\theta +ycos\theta$$

Vector Rotate(Vector A, float rad)
{
    
	return Vector (A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + y *cos(rad));
}

---

二、点与线

2.1. 直线的表达方式

直线表达形式有很多，重点说一般式和斜截式

• 一般式: $ax+by+c=0$
• 斜截式: $y=kx+b$

---

两点确定一条直线，所以我们将直线用两个点表示

struct Line
{
    
    Point p1, p2;
    Line() {
    }
    Line(Point p1, Point p2) :p1(p1), p2(p2) {
    }
    Line(Point p, double angle) //0<=angle<pi
    {
    
        p1 = p;
        if (sgn(angle - pi / 2) == 0)
        {
    
            p2 = p1 + Point(0, 1);
        }
        else
        {
    
            p2 = (p1 + Point(1, tan(angle)));
        }
    }
    //ax+by+c=0
    Line(double a, double b, double c)     
    {
    
        if (sgn(a) == 0)
        {
    
            p1 = Point(0, -c / b);
            p2 = Point(1, -c / b);
        }
        else if (sgn(b) == 0)
        {
    
            p1 = Point(-c / a, 0);
            p2 = Point(-c / a, 1);
        }
        else
        {
    
            p1 = Point(0, -c / b);
            p2 = Point(1, (-c - a) / b);
        }
    }
};

---

• 点与直线的位置关系
  我们把点与直线的关系分为点在直线的左侧，右侧和在直线上。

int Point_line_relation(Point p,Line v)
{
    
	int c=sgn(Cross(p - v.p1,v.p2-v.p1));  //计算叉积的正负从而加以判断
	if (c < 0) return -1;		//p在v左侧
	if (c  >0) return 1;		//p在v右侧
	return 0;				//p在v上
}

---

• 点到直线的距离
  可把点和线补成平行四边形或者三角形，这所求距离即为平行四边形或三角形的高。

double Dis_point_line(Point p,Line v)
{
    
	return Cross(p - v.p1, v.p2 - v.p1) / distance(v.p1, v.p2);
}

---

• 点在直线上的投影

double Point_line_proj(Point p, Line v)
{
    
	double k = Dot(v.p2 - v.p1, p - v.p1) / Len2(v.p2 - v.p1);
	//Len2为求p1p2长度的平方的函数（自定义），前面并未给出
	return v.p1 + (v.p2 - v.p1) * k;
}

---

• 点关于直线的对称点
  我们先借助上面的函数球场投影，再求出对称点

Point Point_line_symmetry()
{
    
	Point q = Point_line_proj(p.v);
	return Point(2 * q.x - p.x, 2 * q.y - p.y);		//两点中点坐标公式变形
}

---

2.2. 线段的表示

typedef Line Segment;		//与直线扩展到向量类似

---

• 点与线段的位置关系
  判断点P在直线v上，首先，用叉积判断是否共线，但这还不过，可能出现一下特殊情况：

此时，就需要再加一条判断条件：$P$与$v$的两个端点夹角是否为钝角(180°)

bool Point_on_seg(Point p,Line v)
{
    
	return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(Dot(p - v.p1, v.p2 - v.p1)) <= 0;
}

---

• 点到线段的距离
  如果p1,p2在P两侧，则最短距离为点到线段的垂直距离；
  但如果p1,p2在P同侧，则不存在垂直距离。

所以需先判断p1,p2是否在P同侧，再根据不同情况利用距离公式计算

Point Dis_point_seg(Point p,Segment v)
{
    
	if (sgn(Dot(v.p2 - v.p1, p - v.p1)) < 0 || sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0)
		return min(Distance(p.v1, p), Distance(p.v2, p));
	return Dis_point_line(p, v);
}

---