## 计算几何

线段属性

两条线段$\overrightarrow {P_0 P_1} \  and \  \overrightarrow {P_0 P_2}$,共端点p0,如何判断P0P1是P0P2的顺时针方向

$ \overrightarrow {P_0 P_1} and \overrightarrow {P_1 P_2}$,从p0到p2，P1是否为左转点

$\overrightarrow {P_0 P_1} and \overrightarrow {P_3 P_4}$相交吗？



叉乘的结果叫做叉积

$p_1 \times p_2 =det \left( \begin{matrix}  x_1 &  x_2\\  y1 & y_2  \\
\end{matrix} \right)  \\ =x_1y_2-x_2y_1=-p2 \times p1$



表示成带符号的平行四边形的面积



![image-20260308172838071](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260308172838071.png)

$p1 \times p2 \\ >0:p1 是 p2顺时针方向 \\ <0:逆时针 \\ =0:平行$

两条线段$\overrightarrow {P_0 P_1} \  and \  \overrightarrow {P_0 P_2}$,共端点p0,如何判断P0P1是P0P2的顺时针方向

$(p1-p0) \times (p2-p0)=(x1-x0)(y2-y0)-(x2-x0)(y1-y0) \\ >0 :顺时针 \\<0:逆时针 \\ =0 :平行$

$ \overrightarrow {P_0 P_1} and \overrightarrow {P_1 P_2}$,，从p0到p2，P1是否为左转点

![image-20260308175954321](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260308175954321.png)

$(p1-p0) \times (p2-p0)$

\> 0 p1在p2的顺时针方向,也就是说p1是左转的

\< 0 p1在p2 的逆时针方向，也就是说p1是右转的

=0 平行



$\overrightarrow {P_0 P_1} and \overrightarrow {P_3 P_4}$相交吗？

相互跨越

要么判断P1P2在P3P4两侧$P3P1 \times P3P4$,$P3P2 \times P3P4$

要么判断P3P4在P1P2两侧，$P1P2 \times P1P3$ 和 $P1P2 \times P1P4$

如果一条线段的端点在P1P2上面，也说是相交的

即$P1P2 \times P1P3$，再看P3的坐标是否在两点坐标之间

![image-20260308185920077](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260308185920077.png)







```
SEGMENTS-INTERSECT
d1 <-DIRECTION(p3,p4,p1)
d2 <- DIRECTION(P3,P4,P2)
d3 <- DIRECTION(P1,P2,P3)
d4 <- DIRECTION(P1,P2,P4)
If ((d1>0 and d2<0) or (d1<0 and d2>0) and ((d3 >0 amd d4<0) amd (d3<0 and d4 >0))
Then return TRUE
Else if d1=0 and ON-SEGMENT(P3,P4,P1)
	Then return TRUE
Else if d2=0 and ON-SEGMENT(P3,P4,P2)
	Then return TRUE
Else if d3=0 and ON-SEGMENT(P1,P2,P3)
	Then return TRUE
Else if d4=0 and ON-SEGMENT(P1,P2,P4)
	Then return TRUE
Else return FALSE


DIRECTION(pi,pj,pk)

​	Return (Pk-Pi) × (Pj-P)

ON-SEGMENT (Pi,pj,pk)

{

if min(xi,xj)≤xk≤max(xi,xj)and 
min(yi,yj)≤yk≤max(yi,jy) (避免平行x轴或者y轴情况)

}

​	Then return TRUE

ELSE return False


```



传统的计算线段相交的方法是什么？

传统方法和本方法的区别？

没有除法的精度损失，准确度也高，只有乘法、减法





 给定一个简单的凸多边形，求其面积

海伦公式：计算量大，精度低

$area(A,B,C)=\frac {(\overrightarrow {AB} )\times(\overrightarrow AC) }{2}$

以一个顶点P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形都在多边形内。

那么$A=\Sigma(A_i) i=1,2,...,N-2$

凹多边形呢？依然成立

“有向面积”Ai比“面积”S更本质



也可以分成N个三角形，以多边形内部的一个点为扇心。

那能否把扇心移到多边形之外呢？分成N个三角形也是可以的。把P0设置坐标原点

$A=\Sigma\left| \begin{matrix} X_i & Y_i\\ X_{i+1} & Y_{i+1} \\
\end{matrix} \right| /2 \ i=1...N $

给定一个简单多边形，求其重心

输入：顶点按逆时针顺序排列

输出：重心点C

三角形是否可以推广$\Sigma (x_i) /N,\Sigma(y_i)/N,(i=1...N)$

不行，多边形必须重量只在顶点上并且重量相同

如果是均匀分布的，只知道顶点坐标，怎么办

首先在内部找个顶点划分成N个三角形，然后根据三角形重心坐标找到各自的重心，那么也就相当于这个三角形的重量都聚集在这个重心上，也就转换成多边形的重心在顶点上的问题。就可以用加权平均去求。

求凸包（Convex Hull）

给出平面的一系列点$P1...Pn$,找到最小的凸包（凸多边形）来涵盖所有的点。

graham扫描法

找一个y最小的点P0，和其余点连线，按照和x轴夹角排序。

按叉乘得sin值根据角度排序

![image-20260308235239812](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260308235239812.png)

取出角度最小的前3个点P0P1P2，是否为左转，P1是左转，因此包含

因为P1P2P3是P2是右转的，是凹进去的，不在凸包上，所以排除P2

P1P3P4，P3左转，因此包含。

P3P4P5，右转，因此排除

P3P5P6

```
procedure GrahamScan(set Q)
let p0 be the point with the minimum y-coordinate
let <p, ..., Pm> be the remaining points in Q, sorted by the angle in counterclockwise order around P0
Top(S)<-0
Push(P0, S); Push(p1, S); Push(p2, S)
fori-3 to m do
	while the angle formed by points NextToTop(S), Top(S)
	and p; makes a non-left turn do
		Pop(S)
	Push(pi,S)
return S
```

$T(n)=\Theta(nlog n)+const\Theta(n)=\Theta(nlogn)$







Javir March算法



先找到y最低和y最高的点，然后相连，P0和x轴为绳子，围绕P0转，当遇到第一个点P1，换成P0P1为直线找，找到P3，然后以P1P3为直线找

![image-20260309001207434](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20260309001207434.png)

时间复杂度为O(n)