计算几何之求两线段的交点
计算几何之求两线段的交点

计算几何之求两线段的交点

当两条线段有交点的时候,交点坐标可以用叉乘来求。

思路就是连接线段的端点,构造向量,从而构造出相似三角形,然后求出交点在一条线段上的位置(用比例t来表示),然后再加到线段端点上就可以了。

题目:CGL_2_C

AC代码:

#include <iostream>
#include<cstdio>
#include <math.h>
using namespace std;

#define COUNTER_CLOCKWISE -1 //逆时针
#define CLOCKWISE 1          //顺时针
#define ONLINE_BACK -2       //p2 p0 p1依次排列在一条直线上
#define ONLINE_FRONT 2       //p0 p1 p2依次排列在一条直线上
#define ON_SEGMENT 0         //p2在线段p0p1上

#define EPS 1E-8

class Point
{
public:
    double x, y;
    Point()
    {
    }
    Point(double x, double y)
    {
        (*this).x = x;
        (*this).y = y;
    }

    double operator^(const Point &p) const //叉乘
    {
        return x * p.y - y * p.x;
    }

    double operator*(const Point &p) const //点乘
    {
        return x * p.x + y * p.y;
    }

    Point operator*(const double &d) const
    {
        return Point(x * d, y * d);
    }
    

    Point operator/(const double &d) const
    {
        return Point(x / d, y / d);
    }

    Point operator-(const Point &p) const
    {
        return Point(x - p.x, y - p.y);
    }

    Point operator+(const Point &p) const
    {
        return Point(x + p.x, y + p.y);
    }

    double sqr()
    {
        return x * x + y * y;
    }
    double abs()
    {
        return sqrt(sqr());
    }

    double distance(const Point &p)
    {
        return fabs((*this - p).abs());
    }

    
    void print()
    {

        printf("%.10lf %.10lf\n", x, y);
    }
    
};

class Line
{
public:
    Point p1, p2;
    Line()
    {
    }
    Line(Point p1, Point p2)
    {
        (*this).p1 = p1;
        (*this).p2 = p2;
    }
};

int main()
{
    
    int q;
    cin >> q;

    while (q--)
    {
        Line l[2];
        cin >> l[0].p1.x >> l[0].p1.y >> l[0].p2.x >> l[0].p2.y;
        cin >> l[1].p1.x >> l[1].p1.y >> l[1].p2.x >> l[1].p2.y;

        double d1 = fabs((l[0].p1-l[1].p1)^(l[1].p2-l[1].p1));
        double d2 = fabs((l[0].p2-l[1].p1)^(l[1].p2-l[0].p2));

        double t = d1/(d1+d2);

        Point ans = l[0].p1+(l[0].p2-l[0].p1)*t;
        ans.print();


    }
}

转载请注明:https://www.longjin666.top/?p=790

发表评论