快速矩形与矩形相交

Question

如何快速测试两个矩形是否相交？

---

在网上搜索到了这个一行代码（厉害！），但我不知道如何用Javascript编写它，它似乎是用一个古老的C++版本编写的。

struct
{
    LONG    left;
    LONG    top;
    LONG    right;
    LONG    bottom;
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2)
{
    return ! ( r2->left > r1->right
        || r2->right < r1->left
        || r2->top > r1->bottom
        || r2->bottom < r1->top
        );
}

- Robin Rodricks

---

我认为你在复制/粘贴时出现了打字错误。 - fmark

原文中有一个错别字。 r2->right left没有意义。可能是由于HTML转义问题而导致的错误。 - Marcelo Cantos

我很好奇你认为上述代码在“现代”C++中会有何不同。 - jamesdlin

我相信缺失的字符是由于 HTML 转义导致 < 符号丢失。 - devios1

@jamesdlin 你可以将该函数作为结构体的成员函数并传入一个参数。其次，通常应该使用const&而不是const*。你可以使用模板来具有int、long和double版本，而不是使用一些Win32宏...（它也无法编译，因为RECT最终成为未命名结构体的实例，而不是类型名称）。 示例：http://ideone.com/bnzwl3 - Sebastian Wahl

Answer 1

以下是将该代码转换为JavaScript的方法。请注意，您的代码以及文章中都存在拼写错误，就像注释所建议的那样。具体来说，r2->right left应更改为r2->right < r1->left，r2->bottom top也应更改为r2->bottom < r1->top才能使该函数正常运行。

function intersectRect(r1, r2) {
  return !(r2.left > r1.right || 
           r2.right < r1.left || 
           r2.top > r1.bottom ||
           r2.bottom < r1.top);
}

测试案例：

var rectA = {
  left:   10,
  top:    10,
  right:  30,
  bottom: 30
};

var rectB = {
  left:   20,
  top:    20,
  right:  50,
  bottom: 50
};

var rectC = {
  left:   70,
  top:    70,
  right:  90,
  bottom: 90
};

intersectRect(rectA, rectB);  // returns true
intersectRect(rectA, rectC);  // returns false

- Daniel Vassallo

---

只是为了补充/确认 - 这是测试三个大小为20px x 20px的框，除了rectB，它是30px x 30px。 - verenion

如果 r1 和 r2 是相同的，intersectRect 函数将返回 false。 - zumalifeguard

绝妙的Eloquent实现。太棒了！+1，完美地为我的游戏工作。 - Unome

@zumalifeguard 你为什么这样想？ - Minix

这个函数太聪明了。我从来没有想过那样做，我会尝试让两个框相交。 - nikk wong

Answer 2

function intersect(a, b) {
  return (a.left <= b.right &&
          b.left <= a.right &&
          a.top <= b.bottom &&
          b.top <= a.bottom)
}

假设top通常小于bottom（即y坐标向下增加）。

- DS.

---

好的、可行的解决方案，但应该会慢一些，因为必须评估所有条件。另一个解决方案在任何一个条件评估为真时就完成了。 - Gigo

只要其中一个条件评估为 false，这个也会立即完成。也就是说，在与另一个条件完全相同的情况下。 - DS.

这样更好，因为它去除了否定动作。 - Discipol

更整洁比被接受的答案好一点，如果使用半开区间（即矩形包括顶部和左侧但不包括底部和右侧，这在许多图形系统中很常见），将“<=”改为“<”应该可行。 - Jules

我喜欢这个解决方案，因为我可以为每个条件删除 =，并且它允许矩形在边界上“接触”。 - prograhammer

Answer 3

这就是 .NET Framework 如何实现 Rectangle.Intersect 方法的方式。

public bool IntersectsWith(Rectangle rect)
{
  if (rect.X < this.X + this.Width && this.X < rect.X + rect.Width && rect.Y < this.Y + this.Height)
    return this.Y < rect.Y + rect.Height;
  else
    return false;
}

或者静态版本：

public static Rectangle Intersect(Rectangle a, Rectangle b)
{
  int x = Math.Max(a.X, b.X);
  int num1 = Math.Min(a.X + a.Width, b.X + b.Width);
  int y = Math.Max(a.Y, b.Y);
  int num2 = Math.Min(a.Y + a.Height, b.Y + b.Height);
  if (num1 >= x && num2 >= y)
    return new Rectangle(x, y, num1 - x, num2 - y);
  else
    return Rectangle.Empty;
}

- Schwarrior

Answer 4

另一种更简单的方法。（假设y轴向下增加）。

function intersect(a, b) {
  return Math.max(a.left, b.left) < Math.min(a.right, b.right) &&
          Math.max(a.top, b.top) < Math.min(a.bottom, b.bottom);
}

以上条件中的4个数字（最大值和最小值）也给出了交点。

- Duke

Answer 5

这里有一个 Rect 类型，你可以使用它。它已经是 JavaScript。

https://dxr.mozilla.org/mozilla-beta/source/toolkit/modules/Geometry.jsm

- englebart

---

这段代码将会对矩形A(0,0,100,100)和B(100,100,100,100)返回false。我认为应该使用<=而不是<。 - Stanislav S.

<= 给出高度为0的矩形，对于我的目的没有用。 - englebart

Answer 6

我使用了多种方法来检测大矩形内的小矩形。这是一个Node.js方法，使用宽度/高度，但可以轻松适应。

            isIntersectingRect: function (r1, r2) {
              var quickCheck = (r1.x <= r2.x + r2.w &&
                      r2.x <= r1.x + r1.w &&
                      r1.y <= r2.y + r2.h &&
                      r2.y <= r1.y + r1.h)
              if (quickCheck) return true;
              var x_overlap = Math.max(0, Math.min(r1.x + r1.w, r2.x + r2.w) - Math.max(r1.x, r2.x));
              var y_overlap = Math.max(0, Math.min(r1.y + r1.h, r2.y + r2.h) - Math.max(r1.y, r2.y));
              var overlapArea = x_overlap * y_overlap;
              return overlapArea == 0;
            }

- Langerz

Answer 7

目前的.NET方式很简单

    public bool IsEmpty => _width < 0.0;   

    public bool IntersectsWith(Rect rect)
    {
        if (IsEmpty || rect.IsEmpty)
        {
            return false;
        }

        if (rect.Left <= Right && rect.Right >= Left && rect.Top <= Bottom)
        {
            return rect.Bottom >= Top;
        }

        return false;
    }

- SpeedOfSpin

Answer 8

修改了接受的答案，适用于常规坐标系（y轴向上增长）

public static bool AARectsOverlap(float2 r1bl, float2 r1tr, float2 r2bl, float2 r2tr)
{
    return !(r2bl.x > r1tr.x || r2tr.x < r1bl.x || r2tr.y < r1bl.y || r2bl.y > r1tr.y);
}

- fakepersun