Быстрое пересечение прямоугольника с прямоугольником

81

Какой быстрый способ проверить, пересекаются ли 2 прямоугольника?


Поиск в Интернете нашел этот однострочный (WOOT!), Но я не понимаю, как написать его на 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
        );
}
Робин Родрикс
источник
5
Я думаю, вы допустили опечатку при копировании / вставке
fmark
5
В исходной статье есть опечатка. r2->right leftне имеет смысла. Он может быть сломан из-за проблем с экранированием HTML.
Марсело Кантос
42
Мне любопытно, как, по вашему мнению, будет отличаться приведенный выше код в «современной» форме C ++.
jamesdlin
3
Я уверен, что отсутствующие символы являются <символами из-за экранирования HTML.
devios1
1
@jamesdlin, вы должны сделать функцию функцией-членом структуры, принимая один параметр. Во-вторых, вы обычно используете const & вместо const *. Вы можете использовать шаблоны для версий int, long и double вместо использования какого-либо макроса Win32 ... (Он также не компилируется, поскольку RECT в конечном итоге является экземпляром безымянной структуры, а не именем типа.) Пример. : ideone.com/bnzwl3
Себастьян Валь

Ответы:

142

Вот как этот код можно перевести на 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
Даниэль Вассалло
источник
Просто чтобы добавить / подтвердить - это тестирование трех блоков размером 20px x 20px, кроме rectB, который имеет размер 30px x 30px
verenion
6
если r1 и r2 идентичны, функция
IntercctRect
Фантастическая красноречивая реализация. Любить это! +1, отлично сработало для моей игры.
Unome
1
@zumalifeguard Почему ты так думаешь?
Minix
Эта функция настолько гениальна. Я бы никогда об этом не подумал, вместо этого я бы попытался пересечь два квадрата.
Никк Вонг 08
69
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
21
Это также выполняется, как только одно из условий оценивается как ложное. Т.е. в тех же случаях, что и другой.
ДС.
3
Это лучше, так как устраняет действие отрицания.
Discipol
4
+1, намного аккуратнее, чем принятый ответ. при использовании полуоткрытых диапазонов (т. е. прямоугольник включает верхний и левый, но не включает нижний и правый, как это часто бывает во многих графических системах), изменение <=на <должно работать.
Жюль
Мне нравится это решение, потому что я могу удалить =для каждого условия, и это позволяет прямоугольникам «касаться» границ.
programhammer 03
20

Вот как .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;
}
Шварриор
источник
6

Еще один более простой способ. (Предполагается, что ось 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 числа (макс. И мин.) В приведенном выше условии также дают точки пересечения.

Герцог
источник
1

У него есть тип Rect, который вы можете использовать. Это уже JavaScript.

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

Englebart
источник
Этот код вернет false для прямоугольников A (0,0,100,100) и B (100,100,100,100). Я думаю, что здесь должно быть <= вместо <
Станислав С.
<= дает прямоугольник с высотой 0. Бесполезен для моих целей.
englebart
0

Я использовал сочетание методов, чтобы обнаружить меньший прямоугольник внутри большого прямоугольника. Это метод nodejs, использующий ширину / высоту, но его легко адаптировать.

            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;
            }
Лангерц
источник