Задача минимальных проекций
Есть набор точек в 2D (Xi,Yi). Задача до безобразия проста: найти такое направление (вектор или угол, как угодно), чтобы разница между максимальным и минимальным значением из всех проекций (ширина проекции) точек на это направление было минимальным. Можно сказать так: найти ширину объекта по набору его точек.
"заначение проекции" - это скаларное произведение вектора направления на р-вектор точки.
МНК никак сюда не прикрутить :)
Могу сформулировать задачу так:
alpha' = argmin(w(alpha));
w(alpha) = max(L(alpha)*P)-min(L(alpha)*P);
L(alpha) = [cos(alpha); sin(alpha)];
P - данные точки
*-скалярное произведение
Найти: либо alpha' либо L(alpha')
Ну задача всетаки непрерывно-дискретная: по i-дискретная, по alpha-непрерывная, т.е. даже перебором не обойтись. Конечно можно взять дискретный набор углов из множетва [0,PI) и выбрать оптимальный. Это и есть то решение, которое я реализовал...но оно обладает "точностью" в математичеком смысле. А хотелось бы реализовать точный метод.
Графиками проекций от угла будут синусоиды...вот эту кашу-то и надо как-то переварить
P.S. Т.е. объект всегда будет иметь какую-то ширину в зависимости от того, в каком направлении ты его рассматриваешь.
P.S. Т.е. объект всегда будет иметь какую-то ширину в зависимости от того, в каком направлении ты его рассматриваешь.
Не совсем понял...Imax и Imin перебирать или искать? если перебирать, то не все пары будут при каком-то угле крайними. А если искать, то они зависят от alpha: Imax(alpha), Imin(alpha) - ведь крайние точки меняются в зависимости от направления.
Так ни тот, ни другой вариант не решит задачу.
В первом случае задача-то тривиальна, зная направление, без проблем можно найти минимум а максимум проекций, но мне же нужно не какое-то фиксированное, а то, которое приведет к минимуму ширины проекции. Во втором случае если я буду решать задачу max(Imax)-min(Imin)->min, то получу просто перпендикулярное направление к отрезку прямой, соединяющей точки P[Imax] и P[Imin], т.к. при этом условии max(Imax)-min(Imin)=0 - и есть минимум
Я давно не заходила на этот форум, а тут вдруг увидела интересный вопрос по моей специальности :)
Разумеется, задача имеет аналитическое решение. Если это еще актуально, могу написать алгоритм.
Мне кажутся очевидными следующие утверждения:
1. На одной из двух прямых, которые ограничивают отрезок на проведенном искомом векторе и являются перпендикулярными этому вектору, должно лежать две точки. То есть надо искать наименьшее расстояние от какой-то "крайней" точки до прямой, образованой двумя точками.
2. Очевидно, что нам интересны только те пары точек для образования прямой, чтобы все остальные точки были по одну сторону от нее. Алгоритм под такую задачу для массива написать совсем не сложно, как и сразу найти самую дальнюю точку от этой пары.
Проходим максимум 2 раза по всему массиву, находим наименьший результат. Это для массива точек.
Сначала я бы построила выпуклую оболочку множества точек (для этого есть стандартные алгоритмы, например алгоритм Грэхема). В результате получается некий многоугольник. Дальше задача сводится к отысканию ширины этого многоугольника... Ну, а это, в принципе, тоже известная задача, если вспомнить школьную геометрию :)
А если рассмотреть недискретную формулировку, то получится что-то вроде этого:
1. Обходим границу тела, проводя прямую, касательную к ней, причем рассматриваем только такие, чтобы граница целиком лежала по одну сторону от прямой.
2. Находим наибольшее расстояние от этой прямой до точки границы
3. Выбираем направление, соответствующее минимальному расстоянию
Спасибо!
Сначала я бы построила выпуклую оболочку множества точек (для этого есть стандартные алгоритмы, например алгоритм Грэхема). В результате получается некий многоугольник. Дальше задача сводится к отысканию ширины этого многоугольника... Ну, а это, в принципе, тоже известная задача, если вспомнить школьную геометрию :)
Да все верно, вышеописанный алгоритм вообщим-то так и делает :)