[数据结构与算法][计算几何] 使用叉积计算直线交点

使用叉积计算直线交点

已知直线 $AB$ 和 $CD$ ，其交点为 $P$ ， 求 $P$ 的坐标

计算几何中一般存储向量 $p,v$ 表示起点的向量表示和方向向量

例如直线 $AB$ 一般存储为 $\stackrel{?}{\mathrm{OA}},\stackrel{?}{\mathrm{AB}}$

const double eps=1e-10;
struct vct{double x,y;}p[N];
#define pf(x) ((x)*(x))
vct operator+(vct a,vct b){return {a.x+b.x,a.y+b.y};}
vct operator-(vct a,vct b){return {a.x-b.x,a.y-b.y};}
vct operator*(vct a,double b){return {a.x*b,a.y*b};}
vct operator/(vct a,double b){return {a.x/b,a.y/b};}
double cross(vct a,vct b){return a.x*b.y-a.y*b.x;}
double dot(vct a,vct b){return a.x*b.x+a.y*b.y;}
double len(vct a){return sqrt(pf(a.x)+pf(a.y));}
struct line
{
    vct p,way;
    double k;
    void mkline(vct a,vct b)
    {
        p=a;way=b;
        k=atan2(b.y,b.x); // 部分题会用到的极角排序，并不是必不可缺的
    }
    void mk(double x1,double y1,double x2,double y2)
    {
        mkline({x1,y1},{x2-x1,y2-y1});
    }
}a[N];

因此，可以得到下图

其中 $v_1,v_2$ 为方向向量

则 $P=p_1+t{v}_1$

$\because (p_1+t{v}_1?p_2)\times v_2=0$

$\therefore t=\frac{(p_2?p_1)\times v_2}{v_1\times v_2}$

则代入 $P=p_1+t{v}_1$ 即可

代码如下

vct intersect(line a,line b)
{
    double x=cross(b.way,a.p-b.p)/cross(a.way,b.way);
    return a.p+a.way*x;
}

完整代码摘自这里 其实是懒得再打一遍 qwq

转载请说明出处

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