Какой самый быстрый способ определить пересечение 2D ограничительной рамки?

62

Предположим, что каждый объект Box имеет свойства x, y, width, height и имеет свое происхождение в центре, и что ни объекты, ни ограничивающие прямоугольники не вращаются.

Iain
источник
Это ограничивающие рамки для оси или объекта?
Tenpn
3
Когда вы зададите этот вопрос, вам обязательно нужно будет проверить другие типы пересечений в будущем;). Поэтому я предлагаю СПИСОК о пересечении объекта / объекта. В таблице представлены пересечения между всеми популярными типами объектов (прямоугольники, сферы, треугольники, циклиндеры, конусы, ...) как в статических, так и в динамических ситуациях.
Дейв О.
2
Пожалуйста, перефразируйте Ваш вопрос к обязательным статьям. С моей точки зрения коробка подразумевает 3d объект.
Дейв О.

Ответы:

55

(Псевдокод C-ish - адаптировать языковые оптимизации по мере необходимости)

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));
}

На английском: на каждой оси проверьте, достаточно ли близки центры ячеек, чтобы они пересекались. Если они пересекаются по обеим осям, то коробки пересекаются. Если они этого не делают, значит, нет.

Вы можете изменить <'на <=, если вы хотите считать касание края пересекающимся. Если вам нужна конкретная формула только для касания кромок, вы не можете использовать == - это скажет вам, касаются ли углы, а не касаются ли кромки. Вы хотели бы сделать что-то логически эквивалентное return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

Стоит отметить, что вы можете получить небольшое, но значительное увеличение скорости, сохраняя половину ширины и половину высоты в дополнение (или вместо) к полной ширине и полной высоте. С другой стороны, пересечение 2d ограничивающей рамки редко является узким местом для производительности.

ZorbaTHut
источник
9
Это, очевидно, предполагает, что блоки выровнены по оси.
Tenpn
1
Абс не должен быть особенно медленным - по крайней мере, не медленнее, чем условный, и единственный способ сделать это без пресса (который я знаю) включает дополнительные условные выражения.
ZorbaTHut
4
Да, он предполагает выравнивание по оси. Структуры, как описано, не имеют никакого способа обозначить вращение, поэтому я чувствовал, что это безопасно.
ZorbaTHut
3
Вот несколько хороших советов для ускорения вычислений в Actionscript (в основном, integer calc): lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math Я публикую это, потому что он также содержит более быстрый замена для Math.abs (), которая действительно замедляет действия в Actionscript (конечно, говоря о проблемах с производительностью).
bummzack
2
Вам не хватает того, что они имеют происхождение в центре, а не на левом краю. Ящик, который работает от 0 до 10, на самом деле будет иметь «x = 5», в то время как ящик, который работает с 8 до 12, будет иметь «x = 10». Вы в конечном итоге с abs(5 - 10) * 2 < (10 + 4)=> 10 < 14. Вам нужно будет сделать несколько простых настроек, чтобы он работал с topleft-angle-and-size.
ZorbaTHut
37

Это работает для двух прямоугольников, выровненных по оси X и Y.
Каждый прямоугольник имеет свойства:
«left», координата x его левой стороны,
«top», координата y его верхней стороны,
«right», координата x его правой стороны,
«bottom», координата y его нижняя сторона,

function IntersectRect(r1:Rectangle, r2:Rectangle):Boolean {
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top);
}

Обратите внимание, что это разработано для системы координат, в которой ось + y направлена вниз, а ось + x направлена ​​вправо (т.е. типичные координаты экрана / пикселя). Чтобы адаптировать это к типичной декартовой системе, в которой + y направлен вверх, сравнения по вертикальным осям будут обратными, например:

return !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

Идея состоит в том, чтобы охватить все возможные условия, при которых прямоугольники не будут перекрываться, а затем отменить ответ, чтобы увидеть, не перекрываются ли они . Независимо от направления осей, легко увидеть, что два прямоугольника не будут перекрываться, если:

  • левый край r2 дальше, чем правый край r1

     ________     ________
    |        |   |        |
    |   r1   |   |   r2   |
    |        |   |        |
    |________|   |________|
  • или правый край r2 дальше влево, чем левый край r1

     ________     ________
    |        |   |        |
    |   r2   |   |   r1   |
    |        |   |        |
    |________|   |________|
  • или верхний край r2 находится ниже нижнего края r1

     ________ 
    |        |
    |   r1   |
    |        |
    |________|
     ________ 
    |        |
    |   r2   |
    |        |
    |________|
  • или нижний край r2 выше верхнего края r1

     ________ 
    |        |
    |   r2   |
    |        |
    |________|
     ________ 
    |        |
    |   r1   |
    |        |
    |________|

