Как определить, пересекает ли эллипс (сталкивается с) круг

Ответ 1

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

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

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

• Центр эллипса: (0,0)
• Центр круга: c = (cx, cy)
• Радиус круга: r
• Радиус оси x с эллипсом: a
• Радиус y-выровненной оси эллипса: b.

Уравнение эллипса тогда дается выражением a cos(t), b sin(t). Чтобы найти ближайшую точку, мы хотим минимизировать квадратное расстояние || (a cos t, b sin t) - c ||^2. Как отмечает Жан, это "просто исчисление": возьмите производную и установите ее равной 0. Если я чего-то не упустил, решение результирующего (довольно неприятного) уравнения для t невозможно аналитически и должны быть аппроксимированы, например, Метод Ньютона. Подключите t, который вы найдете в параметрическом уравнении, чтобы получить ближайшую точку.

• Pro: численный решается только в одной переменной, t.
• Con: Вы должны иметь возможность записать параметризацию эллипса или преобразовать свои координаты, чтобы вы могли. Это не должно быть слишком сложно для любого разумного представления о эллипсе. Тем не менее, я покажу вам второй метод, который гораздо более общий и может быть полезен, если вам нужно обобщить вашу проблему, скажем, на 3D.

Подход 2. Используйте многомерное исчисление. Изменение координат не требуется.

• Центр круга: c = (cx, cy)
• Радиус cirlce: r
• Эллипс задается функцией g (x, y) = 0 для функции g. Например, на каждый ответ Curd вы можете использовать g (x, y) = расстояние (x, y) от фокуса 1 + расстояние (x, y) от фокуса 2 - e.

Поиск точки на эллипсе, ближайшем к центру круга, можно затем сформулировать как ограниченную задачу минимизации:

Minimize ||(x,y) - c||^2 subject to g(x,y) = 0

(Минимизация квадратного расстояния эквивалентна минимизации расстояния и гораздо приятнее иметь дело, поскольку это квадратичный многочлен от x, y.)

Для решения проблемы ограниченной минимизации мы введем множитель Лагранжа лямбда и решим систему уравнений

2 * [ (x,y) -c ] + lambda * Jg(x,y) = 0
g(x,y) = 0

Здесь Jg - градиент g. Это система из трех (нелинейных) уравнений с тремя неизвестными: x, y и лямбда. Мы можем решить эту систему, используя метод Ньютона, и получим (x, y), которая является ближайшей точкой к центру окружности.

• Pro: параметризаций не требуется.
• Pro: Метод очень общий и хорошо работает, когда писать g проще, чем найти параметрическое уравнение (например, в 3D).
• Con: Требуется многовариантное решение Newton, которое очень волосатое, если у вас нет доступа к пакету числовых методов.

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

Потенциальный третий подход?. Возможно, можно напрямую решить для корней системы двух квадратичных уравнений две переменные, представляющие круг и эллипс. Если существует реальный корень, объекты пересекаются. Самый прямой способ решения этой системы, опять-таки используя численный алгоритм, такой как метод Ньютона, не поможет, потому что отсутствие конвергенции не обязательно подразумевает несуществование реального корня. Однако для двух квадратичных уравнений с двумя переменными может существовать специализированный метод, гарантирующий найти реальные корни, если они существуют. Я сам не могу придумать, как это сделать, но вы можете сами исследовать его (или посмотреть, может ли кто-то из stackoverflow выработать.)

Ответ 2

Эллипс определяется как множество точек, сумма расстояния до точки А и расстояние до точки В постоянны е. (A и B называются фокусами эллипса).

Все точки P, сумма которых AP + BP меньше e, лежат внутри эллипса.

Круг определяется как множество точек, расстояние до точки C равно r.

Простой критерий пересечения окружности и эллипса следующий:

Найти
P как пересечение круга и прямой AC и Q как пересечение круга и прямой BC.

Круг и эллипс пересекаются (или круг лежит полностью внутри эллипса), если AP + BP <= e или AQ + BQ <= e

