3

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

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

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

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

1
  • 3
    нужно проверить имеет ли система уравнений решение (если имеет то пересекаются), в котором первое это уравнение прямой по двум точкам, второе это уравнение эллипса
    – ampawd
    5 фев 2017 в 23:45

3 ответа 3

4

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
  • "Для того, чтобы отрезок AB пересекал заданный эллипс, необходимо и достаточно, чтобы была верна одна из систем неравенств". Разве? А как же случай, когда обе точки лежат вне эллипса, но при этом отрезок все-таки пересекает эллипс (в двух точках)? 7 фев 2017 в 21:18
  • @AnT, Этот случай я не рассмотрел. Вы правы.
    – post_zeew
    7 фев 2017 в 21:24
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))

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

4
  • Какую линию задает Ваше последнее уравнение?
    – post_zeew
    6 фев 2017 в 0:21
  • @post_zeew y=sqrt((1/b^2)-(x^2/a^2*b^2)) это выраженный y из канонического уравнения эллипса - x^2/a^2+y^2/b^2=1
    – Tr1nks
    6 фев 2017 в 0:27
  • 1
    Я это понимаю. Но эти два выражения не эквиваленты. То, что Вы выразили, задает часть дуги эллипса, которая лежит в верхней полуплоскости. В общем +/- там должен быть.
    – post_zeew
    6 фев 2017 в 0:31
  • @post_zeew Точно, там же из под корня под модулем..., согласен с вашим замечанием, спасибо!
    – Tr1nks
    6 фев 2017 в 0:33
0

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

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

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.