Пересечение окружности с прямоугольником (2 видео)

Обнаружение столкновения окружности с прямоугольником (пересечение)

Как я могу определить, пересекаются ли круг и прямоугольник в евклидовом пространстве 2D? (т.е. классическая 2D геометрия)

Есть только два случая, когда круг пересекается с прямоугольником:

Либо центр круга лежит внутри прямоугольника, либо
Один из краев прямоугольника имеет точку в круге.

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

(Один из способов убедиться в этом: если ни одно из ребер не имеет точки в окружности (если все ребра находятся полностью «вне» окружности), то единственный способ, которым окружность все еще может пересекать многоугольник, — это если он полностью лежит внутри многоугольник.)

С этим пониманием, что — то вроде следующего будет работать, где круг имеет центр P и радиус R , а прямоугольник имеет вершины A , B , C , D в таком порядке (не полный код):

Если вы пишете какую-либо геометрию, возможно, у вас уже есть вышеуказанные функции в вашей библиотеке. В противном случае pointInRectangle() может быть реализовано несколькими способами; любой из общих пунктов в методах многоугольника будет работать, но для прямоугольника вы можете просто проверить, работает ли это:

И intersectCircle() это тоже легко реализовать: одним из способов было бы проверить, достаточно ли P близко подошва перпендикуляра к линии и между конечными точками, и проверить конечные точки в противном случае.

Круто то, что та же самая идея работает не только для прямоугольников, но и для пересечения круга с любым простым многоугольником — даже не должно быть выпуклым!

Вот как я бы это сделал:

Вот как это работает:

Первая пара линий вычисляет абсолютные значения разности x и y между центром круга и центром прямоугольника. Это объединяет четыре квадранта в один, так что вычисления не нужно выполнять четыре раза. На рисунке показана область, в которой теперь должен находиться центр круга. Обратите внимание, что отображается только один квадрант. Прямоугольник — это серая область, а красная граница очерчивает критическую область, которая находится ровно в одном радиусе от краев прямоугольника. Центр круга должен находиться внутри этой красной границы, чтобы произошло пересечение.

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

Третья пара линий обрабатывает простые случаи, когда окружность достаточно близка к прямоугольнику (в любом направлении), чтобы пересечение гарантировалось. Это соответствует оранжевой и серой полосам на изображении. Обратите внимание, что этот шаг должен быть выполнен после шага 2, чтобы логика имела смысл.

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

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

С любой приличной математической библиотекой это можно сократить до 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, если вы не хотите быстрой, но избыточной проверки.

Содержание

Обнаружение столкновения круг-прямоугольник (пересечение)
19 ответов
Расчет площади пересечения окружностей методом Монте-Карло
Обоснование
Реализация задачи на JavaScript
Пара гвоздей в метод Бутстрапа
🔥 Видео

Видео:Алгоритмы. Пересечение окружностейСкачать

Обнаружение столкновения круг-прямоугольник (пересечение)

Как я могу сказать, пересекаются ли круг и прямоугольник в 2D Евклидовом пространстве? (т. е. классическая 2D геометрия)

Видео:Всё про углы в окружности. Геометрия | МатематикаСкачать

19 ответов

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

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

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

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

С этим пониманием, что-то вроде следующего будет работать, где круг имеет центр P и радиусом R , а прямоугольник имеет вершины A , B , C , D в таком порядке (не полный код):

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

и intersectCircle() легко реализовать тоже: одним из способов было бы проверить, если нога перпендикуляра от P к линии достаточно близко и между конечными точками, и проверьте конечные точки в противном случае.

самое классное, что то же самое идея работает не только для прямоугольников, но и для пересечения окружности с любой простые полигональные — даже не должно быть выпуклым!

вот как я бы сделал это:

вот как это работает:

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

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

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

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

вот еще одно решение, которое довольно просто реализовать (и довольно быстро). Он будет ловить все пересечения, в том числе, когда сфера полностью вошла в прямоугольник.

