То, как обнаружить, если эллипс пересекается (сталкивается с), круг

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

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

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

Вот простой тест на пересечение круга и эллипса:

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

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

EDIT :

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

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

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

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

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 (Θ))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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