Question

请C++高手做一个判断三角形和矩形是否相交的程序

Answer 1

class Vector2D { //2D向量类
public:
    double x, y;
    Vector2D(double x_ = 0, double y_ = 0): x(x_), y(y_) {}
};

bool isZero(const Vector2D &vec, double tolerance = 0.05) const {
            return std::abs(vec.x) < tolerance && std::abs(vec.y) < tolerance;
}

Vector2D tripleProduct(const Vector2D &v1, const Vector2D &v2, const Vector2D &v3) { //三角乘积
    double p = v1.x * v2.y - v1.y * v2.x;
    return Vector2D(-p * v3.y, p * v3.x);
}

double dot(const Vector2D &v1, cosnt Vector2D &v2) { //点乘
    return v1.x * v2.x + v1.y * v2.y;
}

Vector2D negate(const Vector2D &vec) { //向量取反
    return Vector2D(-vec.x, -vec.y);
}

Vector2D sub(const Vector2D &v1, const Vector2D &v2) { //向量相减
    return Vector2D(v1.x - v2.x, v1.y - v2.y);
}

Vector2D getFarthestPoint(const Vector2D &dir, const Vector2D poly[], int len) { //求一个凸多边形poly在某个方向dir上最远的一点
    Vector2D bestPoint = poly[0];
    double bestProj = dot(bestPoint, dir);
    for (int i = 1; i < len; ++i) {
        Vector2D curr = poly[i];
        double proj = dot(curr, dir);
        if (proj > bestProj) {
            bestPoint = curr;
            bestProj = proj;
        }
    }
    return bestPoint;
}

Vector2D getSupportPoint(const Vector2D &dir, const Vector2D poly1[], int len1, const Vector2D poly2[], int len2) { //GJK算法的一部分, 求两个凸多边形的闵可夫斯基差在某个方向dir上最远的一点
    Vector2D v1 = getFarthestPoint(dir, poly1, len1),
             v2 = getFarthestPoint(negate(dir), poly2, len2);
    return sub(v1, v2);
}

bool isIntersect(const Vector2D poly1[], int len1, const Vector2D poly2[], int len2) {
    Vector2D simplexA, simplexB, simplexC, dir = Vector2D(-1, -1);

    simplexA = getSupportPoint(dir, poly1, len1, poly2, len2);
    if (dot(simplexA, dir) <= 0) {
        return false;
    }

    dir = negate(simplexA);
    simplexB = getSupportPoint(dir, poly1, len1, poly2, len2);
    if (dot(simplexB, dir) <= 0) {
        return false;
    }

    Vector2D ab = sub(simplexB, simplexA);
    dir = tripleProduct(ab, negate(simplexA), ab);

    for (int i = 25; i--;) { //25是最大迭代次数, 一般迭代3次以内就能完成
        if (isZero(dir)) {
            return true;
        }

        simplexC = getSupportPoint(dir, poly1, len1, poly2, len2);
        if (dot(simplexC, dir) <= 0) {
            return false;
        }

        Vector2D ba = sub(simplexA, simplexB),
                ac = sub(simplexC, simplexA),
                bc = sub(simplexC, simplexB),
                acPerp = tripleProduct(ac, negate(ba), ac),
                bcPerp = tripleProduct(bc, ba, bc);

        if (dot(acPerp, simplexA) > 0) {
            simplexB = simplexC;
            dir = negate(acPerp);
        } else if (dot(bcPerp, simplexB) > 0) {
            simplexA = simplexC;
            dir = negate(bcPerp);
        } else {
            return true;
        }
    }

    return false;
}

这个是我把自己的代码里的一段截出来改了下变量名和参数什么的, 不确定有没哪里漏了改的, 如果运行有错误可以自己修一下

isIntersect可以判断任意两个凸多边形是否相交, 用的GJK算法

三角形和矩形存在一个Vector2D数组里, 用isIntersect(poly1, poly1len, poly2, poly2len)就能判断

改一下getFarthestPoint还能变成任意两个凸图形是否相交