Пересечение эллипсов. , Установть факт.

[Bomon]

Тема подымалась ранее на разнообразных форумах и всякие умники авторитетно советуют решать уравнение четвертой степени или по теореме Штурма определить количество вещественных корней. Так вот первое у меня не получается, второе же не подходит(обязательным условием теоремы есть отсутствие кратных корней).

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

Расскажу что пытался сделать сам.
1. Если один из них записать в канонической форме, а второй в параметрической получим уравнения, в котором неизвестное входит под знаки синуса и косинуса в 1 и 2 степени. Решить его я не знаю как, так как ни одна замена не приводит его к решаемому тригонометрическому уравнению. Если же сделать универсальную замену то так же сойдемся к уравнению 4 степени, точный алгоритм которого мне не известен.

2. Есть вариант аппроксимировать один из эллипсов многоугольником, вписав последний в первый. Алгоритм проверки пересечения многоугольника и эллипса я уже написал. Но этот случай не всегда дает правильный результат, или же количество ребер многоугольника должно быть достаточно большим, так что этот вариант откладывается на тот случай если ничего не выйдет со всем остальным.

Любые замечания и предложения в студию. Спасибо за внимание.

[MBo]

http://prografix.narod.ru/rus_alg_ur4.html

[Akina]

Цитата Bomon @ 20.05.09, 06:00

всякие умники авторитетно советуют решать уравнение четвертой степени

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

[Bomon]

Цитата Akina @ 20.05.09, 06:18

лёгким движением руки

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

[HOMO_PROGRAMMATIS]

А ссылка в посте 2 разве не про это?

[MBo]

>его заменой привести к неполному
это нетрудно
x^4+a*x^3+b*x^2+c*x+d=0
приводится к неполному виду заменой
x=y-a/4

[Bomon]

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

MBo
Я именно так и делаю. =)

[Akina]

Цитата Bomon @ 20.05.09, 10:24

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

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

[prografix]

Я бы сделал так:
1) Один эллипс путём линейного преобразования сделать окружностью с центром в начале координат и единичным радиусом.
2) Если второй эллипс ( преобразованный ) содержит начало координат значит эллипсы пересекаются.
3) Иначе находим точку второго эллипса ближайшую к началу координат ( это квадратичная задача ) и квадрат расстояния.
4) Если квадрат расстояния больше 1, то эллипсы не пересекаются.

[Bomon]

prografix
А в результате линейного преобразования сохранится ли пересечение?
И как найти ближайшую точку эллипса к началу координат?

[prografix]

1) да
2) нормаль к эллипсу в этой точке направлена на начало координат.

[MBo]

> это квадратичная задача
Неа...

[prografix]

Да, я ошибся насчёт квадратичности. Задача ближайшей точки к эллипсу решается через уравнение 4-й степени. Причём в качестве неизвестной величины можно брать разные переменные. Я рекомендую брать множитель Лагранжа. Итак новый вариант проверки:
1. Проверить входят ли центры эллипсов в друг друга. Если да, то конец, иначе
2. Найти точку первого эллипса наиболее "близкую" ко второму эллипсу, используя множитель Лагранжа и для этой точки определить пересекаются ли эллипсы.
Замечания:
Первый пункт не только сокращает время при удачном раскладе, но и делает решение второго пункта единственным.
Полученное уравнение 4-й степени можно решать разными способами, в том числе и методом "золотого сечения", т.к. интервал на котором находится решение уравнения легко определяется.

[Bomon]

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