Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Задача минимальных проекций

505
18 февраля 2007 года
vAC
343 / / 28.02.2006
Вот уже второй раз сталкиваюсь с подобной задачей, решение которой реализовал только численное. Хотелось узнать мнение о построении аналитического.

Есть набор точек в 2D (Xi,Yi). Задача до безобразия проста: найти такое направление (вектор или угол, как угодно), чтобы разница между максимальным и минимальным значением из всех проекций (ширина проекции) точек на это направление было минимальным. Можно сказать так: найти ширину объекта по набору его точек.
391
18 февраля 2007 года
Archie
562 / / 03.02.2005
Что такое "заначение проекции"??? Проекция точки на прямую, будет точкой. Тебя интересует расстояние между точкой и ее проекцией? Тогда, может быть это банальный МНК?
505
18 февраля 2007 года
vAC
343 / / 28.02.2006
Цитата: Archie
Что такое "заначение проекции"??? Проекция точки на прямую, будет точкой. Тебя интересует расстояние между точкой и ее проекцией? Тогда, может быть это банальный МНК?



"заначение проекции" - это скаларное произведение вектора направления на р-вектор точки.
МНК никак сюда не прикрутить :)
Могу сформулировать задачу так:

alpha' = argmin(w(alpha));
w(alpha) = max(L(alpha)*P)-min(L(alpha)*P);
L(alpha) = [cos(alpha); sin(alpha)];

P - данные точки
*-скалярное произведение

Найти: либо alpha' либо L(alpha')

391
18 февраля 2007 года
Archie
562 / / 03.02.2005
Хм... Аналитически можно было бы решить для непрерывных функций, а тут дискретный набор значений (координаты точек). Т.о. минимумы и максимумы нужно искать по индексу i, что можно сделать только перебором (т.к. координаты точек с их индексом никак не связаны математически).
505
18 февраля 2007 года
vAC
343 / / 28.02.2006
Цитата: Archie
Хм... Аналитически можно было бы решить для непрерывных функций, а тут дискретный набор значений (координаты точек). Т.о. минимумы и максимумы нужно искать по индексу i, что можно сделать только перебором (т.к. координаты точек с их индексом никак не связаны математически).



Ну задача всетаки непрерывно-дискретная: по i-дискретная, по alpha-непрерывная, т.е. даже перебором не обойтись. Конечно можно взять дискретный набор углов из множетва [0,PI) и выбрать оптимальный. Это и есть то решение, которое я реализовал...но оно обладает "точностью" в математичеком смысле. А хотелось бы реализовать точный метод.
Графиками проекций от угла будут синусоиды...вот эту кашу-то и надо как-то переварить

505
18 февраля 2007 года
vAC
343 / / 28.02.2006
Да, под словом аналитическое я не имею ввиду решение на непрерывном множестве, а всеголишь алгоритм получения точного решения (отсутствие задания точности).
391
18 февраля 2007 года
Archie
562 / / 03.02.2005
Ну, смотри. Нужно найти минимум функции w(alpha). Минимум характеризуется нулевой производной 1-го прядка: d/dalpha(w(alpha)) = 0 (а производная второго порядка должна быть >=0). Т.е. d/dalpha(max(L(alpha) * P) - min(L(alpha) * P) = 0. Значения max(L(alpha)*P) и min(L(alpha)*P) достигаются для каких-то Imax и Imin, соответственно. Т.е. d/dalpha(L(alpha)*P[Imax] - L(alpha)*P[Imin]) = 0. Т.о. tg(alpha) = (Y[Imax] - Y[Imin]) / (X[Imax] - X[Imin]). Ну вот, для любых значений Imax и Imin можно найти такой alpha, что условие задачи будет выполнятся.

P.S. Т.е. объект всегда будет иметь какую-то ширину в зависимости от того, в каком направлении ты его рассматриваешь.
505
18 февраля 2007 года
vAC
343 / / 28.02.2006
Цитата: Archie
Ну, смотри. Нужно найти минимум функции w(alpha). Минимум характеризуется нулевой производной 1-го прядка: d/dalpha(w(alpha)) = 0 (а производная второго порядка должна быть >=0). Т.е. d/dalpha(max(L(alpha) * P) - min(L(alpha) * P) = 0. Значения max(L(alpha)*P) и min(L(alpha)*P) достигаются для каких-то Imax и Imin, соответственно. Т.е. d/dalpha(L(alpha)*P[Imax] - L(alpha)*P[Imin]) = 0. Т.о. tg(alpha) = (Y[Imax] - Y[Imin]) / (X[Imax] - X[Imin]). Ну вот, для любых значений Imax и Imin можно найти такой alpha, что условие задачи будет выполнятся.

P.S. Т.е. объект всегда будет иметь какую-то ширину в зависимости от того, в каком направлении ты его рассматриваешь.



Не совсем понял...Imax и Imin перебирать или искать? если перебирать, то не все пары будут при каком-то угле крайними. А если искать, то они зависят от alpha: Imax(alpha), Imin(alpha) - ведь крайние точки меняются в зависимости от направления.

391
18 февраля 2007 года
Archie
562 / / 03.02.2005
Я ж и говорю, что они зависят от направления. Поэтому, либо фиксировать направление и находить крайние точки, или фиксировать крайние точки и находить направление :) Неизвестных в задаче три, а условие на них накладывается только одно...
252
18 февраля 2007 года
koderAlex
1.4K / / 07.09.2005
метод половинного деления .
505
18 февраля 2007 года
vAC
343 / / 28.02.2006
Цитата: Archie
Я ж и говорю, что они зависят от направления. Поэтому, либо фиксировать направление и находить крайние точки, или фиксировать крайние точки и находить направление :) Неизвестных в задаче три, а условие на них накладывается только одно...