С любой приличной математической библиотекой, которая может быть сокращена до 3 или 4 строк.

ваша сфера и прямая пересекаются IIF
расстояние между центром круга и одной вершиной прямой кишки меньше радиуса вашей сферы
Или
расстояние между центром круга и одним краем прямой кишки меньше радиуса сферы ([расстояние между точками ])
Или
центр круга находится внутри прямой кишки

центр круга внутри прямой кишки:
возьмите разделяющую ось: если существует проекция на линию, которая отделяет прямоугольник от точки, они не пересекаются

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

нужно просто внутренний продукт (x= [x1,x2] , y = [y1,y2] , x*y = x1*y1 + x2*y2 )

ваш тест будет выглядеть так:

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

Это самое быстрое решение:

обратите внимание на порядок выполнения и половины ширины/высоты предварительно просчитываться. Также квадрат делается «вручную», чтобы сохранить некоторые такты.

на самом деле, это гораздо проще. Вам нужно только две вещи.

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

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

вот мой код C для разрешения столкновения между сферой и неосевым выровненным полем. Он опирается на пару моих собственных библиотечных процедур, но он может оказаться полезным для некоторых. Я использую его в игре и он отлично работает.

чтобы визуализировать, возьмите цифровую клавиатуру. Если ключ » 5 » представляет ваш прямоугольник, то все ключи 1-9 представляют 9 квадрантов пространства, разделенных линиями, которые составляют ваш прямоугольник (с 5 внутри.)

1) Если центр круга находится в квадранте 5 (т. е. внутри прямоугольника), то две фигуры пересекаются.

с этим из Пути, есть два возможных случая: a) окружность пересекается с двумя или более соседними краями прямоугольник. b) окружность пересекается с одним краем прямоугольника.

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

эта функция обнаруживает столкновения (пересечения) между кругом и прямоугольником. Он работает как Э. Метод Джеймса в своем ответе, но этот обнаруживает столкновения для всех углов прямоугольника (а не только для правого угла).

Примечание:

aRect.происхождение.x и aRect.происхождение.y — координаты нижнего левого угла прямоугольника!

круге составляет.x и круге составляет.y — координаты круга Центр!

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

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

вы можете делать все это с помощью нескольких операций, и даже избежать функции sqrt.

и это все! Вышеприведенное решение предполагает происхождение в верхнем левом углу мира с осью x, направленной вниз.

Если вы хотите решение для обработки столкновений между движущимся кругом и прямоугольником это намного сложнее и покрыто в другом моем ответе.

Я создал класс для работы с формами надеюсь, вам понравится

Видео:Как найти центр круга #2Скачать

Расчет площади пересечения окружностей методом Монте-Карло

Эта статья родилась как логическое продолжение пятничного поста о методе Бутстрапа, а особенно, комментариев к нему. Не защищая метод Бутстрапа, стоит уделить внимание методам Монте-Карло. Здесь я хочу поделиться своим опытом применения Монте-Карло в одной из своих практических задач, а также обоснованием законности этого применения.

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

Обоснование

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

А вот решения общего случая для пересечения даже трех окружностей уже далеко не так тривиальны. В процессе поиска я нашел даже исследования по расчету площади пересечения N окружностей, однако они настолько же интересны, насколько и сложны.

Здесь на сцену выходит метод Монте-Карло. Благодаря современным компьютерным мощностям этот метод позволяет провести большое количество статистических испытаний, на основе результатов которых делается обобщение.

Итак, алгоритм расчета площади любой фигуры методом Монте-Карло сводится к следующему:

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

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

Реализация задачи на JavaScript

Пара гвоздей в метод Бутстрапа

Если говорить именно о методе Бутстрапа, то мое личное мнение заключается в том, что случайная генерация набора данных по имеющемуся набору в общем случае не может служить для оценки закономерностей, поскольку сгенерированная информация не является достоверной. В общем, это же, только более умными (и нередко более резкими) словами, говорят и многие авторы, например, Орлов в своем учебнике по Эконометрике.