计算几何基础----向量_向量几何计算

一.向量及其运算

1.向量运算基础

A = (x1,y1) = x1 i + y1 j ; B = (x2,y2) = x2 i + y2 j;

（1）.运算重载
  A + B = (x1+x2,y1+y2)
  A - B = (x1 - x2,y1 - y2)
  p*A = (px1,py1)
  A/p = (x1/p,y1/p)

（2）.已知点P1(x1,y1) P2(x2,y2)  向量P1P2 = (x2-x1,y2-y1)

（3）.A的模长 = sqrt(x1*x1 + y1*y1)

（4）.向量点乘 = 数值

A 点 B = x1*x2 + y1*y2 = |A| *| B| *cos<A,B>

A 点 B/|A| = B在A向量上的投影

cos<A,B> = A·B / |A|*|B| = x1x2 + y1y2/|A|*|B|  <A,B> = acos(cos)

若向量AB均非零且垂直：x1*x2 + y1*y2 = 0

若向量平行 A = r*B ：x1y2 - x2y1 = 0

（5）.向量叉积（三维才存在叉积）

AxB = (x1y2 - x2y1)k = 行列式

|A x B| = |A|*|B|*sin<A,B>
 

2.几何应用

1：判断点与直线位置关系

2：判断折线拐向，可转化为判断第三点在前两的形成直线的顺逆时针方向，然后判断拐向。

3：判断一个点在一条直线的那一侧，同样上面的方法。

4：判断点是否在线段上，可利用叉乘首先判断是否共线，然后在判断是否在其上。

5：判断两条直线是否想交（跨立实验）

根据判断点在直线那一侧我们可以判断一个线段的上的两点分别在另一个线段的两侧，当然这是不够的，因为我们画图发现这样只能够让直线想交，而不是线段，所以我们还要对另一条线段也进行相同的判断就ok。

参考：https://blog.csdn.net/y990041769/article/details/38258761

          https://blog.csdn.net/danliwoo/article/details/49836983

         https://blog.csdn.net/codeswarrior/article/details/79834257

3.板子：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
struct Point{
   double x,y;
   Point(double xx = 0,double yy = 0):x(xx),y(yy) {}
};
typedef Point Vector;
//四则运算
Vector operator +(Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
Vector operator -(Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
Vector operator *(Vector A,double p) {return Vector(A.x*p,A.y*p);}
Vector operator /(Vector A,double p) {return Vector(A.x/p,A.y/p);}
//构建向量
Vector BuildVector(Point A,Point B){
    return Vector(B.x-A.x,B.y-A.y);
}
//点乘
double Dot(Vector A,Vector B){return A.x*B.x + A.y*B.y;}
//模长
double Lenth(Vector A){return sqrt(A.x*A.x + A.y*A.y);}
//夹角
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Lenth(A)/Lenth(B));}
//叉积
double Cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;}
//判断点与直线的关系
double Realition(Point A,Point B,Point C){
    return Cross(BuildVector(A,B),BuildVector(A,C));
}
//向量逆时针旋转弧度rad
Vector RotateN(Vector A,double rad){
   return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//顺时针旋转
Vector RotateS(Vector A,double rad){
   return Vector(A.x*cos(-rad)-A.y*sin(-rad),A.x*sin(-rad)+A.y*cos(-rad));
}
//判断线段关系
bool CoverLine(Point A,Point B,Point C,Point D){
    //共线或者不相交
    if((Realition(A,B,C)==0&&Realition(A,B,D)==0)||Realition(A,B,C)*Realition(A,B,D)>0||Realition(C,D,A)*Realition(C,D,B)>0)
        return false;
    return true;
}

4.例题1  POJ2318

板子题，判断点与直线位置关系

#include <iostream>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 5000 + 7;
struct Point{
   int  x,y;
   Point(int xx = 0,int yy = 0):x(xx),y(yy) {}
};
typedef Point Vector;
//四则运算
Vector operator +(Vector A,Vector B) {return Vector(A.x+B.x,A.y+B.y);}
Vector operator -(Vector A,Vector B) {return Vector(A.x-B.x,A.y-B.y);}
Vector operator *(Vector A,int p) {return Vector(A.x*p,A.y*p);}
Vector operator /(Vector A,int p) {return Vector(A.x/p,A.y/p);}
//构建向量
Vector BuildVector(Point A,Point B){
    return Vector(B.x-A.x,B.y-A.y);
}
//点乘
int Dot(Vector A,Vector B){return A.x*B.x + A.y*B.y;}
//叉积
int Cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;}
//判断点与直线的关系
int Realition(Point A,Point B,Point C){
    return Cross(BuildVector(A,B),BuildVector(A,C));
}
//向量逆时针旋转弧度rad
Vector RotateN(Vector A,double rad){
   return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//顺时针旋转
Vector RotateS(Vector A,double rad){
   return Vector(A.x*cos(-rad)-A.y*sin(-rad),A.x*sin(-rad)+A.y*cos(-rad));
}
//判断线段关系
bool CoverLine(Point A,Point B,Point C,Point D){
    //共线或者不相交
    if((Realition(A,B,C)==0&&Realition(A,B,D)==0)||Realition(A,B,C)*Realition(A,B,D)>0||Realition(C,D,A)*Realition(C,D,B)>0)
        return false;
    return true;
}
int n,m,xa,ya,xb,yb,Sum[maxn];
struct Node{
   int Ui,Li;
}Board[maxn];
int main(){
    while(scanf("%d",&n)!=EOF&&n){
        scanf("%d%d%d%d%d",&m,&xa,&ya,&xb,&yb);
        memset(Sum,0,sizeof(Sum));
        for(int i = 1;i<=n;i++){
            scanf("%d%d",&Board[i].Ui,&Board[i].Li);
        }
        for(int i = 0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            bool flag = false;
            for(int j = 1;j<=n;j++){
                if(Realition(Point(Board[j].Li,yb),Point(Board[j].Ui,ya),Point(x,y))>0){
                    Sum[j-1]++;
                    flag = true;
                    break;
                }
            }
            if(!flag)Sum[n]++;
        }
        for(int i = 0;i<=n;i++){
            printf("%d: %d\n",i,Sum[i]);
        }
        printf("\n");
    }
    return 0;
}

判断点与直线位置关系，模板题