向量叉积有甚多应用,包括求三角形面积,判断线段相交,求多边形面积,判断多边形凹凸性,而且不需要推大量公式,误差较小,非常实用,下面是代码

//向量叉积的应用
#include <bits/stdc++.h>
#define EPS 1e-10
using namespace std;

struct point{
    double x, y;
    point(int x = 0, int y = 0) : x(x), y(y) {}
};

struct vect{
    double x, y;
};

//获取由点a指向b的向量
vect get_vect(const point & a, const point & b)
{
    vect res;
    res.x = b.x - a.x;
    res.y = b.y - a.y;
    return res;
}

//计算两个向量的叉积
double chaji(const vect & v1, const vect & v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

//计算三角形面积,a、b为三角形的两条边
double tri_area(const vect & a, const vect & b)
{
    return abs(chaji(a, b))/2.0;
}

//判断点P是否在直线AB上
bool dot_in_line(const point & P, const point & A, const point & B)
{
    vect v1 = get_vect(P, A);
    vect v2 = get_vect(P, B);
    return fabs(chaji(v1, v2))<EPS;
}

//判断两条线段P1P2,Q1Q2是否相交
bool is_intersect(const point & P1, const point & P2, const point & Q1, const point & Q2)
{
    //P1P2跨立Q1Q2
    vect v1 = get_vect(P1, Q1);
    vect v2 = get_vect(Q2, Q1);
    vect v3 = get_vect(P2, Q1);
    double res1 = chaji(v1, v2) * chaji(v3, v2);
    //Q1Q2跨立P1P2
    vect u1 = get_vect(Q1, P1);
    vect u2 = get_vect(P2, P1);
    vect u3 = get_vect(Q2, P1);
    double res2 = chaji(u1, u2) * chaji(u3, u2);
    return res1<=0 && res2<=0;
}

//计算多边形的面积
double area(const vector<point> & dots)
{
    vector<vect> vs;
    for(size_t i = 1; i < dots.size(); i++)
        vs.push_back(get_vect(dots.front(), dots[i]));
    double sum = 0;
    for(size_t i = 0; i < vs.size()-1; i++)
        sum += tri_area(vs[i], vs[i+1]);
    return sum;
}

//判断多边形的凹凸性
bool is_tu(const vector<point> & dots)
{
    vector<vect> vs;
    for(size_t i = 0; i < dots.size()-1; i++)
        vs.push_back(get_vect(dots[i], dots[i+1]));
    vs.push_back(get_vect(dots.back(), dots.front()));
    vector<double> res;
    for(size_t i = 0; i < vs.size()-1; i++)
        res.push_back(chaji(vs[i], vs[i+1]));
    res.push_back(chaji(vs.back(), vs.front()));
    for(size_t i = 1; i < res.size(); i++)
        if(!((res.front()>0 && res[i]>0)||(res.front()
}

1 条评论

欢迎留言