Как определить коллизию квадратов?

Question

[Filipp42]

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

Comments

[Армянское Радио]

Если стороны квадратов параллельны осям координнат, дело сводится к проверке неравенств.

[Сергей П]

Как же это вы игру пишете, если не способны тривиальное условие сформулировать?
Это, пожалуй, самое простое в написании игры. С остальными задачами тоже сюда придёте?
Так и где ваша попытка решить эту задачу? Где ваш код, который не работает?

[Filipp42]

Сергей Паньков, Всё работает, только немного странно. Оказалось, формула, которую мне дали принимает координаты центров.
Вот код: https://notabug.org/Regrin/SDL2-experements/src/ma...

[Модератор]

Фрагменты кода надо размещать в виде текста и оборачивать тэгом code для корректного отображения. Удобно делать кнопкой </>
Это обязательно, см.п.3.8 Регламента.
Сюда же относится traceback, ввод и вывод в консоли и другая структурированная текстовая инфа.

[Алан Гибизов]

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

[Filipp42]

Алан Гибизов, Так дело не в коде, а в алгоритме. Мне как раз нужно его придумать.

[Евгений Шатунов]

Filipp42, для алгоритмов фигуру удобнее представлять не точкой и размером, а двумя точками - минимальной и максимальной точками в пространстве фигуры. Из этих двух точек выражаются все остальные метрики: аксиальный размер фигуры, точка центра, все четыре угла фигуры.
И операции с фигурами в этом случае становятся значительно проще. Проверка на принадлежность одной фигуры пространству другой - это проверка всего двух пар точек. Проверка пересечения двух фигур - это просто четыре проверки по осям координат.
Даже придумывать ничего не надо в этом случае. Оптимальные варианты сами в голову приходят. Тебе просто надо поменять представление своих фигур.

[Filipp42]

Евгений Шатунов, Представление фигур привязано к SDL2 - графической библиотеке. Но да, возможно, вы правы.

[Алан Гибизов]

Filipp42, дело вот в чем:
Либо у вас есть свое решение, пусть не правильное, и вы спрашиваете, что в нем не так; либо вы пришли, чтобы за вас решили и дали готовый алгоритм.
В первом случае надо либо опубликовать собственно ваш алгоритм, либо его реализацию в коде.
Во втором вам на фриланс.

[Алан Гибизов]

Filipp42, кстати, с координатами центров вариант тоже работает. И он может быть реализован и для квадратных и для круглых объектов, немного разные варианты.

[Евгений Шатунов]

Filipp42, я не возможно прав. Я прав. Как прав я и в том, что представление фигур в твоем собственном коде привязано только к твоему желанию выбрать это представление.

Answer 1

[Сергей П]

Алгоритмов тут за вас никто придумывать не будет. Этот ресурс не для этого.
Учитесь решать такие задачи начиная с более простых.
Двухмерный случай с квадратами можно упростить понизив размерность задачи.
Представьте, что у вас не квадраты, а отрезки и не на плоскости, а на оси.
Нужно сформулировать булево выражение, которое будет истинно только в случае наложения отрезков (хотя бы частичного).
Вам уже предлагали в комментариях попробовать представить квадраты не размерами, а координатами границ. Если у вас возникнут трудности и с вычислением координат правых нижних углов, то у меня для вас плохие новости...
Попробуйте решить задачу для отрезков на оси, а потом подумать как расширить её для квадратов на плоскости.
Если на этом этапе ещё не очевидно решение, то начинать следует с более простого. Хотя, казалось бы, куда уж проще.

Answer 2

[Wataru]

Вот тут программисту и нужна математика (совсем чуть чуть).

Квадрат - это все точки (X, Y), которые удовлетворяют неравенствам:

x1 <= X <= x1 + w1
y1 <= Y <= y1 + w1

Пересечение двух квадратов - это точки, которые удовлетворяют одновременно каждой паре неравенств, т.е. удовлетворяют сразу четырем неравенствам:

