如何测试线段是否与2D中的轴对齐矩形相交？

Question

如何测试线段是否与2D中的轴对齐矩形相交？该段的两端定义为:p1,p2.矩形定义为左上角和右下角.

Answer 1

原始海报想要检测线段和多边形之间的交叉点.如果有交叉点,则无需定位交叉点.如果这就是你的意思,那么你可以做的工作少于Liang-Barsky或Cohen-Sutherland:

设分段端点为p1 =(x1 y1),p2 =(x2 y2).
让矩形的角为(xBL yBL)和(xTR yTR).

那么你所要做的就是

A.检查矩形的所有四个角是否都在线的同一侧.通过p1和p2的线的隐式方程是:

F(xy)=(y2-y1)*x +(x1-x2)*y +(x2*y1-x1*y2)

如果F(xy)= 0,则(xy)在该行上.
如果F(xy)> 0,则(xy)在该线的"上方".
如果F(xy)<0,则(xy)在该线的"下方".

将所有四个角替换为F(xy).如果它们都是负数或全部为正数,则没有交集.如果有些是肯定的而有些是否定的,请转到步骤B.

B.将端点投影到x轴上,并检查线段的阴影是否与多边形的阴影相交.在y轴上重复:

如果(x1> xTR和x2> xTR),则没有交点(行是矩形的右边).
如果(x1 <xBL和x2 <xBL),则没有交点(行是矩形的左边).
如果(y1> yTR和y2> yTR),则没有交点(线在矩形上方).
如果(y1 <yBL和y2 <yBL),则没有交点(线条在矩形下方).
否则,有一个十字路口.Cohen-Sutherland或您问题的其他答案中提到的任何代码.

当然,你可以先做B,然后做A.

阿莱霍

Answer 2

写了非常简单和有效的解决方案:

      bool SegmentIntersectRectangle(double a_rectangleMinX,
                                 double a_rectangleMinY,
                                 double a_rectangleMaxX,
                                 double a_rectangleMaxY,
                                 double a_p1x,
                                 double a_p1y,
                                 double a_p2x,
                                 double a_p2y)
  {
    // Find min and max X for the segment

    double minX = a_p1x;
    double maxX = a_p2x;

    if(a_p1x > a_p2x)
    {
      minX = a_p2x;
      maxX = a_p1x;
    }

    // Find the intersection of the segment's and rectangle's x-projections

    if(maxX > a_rectangleMaxX)
    {
      maxX = a_rectangleMaxX;
    }

    if(minX < a_rectangleMinX)
    {
      minX = a_rectangleMinX;
    }

    if(minX > maxX) // If their projections do not intersect return false
    {
      return false;
    }

    // Find corresponding min and max Y for min and max X we found before

    double minY = a_p1y;
    double maxY = a_p2y;

    double dx = a_p2x - a_p1x;

    if(Math::Abs(dx) > 0.0000001)
    {
      double a = (a_p2y - a_p1y) / dx;
      double b = a_p1y - a * a_p1x;
      minY = a * minX + b;
      maxY = a * maxX + b;
    }

    if(minY > maxY)
    {
      double tmp = maxY;
      maxY = minY;
      minY = tmp;
    }

    // Find the intersection of the segment's and rectangle's y-projections

    if(maxY > a_rectangleMaxY)
    {
      maxY = a_rectangleMaxY;
    }

    if(minY < a_rectangleMinY)
    {
      minY = a_rectangleMinY;
    }

    if(minY > maxY) // If Y-projections do not intersect return false
    {
      return false;
    }

    return true;
  }

Answer 3

由于矩形是对齐的,所以Liang-Barsky可能是一个很好的解决方案.如果速度很重要,它比Cohen-Sutherland快.

Siggraph解释
另一个很好的描述
当然,维基百科

Answer 4

你还可以在段之外创建一个矩形,并测试另一个矩形是否与它发生碰撞,因为它只是一系列的比较.来自pygame来源:

def _rect_collide(a, b):
    return a.x + a.w > b.x and b.x + b.w > a.x and \
           a.y + a.h > b.y and b.y + b.h > a.y

Answer 5

使用Cohen-Sutherland算法.

它用于剪裁,但可以稍微调整一下这项任务.它将2D空间划分为井字板,矩形为"中心正方形".
然后检查你的线的两个点中的九个区域中的哪一个.

• 如果两个点都是左,右,上或下,那么你就会轻易拒绝.
• 如果任何一点在里面,你就可以接受了.
• 在极少数情况下,您可以根据它们所在的区域,与矩形中可能相交的任何一侧进行数学交叉.