【蒟蒻计算几何】叉积

这几天闲来无事去学习了一下计算几何,发现其实不(sang)是(xin)太(bing)难(kuang):stuck_out_tongue:
今天就重点介绍一下简单的叉积及其简单的运用(毕竟作为蒟蒻,难的搞不来啊)

什么是计算几何?

“对几何外形信息的计算机表示、分析和综合”——福雷斯特

其实所谓计算几何,就是用计算机去解决不同维度上的几何问题,而我们要做的,就是设计一套算法,让计算机去分析和解决一系列的几何问题。

一些基本知识

坐标的存储

一般来说,计算几何都涉及到了小数坐标,这时开一个含两个double类型的结构体就比较稳健,我一般的定义如下:

struct node//定义一个点 
{
    double x,y;
}a[11000];
线段的存储

聪明绝顶的你肯定已经想到了,线段就是包含两个点的一个结构体,所以我一般的定义如下

struct line//定义一条线
{
    node p1,p2;
} list[11000];

叉积

终于到今天的主角—叉积了!:stuck_out_tongue_closed_eyes:
那么什么是叉积呢?叉积其实是两个矢量模的乘积再乘夹角正弦,经过推导可以发现两个向量A(x1,y1),B(x2,y2)的叉积为:
x1*y2-x2*y1
先丢出代码:


double multi(node p1,node p2,node p0)//计算叉积,p1,p2,p0都为点
{
    double x1,y1,x2,y2;
    x1=p1.x-p0.x;
    y1=p1.y-p0.y;
    x2=p2.x-p0.x;
    y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}

这就是传说中的叉积计算了!是不是很短呢,那就让我们来理解一下这个multi函数吧。

由于叉积是向量间的运算,大家都知道向量可以用末坐标减去首坐标得到,那么其实multi函数计算的就是向量A(x1,y1)与向量B(x2,y2)的叉积。

对于multi函数的意义,首先multi的正负是有特殊含义的:以p0为参考点,如果multi大于0,则p2在p1的逆时针方向,反正,如果multi小于0,则p2在p1的顺时针方向,特殊的,当multi等于0,p1、p2、p0三点共线。
cj1.PNG

其次,multi的值也是有含义的!通过后面的学习你就会发现,multi的绝对值就是以p0、p1、p2三点构成的三角形的面积的两倍!利用这个规律,可以完成很多与计算几何有关的题目。

一些简单的运用

【caioj 1212 判断线段相交(跨立实验)】

题目描述
【题意】
有n条线段(编号为1~n),按1~n的顺序放在二维坐标系上(就是先放1号,再放2号……),
要求输出最上面的那些线段的编号(就是没有其他线段压在它上面的那些线段)
【输入格式】
第一行第一个数n( 1 <= n <= 10000)表示这组数据有n条线段。
下来n行,每行两个坐标,表示第i条线段的两个端点。
【输出格式】
一行。输出最上面的线段的编号(从小到大)。相邻两个编号用空格隔开,最后一个编号没有空格。
【样例1输入】
5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
【样例1输出】
2 4 5
【样例2输入】
3
0 0 1 1
1 0 2 1
2 0 3 1
【样例2输出】
1 2 3

这道题很明显要让我们判断任意两条线段是否相交,这就要用到刚刚讲到的叉积的第一种用法了!

很明显,相交有两种情况,相交且穿过和相交但不穿过(如下图)cj3.PNG

我们首先先讨论第一种情况,如何判断两条直线相交且穿过?
cj.PNG
如上图,先假设两条直线为L1和L2,每条直线的两个端点分别为p1和p2,那么如果以
L1.p1为一个参考点,如果L1.p2在L2.p1与L2.p2中间;再以L2.p1为参考点,如果L2.p2在L1.p1与L1.p2中间,那么就可以判断L1与L2相交且穿过(如下图)
cj2.PNG

