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

Question

Я хочу улучшить систему столкновений.

Прямо сейчас я обнаруживаю, сталкиваются ли 2 неправильных объекта, если сталкиваются их ограничивающие прямоугольники.

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

Знаете ли вы алгоритм для проверки, пересекает ли круг эллипс?

Answer 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)
• Радиус вихря: r
• Эллипс задается как g (x, y) = 0 для функции g. Например, согласно ответу Творда вы можете использовать g (x, y) = расстояние (x, y) от фокуса 1 + расстояние (x, y) от фокуса 2 - е.

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

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 и lambda. Мы можем решить эту систему, используя метод Ньютона, и (x, y), который мы получаем, является ближайшей точкой к центру круга.

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

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

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

Answer 2

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

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

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

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

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

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

EDIT

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

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

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

Answer 3

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

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

Надеюсь, это кому-нибудь поможет.

Answer 4

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

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

Answer 5

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

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

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

Answer 6

если окружность и эллипс сталкиваются, то их границы пересекаются 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) </p>

Чтобы проверить, находится ли один из них внутри другого, вы можете оценить уравнение круга по координатам центра эллипса (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

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

Answer 7

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

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

заданный центр α β на эллипсе
и (из-за отсутствия запоминания термина) 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 (Θ))

и продолжайте идти и идти, и, надеюсь, вы можете решить за Θ
У фреймворка, в котором вы работаете, могут быть вещи, которые помогут вам решить эту проблему, и вы всегда можете выбрать легкий путь и приблизить корни с помощью метода Ньютона

Answer 8

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

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

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

Answer 9

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

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

(взято из статьи в Википедии Ellipses )

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

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

Answer 10

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

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

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

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

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

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

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

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

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