x1 <= X <= x1 + w1
y1 <= Y <= y1 + w1
x2 <= X <= x2 + w2
y2 <= Y <= y2 + w2

Тут уже видно, что фактически есть пара неравенств на X, и есть пара неравенств на Y. Они независимые. Вот и получается, что пересечение можно искать отдельно по каждой оси.

Рассмотрим одну пару:

x1 <= X <= x1 + w1
x2 <= X <= x2 + w2

Вообще, такие системы неравнеств решают в школе, классе этак в 7.

Сконцентрируемся на левых границах. Что значит, что X >= x1 и X >= x2? Это значит, что X больше обоих чисел x1 и x2. Это можно записать одним неравнеством - X больше максимума из двух чисел:
max(x1, x2) <= X

Так же и по правым границам:
X <= min(x1 + w1, x2 + w2)

В итоге:
max(x1, x2) <= X <= min(x1 + w1, x2 + w2)

Эти неравенства имеют решение, если левая граница не превосходит правой:
max(x1, x2) <= min(x1 + w1, x2 + w2)

Вот у вас условие, что по оси OX есть хоть одна точка пересечения. Если вам касающиеся квадраты не надо считать пересекающимеся, то замените знак <= на строгое неравенство.

Точно также проверьте, что есть пересечение по OY. Если пересечение есть и там и там, то квадраты пересекаются. Т.е. весь ваш код должен найти 2 минимума, 2 максимума, сделать 2 сравнения и соединить их через логичиское И.

Comments

[Akina]

Чё так сложно-то? минимумы какие-то... все гораздо проще. Если есть две проекции на ось [A,B] и [C,D], то они пересекаются, если ((A < D) AND (C < B)). Ну или, как сформулировала одна гражданка, "любое начало меньше другого кончала".

[Wataru]

Akina, Если человеку это сразу не очевидно, то надо расписывать подробно.

[Akina]

С учётом A < B и C < D есть всего 6 вариантов взаимного расположения их на числовой оси. С учётом симметрии - 3.

-A-B-C-D- пересечения нет, ((A < D) AND (C < B)) не выполняется
-A-C-B-D- пересечение есть, ((A < D) AND (C < B)) выполняется
-A-C-D-B- пересечение есть, ((A < D) AND (C < B)) выполняется

Вот что тут ещё подробнее надо расписывать?

[Wataru]

Akina, А вы распишите, почему только 6 вариантов и почему достаточно только 3 рассматривать. Подробно, чтобы человек не дружащий с математикой и логикой понял. У вас не сильно короче моего ответа получится.

А вообще, я предпочитаю минимумы/максимумы, потому что это не только позволяет проверить наличие пересечения, но и сразу его находит.

[Filipp42]

Спасибо!

Answer 3

[Griboks]

Для разнообразия: расстояние между центрами квадратов меньше суммы радиусов вписанных окружностей.

Comments

[Wataru]

Не работает, если квадраты почти касаются по стороне. Расстояние там почти что 1 сторона. А сумма радиусов - sqrt(2)*сторона.

А стоп. вписанных. Тогда не работает, когда они чуть-чуть пересекаются по углам.

[Griboks]

Wataru, тогда используйте радиус описанных или между ними в зависимости от требуемой погрешности.

[Wataru]

Griboks, вписанная окружность будет давать ложно-отрицательный ошибки. Описанная - ложно полложительные. Плюс эти вычисления будут тяжелее точной проверки, ибо для расстояния надо или корни считать, или сумму радиусов в квадрат возводить.

[Griboks]

Wataru, суть в том, что эти вычисления намного легче кучи проверок, поэтому есть смысл их использовать в обмен на точность.

[Wataru]

Griboks, чем оно легче кучи проверок? Точнее, легче одной проверки?

[hint000]

Wataru,

вписанная окружность будет давать ложно-отрицательный ошибки. Описанная - ложно полложительные.

Можно взять средний радиус между вписанной и описанной для статистического уменьшения погрешности. Получим столкновения кругов, несущих на себе квадратный камуфляж. Солдатско-математический юморок, если такой вообще бывает.