ИЗМЕНИТЬ

После комментария Мартина ДеМелло и, соответственно, адаптировав мой ответ, я больше подумал о проблеме и обнаружил, что ответ (со второй проверкой) по-прежнему не обнаруживает пересечения all:

Если круг и эллипс пересекаются только очень мало (чуть больше, чем касательные), то P и Q не будут находиться внутри эллипса:

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

Ответ 3

Увеличьте большой и средний радиус эллипса радиусом круга. Затем проверьте, находится ли центр данного круга внутри этого нового большего эллипса, суммируя расстояния до фокусов расширенного эллипса.

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

Ответ 4

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

изменить: вот путь к решению, так как что-то не так с творогом

заданный центр α β на эллипсе
и (из-за отсутствия запоминания термина) x радиус a, y радиус b параметризация - это r (Θ) = (ab)/(((BcosΘ) ^ 2 + (asinΘ) ^ 2) ^ 5)
x (Θ) = α + sin (Θ) r (Θ)
y (Θ) = β + cos (Θ) r (Θ)

а затем просто возьмем окружность с центром в (φ, ψ) и радиусом r то расстояние d (Θ) = ((φ - x (Θ)) ^ 2 + (ψ - y (Θ)) ^ 2) ^ 5

минимум этого расстояния равен d '(Θ) = 0 (' для производной)

d '(Θ) = 1/d (Θ) * (-φx' (Θ) + x (Θ) x '(Θ) - ψy' (Θ) + y (Θ) y '(Θ))
== >
x '(Θ) * (-φ + x (Θ)) = y' (Θ) * (ψ - y (Θ))

и продолжайте идти и идите, и, надеюсь, вы можете решить для Θ
Рамка, в которой вы работаете, может помочь вам решить эту проблему, и вы всегда можете легко вывести и приблизить корни через Newton Method

Ответ 5

если круг и эллипс сталкиваются, то либо их границы пересекаются 1, 2, 3 или 4 раза (или бесконечно много в случае кругового эллипса, совпадающего с окружностью), либо круг находится внутри эллипса или наоборот.

Я предполагаю, что у круга есть уравнение (x - a) ^ 2 + (y - b) ^ 2 <= r ^ 2 (1), а эллипс имеет уравнение [(x - c) ^ 2]/[d ^ 2] + [(y - e) ^ 2]/[f ^ 2] <= 1 (2)

Чтобы проверить, находится ли один из них внутри другого, вы можете оценить уравнение круга в координатах центра эллипса (x = c, y = e) или наоборот и посмотреть, выполняется ли неравенство имеет место.

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

вы можете сделать это, добавив (1) и (2), предоставив вам

(x - a)^2 + (y - b)^2 + [(x - c)^2]/[d^2] + [(y - e)^2]/[f^2] = r^2 + 1

Затем вы умножаете термины, предоставляя

x^2 - 2ax + a^2 + y^2 - 2by + b^2 + x^2/d^2 - 2cx/d^2 + c^2/d^2 + y^2/f^2 - 2ey/f^2 + e^2/f^2 = r^2 + 1

собирающие подобные члены, получаем

(1 + 1/d^2)x^2 - (2a + 2c/d^2)x + (1 + 1/f^2)y^2 - (2b + 2e/f^2)y = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

теперь пусть m = (1 + 1/d^2), n = -(2a + 2c/d^2), o = (1 + 1/f^2), and p = -(2b + 2e/f^2)

теперь уравнение mx^2 + nx + oy^2 + py = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

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

