Как я могу определить, пересекаются ли круг и прямоугольник в евклидовом пространстве 2D? (т.е. классическая 2D геометрия)
192
Как я могу определить, пересекаются ли круг и прямоугольник в евклидовом пространстве 2D? (т.е. классическая 2D геометрия)
Ответы:
Есть только два случая, когда круг пересекается с прямоугольником:
Обратите внимание, что для этого не требуется, чтобы прямоугольник был параллельным оси.
(Один из способов убедиться в этом: если ни одно из ребер не имеет точки в окружности (если все ребра находятся полностью «вне» окружности), то единственный способ, которым окружность все еще может пересекать многоугольник, - это если он полностью лежит внутри многоугольник.)
С этим пониманием, что - то вроде следующего будет работать, где круг имеет центр
P
и радиусR
, а прямоугольник имеет вершиныA
,B
,C
,D
в таком порядке (не полный код):Если вы пишете какую-либо геометрию, возможно, у вас уже есть вышеуказанные функции в вашей библиотеке. В противном случае
pointInRectangle()
может быть реализовано несколькими способами; любой из общих пунктов в методах многоугольника будет работать, но для прямоугольника вы можете просто проверить, работает ли это:И
intersectCircle()
это тоже легко реализовать: одним из способов было бы проверить, достаточно лиP
близко подошва перпендикуляра к линии и между конечными точками, и проверить конечные точки в противном случае.Круто то, что та же самая идея работает не только для прямоугольников, но и для пересечения круга с любым простым многоугольником - даже не должно быть выпуклым!
источник
Вот как я бы это сделал:
Вот как это работает:
Первая пара линий вычисляет абсолютные значения разности x и y между центром круга и центром прямоугольника. Это объединяет четыре квадранта в один, так что вычисления не нужно выполнять четыре раза. На рисунке показана область, в которой теперь должен находиться центр круга. Обратите внимание, что отображается только один квадрант. Прямоугольник - это серая область, а красная граница очерчивает критическую область, которая находится ровно в одном радиусе от краев прямоугольника. Центр круга должен находиться внутри этой красной границы, чтобы произошло пересечение.
Вторая пара линий исключает простые случаи, когда круг находится достаточно далеко от прямоугольника (в любом направлении), и пересечение невозможно. Это соответствует зеленой области на изображении.
Третья пара линий обрабатывает простые случаи, когда окружность достаточно близка к прямоугольнику (в любом направлении), чтобы пересечение гарантировалось. Это соответствует оранжевой и серой полосам на изображении. Обратите внимание, что этот шаг должен быть выполнен после шага 2, чтобы логика имела смысл.
Оставшиеся строки рассчитывают сложный случай, когда круг может пересекать угол прямоугольника. Чтобы решить, вычислите расстояние от центра круга и угла, а затем убедитесь, что расстояние не больше радиуса круга. Это вычисление возвращает false для всех кругов, центр которых находится внутри красной заштрихованной области, и возвращает true для всех кругов, центр которых находится внутри белой заштрихованной области.
источник
;)
circleDistance_x = abs(circle.x - (rect.x-rect.w/2)); circleDistance_y = abs(circle.y - (rect.y-rect.h/2));
Вот еще одно решение, которое довольно просто реализовать (и довольно быстро). Он поймает все пересечения, в том числе, когда сфера полностью вошла в прямоугольник.
С любой приличной математической библиотекой это можно сократить до 3 или 4 строк.
источник
Ваша сфера и прямоугольник пересекаются. IIF.
Расстояние между центром круга и одной вершиной вашего прямоугольника меньше радиуса вашей сферы
ИЛИ
расстояние между центром круга и одним краем вашего прямоугольника меньше радиуса вашей сферы ( [ расстояние от линии до точки ])
ИЛИ
центр окружности находится внутри расстояния от
точки до точки:
расстояние до точки:
центр круга внутри прямоугольника:
выберите разделительную ось: если существует проекция на линию, которая отделяет прямоугольник от точки, они не пересекаются
Вы проецируете точку на линиях, параллельных сторонам вашего прямоугольника, и затем можете легко определить, пересекаются ли они. если они не пересекаются на всех 4 проекциях, они (точка и прямоугольник) не могут пересекаться.
вам просто нужен внутренний продукт (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)
ваш тест будет выглядеть так:
это не предполагает выравнивания по оси прямоугольника и легко расширяется для проверки пересечений между выпуклыми наборами.
источник
Это самое быстрое решение:
Обратите внимание на порядок выполнения, и половина ширины / высоты предварительно вычисляется. Также возведение в квадрат выполняется "вручную", чтобы сохранить некоторые тактовые циклы.
источник
Самое простое решение, которое я придумал, довольно простое.
Это работает, находя точку в прямоугольнике, ближайшем к кругу, затем сравнивая расстояние.
Вы можете сделать все это с помощью нескольких операций и даже избежать использования функции sqrt.
И это все! Приведенное выше решение предполагает начало координат в верхнем левом углу мира с осью X, направленной вниз.
Если вы хотите найти решение для обработки столкновений между движущимся кругом и прямоугольником, оно намного сложнее и освещено в другом моем ответе.
источник
На самом деле, это гораздо проще. Вам нужны только две вещи.
Сначала вам нужно найти четыре ортогональных расстояния от центра круга до каждой линии прямоугольника. Тогда ваш круг не будет пересекать прямоугольник, если любые три из них больше, чем радиус круга.
Во-вторых, вам нужно найти расстояние между центром круга и центром прямоугольника, тогда ваш круг не будет находиться внутри прямоугольника, если расстояние больше половины длины диагонали прямоугольника.
Удачи!
источник
Вот мой C-код для разрешения столкновения между сферой и не выровненным по оси прямоугольником. Он опирается на пару моих собственных библиотечных процедур, но может оказаться полезным для некоторых. Я использую его в игре, и он отлично работает.
источник
Для визуализации возьмите цифровую клавиатуру. Если клавиша «5» представляет ваш прямоугольник, то все клавиши 1–9 представляют 9 квадрантов пространства, разделенных линиями, составляющими ваш прямоугольник (с 5 внутри.)
1) Если центр круга находится в квадранте 5 (то есть внутри прямоугольника), тогда две фигуры пересекаются.
При этом существует два возможных случая: а) круг пересекается с двумя или более соседними краями прямоугольника. б) круг пересекается с одним краем прямоугольника.
Первый случай прост. Если круг пересекается с двумя соседними краями прямоугольника, он должен содержать угол, соединяющий эти два ребра. (Это, или его центр лежит в квадранте 5, который мы уже охватили. Также обратите внимание, что случай, когда круг пересекается только с двумя противоположными краями прямоугольника, также покрыт.)
2) Если любой из углов A, B, C, D прямоугольника находится внутри круга, то эти две фигуры пересекаются.
Второй случай сложнее. Следует отметить, что это может произойти только тогда, когда центр круга находится в одном из квадрантов 2, 4, 6 или 8. (Фактически, если центр находится в каком-либо из квадрантов 1, 3, 7, 8, соответствующий угол будет ближайшей точкой к нему.)
Теперь у нас есть случай, когда центр круга находится в одном из «реберных» квадрантов, и он пересекается только с соответствующим ребром. Тогда точка на краю, ближайшая к центру круга, должна лежать внутри круга.
3) Для каждой линии AB, BC, CD, DA построите перпендикулярные линии p (AB, P), p (BC, P), p (CD, P), p (DA, P) через центр круга P. Для каждая перпендикулярная линия, если пересечение с исходным ребром лежит внутри круга, то две фигуры пересекаются.
Существует ярлык для этого последнего шага. Если центр окружности находится в квадранте 8, а ребро AB - это верхнее ребро, точка пересечения будет иметь координату Y от A и B и координату X от центра P.
Вы можете построить четыре пересечения линий и проверить, лежат ли они на соответствующих ребрах, или выяснить, в каком квадранте P находится, и проверить соответствующее пересечение. Оба должны упростить до одного и того же логического уравнения. Остерегайтесь того, что вышеприведенный шаг 2 не исключает, что P находится в одном из «угловых» квадрантов; он просто искал пересечение.
Изменить: Как оказалось, я упустил из виду простой факт, что № 2 является подслучае № 3 выше. Ведь углы тоже являются точками по краям. Посмотрите ответ @ ShreevatsaR ниже для хорошего объяснения. А пока, забудьте про № 2, если вы не хотите быстрой, но избыточной проверки.
источник
Эта функция обнаруживает столкновения (пересечения) между Кругом и Прямоугольником. В своем ответе он работает как метод e.James, но этот обнаруживает столкновения для всех углов прямоугольника (не только для правого угла).
НОТА:
aRect.origin.x и aRect.origin.y - это координаты нижнего левого угла прямоугольника!
aCircle.x и aCircle.y - это координаты Центра Круга!
источник
У меня есть метод, который позволяет избежать дорогостоящего пифагора, если в этом нет необходимости - т.е. при этом ограничивающие прямоугольники прямоугольник и круг не пересекаются.
И это будет работать для неевклидовых тоже:
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon
. Конечно, если вы используете этот метод normDist, вам нужно будет создатьnormedDist = dist*dist;
для кругаСмотрите полный код BBox и Circle моего проекта GraphHopper .
источник
Я создал класс для работы с фигурами надеюсь, вам понравится
источник
Вот модифицированный код, работающий на 100%:
Бассам Алугили
источник
Вот быстрый однострочный тест для этого:
Это выровненный по оси случай, когда
rect_halves
положительный вектор указывает от середины прямоугольника к углу. Выражение внутриlength()
представляет собой дельта-вектор отcenter
ближайшей точки в прямоугольнике. Это работает в любом измерении.источник
Это эффективно, потому что:
источник
работал для меня (работает только при угле прямоугольника 180)
источник
Немного улучшив ответ e.James :
Это вычитает
rect.w / 2
иrect.h / 2
один раз вместо трех раз.источник
Для тех, кто должен вычислить столкновение Круг / Прямоугольник в Географических Координатах с SQL,
это моя реализация в предложенном оракулом 11 алгоритме e.James .
Для ввода требуются координаты окружности, радиус окружности в км и координаты двух вершин прямоугольника:
источник
Работает, только что понял это неделю назад и только сейчас приступил к тестированию.
источник
источник
Предполагая, что у вас есть четыре ребра прямоугольника, проверьте расстояние от ребер до центра круга, если его радиус меньше радиуса, то фигуры пересекаются.
источник
Если прямоугольник пересекается с кругом, одна или несколько угловых точек прямоугольника должны быть внутри круга. Предположим, что четыре точки прямоугольника - это A, B, C, D. хотя бы один из них должен пересекать круг. поэтому, если расстояние от одной точки до центра окружности меньше радиуса окружности, оно должно пересекать окружность. Чтобы получить расстояние вы можете использовать теорему Пифагора,
Эта техника имеет некоторые ограничения. Но это будет работать лучше для разработчиков игр. особенно обнаружение столкновений
Это хорошее обновление для алгоритма Арво
источник