чем оно легче кучи проверок?

А вот для случая квадратов с произвольным наклоном было бы существенно проще. Но, учитывая, что там по физике в сто раз больше рассчётов будет, так эта сложность определения момента столкновения уже покажется смехотворно простой.

[Griboks]

Wataru,

чем оно легче кучи проверок?

Меньше сложность, поэтому быстрее работает.

точнее, легче одной проверки?

Проверок очень много как и других операций.
В вашем примере max(x1, x2) <= min(x1 + w1, x2 + w2) можно увидеть и вызовы функции, и сортировку, и промежуточные сложения, и дерево ветвлений.

Кроме того, вы забыли учесть произвольный поворот квадратов в пространстве (впроечем, автор вроде их не поворачивает).

Напротив сравнить столкновение окружностей (x1-x2)^2+(y1-y2)^2<=(r1+r2)^2 занимает всего 8 операций независимо от поворота или размерности пространства, тяжёлые из которых - это вычитания.

[Wataru]

hint000,
> Можно взять средний радиус между вписанной и описанной

Тогда будут и те и другие ошибки.

Вот для невыровненых по осям фигур, да в геймдеве, где можно и неточности допускать, или для сложных моделей, действительно, аппроксимируют фигуры всякими кругами-шарами. Но в этой задаче смысла так делать точно нет.

[Griboks]

Wataru,

в геймдеве действительно, аппроксимируют фигуры всякими кругами-шарами

Пишу простенькую игру,

Но в этой задаче смысла так делать точно нет.

[Wataru]

Griboks,

можно увидеть и вызовы функции, и сортировку, и промежуточные сложения, и дерево ветвлений.

Нормальные языки никаких вызовов не делают. Это все инлайнится. Сортировки никакой нет.

Поворота в пространстве тут нет, иначе квадраты не задать одним углом и размером.

И возведение в квадрат - более тяжелая операция, чем вычитание.

[Wataru]

Griboks, вы пропустили всю предыдущую часть сообщения. Когда формы сложные. Если проще сравнить исходные фигуры, то круги не используют. Даже в геймдеве.

[Griboks]

Wataru, давайте посчитаем вместе. У вас 4 случая для оси Ox, т.е. 10 операций, всего на обе оси получается 20. А у меня только 8, и они универсальные, т.е. в 2,5 раза меньше.

Если ещё учесть векторные процессоры, то нетрудно вычислить, скажем, fps игры при 5000 объектов на карте. (Но мне трудно, потому что я не знаю, как работают векторные условия. Возможно, это даже не векторные операции!)

[Wataru]

Griboks,

Итак. Вы признаете, что ваше решение не точное. Но утверждаете, что оно имеет право на жизнь, потому что оно быстрее.

Возможно, ваше решение быстрее неоптимальной реализации точного решения (но это не точно). Но оно 100% медленнее оптимальной реализации.

Во-первых-, вы читерите немного. Квадраты же заданы углами. Центр и радиусы вам надо считать. Если же они у вас предподсчитаны, то и в моем решении можно предподсчитать x1r=x1l+w1 и т.д.

У вас 4 случая для оси Ox, т.е. 10 операций

Как вы случаи-то считаете? Там 2 операции минимума и одно сравнение (вычитание). И так по двум осям, т.е. 4 минимума, 2 сравнения и одно логичесское И. Минимум в нормальных языках итак
оптимизирован до 3 процессорых инструкций (cmp, mov, cmovle - всего 3 такта. Как 3 вычитания) . А мы же тут скоростью меряемся, так что питон условный рассматривать смысла нет, правда? Т.е. неоптимальная, в лоб реализация моего решения занимает 15 тактов (3*4 для минимумов, 2 для сравнений, 1 для логического И).

Потом, как заметил Akina, max(x1l,x2l) <= min(x1r, x2r) тут эквивалентно x1l <= x2r && x2l <= x1r.

