我正在尝试查找一个矩形是否与一个凹多边形相交。这个算法能够实现吗？

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次（从上到右，从上到下左，从上到下右，从下到右）*（我的多边形的所有边缘），这是否能有效和准确地告诉我矩形是否包含部分或全部凹多边形？如果不是，还有什么遗漏的吗？

谢谢。

- jmasterx

Answer 1

这段代码试图找到两条线段AB和CD的交点。

有许多不同的方法来解释它是如何做到这一点的，这取决于你如何解释这些操作。

假设点A的坐标为(xa, ya)，B为(xb, yb)等等。

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

以下是两个线性方程组：

3x + 2y = 8

-2x + y = 2

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

如果解决了t和u，将为您提供在线AB上交点的比例位置（值t）和在线CD上的比例位置（值u）。如果该点属于相应线段，则这些值将位于[0, 1]范围内，如果该点位于线段外（在线段所在的直线上），则这些值将超出该范围。

为了解决这个线性方程组，我们可以使用众所周知的克莱姆法则。为此，我们需要计算行列式。

| dxAB dxCD |
|           |
| dyAB dyCD |

这正是您代码中的determinant(b - a, c - d)。实际上，我这里有determinant(b - a, d - c)，但对于本次解释的目的并不重要。您发布的代码出于某种原因交换了C和D，请参见下面的P.S.注释。

我们还需要计算

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

这与你的代码中的 determinant(c-a,c-d) 精确相符，而且是

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

这里涉及的是 determinant(b-a,c-a) 的计算。

按照克莱姆法则对这些行列式进行分解，将给出 t 和 u 的值，这正是您发布的代码中所做的。

然后，该代码继续测试 t 和 u 的值，以检查线段是否实际相交，即它们都属于 [0,1] 范围。如果是，则通过评估 a*t+b*(1-t)（等效地，它可以评估 c*u+d*(1-u)）来计算实际的交点。（再次查看下面的 P.S. 注释）。

P.S. 在原始代码中，点 D 和 C 有一种“交换”的方式，即代码执行 c - d，而我在我的说明中执行 d - c。但是，只要小心符号，这对于算法的一般思想没有影响。

这种交换 C 和 D 点的原因也是在计算交点时使用 a*(1-t)+t*b 表达式的原因。通常情况下，如在我的解释中，人们会期望看到类似于 a*t+b*(1-t) 的表达式。 （不过我对此有些怀疑。我希望在您的版本中也能看到 a*t+b*(1-t)。可能是个 bug。）

P.P.S. 代码作者忘记检查 det == 0（或非常接近 0），这种情况发生在线段平行的情况下。

- AnT stands with Russia

Answer 2

我认为以下内容应该有效：

(1) for each e1 in rectangle_edges, e2 in polygon_edges
    (1.1) if edgeIntersection(e1,e2) != NO_INTERSECTION
        (1.1.1) return true
(2) if (max_polygon_x < max_rectangle_x) and (min_polygon_x > min_rectangle_x) and (max_polygon_y < max_rectangle_y) and (min_polygon_y > min_rectangle_y)
    (2.1) return true
(2) return false

编辑：增加了检查多边形是否在矩形内部的功能。

- Amir Rachum

---

好的，谢谢。我本来想这么做，但是如果行不通的话就不想遇到任何调试问题了。 - jmasterx

你必须处理多边形完全包含在矩形内或反之的情况。 - jpalecek

Answer 3

据我初步了解，它试图确定两条线段是否相交，如果相交，还会计算出交点的坐标。

不，仅仅确定矩形和多边形是否相交是不够的，因为你仍然会忽略多边形完全在矩形内或者反过来的情况。

- bart