Так ни тот, ни другой вариант не решит задачу.
В первом случае задача-то тривиальна, зная направление, без проблем можно найти минимум а максимум проекций, но мне же нужно не какое-то фиксированное, а то, которое приведет к минимуму ширины проекции. Во втором случае если я буду решать задачу max(Imax)-min(Imin)->min, то получу просто перпендикулярное направление к отрезку прямой, соединяющей точки P[Imax] и P[Imin], т.к. при этом условии max(Imax)-min(Imin)=0 - и есть минимум

391
19 февраля 2007 года
Archie
562 / / 03.02.2005
Так а что ж ты хочешь? У тебя аргумент дискретный (индекс). Как найти минимум функции дискретного аргумента аналитически? А никак, только перебирая индексы. Повторю, у тебя неизвестных три, а условие - одно. Поэтому-то для любых Imax, Imin всегда существует ортогональне направление, которое приводит к минимуму.
15K
04 марта 2007 года
Sara
79 / / 04.01.2007
Прошу прощения за поздний ответ :)
Я давно не заходила на этот форум, а тут вдруг увидела интересный вопрос по моей специальности :)
Разумеется, задача имеет аналитическое решение. Если это еще актуально, могу написать алгоритм.
239
04 марта 2007 года
Dolonet
1.7K / / 20.05.2000
Цитата: vAC
Есть набор точек в 2D (Xi,Yi). Задача до безобразия проста: найти такое направление (вектор или угол, как угодно), чтобы разница между максимальным и минимальным значением из всех проекций (ширина проекции) точек на это направление было минимальным. Можно сказать так: найти ширину объекта по набору его точек.


Мне кажутся очевидными следующие утверждения:
1. На одной из двух прямых, которые ограничивают отрезок на проведенном искомом векторе и являются перпендикулярными этому вектору, должно лежать две точки. То есть надо искать наименьшее расстояние от какой-то "крайней" точки до прямой, образованой двумя точками.
2. Очевидно, что нам интересны только те пары точек для образования прямой, чтобы все остальные точки были по одну сторону от нее. Алгоритм под такую задачу для массива написать совсем не сложно, как и сразу найти самую дальнюю точку от этой пары.
Проходим максимум 2 раза по всему массиву, находим наименьший результат. Это для массива точек.

15K
04 марта 2007 года
Sara
79 / / 04.01.2007
Я бы стала решать эту задачу так.
Сначала я бы построила выпуклую оболочку множества точек (для этого есть стандартные алгоритмы, например алгоритм Грэхема). В результате получается некий многоугольник. Дальше задача сводится к отысканию ширины этого многоугольника... Ну, а это, в принципе, тоже известная задача, если вспомнить школьную геометрию :)
505
04 марта 2007 года
vAC
343 / / 28.02.2006
Да, по-моему абсолютно верное решение :)
А если рассмотреть недискретную формулировку, то получится что-то вроде этого:
1. Обходим границу тела, проводя прямую, касательную к ней, причем рассматриваем только такие, чтобы граница целиком лежала по одну сторону от прямой.
2. Находим наибольшее расстояние от этой прямой до точки границы
3. Выбираем направление, соответствующее минимальному расстоянию

Спасибо!
505
04 марта 2007 года
vAC
343 / / 28.02.2006
Цитата: Sara
Я бы стала решать эту задачу так.
Сначала я бы построила выпуклую оболочку множества точек (для этого есть стандартные алгоритмы, например алгоритм Грэхема). В результате получается некий многоугольник. Дальше задача сводится к отысканию ширины этого многоугольника... Ну, а это, в принципе, тоже известная задача, если вспомнить школьную геометрию :)



Да все верно, вышеописанный алгоритм вообщим-то так и делает :)

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог