7

我试图找出一个矩形是否与一个凹多边形相交。我发现了这个算法：

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 次（从上到右，从上到左下，从上到下，从下到右）*（我的多边形的所有边缘）这将有效且准确地告诉我矩形是否具有部分或全部凹面里面的多边形？如果不是，会缺少什么？

谢谢

4

3 回答 3

13

该代码试图找到两个线段的交点 - 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和，将为您提供 AB 线（值）和 CDu线（值）上的交点的比例位置。如果该点属于相应的线段，这些值将位于范围内，如果该点位于线段之外（在包含该线段的线上），则这些值将位于该范围之外。tu[0, 1]

为了求解这个线性方程组，我们可以使用著名的克莱默规则。为此，我们需要行列式

| 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)。

根据克莱默规则划分这些行列式将为我们提供 和 的值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在解释中所做的那样。但这对算法的总体思路没有影响，只要注意符号即可。

a*(1-t)+t*b这种 C 点和 D 点的交换也是求交点时使用表达式的原因。通常，正如我的解释，人们希望看到类似的东西a*t+b*(1-t)。（不过，我对此表示怀疑。我希望a*t+b*(1-t)即使在您的版本中也能看到那里。可能是一个错误。）

PPS作者如果代码忘记检查det == 0（或非常接近于 0），这将在段并行的情况下发生。

于 2010-08-11T22:30:41.533 回答
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

编辑：添加检查多边形是否在矩形内。

于 2010-08-11T22:12:33.010 回答
0

据我快速浏览后所知，它试图确定 2 条线段是否相交，如果相交，则相交点的坐标是什么。

不，确定您的矩形和多边形是否相交还不够好，因为您仍然会错过多边形完全在矩形内或相反的情况。

于 2010-08-11T22:56:31.190 回答