精华内容
下载资源
问答
  • 计算几何

    千次阅读 2019-01-04 16:55:10
    1.高中计算几何基础知识 2.深刻的认识到计算几何用向量而不用解析几何。 3.图形的记录 (1):点,向量。这两个是差不多的。 (2):线:直线上一点和直线的方向向量。 (3):线段:只需要记录左右端点即可。...

    OI中少有的以高中知识为主的版块。
    1.高中计算几何基础知识
    2.深刻的认识到计算几何用向量而不用解析几何。
    3.图形的记录
    (1):点,向量。这两个是差不多的。
    (2):线:直线上一点和直线的方向向量。
    (3):线段:只需要记录左右端点即可。。。。

    4.正弦定理:
    a S i n A = b S i n B = c S i n C = 2 R \frac {a}{Sin A} = \frac {b}{SinB}=\frac c{SinC}=2R SinAa=SinBb=SinCc=2R
    R R R为三角形的外接圆半径。
    5.余弦定理:
    a 2 = b 2 + c 2 − 2 C o s A   b c a^2=b^2+c^2-2CosA\ bc a2=b2+c22CosA bc
    C o s A = b 2 + c 2 − a 2 2 b c Cos A=\frac {b^2+c^2-a^2}{2bc} CosA=2bcb2+c2a2
    6.判断点在直线的哪端
    计算叉积,正为逆时针,负为逆时针。
    7.C++的计算几何函数:
    s i n , c o s , t a n sin , cos , tan sin,cos,tan最基础
    a t a n ( x ) atan(x) atan(x) 返回的是 [ − π / 2 , + π / 2 ] [-\pi/2,+\pi/2] [π/2,+π/2]的弧度值
    a t a n ( y , x ) atan(y,x) atan(y,x)返回的是(x,y)在的单位圆中以x正半轴为起始边的弧度值 [ − π , π ] [-\pi,\pi] [π,π]
    a c o s ( x ) acos(x) acos(x)Principal arc cosine of x, in the interval [0,pi] radians.
    a s i n ( x ) asin(x) asin(x)Principal arc sine of x, in the interval [-pi/2,+pi/2] radians.
    8.基础模板

    #include<bits/stdc++.h>
    using namespace std;
    
    struct Point
    {
    	double x,y;
    	Point(double x,double y):x(x),y(y){}
    	Point operator +(const Point B)const{ return Point(x+B.x,y+B.y); }
    	Point operator -(const Point B)const{ return Point(x-B.x,y-B.y); }
    	Point operator *(const double B)const{ return Point(x*B,y*B); }
    	double Cross(const Point B)const{ return x*B.y-y*B.x; }
    	double Dot(const Point B)const{ return x*B.x+y*B.y; }
    	double Len()const{ return sqrt(Dot(*this)); }
    	double Angle(const Point B)const{ return acos(Dot(B)/Len()/B.Len()); }
    };
    
    int main()
    {
    	sin(0);
    }
    

    计算几何不要怕代码长,严谨直接不卡精度最重要。

    9.快速排斥实验与跨立实验
    规定「一条线段的区域」为以这条线段为对角线的,各边均与某一坐标轴平行的矩形所占的区域,那么可以发现,如果两条线段没有公共区域,则这两条线段一定不相交。
    这快速排斥好像没啥用。。。。。
    相反跨立实验就很有用了,线段相交的充要条件是A线段的两端点在B线段两端且B线段的两端点在A线段两端。
    Code:

    //线段规范相交判定
    bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)
    {
        double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1),
               c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
        return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
    }
    

    这个dcmp是用来防止卡精度的。

    int dcmp(double x)
    { //三态函数,克服浮点数精度陷阱,判断x==0?x<0?x>0?
        if (fabs(x) < eps)
            return 0;
        else
            return x < 0 ? -1 : 1;
    }
    

    10:判断一点是否在任意多边形内部
    (1)光线投射算法
    我们考虑以该点为端点引出一条射线,如果这条射线与多边形有奇数个交点,则该点在多边形内部,否则该点在多边形外部,我们简记为奇内偶外。这个算法同样被称为奇偶规则 ,就具体实现而言,可以把射线变成长的线段,然后对每一条边做跨立实验即可。
    (2)回转数算法
    我们把该点与多边形的所有顶点连接起来,计算相邻两边夹角的和。注意这里的夹角是有方向的。如果夹角和为0 ,则这个点在多边形外,否则在多边形内。

    11.求两条直线的交点
    这个用向量也可以解决。
    你们还是去看OI-WIKI
    直接上公式:
    直线 P ⃗ + k u ⃗ \vec{P} + k\vec{u} P +ku 与直线 Q ⃗ + k v ⃗ \vec{Q}+k\vec{v} Q +kv 的交点向量为 Q ⃗ + C r o s s ( u ⃗ , Q ⃗ − P ⃗ ) C r o s s ( u ⃗ , v ⃗ ) ∗ v ⃗ \vec{Q}+\frac {Cross(\vec{u}, \vec{Q}-\vec{P})}{Cross(\vec{u},\vec{v})}*\vec{v} Q +Cross(u ,v )Cross(u ,Q P )v
    解释:(我是盗图的)在这里插入图片描述
    Code:

    Point GetLineIntersection(Point P, Vector v, Point Q, Vector w)
    {
        Vector u = P - Q;
        double t = Cross(w, u) / Cross(v, w);
        return P + v * t;
    }
    

    有类似线代做法,简单无脑:
    在这里插入图片描述
    在这里插入图片描述
    12 求任意多边形的面积
    选一个多边形的点为原点,每个点对于这个点有一个向量,将每一条边上两个端点的向量按同一个方向求叉积和的绝对值再除二。

    圆与直线相关
    13.求直线与圆的交点
    首先判断直线与圆的位置关系。如果直线与圆相离则无交点,若相切则可以利用切线求出切点与半径所在直线,之后转化为求两直线交点。

    若有两交点,则可以利用勾股定理求出两交点的中点,然后沿直线方向加上半弦长即可。
    14.求两圆交点
    判断位置关系后,如果有两个交点,就用余弦定理,然后就完了。

    放一个毒瘤题吧: CF 780H

    15.维护可插入的凸包CF 70D
    set维护极角序,插入删除点即可。

    AC Code:

    #include<bits/stdc++.h>
    #define eps 1e-5
    using namespace std;
    
    struct Point
    {
    	double x,y,ag;
    	Point (double x=0,double y=0):x(x),y(y){}
    	Point operator +(const Point &B)const{ return Point(x+B.x,y+B.y); }
    	Point operator -(const Point &B)const{ return Point(x-B.x,y-B.y); }
    	double operator *(const Point &B)const{ return x*B.y-y*B.x; }
    }P[3],O;
    
    struct node
    {
    	bool operator ()(const Point &A,const Point &B)
    	{
    		return A.ag < B.ag;
    	}
    };
    set<Point,node>st;
    set<Point,node>::iterator pre,nxt,ppre,nnxt;
    
    int main()
    {
    	int q,op,x,y;
    	scanf("%d",&q);
    	q-=3;
    	scanf("%d%lf%lf",&op,&P[0].x,&P[0].y);
    	scanf("%d%lf%lf",&op,&P[1].x,&P[1].y);
    	scanf("%d%lf%lf",&op,&P[2].x,&P[2].y);
    	O.x = (P[0].x + P[1].x + P[2].x) / 3;
    	O.y = (P[0].y + P[1].y + P[2].y) / 3;
    	for(int i=0;i<3;i++)
    		P[i]=P[i]-O,P[i].ag=atan2(P[i].y,P[i].x);
    	st.insert(P[0]),st.insert(P[1]),st.insert(P[2]);
    	for(;q--;)
    	{
    		scanf("%d%lf%lf",&op,&P[0].x,&P[0].y);
    		P[0] = P[0] - O;	
    		P[0].ag = atan2(P[0].y,P[0].x);
    		if(op == 1)
    		{
    			nxt = st.lower_bound(P[0]) , pre = nxt;
    			if(pre == st.begin()) pre = st.end();
    			pre --;
    			if(nxt == st.end()) nxt = st.begin();
    			if(((*nxt)-(*pre)) * ((*nxt)-P[0]) > eps)
    			{
    				for(;st.size()>=2;st.erase(*nxt),nxt=nnxt)
    				{
    					nnxt = nxt , nnxt ++;
    					if(nnxt == st.end()) nnxt = st.begin();
    					if(((*nnxt)-(*nxt)) * ((*nxt)-P[0]) < eps) break;
    				}
    				
    				for(;st.size()>=2;st.erase(*pre),pre=ppre)
    				{
    					ppre = pre;
    					if(ppre == st.begin()) ppre = st.end();
    					ppre --;
    					if((P[0] - (*pre)) * ((*pre) - (*ppre)) < eps) break;
    				}
    				st.insert(P[0]);
    			}
    		}
    		else
    		{
    			nxt = st.lower_bound(P[0]) , pre = nxt;
    			if(pre == st.begin()) pre = st.end();
    			pre --;
    			if(nxt == st.end()) nxt = st.begin();
    			if(((*nxt)-(*pre)) * ((*nxt)-P[0]) > eps)
    				puts("NO");
    			else 
    				puts("YES");
    		}
    	}
    }
    

    16.半平面交
    我的模板
    17.旋转卡壳
    18.三维凸包
    19.Pick定理、欧拉公式和圆的反演
    20.最小圆覆盖
    21.圆的公切线

    展开全文
  • 计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何
  • 计算几何算法与应用计算几何算法与应用
  • 计算几何-源码

    2021-02-21 10:53:09
    计算几何
  • 很详细的计算几何资源集合,囊括了几乎所有的计算几何书籍,包括《计算几何导论》、《计算几何基础》,很经典的计算几何书籍
  • 计算几何.rar计算几何.rar计算几何.rar计算几何.rar计算几何.rar计算几何.rar计算几何.rar计算几何.rar
  • ㈠ 点的基本运算 1. 平面上两点之间距离 1 2. 判断两点是否重合 1 3. 矢量叉乘 1 4. 矢量点乘 2 5. 判断点是否在线段上 2 6. 求一点饶某点旋转后的坐标 2 7. 求矢量夹角 2 。。。。
  • 计算几何资料

    2018-09-25 02:07:29
    ACM计算几何资料,从基本到全面的介绍计算几何题,有模板,全!
  • 计算几何PPT

    2016-07-08 09:10:48
    计算几何课件
  • 计算几何入门

    千次阅读 2017-02-02 17:02:49
    计算几何

    以下内容由各位大神的博客提取出来

    矢量的概念

        矢量。如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点,我们可以把它称为矢量(vector)p2。
    

    矢量的加减

        设二维矢量P = ( x1, y1 ),Q = ( x2 , y2 ),则矢量加法定义为: P + Q = ( x1 + x2 , y1 + y2 ),同样的,矢量减法定义为: P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P,P - Q = - ( Q - P )。
    

    矢量叉积

         计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 ),Q = ( x2, y2 ),则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积,即:P × Q = x1*y2 - x2*y1,其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下,本文下述算法中所有的点都看作矢量,两点的加减法就是矢量相加减,而点的乘法则看作矢量叉积。叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:
        若 P × Q > 0 , 则P在Q的顺时针方向。
        若 P × Q < 0 , 则P在Q的逆时针方向。
        若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。
    

    折线段的拐向判断

        折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:
        若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。
        若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。
        若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。
    

      具体情况可参照下图:
    这里写图片描述

        设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内。前者保证Q点在直线P1P2上,后者是保证Q点不在线段P1P2的延长线或反向延长线上,对于这一步骤的判断可以用以下过程实现:
    
    bool ON-SEGMENT(int pi,int pj,int pk){
    //pi,pj,pk三个点
      if(min(xi,xj)<=xk<=max(xi,xj) && min(yi,yj)<=yk<=max(yi,yj))
      
      return true;
    
      else return false;
    }

    判断两线段是否相交

     我们分两步确定两条线段是否相交:
     1.快速排斥试验:
         设以线段 P1P2 为对角线的矩形为 R,设以线段 Q1Q2 为对角线的矩形为 T,若 R、T 不相交,则两线段不可能相交
         假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3), Q2 = (x4, y4),设矩形 R 的 x 坐标的最小边界为 minRX = min(x1, x2),以此类推,将矩形表示为 R = (minRX, minRY, maxRX, maxRY) 的形式,若两矩形相交,则相交的部分构成了一个新的矩形 F,如图所示,我们可以知道 F 的 minFX = max(minRX, minTX), minFY = max(minRY, minTY), maxFX = min(maxRX, maxTX), maxFY = min(maxRY, maxTX),得到 F 的各个值之后,只要判断矩形 F 是否成立就知道 R 和 T 到底有没有相交了,若 minFX > maxFX 或 minFY > maxFy 则 F 无法构成,RT不相交,否则 RT相交。具体如图所示:   
    

    这里写图片描述

    2. 跨立试验:
        如果两线段相交,则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是:( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示:
    

    这里写图片描述

    总的效果如下图:
    

    这里写图片描述

    判断线段和直线是否相交

        有了上面的基础,这个算法就很容易了。如果线段P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。
    

    判断矩形是否包含点

      只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。
      
    

    判断线段、折线、多边形是否在矩形中

    因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。
    

    判断点是否在多边形中

        判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左(右)方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。
        但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中,L和多边形的顶点相交,这时候交点只能计算一个;在图(b)中,L和多边形顶点的交点不应被计算;在图(c)和(d) 中,L和多边形的一条边重合,这条边应该被忽略不计。如果L和多边形的一条边重合,这条边应该被忽略不计。
    

    这里写图片描述

        为了统一起见,我们在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。
        其中做射线L的方法是:设P'的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),则P和P'就确定了射线L。
    

    判断线段是否在多边形内

        线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能为凹,所以这不能成为判断的充分条件。如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交。
        线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是否包含于多边形内部(反例见图b)。 
    

    这里写图片描述

        因此我们可以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序(X坐标小的排在前面,对于X坐标相同的点,Y坐标小的排在前面,这种排序准则也是为了保证水平和垂直情况的判断正确),这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形内。 
    

    证明如下:

        命题1:
        如果线段和多边形的两相邻交点P1 ,P2的中点P' 也在多边形内,则P1, P2之间的所有点都在多边形内。
        证明:
        假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P'之间,因为多边形是闭合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P'属于多边性内部,P1-Q-P'完全连续,所以P1Q和QP'一定跨越多边形的边界,因此在P1,P'之间至少还有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕。
        由命题1直接可得出推论:
        推论2:
        设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多边形内。
        在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段上就可以了。
    

    至此我们得出算法如下:

        if( 线端PQ的端点不都在多边形内 )
           return false;
        点集pointSet初始化为空;
        for( 多边形的每条边s ){
             if 线段的某个端点在s上
                将该端点加入pointSet;
             else if s的某个端点在线段PQ上
                将该端点加入pointSet;
             else if s和线段PQ相交 // 这时候已经可以肯定是内交了
                return false;
        }
        将pointSet中的点按照X-Y坐标排序;
        for() pointSet中每两个相邻点 pointSet[i] , pointSet[i+1] ){
          if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
               return false;
         }
        return true;
    
        这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n,所以最多是常数级的复杂度,几乎可以忽略不计。因此算法的时间复杂度也是O(n)。 
    
    展开全文
  • ACM 计算几何

    2010-11-08 23:02:58
    计算几何
  • MATLAB计算几何

    2021-06-15 18:27:08
    MATLAB计算几何,包括几何图元的关系运算、点集的凸包、Delaunay剖分和Voronoi图等内容。
  • 计算几何.pptx

    2018-05-16 16:10:42
    计算几何上课课件,ACM算法学习,计算几何入门,算法资源
  • Type Segment2D::cross(const Point2D& p) const { return (p - s).X(t - s); } bool Segment2D::lineCross(const Segment2D& other) const { return threeValue(cross(other.s)) * threeValue(cross...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 180,119
精华内容 72,047
关键字:

计算几何