Оригинальную функцию - и альтернативное описание того, почему она работает - можно найти здесь: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect- друг-друга или не-/

Ponkadoodle
источник
1
Удивительно интуитивно и еще раз показывает, что когда найти ответ слишком сложно, попытка найти ответ на противоположный вопрос может помочь вам. Спасибо!
Lodewijk
1
Следует отметить, что ось Y направлена ​​вниз (как на изображении). В противном случае неравенства r2.top> r1.bottom и r2.bottom <r1.top необходимо поменять местами.
user1443778
@ user1443778 хороший улов! Я пошел дальше и в общих чертах объяснил логику этого алгоритма независимо от системы координат.
Ponkadoodle
11

Если вы хотите, чтобы выровненные рамки были выровнены по объектам , попробуйте этот урок по теореме об отделении от metanet: http://www.metanetsoftware.com/technique/tutorialA.html

SAT не самое быстрое решение, но оно относительно простое. Вы пытаетесь найти одну линию (или плоскость, если 3D), которая будет отделять ваши объекты. Если эта линия существует, то она должна быть параллельной к краю одного из ваших блоков, поэтому вы повторяете тестирование всех ребер, чтобы увидеть, разделяет ли он блоки.

Это также работает для выровненных по оси блоков, ограничивая только ось x / y.

tenpn
источник
Я не думал о ротации, но спасибо, это интересная ссылка.
Iain
5

Приведенный выше DoBoxesIntersect является хорошим попарным решением. Однако, если у вас много ящиков, у вас все еще есть проблема O (N ^ 2), и вы можете обнаружить, что вам нужно что-то сделать поверх того, на что ссылается Кадж. (В литературе по обнаружению 3D-столкновений это известно как наличие как широкофазного, так и узкофазного алгоритма. Мы сделаем что-то действительно быстрое, чтобы найти все возможные пары перекрытий, а затем что-то более дорогое, чтобы увидеть, если это возможно пары являются реальными парами.)

Широкофазный алгоритм, который я использовал ранее, это «подметание и сокращение»; для 2D вы должны поддерживать два отсортированных списка начала и конца каждого блока. Пока перемещение рамки не >> масштабируется от кадра к кадру, порядок этих списков не будет сильно меняться, и поэтому вы можете использовать пузырьковую или вставочную сортировку, чтобы поддерживать ее. Книга «Рендеринг в реальном времени» имеет хорошую рецензию на оптимизации, которые вы можете сделать, но она сводится к O (N + K) времени в широкой фазе, для N блоков, K из которых перекрываются, и с превосходным реальным миром производительность, если вы можете позволить себе N ^ 2 логических значений, чтобы отслеживать, какие пары ячеек пересекаются от кадра к кадру. Тогда у вас будет общее время O (N + K ^ 2), что составляет << O (N ^ 2), если у вас много блоков, но только несколько перекрытий.

Том Хадсон
источник
5

Здесь много математики для очень простой задачи, предположим, что у нас есть 4 точки, определенные для прямоугольника, сверху, слева, снизу, справа ...

В случае определения того, сталкиваются ли 2 канала, нам нужно только посмотреть, чтобы все возможные крайности, которые предотвратили бы столкновения, если ни один из них не соблюден, тогда 2 канала ДОЛЖНЫ столкнуться, если вы хотите включить граничные столкновения, просто замените> и < с соответствующими> = и = <.

struct aRect{
  float top;
  float left;
  float bottom;
  float right;
};

bool rectCollision(rect a, rect b)
{
  return ! ( b.left > a.right || b.right < a.left || b.top < a.bottom || b.bottom > a.top);
}
user35189
источник
Я, честно говоря, не уверен, почему это не самый популярный ответ. Это просто, правильно и эффективно.
3Dave
3

Альтернативная версия ответа ZorbaTHut:

bool DoBoxesIntersect(Box a, Box b) {
     return (abs(a.x - b.x) < (a.width + b.width) / 2) &&
     (abs(a.y - b.y) < (a.height + b.height) / 2);
}
Iain
источник
На самом деле эта арифметика работает в любом случае. Вы можете выполнить любую арифметическую операцию с любой стороны от <, и она не изменит ее (умножение на отрицательное означает, что вы должны изменить меньшее, чем). В этом примере ящики не должны сталкиваться. Если центр поля А находится в 1, он охватывает от -4 до 6. Поле В центрируется в 10 и охватывает 7,5-12,5, там нет столкновений ... Теперь метод, который Уоллаколо опубликовал, не только верен, но будет работать быстрее на языках, в которых реализовано короткое замыкание, так как большинство проверок все равно будет возвращать ложное значение, короткое замыкание может отключиться после как
Deleter
Да, я понял это, когда проснулся этим утром. Крис ошарашил меня своей <> путаницей.
Иан
1
Две проблемы: во-первых, деление имеет тенденцию быть значительно медленнее, чем умножение. Во-вторых, если используемые значения являются целыми числами, это может привести к некоторым проблемам с усечением целых чисел (ax = 0, bx = 9, a.width = 9, b.width = 10: abs (0-9) <(9 + 10) / 2, 9 <19/2, 9 <9, функция возвращает false, несмотря на то, что ящики окончательно пересекаются.)
ZorbaTHut
2