这种情况非常好理解吧,下一种情况就更加简单了,仅需讨论哪三个点在一条“直线”上(毕竟不穿过,所以必有三点共线),然后判断一下
不穿过的那个点是否在一条“线段”上(如下图)
cj5.PNG
具体代码如下

    double check(line l1,line l2)//判断是否相交 
    {
        if(multi(l2.p1,l1.p2,l1.p1)*multi(l1.p2,l2.p2,l1.p1)>0)//判断以L1.p1为基准,L1.p2是否在L2.p1与L2.p2中间
        if(multi(l1.p1,l2.p2,l2.p1)*multi(l2.p2,l1.p2,l2.p1)>0)//判断以L2.p1为基准,L2.p2是否在L1.p1与L2.p2中间
        return true;//大部分情况下,能判断两直线相交   if(multi(l2.p1,l1.p1,l1.p2)==0)if(mymin(l1.p1.x,l1.p2.x<=l2.p1.x)if(mymax(l1.p1.x,l1.p2.x)>=l2.p1.x)return true;
        if(multi(l2.p2,l1.p1,l1.p2)==0)if(mymin(l1.p1.x,l1.p2.x<=l2.p2.x)if(mymax(l1.p1.x,l1.p2.x)>=l2.p2.x)return true;
        if(multi(l1.p1,l2.p1,l2.p2)==0)if(mymin(l2.p1.x,l2.p2.x<=l1.p1.x)if(mymax(l2.p1.x,l2.p2.x)>=l1.p1.x)return true;
        if(multi(l1.p2,l2.p1,l2.p2)==0)if(mymin(l2.p1.x,l2.p2.x<=l1.p2.x)if(mymax(l2.p1.x,l2.p2.x)>=l1.p2.x)return true;
        //判断两条直线相交且一条直线端点在另一条直线上 
        return false;
    }

主程序就很简单了,一条一条边读入,读入第i条边时判断他与前i-1条边是否相交,若相交,这之前的边j被盖住,判断数组bo【j】=1。最后统计bo【i】==0的边就好啦
附上完整代码:

#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
struct node//定义一个点 
{
    double x,y;
};

struct line//定义一条线 
{
    node p1,p2;
} list[11000];

int a[11000]={0};
bool bo[11000]={0};
int i,j,k,m,n,o,p,js,jl,jk,len;

//================================
double mymax(double x,double y)//求max 
{
    if(x>y)return x;
    else return y;
}

double mymin(double x,double y)//求min 
{
    if(x<y)return x;
    else return y;
}

//=================================

double multi(node p1,node p2,node p0)//计算叉积:而且值为三点构成三角形的面积的两倍 
{
    double x1,y1,x2,y2;
    x1=p1.x-p0.x;
    y1=p1.y-p0.y;
    x2=p2.x-p0.x;
    y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}

double check(line l1,line l2)//判断是否相交 
{
    if(multi(l2.p1,l1.p2,l1.p1)*multi(l1.p2,l2.p2,l1.p1)>0)
    if(multi(l1.p1,l2.p2,l2.p1)*multi(l2.p2,l1.p2,l2.p1)>0)
    return true;//大部分情况下,判断两直线相交 
    if(multi(l2.p1,l1.p1,l1.p2)==0)if(mymin(l1.p1.x,l1.p2.x)<=l2.p1.x)if(mymax(l1.p1.x,l1.p2.x)>=l2.p1.x)return true;
    if(multi(l2.p2,l1.p1,l1.p2)==0)if(mymin(l1.p1.x,l1.p2.x)<=l2.p2.x)if(mymax(l1.p1.x,l1.p2.x)>=l2.p2.x)return true;
    if(multi(l1.p1,l2.p1,l2.p2)==0)if(mymin(l2.p1.x,l2.p2.x)<=l1.p1.x)if(mymax(l2.p1.x,l2.p2.x)>=l1.p1.x)return true;
    if(multi(l1.p2,l2.p1,l2.p2)==0)if(mymin(l2.p1.x,l2.p2.x)<=l1.p2.x)if(mymax(l2.p1.x,l2.p2.x)>=l1.p2.x)return true;
    //判断两条直线相交且一条直线端点在另一条直线上 
    return false;
}
//==================================
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&list[i].p1.x,&list[i].p1.y,&list[i].p2.x,&list[i].p2.y);
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        if(check(list[i],list[j]))//判断相交 
        {
            bo[i]=1;
            break;
        }
    }
    len=0;
    for(int i=1;i<=n;i++)if(bo[i]==0)a[++len]=i;
    for(int i=1;i<len;i++)printf("%d ",a[i]);
    printf("%d\n",a[len]);
}

