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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.09.2010, 21:32
WW_ WW_ вне форума
Новичок

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

Прямоугольник, наилучшим образом приближающий выпуклый четырехугольник
Пусть на плоскости задан выпуклый четырехугольник набором координат своих вершин: (x_0,y_0), (x_1,y_1), (x_2,y_2), (x_3,y_3) (предположим, что вершины перечислены в порядке обхода по часовой стрелке).
Стоит две задачи:
1) Найти прямоугольник наилучшим образом приближающий заданный прямоугольник. Под "наилучшим образом" понимается то, что площадь отсекаемых (добавленных) фигур минимальна.
2) Найти MBR (minimum bounding rectangle) - описанный прямоугольник минимальной площади (для заданного выпуклого четырехугольника).

Вторую задачу решить даже важнее.
  #2  
Старый 30.09.2010, 21:57
гость

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

Цитата:
2) Найти MBR (minimum bounding rectangle) - описанный прямоугольник минимальной площади (для заданного выпуклого четырехугольника).
http://en.wikipedia.org/wiki/Minimum...box_algorithms
  #3  
Старый 30.09.2010, 21:59
WW_ WW_ вне форума
Новичок

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

Похоже со второй частью разобрался
Во второй задаче похоже разобрался.
Если утверждение что одна сторона ограничевающего прямоугольника будет совпадать (лежать на той же прямой) со стороной заданного четырехугольника, то дальше - простой перебор четырех вариантов.
Но первая задача всё ещё в силе.
  #4  
Старый 30.09.2010, 22:14
гость

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

Ну, там задача всего с пятью параметрами - угол и ординаты/абсциссы сторон. И целевой функционал непрерывен по ним. По-моему, тут проще всего будет забабахать любой метод численной (не-градиентной) оптимизации, см. http://cs.gmu.edu/~sean/book/metaheuristics/
Генетику там, или дифференциальную эволюцию попробуй.
  #5  
Старый 30.09.2010, 22:29
гость

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

Сообщение от гость Посмотреть сообщение
не-градиентной
хотя нет, вру. Градиент везде есть, это всего лишь второй производной иногда нет. Так что все у вас хорошо с задачей в численном плане.
  #6  
Старый 01.10.2010, 12:28
Местный

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

А критерий первой задачи изменить можно?
Например, я для аппроксимации многоугольника прямоугольником использую такой подход - центры масс и моменты инерции двух фигур должны совпадать.
  #7  
Старый 03.10.2010, 10:53
WW_ WW_ вне форума
Новичок

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

Сообщение от prografix Посмотреть сообщение
А критерий первой задачи изменить можно?
Например, я для аппроксимации многоугольника прямоугольником использую такой подход - центры масс и моменты инерции двух фигур должны совпадать.
Спасибо, это интересно. Можно поподробнее, пожалуйста.
Совпадение центров масс даст сразу точку пересечения диагоналей (центр прямоугольника). Остается еще 3 параметра (например, поворот, высота и ширина). Как получить их из совпадения моментов инерции?
Приравнять осевые моменты инерции и центральные моменты инерции?

Вообще, очень интересно, попробую обязательно. Еще раз спасибо.
  #8  
Старый 03.10.2010, 11:59
Местный

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

Детали этого алгоритма объяснить непросто, но у меня уже есть программа на С++ (ссылка), которая это делает.
  #9  
Старый 04.10.2010, 18:30
Местный

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

Хочу добавить, что при использовании моментов 2-го порядка для некоторых фигур ( например, для правильных многоугольников ) максимальный и минимальный моменты равны друг другу, и в этом случае направления осей инерции не определены. Известно только, что аппроксимирующий прямоугольник - это квадрат, а также его размеры и положение центра. Осталось найти его поворот. Это можно сделать путём нахождения максимума площади пересечения квадрата и исходной фигуры. Эту одномерную оптимизацию можно сделать при помощи метода золотого сечения.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
отрезок и прямоугольник @rtur Вычислительная геометрия 1 24.11.2007 18:16