m[x^2 + (n/m)x] + o[y^2 + (p/o)y] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m[x^2 + (n/m)x + (n/2m)^2 - (n/2m)^2] + o[y^2 + (p/o)y + (p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m[(x + n/2m)^2 - (n/2m)^2] + o[(y + p/2o)^2 - (p/2o)^2] = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m(x + n/2m)^2 - m(n/2m)^2 + o(y + p/2o)^2 - o(p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2

m(x + n/2m)^2 + o(y + p/2o)^2 = 1 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2

эта система имеет решение iff 11 + r^2 - a^2 - b^2 - c^2/d^2 - e^2/f^2 + m(n/2m)^2 + o(p/2o)^2 >= 0

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

Ответ 6

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

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

Если вы действительно хотите пойти на математику, у Wolfram MathWorld есть хорошая статья здесь: http://mathworld.wolfram.com/Circle-EllipseIntersection.html, но будьте осторожны, все равно придется писать решатель уравнения полинома, возможно, используя что-то вроде бинарного поиска.

Ответ 7

Это не так сложно. user168715 Ответ в целом правильный, но исчисление не требуется. Просто тригонометрия.

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

(Взято из статьи Википедии о Эллипсы)

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

Может быть, я что-то упустил; возможно, ArcTan/Cos/Sin медленны, но я так не думаю, и при необходимости должны быть быстрые аппроксимации.

Ответ 8

Пред- полагая:   эллипс центрирован в начале и с полумагом ось (длины а), ориентированная вдоль оси х, и с полуосей ось длины b; E2 - квадрат эксцентриситета, т.е. (Aa-bb)/(a ​​* a); окружность центрирована по X, Y и радиусу r.

Простые случаи:   центр окружности находится внутри эллипса (т.е. гипотеза (X/a, Y/b) <= 1) так что есть пересечение;   центр окружности находится вне окружности с центром в 0 радиуса a + r (т.е. hypot (X, Y) > a + r), поэтому нет пересечения.

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

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

В формулах преобразование из геодезических координат lat, ht в декартовых координат X, Y является X = (nu + ht) * cos (lat), Y = (nu * (1-E2) + ht) * sin (lat) где nu = a/sqrt (1 - E2 * sin (lat) sin (lat)). Точка на эллипсе, ближайшем к X, Y, является точкой с той же широтой, но с нулевой высотой, т.е. x = nucos (lat), y = nu * (1-E2) * sin (lat). Заметим, что nu является функцией широты.

К сожалению, процесс нахождения lat, ht из X, Y является итеративный. Один из подходов состоит в том, чтобы сначала найти широту, а затем высота.

Маленькая алгебра показывает, что широта удовлетворяет lat = atan2 (Y + E2 * nusin (lat), X) который может быть использован для вычисления последовательных приближений к широте, начиная с lat = atan2 (Y, X (1,0-E2)) или (более эффективно) может быть решена с использованием метода Ньютона.

Чем больше E2, тем более плоский эллипс, тем больше потребуются итерации. Например, если эллипс почти (например, E2 < 0,1), то пять итераций получат x, y ниже с точностью до * 1e-12, но если эллипс очень плоский, например, E2 = 0,999 вам понадобится около 300 итераций, чтобы получить такую ​​же точность!

Наконец, учитывая широту, можно вычислить высоту вычисляя (x, y): x = nucos (lat), y = nu (1-E2) * sin (lat) а затем h - расстояние от x, y до центра окружности, h = hypot (X-x, Y-y)

Ответ 9

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

Чтобы интерполировать эллипс на n-мерный многоугольник, вы можете использовать:

    float delta = (2 * PI) / n;

    std::vector<Point*> interpolation;

    for(float t = 0; t < (2 * PI); t += delta) {

        float x = rx * cos(t) + c->get_x();
        float y = ry * sin(t) + c->get_y();

        interpolation.push_back(new Point(x, y));
    }

c: Центр эллипса. rx: радиус x-выровненной оси эллипса. ry: Радиус y-выровненной оси эллипса.

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

Надеюсь, это поможет любому.

Ответ 10

Я хотел внести некоторый вклад в более общую проблему, связанную с контактом между двумя эллипсами. Вычисление расстояния ближайшего приближения двух эллипсов было долговременной проблемой и анализировалось только аналитически в течение последних десяти лет - это отнюдь не просто. Решение проблемы можно найти здесь http://www.e-lc.org/docs/2007_01_17_00_46_52/.

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

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