【caioj 1213 面积】

题目描述
【题意】
在一个平面坐标系上随意画一条有n个点的封闭折线(按画线的顺序给出点的坐标),保证封闭折线的任意两条边都不相交。最后要计算这条路线包围的面积。cj6.png
【输入格式】
第一行整数 n (3 <= n <= 1000),表示有n个点。
下来n行,每行两个整数x(横坐标)和y(纵坐标),表示点坐标(-10000<x,y<=10000)。
【输出格式】
一行一个实数,即封闭折线所包围的面积(保留4位小数)。
【样例1输入】
4
2 1
5 1
5 5
2 5
【样例1输出】
12.0000
【样例2输入】
5
2 1
5 1
3 2
5 3
2 3
【样例2输出】
4.0000

这道题对比上一道题就简单很多了,这道题要用到叉积的第二种用法——计算面积!对于任意一个多边形,只要以一号点p1为参考点,枚举任意两个相邻的点pi和pi-1(i>=3),带符号计算p1和pi、pi-1所构成的三角形的面积(multi(pi,pi-1,p1)/2),累加取绝对值就是答案了。

至于为什么要带符号运算,请看我用下面这幅图演示cj7.PNG
对于这个多边形,首先先加上multi(p3,p2,p1)/2的值(由于p3在p2的逆时针方向,所以为正)即为加上了红色部分cj8.PNG
然后再加上multi(p4,p3,p1)/2的值(由于p4在p3的顺时针方向,所以为负)即为减去了绿色部分
cj9.PNG
然后再加上multi(p5,p4,p1)/2的值(由于p5在p4的逆时针方向,所以为正)即为加上了黄色部分,就是答案了cj10.PNG

最后附上代码

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    double x,y;
}a[11000];

int i,j,k,m,n,o,p,js,jl;
double ans;

double multi(node p1,node p2, node p0)
{
    double x1=p1.x-p0.x;
    double y1=p1.y-p0.y; 

    double x2=p2.x-p0.x;
    double y2=p2.y-p0.y;

    return(x1*y2-x2*y1); 
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);

    for(int i=2;i<=n;i++)
    {
        ans=ans+multi(a[i],a[i-1],a[1]);
    }
    ans=ans/2.0;
    if(ans<0)ans=-ans;

    printf("%0.4lf",ans);
    return 0;
}

结语

通过上面的学习和例题,是不是已经初步了解了计算几何的一点点精(皮)髓(毛)呢,希望你能有所收获,在计算几何的路上越走越远吧(蒟蒻的我可能是走不下去了)
最后Orz各位大佬,写的不好请各位神犇提出建议和意见,感谢你的阅读:neckbeard:

Last modification:March 15th, 2019 at 01:58 pm
If you think my article is useful to you, please feel free to appreciate

