C++判断线段是否相交

引言

在多边形绘制中通常需要判断线段是否相交，本文先把代码贴出来，后续补充原理讲解（狗头.jpg）

原理

完整代码

// 叉乘
double crossProduct(QPoint pOri, QPoint p1, QPoint p2)
{
    return (pOri.x() - p1.x()) * (pOri.y() - p2.y()) - (pOri.y() - p1.y()) * (pOri.x() - p2.x());
}

// 判断是否相交, AB组成线段1, CD组成线段2
bool isIntersect(QPoint posA, QPoint posB, QPoint posC, QPoint posD)
{
    // 快速排斥实验
    if (qMax(posA.x(), posB.x()) < qMin(posC.x(), posD.x()))
        return false;
    if (qMax(posA.y(), posB.y()) < qMin(posC.y(), posD.y()))
        return false;
    if (qMax(posC.x(), posD.x()) < qMin(posA.x(), posB.x()))
        return false;
    if (qMax(posC.y(), posD.y()) < qMin(posA.y(), posB.y()))
        return false;
    //跨立实验
    if (crossProduct(posA, posC, posB) * crossProduct(posA, posB, posD) <= 0)
        return false;
    if (crossProduct(posC, posA, posD) * crossProduct(posC, posD, posB) <= 0)
        return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25