В зависимости от проблемы, которую вы пытаетесь решить, вам может быть лучше отслеживать объект, пока вы его перемещаете, то есть хранить список отсортированных x начальных и конечных положений и по одному для начальной и конечной y позиций. Если вам нужно выполнить МНОЖЕСТВО проверок перекрытия и, следовательно, необходимо оптимизировать их, вы можете использовать это в своих интересах, так как вы можете сразу посмотреть, кто заканчивает, закрывается слева от вас, все, кто заканчивает, находятся слева от этого, могут быть сокращены. немедленно. То же самое относится к верху, низу и справа.
Конечно, бухгалтерия стоит времени, поэтому она больше подходит для ситуации, когда мало движущихся объектов, но много проверок на совпадение.
Другим вариантом является пространственное хеширование, когда вы группируете объекты на основе приблизительной позиции (размер может поместить их в несколько сегментов), но опять же, только если объектов много, причем относительно небольшое их количество перемещается за одну итерацию из-за затрат на ведение бухгалтерского учета.
По сути, все, что позволяет избежать (n * n) / 2 (если вы проверяете объект a по отношению к b, вам не нужно проверять b по отношению к a), помогает больше, чем оптимизация проверок ограничивающего прямоугольника. Если ограничивающие проверки являются узким местом, я бы серьезно посоветовал поискать альтернативные решения проблемы.

Кая
источник
2

Расстояние между центрами не совпадает с расстоянием между углами (например, когда одна коробка находится внутри другой), поэтому в общем случае это решение является правильным (я думаю, что).

расстояние между центрами (скажем, х): abs(x1+1/2*w1 - x2+1/2*w2)или1/2 * abs(2*(x1-x2)+(w1-w2)

Минимальное расстояние есть 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). половинки отменяют так ..

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));
Владимир Дижур
источник
1
Что там с оператором return?
двойник
1

Вот моя реализация в Java, предполагающая архитектуру с двумя дополнениями . Если вы не пользуетесь двойным дополнением, используйте вместо этого стандартный вызов функции Math.abs :

boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
    return
        (
            lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
            lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
            lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
        ) == 0;
}

int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
    final int
            leftWidth = leftMax - leftMin,
            rightWidth = rightMax - rightMin,

            leftMid = leftMin + ((leftMax - leftMin) >> 1),
            rightMid = rightMin + ((rightMax - rightMin) >> 1);

    return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
}

int abs(int value) {
    final int mask = value >> (Integer.SIZE - 1);

    value ^= mask;
    value += mask & 1;
    return value;
}

Предполагая, что наполовину приличный компилятор / встроенный LLVM расширяет эти функции, чтобы избежать дорогостоящего жонглирования стека и просмотра таблиц. Это не удастся для входных значений, близких к 32-битным крайностям (т. Е. Integer.MAX_VALUEИ Integer.MIN_VALUE).

MadMartian
источник
0

Самый быстрый способ - объединить все 4 значения в одном векторном регистре.

Сохраните коробки в векторе со следующими значениями [ min.x, min.y, -max.x, -max.y ]. Если вы храните такие коробки, тест пересечения занимает всего 3 инструкции процессора:

_mm_shuffle_ps переупорядочить вторую коробку, переворачивая минимальную и максимальную половинки.

_mm_xor_psс магическим числом, _mm_set1_ps(-0.0f)чтобы перевернуть знаки всех 4 значений во втором поле.

_mm_cmple_ps сравнить все 4 значения друг с другом, сравнивая следующие два регистра:

[ a.min.x, a.min.y, -a.max.x, -a.max.y ] < [ b.max.x, b.max.y, -b.min.x, -b.min.y ]

Наконец, при необходимости, _mm_movemask_psполучить результат из векторного модуля в скалярный регистр. Значение 0 означает, что коробки пересекаются. Или, если у вас более двух блоков, это не нужно, оставьте значения в векторных регистрах и используйте побитовые операции для объединения результатов из нескольких блоков.

Вы не указали ни язык, ни платформу, но поддержка SIMD, подобная этой или очень похожей, доступна на всех платформах и языках. На мобильном телефоне ARM имеет NEON SIMD с очень похожим материалом. В .NET имеется Vector128 в пространстве имен System.Runtime.Intrinsics и т. Д.

Soonts
источник