检查方形是否落入三角形内的最简单/有效方法

Question

我只是想知道是否有任何简单/有效的方法来检查方块是否落入三角形内.或者至少有一个角落在里面或有些重叠.例如,考虑下面的图,我应该能够知道3个方块落在里面.即方形1明显在里面,方形2的一个角在里面,3个重叠.

Answer 1

我正在查看这个不错的教程。它解释了如何使用各种技术测试点是否在三角形内部。当一个方角落入内部时，似乎会有帮助。

我喜欢重心技术，在这里我为 matlab 重新实现了它：

function d = isinside(p,a,b,c)

    % Test if a point p(x,y) is inside a triangle
    % with vertices a(x,y), b(x,y) and c(x,y)

    v0 = c - a;
    v1 = b - a;
    v2 = p - a;

    A = [dot(v0,v0) dot(v1,v0);dot(v0,v1) dot(v1,v1)];
    b = [dot(v2,v0); dot(v2,v1)];

    x  = A\b;

    % Check if point is in triangle
    if (x(1) > 0) && (x(2) > 0) && (sum(x) < 1)
        d = true;
    else
        d = false;
    end

然后我会测试正方形的每个顶点，如果其中一个顶点落入其中，我就会返回。计算量相当大，但值得一试。

对于重叠，我将测试三角形和正方形的线条的每种组合的交叉点，如本线程中所讨论的。