我试图找到一个矩形是否与凹多边形相交.这个算法能实现吗？

Question

我试图找到一个矩形是否与凹多边形相交.我发现了这个算法:

double determinant(Vector2D vec1, Vector2D vec2){
    return vec1.x*vec2.y-vec1.y*vec2.x;
}

//one edge is a-b, the other is c-d
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
    double det=determinant(b-a,c-d);
    double t=determinant(c-a,c-d)/det;
    double u=determinant(b-a,c-a)/det;
    if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION;
    return a*(1-t)+t*b;
}

如果我执行这4次(从上到下,从上到下,从上到下,从下到右)*(我的多边形的所有边缘)这将有效且准确地告诉我矩形是否具有部分或全部凹面多边形里面？如果不是会遗漏什么？

谢谢

Answer 1

代码试图找到两个段的交叉点 - AB和CD.

根据您解释这些操作的方式,有许多不同的方法可以解释它是如何做到的.

假设A点有坐标(xa,ya),B - (xb,yb)等等.让我们说吧

dxAB = xb - xa
dyAB = yb - ya
dxCD = xd - xc
dyCD = yd - yc

以下系统的两个线性方程组

| dxAB dxCD |   | t |   | xc-xa |
|           | * |   | = |       |
| dyAB dyCD |   | u |   | yc-ya |

如果求解t和u,将给出线AB(值t)和线CD(值u)上的交点的比例位置.[0, 1]如果该点位于相应的段之外,并且该点位于该段之外(在包含该段的行上),则这些值将位于该范围内.

为了解决这个线性方程组,我们可以使用众所周知的Cramer法则.为此,我们需要决定因素

| dxAB dxCD |
|           |
| dyAB dyCD |

这完全取决于determinant(b - a, c - d)你的代码.(实际上,我在这里有determinant(b - a, d - c),但是对于这个解释的目的并不重要.你发布的代码由于某种原因交换C和D,见下面的PS注释).

而且我们也需要决定性因素

| xc-xa dxCD |
|            |
| yc-ya dyCD |

这完全determinant(c-a,c-d)取决于你的代码和决定因素

| dxAB xc-xa |
|            |
| dyAB yc-ya |

这正是determinant(b-a,c-a).

根据Cramer规则划分这些决定因素将为我们提供t和的值u,这正是您发布的代码中所做的.

然后,代码进行测试的值t和u以检查片段实际相交,即,是否都t和u属于[0, 1]的范围内.如果他们这样做,它会通过评估来计算实际的交叉点a*t+b*(1-t)(相当于它可以评估c*u+d*(1-u)).(再次,请参阅下面的PS说明).

PS在原来代码中的点d和C在一定意义上,代码将"交换" c - d,在那里我做d - c我的解释.但这对算法的一般概念没有任何影响,只要小心一点.

C和D点的这种交换也是a*(1-t)+t*b在评估交叉点时使用表达式的原因.通常,正如在我的解释中,人们希望看到类似的东西a*t+b*(1-t).(我对此有疑问.我希望a*t+b*(1-t)即使你的版本也能看到它.可能是一个错误.)

PPS作者是否忘记检查代码det == 0(或非常接近0),这将在分段并行时发生.