计算几何之判断线段相交

判断线段相交可以用到之前讲的判断点与线段的位置关系的来实现。

两条线段相交的充要条件是：

两条线段都满足“另一条线段的两个端点分别位于当前线段的顺时针方向和逆时针方向”，那么这两条线段相交。

这样的话，就能用之前的ccw来解决了。

题目：CGL_2_B

AC代码：

#include <iostream>
#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 ccw(Point p0, Point p1, Point p2) //判断p2与线段p0p1的关系
{
    Point vec1 = p1 - p0;
    Point vec2 = p2 - p0;

    if ((vec1 ^ vec2) > EPS)
        return COUNTER_CLOCKWISE; //p0、p1、p2逆时针
    else if ((vec1 ^ vec2) < -EPS)
        return CLOCKWISE; //p0 p1 p2顺时针
    else                  //p0 p1 p2在一条线上
    {
        if (vec1 * vec2 < -EPS)
            return ONLINE_BACK;
        else
        {
            if (vec1.abs() - vec2.abs() < -EPS)
                return ONLINE_FRONT;
            else
                return ON_SEGMENT;
        }
    }
}

bool intersect(Line l1, Line l2) //判断线段是否相交。
//如果两条线段都符合“另一条线段的两个端点分别位于当前线段的顺时针和逆时针方向”，那么两条线段相交
{
    return (ccw(l1.p1, l1.p2, l2.p1) * ccw(l1.p1, l1.p2, l2.p2) <= 0 &&
            ccw(l2.p1, l2.p2, l1.p1) * ccw(l2.p1, l2.p2, l1.p2) <= 0);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    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;

        cout << intersect(l[0], l[1]) << endl;
        }
}

转载请注明链接：https://www.longjin666.top/?p=785

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~