Часть ради оптимизации, часть для целей обучения, я позволю себе спросить: как наиболее эффективно проверить, находится ли 2D-точка P
внутри повернутого 2D-прямоугольника XYZW
, используя C # или C ++?
В настоящее время я использую алгоритм «точка в треугольнике», описанный в книге «Обнаружение столкновений в реальном времени» , и запускаю его дважды (для двух треугольников, составляющих прямоугольник, скажем, XYZ и XZW):
bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
// Compute vectors
Vector2 v0 = C - A;
Vector2 v1 = B - A;
Vector2 v2 = P - A;
// Compute dot products
float dot00 = Vector2.Dot(v0, v0);
float dot01 = Vector2.Dot(v0, v1);
float dot02 = Vector2.Dot(v0, v2);
float dot11 = Vector2.Dot(v1, v1);
float dot12 = Vector2.Dot(v1, v2);
// Compute barycentric coordinates
float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
// Check if point is in triangle
if(u >= 0 && v >= 0 && (u + v) < 1)
{ return true; } else { return false; }
}
bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
if(PointInTriangle(X,Y,Z,P)) return true;
if(PointInTriangle(X,Z,W,P)) return true;
return false;
}
Тем не менее, у меня есть ощущение, что может быть чище и быстрее. В частности, чтобы уменьшить количество математических операций.
Ответы:
Простая и понятная оптимизация состояла бы в изменении конечного условия в
PointInTriangle
:код уже был в значительной степени
PointInRectangle
, было условие,(u + v) < 1
чтобы проверить, не находится ли он во «втором» треугольнике прямоугольника.В качестве альтернативы, вы также можете выполнить
isLeft
тест (первый пример кода на странице, также с большим объяснением) четыре раза и проверить, что все они возвращают результаты с одинаковым знаком (который зависит от того, были ли заданы точки по часовой стрелке или против часовой стрелки) для точка быть внутри. Это работает и для любого другого выпуклого многоугольника.источник
isLeft
метод. Он не требует триггерных функций (какVector2.Dot
и), что значительно ускоряет процесс.public static bool PointInRectangle(Vector2 P, Vector2 X, Vector2 Y, Vector2 Z, Vector2 W) { return !(( (Y.x - X.x) * (P.y - X.y) - (P.x - X.x) * (Y.y - X.y) ) < 0 || ( (Z.x - Y.x) * (P.y - Y.y) - (P.x - Y.x) * (Z.y - Y.y) ) < 0 || ( (W.x - Z.x) * (P.y - Z.y) - (P.x - Z.x) * (W.y - Z.y) ) < 0 || ( (X.x - W.x) * (P.y - W.y) - (P.x - W.x) * (X.y - W.y) ) < 0 ); }
isLeft
встроенного компилятора сделает для вас нечто похожее (и, вероятно, лучше, чем вы могли бы, потому что инженеры, пишущие компилятор, лучше знали процессоры, выбирая любой из самых быстрых вариантов), делая ваш код более читабельным с тем же или лучшим эффектом.Редактировать: Комментарий ОП скептически относился к эффективности предлагаемой проверки отрицательной круговой границы для улучшения алгоритма, чтобы проверить, находится ли произвольная 2D-точка в повернутом и / или движущемся прямоугольнике. Немного покопавшись в моем 2D игровом движке (OpenGL / C ++), я дополняю свой ответ, предоставляя тест производительности моего алгоритма по сравнению с текущими алгоритмами проверки точки-прямоугольника ОП (и их вариациями).
Первоначально я предложил оставить алгоритм на месте (так как он почти оптимален), но упростил с помощью простой игровой логики: (1) использование предварительно обработанного круга вокруг исходного прямоугольника; (2) сделать проверку расстояния и находится ли точка в заданном круге; (3) использовать OP или любой другой простой алгоритм (я рекомендую алгоритм isLeft, как указано в другом ответе). Логика, лежащая в основе моего предложения, заключается в том, что проверка, находится ли точка внутри круга, значительно эффективнее, чем проверка границы повернутого прямоугольника или любого другого многоугольника.
Мой первоначальный сценарий для теста производительности состоит в том, чтобы запустить большое количество появляющихся и исчезающих точек (чье положение меняется в каждом игровом цикле) в ограниченном пространстве, которое будет заполнено примерно 20 вращающимися / движущимися квадратами. Я опубликовал видео ( ссылка на YouTube ) в целях иллюстрации. Обратите внимание на параметры: количество случайно появляющихся точек, число или прямоугольники. Я сравню со следующими параметрами:
OFF : простой алгоритм, предоставляемый OP, без отрицательных проверок границы круга
НА : использование обработанных (граничных) окружностей вокруг прямоугольников в качестве первой проверки исключения
ON + Стек : создание круговых границ во время выполнения в цикле в стеке
ON + квадратное расстояние : использование квадратного расстояния в качестве дополнительной оптимизации, чтобы избежать использования более дорогого алгоритма квадратного корня (Pieter Geerkens).
Вот краткое изложение различных характеристик различных алгоритмов, показывающее время, необходимое для итерации цикла.
Ось X показывает повышенную сложность, добавляя больше точек (и таким образом замедляя цикл). (Например, при 1000 случайно появляющихся точечных проверках в конфиденциальном пространстве с 20 прямоугольниками цикл повторяется и вызывает алгоритм 20000 раз.) Ось Y показывает время (мс), необходимое для завершения всего цикла с использованием высокого разрешения Таймер производительности. Более 20 мс было бы проблематично для приличной игры, так как для интерполяции плавной анимации не использовались бы высокие fps, и игра иногда могла бы выглядеть таким образом «бурной».
Результат 1 : Предварительно обработанный алгоритм с круговой границей с быстрой отрицательной проверкой в цикле повышает производительность на 1900% по сравнению с обычным алгоритмом (5% от исходного времени цикла без проверки). Результат примерно пропорционален числу итераций в цикле, поэтому не имеет значения, проверяем ли мы 10 или 10000 случайно появляющихся точек. Таким образом, на этой иллюстрации можно безопасно увеличить количество объектов до 10 тыс. Без потери производительности.
Результат 2 : В предыдущем комментарии было высказано предположение, что алгоритм может быть быстрее, но интенсивнее использовать память. Однако обратите внимание, что сохранение числа с плавающей запятой для предварительно обработанного размера круга занимает всего 4 байта. Это не должно создавать никаких проблем, если ОП не планирует запускать одновременно более 100 000 объектов. Альтернативный и эффективный подход к памяти заключается в том, чтобы вычислить максимальный размер круга в стеке в цикле и позволить ему выходить из области действия при каждой итерации и, таким образом, практически не использовать память при неизвестной цене скорости. Действительно, результат показывает, что этот подход действительно медленнее, чем использование предварительно обработанного размера круга, но он все еще показывает значительное улучшение производительности примерно на 1150% (т.е. 8% от первоначального времени обработки).
Результат 3 : я дополнительно улучшаю алгоритм результата 1, используя квадратные расстояния вместо реальных расстояний и, таким образом, используя вычислительно дорогую операцию квадратного корня. Это лишь незначительно повышает производительность (2400%). (Примечание: я также пробую хеш-таблицы для предварительно обработанных массивов для приближений квадратных корней с похожим, но немного худшим результатом)
Результат 4 : я также проверяю перемещение / столкновение прямоугольников вокруг; однако это не меняет основных результатов (как и ожидалось), поскольку логическая проверка остается практически неизменной.
Результат 5 : я изменяю количество прямоугольников и нахожу, что алгоритм становится тем эффективнее, чем меньше переполнено пространство (не показано в демонстрации). Результат также несколько ожидаем, поскольку вероятность появления точки в крошечном пространстве между кругом и границами объекта уменьшается. С другой стороны, я пытаюсь увеличить количество прямоугольников слишком на 100 в одном и том же ограниченном крошечном пространстве и динамически изменять их размер во время выполнения внутри цикла (sin (итератор)). Это все еще работает очень хорошо с увеличением производительности на 570% (или 15% от первоначального времени цикла).
Результат 6 : я тестирую альтернативные алгоритмы, предложенные здесь, и нахожу очень небольшую, но незначительную разницу в производительности (2%). Интересный и более простой алгоритм IsLeft работает очень хорошо с повышением производительности на 17% (85% от первоначального времени расчета), но далеко от эффективности алгоритма быстрой отрицательной проверки.
Моя цель - сначала рассмотреть бережливый дизайн и игровую логику, особенно когда речь идет о границах и столкновениях. Текущий алгоритм OP уже достаточно эффективен, и дальнейшая оптимизация не так важна, как оптимизация самой концепции. Более того, хорошо сообщить объем и цель игры, так как эффективность алгоритма критически зависит от них.
Я предлагаю всегда пытаться тестировать любой сложный алгоритм на этапе разработки игры, поскольку простое рассмотрение простого кода может не раскрыть правду о фактической производительности во время выполнения. Предложенный алгоритм может даже не понадобиться здесь, если, например, кто-то хочет просто проверить, находится ли курсор мыши внутри прямоугольника или нет, или когда большинство объектов уже касаются. Если большинство проверок точек находятся внутри прямоугольника, алгоритм будет менее эффективным. (Однако тогда можно было бы установить границу «внутреннего круга» как вторичную отрицательную проверку.) Проверка границ круга / сферы очень полезна для любого приличного обнаружения столкновений большого числа объектов, которые, естественно, имеют некоторое пространство между ними. ,
источник
Определение прямоугольника с 4 точками позволяет сделать трапецию. Однако, если вы определите его как x, y, ширину, высоту и поворот вокруг его середины, вы можете просто повернуть точку, которую вы проверяете, на обратное вращение вашего прямоугольника (вокруг того же источника), а затем проверить, в исходном прямоугольнике.
источник
У меня не было времени для этого, но я предложил бы сохранить матрицу преобразования, которая преобразует прямоугольник в выровненный по осям квадрат в диапазоне x и y от 0 до 1. Другими словами, сохраните матрицу, которая превращает один угол прямоугольника в (0,0), а противоположный в (1,1).
Это, конечно, было бы дороже, если бы прямоугольник много перемещался и коллизия проверялась довольно редко, но если бы было гораздо больше проверок, чем обновлений прямоугольника, это было бы по крайней мере быстрее, чем первоначальный подход тестирования с двумя треугольниками, поскольку шесть точечных произведений будут заменены одним матричным умножением.
Но, как всегда, скорость этого алгоритма во многом зависит от вида проверок, которые вы ожидаете выполнить. Если большинство точек даже близко не расположены к прямоугольнику, выполнение простой проверки расстояния (например, (point.x - firstCorner.x)> aLargeDistance) может привести к значительному ускорению, а может даже замедлить работу, если почти все точки находятся внутри прямоугольника.
РЕДАКТИРОВАТЬ: Вот как будет выглядеть мой класс Rectangle:
Вот полный список моих тестов:
Код, конечно, не красивый, но я не вижу серьезных ошибок. С этим кодом я получаю результаты, которые показывают, что мое решение примерно в два раза быстрее, если прямоугольник перемещается между каждой проверкой. Если он не двигается, то мой код кажется более чем в пять раз быстрее.
Если вы знаете, как будет использоваться код, вы даже можете немного ускорить его, разделив преобразование и проверки на два измерения. Например, в гоночной игре, вероятно, было бы быстрее сначала проверить координату, указывающую направление движения, потому что многие препятствия будут находиться впереди или позади автомобиля, но вряд ли какое-либо будет справа или слева от него.
источник