objective-c - 检测线段是否与正方形相交

Question

有人有一个简单的算法吗？不需要旋转或任何东西。只需查找由两点组成的线段是否与正方形相交

Answer 1

这段代码应该可以解决问题。它检查线与边相交的位置，然后检查它是否在正方形的宽度内。返回交集的数量。

float CalcY(float xval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return y0 + (xval - x0)*(y1 - y0)/(x1 - x0);
}

float CalcX(float yval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return x0 + (yval - y0)*(y1 - y0)/(x1 - x0);
}

int LineIntersectsSquare(int x0, int y0, int x1, int y1, int left, int top, int right, int bottom)
{
    int intersections = 0;
    if(CalcX(bottom, x0, y0, x1, y1) < right && CalcX(bottom, x0, y0, x1, y1) > left  ) intersections++;
    if(CalcX(top   , x0, y0, x1, y1) < right && CalcX(top   , x0, y0, x1, y1) > left  ) intersections++;
    if(CalcY(left  , x0, y0, x1, y1) < top   && CalcY(left  , x0, y0, x1, y1) > bottom) intersections++;
    if(CalcY(right , x0, y0, x1, y1) < top   && CalcY(right , x0, y0, x1, y1) > bottom) intersections++;
    return intersections;
}

注意：此代码是理论上的，可能不正确，因为它尚未经过测试

Answer 2

您可以通过投射一个向量并计算它穿过的边数来做到这一点。

如果它穿过的边缘是偶数，它在对象外面，如果它穿过的边缘是奇数，它在里面。

这适用于所有封闭的多边形。

Answer 3

这是一种方法：
- 按 x 坐标对正方形的顶点进行排序 - 按 x 坐标
对线的端点进行排序
- 计算从线的 minX 端到中间两个（按 x 坐标）正方形中的每一个的角度vertices
- 计算
线的角度 - 如果线的角度在可能的角度范围内，您所要做的就是检查长度，是否 maxX 线的末端 > minX 正方形的顶点

如果正方形直接面对，这可能会中断这条线，在这种情况下，我只是通过检查正方形的第一个边缘来特殊情况。