В итоге, оптимальная реализация точного метода занимает 4 вычитания (сравнения) и 3 логических и:

x1l <= x2r && x2l <= x1r && y1l <= y2r && y2l <= y1r

. 7 самых быстрых операций. Всего 7 тактов.

У вас же 4 сложения, 3 умножения, одно сравнение. Уже 8 операций. Но умножения занимают сильно больше 1 такта, как для сложения/вычитания/сравнения.

Плюс, в вашем решении нельзя обойтись только целыми числами. Даже если входные данные целые. Потому что радиусы, да и центры окружностей будут вещественными. Т.е. оно еще на порядки медленнее.

[Griboks]

Wataru, я так понимаю, что цель ваших комментариев - это всех запутать и доказать мою ошибку. Что ж... Тогда давайте опустим бессмысленные спорты, создадим проект на Unity 3D (C#, .Net Framework 4.8) и напишем свою ECS для проверки коллизий.

Проверяем два метода расчёта коллизий: через квадраты

Collisions[i].collisionFlag = unit1.leftBorder <= unit2.rightBorder && unit2.leftBorder <= unit1.rightBorder && unit1.topBorder <= unit2.bottomBorder && unit2.topBorder <= unit1.bottomBorder;

и через окружности

Collisions[i].collisionFlag = (unit1.centerX - unit2.centerX) * (unit1.centerX - unit2.centerX) + (unit1.centerY - unit2.centerY) * (unit1.centerY - unit2.centerY) <= collisionDistance;

.

Добавим много юнитов на сцену, всё, что можно, заранее закэшируем. Затем посчитаем средний FPS за 1000 кадров.



Как вы можете заметить, прирост производительности от "очень тяжёлого умножения" радиусов окружностей не просто значительный. Разрыв заметно увеличивается для больших сцен.

[Griboks]

Wataru,

Но умножения занимают сильно больше 1 такта, как для сложения/вычитания/сравнения.

Плюс, в вашем решении нельзя обойтись только целыми числами. Даже если входные данные целые. Потому что радиусы, да и центры окружностей будут вещественными. Т.е. оно еще на порядки медленнее.

Это, разумеется, полная ерунда. Никаких вещественных чисел не задействуется, потому что квадрат целого числа даёт целое число. А раз так, то, сюрприз, заменяем мега тяжёлое умножение на бинарный сдвиг.

[Wataru]

Griboks, Во-первых, что за collisionDistance у вас там в коде? Там должен быть квадрат суммы радиусов.

Во-вторых, давайте весь код. Непонятно, что вы там сделали. И надо смотреть профайлером. Один код может быть быстрее другого совсем не потому, что вы думаете. Скажем, у вас там объекты лежат в памяти более плотно и т.д. А может shortcut evaluation условных bool операторов тут все портит мне. Тогда чуть-чуть переписав A && B && C &&D в A & B & C & D выключит эту оптимизацию.

В-третьих,

потому что квадрат целого числа даёт целое число.

Что там за целое число-то? x1-x2 может быть половинчатым. Радиус вписанной окружности может тоже быть половинчатым. Радиус описанной окружности - (длина квадрата)/sqrt(2). В принципе, можно свести все к целым числам, но тут надо лишние телодвижения сделать, их я в вашем коде не вижу.

[Griboks]

Wataru,

что за collisionDistance у вас там в коде? Там должен быть квадрат суммы радиусов.

Это кеш расстояния столкновения. Я закэшировал все данные, кроме позиции юнита, как вы и предлагали, чтобы избавиться от "читинга".

Что там за целое число-то? x1-x2 может быть половинчатым.

Ага, 7 - 5 = 2.5, всегда из int получаю float при сложении)

Радиус вписанной окружности может тоже быть половинчатым. Радиус описанной окружности - (длина квадрата)/sqrt(2).

Ну хорошо, давайте закэшируем r=a/2*2. Теперь можно смело заявить, что алгоритм работает для целых чисел тоже. Впрочем, речь о целых числах никогда не шла.

