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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.11.2010, 16:30
Новичок

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

Апроксимирующие эллипс, прямоугольник, треугольник
Дана плоская фигура, заданная маской (по сути массив, в котором значение 0 соответствует фону, 1-объекту). Необходимо решить следующие задачи:
1. Подобрать для объекта аппроксимирующий эллипс (определить оси и угол меду горизонтальной осью и главной осью эллипса)
2. Подобрать для объекта аппроксимирующий прямоугольник (определить стороны прямоугольника и угол)
3. Подобрать для объекта аппроксимирующий треугольник

Поискав в сети и на этом форуме, я пришел к выводу, что задачи [1] и [2] лучше решать через вторые моменты (равенство вторых моментов объекта и аппроксимирующих фигур). Но пока я так и не понял как это сделать. Может кто пояснит как это сделать или даст ссылку на теорию, где можно доступно почитать (имеется ввиду не пояснение, что такое моменты второго порядка, а как перейти от моментов к параметрам аппроксимирующих фигур).

Как решить задачу [3] пока даже предположений нет.

Заранее спасибо за ответы.
P.S.: ветки форума эту и эту видел. Но там только ссылка на готовую реализацию, а мне бы понять суть этих алгоритмов.
  #2  
Старый 11.11.2010, 19:18
Местный

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

> как перейти от моментов к параметрам аппроксимирующих фигур

Для таких фигур, как эллипс и прямоугольник существуют формулы, как вычислить по ним моменты 2-го порядка. Здесь надо решить обратную задачу: по моментам найти параметры фигур.
  #3  
Старый 12.11.2010, 19:41
Новичок

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

Сообщение от prografix Посмотреть сообщение
Для таких фигур, как эллипс и прямоугольник существуют формулы, как вычислить по ним моменты 2-го порядка.
Если можно, дайте ссылку, где можно посмотреть эти формулы.
  #4  
Старый 13.11.2010, 12:11
Местный

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

Например, здесь. Есть и другие статьи ( ищите по запросу "моменты инерции" ).
Что касается исходной задачи, то её можно решать по-другому - искать минимальную фигуру содержащую данные точки. Тогда и треугольник найдётся.
  #5  
Старый 13.11.2010, 15:52
Новичок

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

Сообщение от prografix Посмотреть сообщение
Например, здесь. Есть и другие статьи ( ищите по запросу "моменты инерции" ).
Спасибо за ссылку. Пойду разбираться.

Сообщение от prografix Посмотреть сообщение
Что касается исходной задачи, то её можно решать по-другому - искать минимальную фигуру содержащую данные точки. Тогда и треугольник найдётся.
Здесь не все так просто.
Во-первых, "минимальная ограничивающая фигура" != "аппроксимирующая фигура" (ограничивающая фигура почти всегда больше аппроксимирующей).
Во-вторых, алгоритмы, которые мне встречались, чаще всего предполагают, что ориентация ограничивающей фигуры известна (например, ее оси параллельны осям координат). В моем же случае это совсем не так. Т.е. на изображении может быть правильный квадрат, повернутый на 45 градусов, или правильный треугольник.

В случае прямоугольника и эллипса - решение через моменты (на мой взгляд), будет более правильным. Буду разбираться с ними. А вот в случае треугольника - пока идей вообще никаких.
Если у кого есть какие мысли по поводу "как найти аппроксимирующий треугольник?" буду рад их выслушать.
  #6  
Старый 13.11.2010, 17:04
Местный

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

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

Во-вторых, алгоритмы, которые мне встречались, чаще всего предполагают, что ориентация ограничивающей фигуры известна (например, ее оси параллельны осям координат).

Мне известны алгоритмы которые строят подобные фигуры для любой ориентации.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Минимальный эллипс по 3 точкам prografix Вычислительная геометрия 8 24.11.2010 13:56
Прямоугольник, наилучшим образом приближающий выпуклый четырехугольник WW_ Вычислительная геометрия 8 04.10.2010 18:30
Построение многоугольника через эллипс BOB4uK Математические алгоритмы 4 02.07.2008 17:30
отрезок и прямоугольник @rtur Вычислительная геометрия 1 24.11.2007 18:16
как вписать эллипс макс. площиди в заданый 4-угольник? partizan22 Вычислительная геометрия 0 18.12.2006 00:37