Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.11.2010, 11:48
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Минимальный эллипс по 3 точкам
На плоскости даны 3 точки. Нужно найти эллипс минимальной площади с этими точками на границе. Решение должно быть аналитическим. Все мои попытки приводили к системам нелинейных уравнений, решать которые я не берусь.
  #2  
Старый 09.11.2010, 18:18
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Напиши систему уравнений, для начала, может она и окажется решабильной.
  #3  
Старый 09.11.2010, 18:48
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Оси эллипса параллельны осям координат или общий случай интересен?
  #4  
Старый 10.11.2010, 15:01
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Общий случай.
  #5  
Старый 10.11.2010, 15:17
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

По поводу систем уравнений. Вот один вариант:
a = y23*cos(f1) + y31*cos(f2) + y12*cos(f3)
b = sin(f2) - sin(f1)
-y23*sin(f1)*b - a*cos(f1) + c*y23*cos(f1) = 0
-y31*sin(f2)*b + a*cos(f2) + c*y31*cos(f2) = 0
sin(f3)*b = c*cos(f3)
y23*sin(f1) + y31*sin(f2) + y12*sin(f2) = 0
здесь a, b, c, f1, f2, f3 - неизвестные.

Последний раз редактировалось prografix, 10.11.2010 в 15:43.
  #6  
Старый 20.11.2010, 14:04
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Я всё-таки решил эту задачу и решение получилось несложным: возьмём произвольное аффинное преобразование, которое отображает исходные точки в вершины равностороннего треугольника, опишем вокруг него окружность, а затем применим к ней обратное преобразование. Таким образом получим эллипс минимальной площади ( это следует из того, что аффинное преобразование сохраняет отношение площадей фигур ).
Из этого также следует, что центр эллипса и центр масс исходных точек совпадают. Поэтому для простоты будем считать, что эти центры находятся в начале координат.
Итак даны 3 точки (x1,y1), (x2,y2), (x3,y3).
Введём дополнительные переменные:
x12 = x1 - x2
y12 = y1 - y2
x23 = x2 - x3
y23 = y2 - y3
x31 = x3 - x1
y31 = y3 - y1
Эллипс зададим в виде уравнения:
a*x*x - b*x*y + c*y*y = d
Тогда:
a = y12*y12 + y23*y23 + y31*y31 - y31*y12 - y12*y23 - y23*y31
b = 3 * ( y12*x12 + y23*x23 + y31*x31 )
c = x12*x12 + x23*x23 + x31*x31 - x31*x12 - x12*x23 - x23*x31
d = ( y31*x23 - y23*x31 ) ^ 2
  #7  
Старый 23.11.2010, 20:57
гость

 
Сообщений: n/a

Лучше поздно, чем никогда
Вот здесь:
artspb.com/mironovsky/records/images/Invariants_91.doc
лежит простая и доступная всем брошюра об инвариантах.
Ваша задача там в первых рядах.
Л.А. Мироновский ИНВАРИАНТЫ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра
Комбинированный вид Комбинированный вид


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Минимальный разрез гость Графы 7 01.06.2010 19:24
Построение многоугольника через эллипс BOB4uK Математические алгоритмы 4 02.07.2008 17:30
сфера по 4м точкам algol68 Вычислительная геометрия 1 30.01.2008 02:01
Окружность по трем точкам Mishel Вычислительная геометрия 1 17.12.2007 08:26
как вписать эллипс макс. площиди в заданый 4-угольник? partizan22 Вычислительная геометрия 0 18.12.2006 00:37