В принципе, можно свести все к целым числам, но тут надо лишние телодвижения сделать, их я в вашем коде не вижу.

Вы, видимо, мало работали в геймдеве. Нет принципиальной разницы между координатами центра или угла. Это легко доказать, т.к. смещение системы координат не влияет на метрику (длину ветров/расстояние между точками).

Во-вторых, давайте весь код. Непонятно, что вы там сделали.

Хорошо, жду результатов замеров от вас с профайлером, супер-мега оптимизацией условий и, разумеется, максимальной деградацией формулы квадратов. Было бы чудесно построить графики, но у вас почему-то аллергия на питон.

public class GameObject
	{
		public float LeftBorder, TopBorder, CenterX, CenterY, RightBorder, BottomBorder, R;
	}


	public static class CollisionEngine
	{
		private static readonly (GameObject unit1, GameObject unit2, float collisionDistance, bool collisionFlag)[] Collisions;

		static CollisionEngine()
		{
			var units = new GameObject[1000];
			var random = new Random();
			for (var i = 0; i < units.Length; i++)
			{
				var xl = (float)(random.NextDouble() * 1000);
				var yl = (float)(random.NextDouble() * 1000);
				var r = (float)(random.NextDouble() * 10);
				units[i] = new GameObject { LeftBorder = xl, TopBorder = yl, R = r, CenterX = xl + r, CenterY = yl + r, RightBorder = xl + 2 * r, BottomBorder = yl + 2 * r };
			}

			Collisions = (from unit1 in units from unit2 in units where unit1 != unit2 select (unit1, unit2, (unit1.R + unit2.R) * (unit1.R + unit2.R), false)).ToArray();
		}

		private static void Update()
		{
			for (var i = 0; i < Collisions.Length; i++)
			{
				var (unit1, unit2, collisionDistance, f) = Collisions[i];
				// Check collisions here. Comment out needed algorithm.
				// Exact quadratic algorithm.
				Collisions[i].collisionFlag = unit1.LeftBorder <= unit2.RightBorder && unit2.LeftBorder <= unit1.RightBorder && unit1.TopBorder <= unit2.BottomBorder && unit2.TopBorder <= unit1.BottomBorder;
				//Quick round algorithm.
				// Collisions[i].collisionFlag = (unit1.centerX - unit2.centerX) * (unit1.centerX - unit2.centerX) + (unit1.centerY - unit2.centerY) * (unit1.centerY - unit2.centerY) <= collisionDistance;
			}
		}

		public static float TestFPS()
		{
			const int n = 1000;
			var s = new Stopwatch();
			s.Start();
			for (var i = 0; i < n; i++) Update();
			s.Stop();
			return n / (s.ElapsedMilliseconds / 1000f);
		}
	}

[Wataru]

Это кеш расстояния столкновения. Я закэшировал все данные, кроме позиции юнита, как вы и предлагали, чтобы избавиться от "читинга".

Хитро. А можно я тогда значение

unit1.leftBorder <= unit2.rightBorder && unit2.leftBorder <= unit1.rightBorder && unit1.topBorder <= unit2.bottomBorder && unit2.topBorder <= unit1.bottomBorder;

закеширую?

Я понимаю, если бы вы для каждого квадрата какие-то его свойства предподсчитали. Центр там, размер, что угодно. А так вы часть вычисления для пары объектов вне таймера считаете. Конечно у вас быстрее будет.

Ага, 7 - 5 = 2.5, всегда из int получаю float при сложении)

Это вы расстояние не между центрами квадратов считаете, а между левыми углами? Ну да, если квадраты одного размера, то это еще будет работать. А когда один размера 10x10, а другой - 5x5, это уже не работает. Там надо расстояние между (x1+5, y1+5) и (x2+2.5, y2+2.5) считать. См. ниже.

Вы, видимо, мало работали в геймдеве. Нет принципиальной разницы между координатами центра или угла. Это легко доказать, т.к. смещение системы координат не влияет на метрику (длину ветров/расстояние между точками).

