计算几何
计算几何
基础
向量叉乘
- A (x1,y1) B(x2,y2) A×B= x1y2-x2y1
- 叉乘判断向量位置,
- P×Q < 0 P在 Q 左侧,
- P×Q > 0 P在 Q 右侧,
- P×Q > 0 P与 Q 共线,
向量点乘
- A (x1,y1) B(x2,y2) A·B=x1x2+y1y2 a*b=|a||b|cos0
凸包
Jarvis步进法: O(nH)
- (点少时,H是点个数) 建议 用Graham法
思路：
- 纵坐标最小的那个点一定是凸包上的点，例如图上的 P0。
- 从 P0 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。
- 怎么找下一个点呢？利用夹角。假设现在已经找到 {P0，P1，P2} 了，要找下一个点：剩下的点分别和 P2 组成向量，设这个向量与向量P1P2的夹角为 β 。当 β 最小时就是所要求的下一个点了，此处为 P3 。
注意：
- 找第二个点 P1 时，因为已经找到的只有 P0 一个点，所以向量只能和水平线作夹角 α，当 α 最小时求得第二个点。
共线情况：如果直线 P2P3 上还有一个点 P4，即三个点共线，此时由向量P2P3 和向量P2P4 产生的两个 β 是相同的。我们应该把 P3、P4 都当做凸包上的点，并且把距离 P2 最远的那个点（即图中的P4）作为最后搜索到的点，继续找它的下一个连接点。
Graham法: O(n㏒n)
时间复杂度：O(n㏒n)
思路：Graham扫描的思想和Jarris步进法类似，也是先找到凸包上的一个点，然后从那个点开始按逆时针方向逐个找凸包上的点，但它不是利用夹角。
步骤：
把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。
把所有点的坐标平移一下，使 P0 作为原点，如上图。
计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。
（以上是准备步骤，以下开始求凸包）
以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：
连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。
如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。
当前点是凸包上的点，把它压入栈，执行步骤7。
检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。
最后，栈中的元素就是凸包上的点了。
以下为用Graham扫描法动态求解的过程：
应用
规则图形
判断点在线段上
点Q(x,y),线段P1P2 (x2-x1,y2-y1) 则向量共线 P1Q×P1P2 =0 即(x(y2-y1)-(x2-x1)y)= 0
并且 min(x1,x2) <=x<=max(x1,x2)&&min(y1,y2)<=y<=max(y1,y2)// 在线段内部
判断两线段相交
快速排斥实验
- 两个线段为对角线组成的矩形R和矩形T 若R,T不想交-->不想交,若相交进行跨立实验判断
- 方法: 假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3), Q2 = (x4, y4)，设矩形 R 的 x 坐标的最小边界为 RX1 = min(x1, x2)，RX2=max(x1,x2) ,RY1=min(y1,y2)以此类推，将矩形表示为 R = (RX1, RY1, RX2, RY2) 的形式，若两矩形相交，则相交的部分构成了一个新的矩形 F，我们可以知道 F 的 FX1 = max(RX1, TX1), FY2 = max(RY1, TY1),
- FX2 = min(RX2, TX2), FY2 = min(RY2, TX2)，得到 F 的各个值之后，只要判断矩形 F 是否成立就知道 R 和 T 到底有没有相交了，若 FX1 > FX2 或 FY1 > Fy1 则 F 无法构成，RT不相交，否则 RT相交
跨立实验(互相跨立)
- Q1P1×Q1P2 * Q1Q2×Q1Q1P2 >=0 && Q1P2×P1P2 * P1P2×Q2P2 >=0
线段与圆相交
三种情况, 第一种, 两个端点都在圆内,不相交,第二种,一个在圆外,一个圆内 一定相交;
第三种都在圆外,需要判断;
double x,y,r;
vector<pair<double,double> > V;
typedef pair<double,double> PAIR;
PAIR yuan;
bool judge(PAIR P)// 判断是否在圆内
{
if( (P.first-x)*(P.first-x) + (P.second-y)*(P.second-y) -r*r <=0)
return 1;
return 0;
}
bool Judis(PAIR P1,PAIR P2,double R) //线段与圆的关系
{
if(judge(P1)&&judge(P2))//都在圆内 不相交
return false;
if(!judge(P1)&&judge(P2)||judge(P1)&&!judge(P2))//一个圆内一个圆外 相交
return true;
double A,B,C,dist1,dist2,angle1,angle2;//Ax+By+C=0;//(y1-y2)x +(x2-x1)y +x1y2-y1x2=0
if(P1.first==P2.first)
A=1,B=0,C= -P1.first;
else if(P1.second==P2.second)
A=0,B=1,C= -P1.second;
else
{
A = P1.second-P2.second;
B = P2.first-P1.first;
C = P1.first*P2.second - P1.second*P2.first;
}
dist1 = A * yuan.first + B * yuan.second + C;
dist1 *= dist1;
dist2 = (A * A + B * B) * R * R;
if (dist1 > dist2) return false;//点到直线距离大于半径r 不相交
angle1 = (yuan.first - P1.first) * (P2.first - P1.first) + (yuan.second - P1.second) * (P2.second - P1.second);
angle2 = (yuan.first - P2.first) * (P1.first - P2.first) + (yuan.second - P2.second) * (P1.second - P2.second);
if (angle1 > 0 && angle2 > 0) return true;//余弦都为正，则是锐角 相交
return false;//不相交
}
判断线段和直线相交
- 化成线段相交
判断点在矩形内
- 点在矩形对角线坐标内
判断线段/折现/多边形在矩形内
- 转换为所有点在矩形内
判断矩形在矩形内
- 上下界问题
判断圆在矩形内
- 圆心在矩形内
- 圆的半径R小于min(圆心到四个边距离d)
不规则图形
判断点在多边形
- 多边形问题,射线法
代码:
https://paste.ubuntu.com/26455451/
#include <stdio.h>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const double ESP=1e-6;
const double INFINV=1e10;
struct LineSegment{
struct Point{
double x,y;
};
Point Pt1,Pt2;
typedef vector<Point> Vector;
// 叉乘 |p0p1| x |p0p2|
double Multiply(Point p1,Point p2,Point p0)
{
return ( (p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y));
}
// 点是否在边上
bool IsOnline (Point P,LineSegment line)
{
return( ( fabs( Multiply(line.Pt1,line.Pt2,P) ) )<ESP && ( (P.x-line.Pt1.x)*(P.x-line.Pt2.x) <=0 )&&
( (P.y-line.Pt1.y)*(P.y-line.Pt2.y) <=0 ) ) ;
}
bool Intersect(LineSegment L1,LineSegment L2)
{
return( (max(L1.Pt1.x, L1.Pt2.x) >= min(L2.Pt1.x, L2.Pt2.x)) &&
(max(L2.Pt1.x, L2.Pt2.x) >= min(L1.Pt1.x, L1.Pt2.x)) &&
(max(L1.Pt1.y, L1.Pt2.y) >= min(L2.Pt1.y, L2.Pt2.y)) &&
(max(L2.Pt1.y, L2.Pt2.y) >= min(L1.Pt1.y, L1.Pt2.y)) &&
(Multiply(L2.Pt1, L1.Pt2, L1.Pt1) * Multiply(L1.Pt2, L2.Pt2, L1.Pt1) >= 0) &&
(Multiply(L1.Pt1, L2.Pt2, L2.Pt1) * Multiply(L2.Pt2, L1.Pt2, L2.Pt1) >= 0) );
}
bool main_Judge_Polygon(const Vector& poly,Point P)
{
int n=poly.size();
int count=0;
LineSegment line;
line.Pt1=P;
line.Pt2.y=P.y;
line.Pt2.x= -INFINV;
for(int i=0;i<n;i++)
{
LineSegment side;
side.Pt1=poly[i];
side.Pt2=poly[ (i+1) % n];
if( IsOnline(P,side) )
{// 若点在边上 直接返回
return true;
}
if( fabs(side.Pt1.y-side.Pt2.y) <ESP )
{//判断side是否平行于X轴
continue;
}
if( IsOnline(side.Pt1, line) )
{
if( side.Pt1.y > side.Pt2.y )
count++;
}
else if( IsOnline(side.Pt2,line) )
{
if( side.Pt2.y >side.Pt2.y)
count++;
}
else if( Intersect (line ,side))
{
count++;
}
}
if(count%2==1)
return false;
return true;
}
}JK;
int main()
{
return 0;
}