前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >平面中判断线段与矩形是否相交

平面中判断线段与矩形是否相交

作者头像
charlee44
发布2021-06-21 20:24:54
3K0
发布2021-06-21 20:24:54
举报
文章被收录于专栏:代码编写世界

目录

1. 原理

这个问题的算法思路挺简单的。分成两步来判断:

  1. 判断线段的两个端点是否在矩形内,如果两个端点至少有一个在矩形内,说明线段与矩形相交。
  2. 如果两个端点都不在矩形内,那么需要再判断线段是否与矩形的对角线是否相交。因为两个端点都不在矩形内的线段有可能会切割矩形的角,这时会与矩形的对角线相交。

那么关键就在于两个子算法:判断点在矩形内和判断线段相交。判断点在矩形内非常简单,就是比较点是否在矩形的四至范围就可以了;而判断线段相交可以参考《空间或平面判断两线段相交(求交点)》这篇文章。

2. 实现

关键的C++实现代码如下:

代码语言:javascript
复制
//空间直线
template <class T>
class LineSegment
{
public:
    Vec3<T> startPoint;
    Vec3<T> endPoint;
    Vec3<T> direction;

    Vec3<T> min;
    Vec3<T> max;

    LineSegment()
    {
    }

    LineSegment(Vec3<T> start, Vec3<T> end)
    {
        startPoint = start;
        endPoint = end;
        direction = end - start;      
    }

    inline void Set(Vec3<T> start, Vec3<T> end)
    {
        startPoint = start;
        endPoint = end;
        direction = end - start;      
    }

    //两条线段相交
    inline static bool Intersection2D(LineSegment & line1, LineSegment & line2, Vec3<T>& insPoint)
    {
        double D = -line1.direction.x() * line2.direction.y() + line1.direction.y() * line2.direction.x();
        if(D == 0.0)
        {
            return false;
        }

        auto O12 = line2.startPoint - line1.startPoint;
        T D1 = -O12.x() * line2.direction.y() + O12.y() * line2.direction.x();
        T D2 = line1.direction.x() * O12.y() - line1.direction.y() * O12.x();

        T t1 = D1 / D;
        if(t1<0 || t1 > 1)
        {
            return false;
        }

        T t2 = D2 / D;
        if(t2<0 || t2 > 1)
        {
            return false;
        }

        insPoint = line1.startPoint + line1.direction * t1;     //这样计算得到的Z值是不准确的

        return true;
    }

    //线段与矩形相交
    inline bool static IsIntersectsOrthogon2D(LineSegment & line, Orthogon<T> orthogon)
    {
        if (orthogon.IsContainsPoint(line.startPoint.x(), line.startPoint.y()) ||
                orthogon.IsContainsPoint(line.endPoint.x(), line.endPoint.y()))
        {
            return true;
        }

        LineSegment diagonal1(Vec3<T>(orthogon.minX(), orthogon.minY(), 0),
                              Vec3<T>(orthogon.maxX(), orthogon.maxY(), 0));
        LineSegment diagonal2(Vec3<T>(orthogon.minX(), orthogon.maxY(), 0),
                              Vec3<T>(orthogon.maxX(), orthogon.minY(), 0));

        Vec3<T> point(0,0,0);
        return Intersection2D(line, diagonal1, point) || Intersection2D(line, diagonal2, point);
    }
};

3. 参考

  1. 如何判断一条线段和一个矩形或者圆相交? - 叶飞影的回答 - 知乎
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-06-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 原理
  • 2. 实现
  • 3. 参考
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档