Это если квадраты одного размера, да. Представьте что большой квадрат и очень маленький совпадают по левому верхнему углу. Ваша формула даст 0, когда как центры довольно далеко друг от друга. В задаче про это не сказано, зато сказано, что даны "длинЫ стороны каждого квадрата". Да и у вас в коде радиусы везде разные считаются. Конечно, если считать неправильно, то у вас быстрее будет.

Вот из кучи таких мелких ошибок и читов и получается, что ваше решение работает быстрее. Правда неправильно. Вечером напишу свой бенчмарк. С++ вас устроит?

[Griboks]

Wataru,

А можно я тогда значение закеширую?

Как вы его закэшируете, если оно изменяется каждый кадр? Никак.

Я понимаю, если бы вы для каждого квадрата какие-то его свойства предподсчитали. Центр там, размер, что угодно.

Я заранее просчитал вообще всё, что смог для квадрата.

А так вы часть вычисления для пары объектов вне таймера считаете. Конечно у вас быстрее будет.

Ну так в этом и есть суть замены квадратов на круги. Чтобы было быстрее! Наконец вы это поняли.

Ну да, если квадраты одного размера, то это еще будет работать. А когда один размера 10x10, а другой - 5x5, это уже не работает. Там надо расстояние между (x1+5, y1+5) и (x2+2.5, y2+2.5) считать.

Хорошо, умножьте обе части неравенства на 2. Теперь остались только целые числа, как вы и хотели.

Да и у вас в коде радиусы везде разные считаются. Конечно, если считать неправильно, то у вас быстрее будет.

С удовольствием посмотрю правильный вариант. Возможно, ваша любимая игра на телефоне тормозит, именно потому что я когда-то неправильно посчитал радиус.

Вот из кучи таких мелких ошибок и читов и получается, что ваше решение работает быстрее. Правда неправильно.

Почему неправильно? Каких ошибок? В коде float, коллизии вычисляются. Забудьте про целые числа.

Вечером напишу свой бенчмарк.

Тогда с нетерпением буду ждать.

[Wataru]

Как вы его закэшируете, если оно изменяется каждый кадр? Никак.

Ну вы у себя предположили, что размеры объектов не меняются, да и сами объекты каждый кадр не меняются. Только якобы двигаются. Давайте я предположу, что объекты не двигаются. И то и другое - сильные допущения, в задаче не указанные. В общем случае у вас каждый кадр какие-то пули могут появлятся на экране, объекты менять размер. Такое кеширование - читерство.

Хорошо, умножьте обе части неравенства на 2. Теперь остались только целые числа, как вы и хотели.

Нет, это вы умножте у вас в коде и потом сравните.

Почему неправильно? Каких ошибок?

Еще раз, высчитывание расстояния между квадратами через их углы - неправильно, когда они разного размера. Это какое-то другое расстояние. Это плюс к тому, что у вас есть ложноотрицательные ошибки из-за аппроксимации окружностями.

Возможно, ваша любимая игра на телефоне тормозит, именно потому что я когда-то неправильно посчитал радиус.

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

[Griboks]

Wataru, Убедили, это читерство. Тогда давайте предположим, что объекты могут двигаться, растягиваться и поворачиваться, - по стандарту 2D игр.

Нет, это вы умножте у вас в коде и потом сравните.

Так у меня в коде float. Никто не использует целочисленные координаты в физических движках.

Еще раз, высчитывание расстояния между квадратами через их углы - неправильно, когда они разного размера. Это какое-то другое расстояние.

Нет, у меня используются координаты центра: unit1.centerX - unit2.centerX.

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

Ну так всё правильно. Это не баг, а фича, что при частых прыжках можно взлететь)

[Wataru]

Griboks,

Нет, у меня используются координаты центра:

Но тогда мои утверждения про целые числа в силе. А ваш саркастический комментарий про "складываю два int - получаю float" некорректен, ибо центр может быть половинчатым, поэтому вам при оценке вашего решения надо еще и мерять все умноженное на 2.