11 comments

  1. 2bno_1

    聪明绝♂顶?

  2. 卢本伟

    我是博主的同学
    这篇文章改变了我的一生。
    当我在打lol时,看到了一个残血的人,我就冲上去,把他秒了,博主说我抢了他五杀,我说我抢了你吗比的五杀,我们吵了起来,后来我才知道,他身披国旗,是真的没有开挂。

  3. 无产阶级战士

    (1)“三个代表”是我们的立党之本。我们党自成立之日起,就是走在中国社会发展前列的先进政党。我们的党章规定,中国共产党的中国工人阶级的先锋队。我们党的历史使命、历史地位、历史作用,始终是与党的先进性联系在一起的。什么时候坚持并做到了这样“三个代表”,我们党就兴旺发达,就得到人民群众的拥护,就经得起任何风浪的冲击。什么时候如果偏离或投有完全做到“三个代表”,就会出这样那样的问题,人民就会不满意,党就会遇到困难和曲折。

    (2)“三个代表”是我们的执政之基。我们党的执政地位是历史赋予的、人民赋予的。我们党能够执政、并且能够执好政的基础,从根本上来说,就在于能够代表中国先进生产力的发展要求,代表中国先进文化的前进方向,代表中国:最广大人民的根本利益。我们党执政的内容和任务,就是要不断解放和发展中国社会的生产力,增强综合国力,推进社会发展;就是要不断建设和发展面向现代化、面向世界、面向未来的民族的、科学的、大众的社会主义文化,培育“四有”公民,弘扬民族精神;就是要全心全为人民服务,维护最广大人民的根本利益,不断满足人民群众日益增长的物质文化生活需要。面向新的世纪,我们党治国理政的任务更加艰巨,所要解决的问题也更多、更复杂。只有坚持“三个代表”,当好“三个代表”,我们才能始终用好人民赋予的执政权力,无愧于历史赋予的执政地位;才能不断提高我们的执政水平,巩固我们的执政基础。

    (3)“三个代表”是我们的力量之源。我们党建党之初,只有几十个党员。为什么能够不断发展壮大,成为今天拥有6100多万党员的大党?为什么能够战胜曾经比自己强大得多的国内外敌人,建立起社会主义的新中国?为什么能够在一穷二白的基础上,取得经济和社会发展的巨大成就,解决了12亿人的温饱问题;在本世纪末进入了小康社会?为什么虽然也犯过错误,有过曲折,但始终“岁老根弥壮,阳骄叶更阴”,经得起各种风浪、磨难的考验,得到人民群众的拥护和支持?所有这一切,就是于我们党能够始终从根本上促进中国社会生产力的发展,推动中国文化的进步,切切实实地为人民办实事、谋利益。这是我们全部力量的源泉所在,也是我们不断成功和发展的奥秘所在。

  4. QAQ

    我是博主女朋友
    这篇博客改变了他的一生。
    当我五杀被抢后,我非常绝望,去酒吧喝酒准备一醉不醒,这时,我遇见了他,他看了这篇博客后,学会了赚钱。他找到我后,和我***,之后我放弃了轻生的想法,成为了他的女朋友,虽然我被日后得知,他还有几万个女朋友,但我不在乎,因为他在我绝望的时候拯救了我。现在他回北大读书,我任然天天开他的劳斯莱斯去学校看望他,感觉人生变得如此幸福!!!

  5. 钟良锋

    这篇博客改变了我的一生。
    当我考上北大之后,因为学费交不起,没有办法去北京读书,我愤怒的撕掉了录取通知书,和小伙伴们去网吧电竞去了。这时候,小伙伴们介绍我上了jv%ruo%.co%m,不仅不花钱,学会了以后还能赚钱,不一会我就赚了几十亿,买了劳斯莱斯,找了七八十万个女朋友,北大校长都专门过来,请我回去读书。
    感谢博主

  6. Robin W

    Orz,太强了

  7. FlyInTheSky

    博主让我10min就学会了计算几何!太厉害了

  8. Zm J

    你搞的这个文章啊,Exited!
    要提高姿势水平

  9. cckk4467

    Orz,太强了

  10. cckk4467

    Orz,Orz

  11. FlyInTheSky

    Orz,太强了

Leave a Comment Cancel reply