Пересечение отрезка и эллипса

#java #графика #геометрия

Дан отрезок из двух точек А и В (у каждой точки есть координаты).

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

Задача: узнать пересекаются ли отрезок с эллипсом. Случай, при котором отрезок полностью
в эллипсе не удовлетворяет условие.

Помогите, пожалуйста, а то ничего в голову не приходит. Если возможно, то нужен код
в java, если нет - дайте решение, а код напишу сам.
    

Ответы

Ответ 1

UPD (исходя из комментария @AnT):

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



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

Пусть задан эллипс:

(x-x0)^2/a^2 + (y-y0)^2/b^2 = 1


, где:


(x0;y0) – координаты центра эллипса;
a и b – длины большой и малой полуосей соответственно.


и отрезок AB, где A(x1;y1) и B(x2;y2).

Для того, чтобы отрезок AB пересекал заданный эллипс, необходимо и достаточно, чтобы
была верна одна из систем неравенств:

(x1-x0)^2/a^2 + (y1-y0)^2/b^2 < 1
(x2-x0)^2/a^2 + (y2-y0)^2/b^2 > 1


(случай, когда точка A лежит внутри эллипса, а B – вне его);

(x1-x0)^2/a^2 + (y1-y0)^2/b^2 > 1
(x2-x0)^2/a^2 + (y2-y0)^2/b^2 < 1


(случай, когда точка A лежит вне эллипса, а B – внутри его).

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


Ответ 2

Из геометрии-
две линии пересекаются, если для системы уравнений, описывающей эти линии, существует
решение

создаем систему уравнений из 2х 
прямая = (x-xa)/(xb-xa)=(y-ya)/(yb-ya)
уравнение эллипса необходимо выбирать максимально вам подходящее, после чего в обоих
уравнениях выражаете  y  и решаете систему

для канонического уравнения эллипса (оси эллипса совпадают с осями координат) (x^2/a^2+y^2/b^2=1)
прямая  y=((x-xa)*(yb-ya))/(xb-xa)+ya
эллипс  y=+-sqrt((1/b^2)-(x^2/a^2*b^2))

далее подставляем все известные данные и получаем или не получаем точку, если получили
- есть пересечение, не получили = нет


Ответ 3

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

Из приведенного условия можно неявно заключить, что речь идет не о произвольном эллипсе,
а об эллипсе, оси которого параллельны осям координат. (Кстати, почему этого не сказано
явно в условии?). В такой ситуации требуемое преобразование строится элементарно -
это просто домножение одной из координат на коэффициент a/b - соотношение длин осей
эллипса.

Тем самым мы сводим задачу к задаче о пересечении отрезка и окружности.

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

Обратное преобразование координат даст нам координаты точек пересечения с исходным
эллипсом (если они нас интересуют).