Убедили, это читерство. Тогда давайте предположим, что объекты могут двигаться, растягиваться и поворачиваться, - по стандарту 2D игр.

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

Вы перенесите вычисление расстояния между квадратами в код Update(). И в моем варианте вместо && используйте &. Посмотрите, как изменится время работы.

[Griboks]

Wataru,

Нет, давайте не отходить от задачи в этом вопросе.

Так что в итоге? Даны квадраты параллельные осям, разного размера и разных координат. Они могут перемещаться, но не могут растягиваться и поворачиваться. Я правильно понимаю?

Вы перенесите вычисление расстояния между квадратами в код Update().

Оно и так находится там. Закэшировано только минимальное расстояние до соприкосновения, т.е (r1+r2)^2.

И в моем варианте вместо && используйте &. Посмотрите, как изменится время работы.

Вы не поверите, но результаты ухудшились. Вместо 27 fps стало 19.

[Wataru]

Griboks, Был не прав, признаю.

Вот код: https://godbolt.org/z/PTh5oM188

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

Circles:        1.48417ms found 369434 intersections
Squares:        1.58796ms found 429860 intersections

Решение с кругами процентов на 6% быстрее. И я не понимаю, почему. Если смотреть на ассемблерный код, то используются ровно те вычисления, что я и предпологал. Но моя интуиция меня подвела. Возможно, потому что там 8 обращений к памяти, а не 6, как у вас. А может, потому что сравнения чуть медленнее, ведь там надо не только вычитание сделать и флаги установить, надо флаг еще в регистр скопировать. И imul работает на удивление быстро. С float-ами результат примерно такой же.

Answer 4

[Артем]

Для определения коллизии между двумя квадратами можно использовать простой алгоритм:

Определить границы каждого квадрата, то есть вычислить координаты левого верхнего угла и правого нижнего угла для каждого квадрата.
Проверить, пересекаются ли границы квадратов по осям X и Y. Если пересекаются, значит квадраты могут столкнуться.
Для проверки столкновения на самом деле нам нужно убедиться, что оба квадрата пересекаются на самом деле, а не только их границы. Для этого нужно проверить, есть ли пересечение между сторонами квадратов.
Вот пример функции на JavaScript, которая реализует этот алгоритм:

function detectCollision(sq1, sq2) {
  // вычисляем границы квадратов
  const sq1_left = sq1.x;
  const sq1_right = sq1.x + sq1.side;
  const sq1_top = sq1.y;
  const sq1_bottom = sq1.y + sq1.side;
  
  const sq2_left = sq2.x;
  const sq2_right = sq2.x + sq2.side;
  const sq2_top = sq2.y;
  const sq2_bottom = sq2.y + sq2.side;
  
  // проверяем, пересекаются ли границы квадратов по осям X и Y
  const x_collide = sq1_right >= sq2_left && sq1_left <= sq2_right;
  const y_collide = sq1_bottom >= sq2_top && sq1_top <= sq2_bottom;
  
  // если пересекаются, проверяем наличие пересечения сторон
  if (x_collide && y_collide) {
    const top_collision = sq1_bottom >= sq2_top && sq1_top <= sq2_top;
    const bottom_collision = sq1_top <= sq2_bottom && sq1_bottom >= sq2_bottom;
    const left_collision = sq1_right >= sq2_left && sq1_left <= sq2_left;
    const right_collision = sq1_left <= sq2_right && sq1_right >= sq2_right;
    
    return top_collision || bottom_collision || left_collision || right_collision;
  }
  
  return false;
}

Здесь sq1 и sq2 представляют объекты квадратов со следующими свойствами:

const square = {
  x: 100, // координата левого верхнего угла по оси X
  y: 50, // координата левого верхнего угла по оси Y
  side: 30 // длина стороны квадрата
};

Эта функция возвращает true, если квадраты пересекаются, и false в противном случае