Здравствуйте, alekos, Вы писали:

A>Доброго времени суток!

A>Помогите найти алгоритм, помогающий решить следующую задачу.
A>Мы получаем множество точек на плоскости, которое приблизительно напоминает очертаниями прямоугольник. Задача заключается в том, чтобы вписать в эти очертания прямоугольник и определить его стороны. При этом он может быть как угодно повернут относительно осей координат и могут быть различные выступающие части — помехи, которые нужно игнорировать. По этому я думал, по началу, что нужно описывать прямоугольник, но мне кажется, что лучше именно вписывать его, тогда эти аппендиксы будут автоматических проигнорированы. Нашел два алгоритма:
A>http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rotated_ellipses/bounding_rotated_ellipses.html#bounding-rotated-ellipses
A>и
A>http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rects_circles/bounding_rects_circles.html#bounding-rects-circles
A>очень похоже, но они описывают прямоугольник вокруг объекта.
A>Может быть Вы сталкивались с какими то подобными заданиями?

Мое личное видение решение задачи, не претендующее на полноту или однозначность.
1. Вычисляем центр прямоугольника по среднему координат.
2. Определяем области наиболее удаленные от центра, разбивая их на четыре части. Это можно сделать следующим образом:
— вычисляем среднее удаление от центра Ra;
— сортируем все точки по расстоянию от центра;
— отбрасываем точки, расстояние от центра до которых меньше Ra, тем самым ограничиваем выборку только точками, близкими к краям прямоугольника;
3. Полученные четыре области пересчитываем в четыре средних точки, которые будут первым приближением краев прямоугольника C[4].
Если высокая точность не нужна, на этом можно закончить.
4. Статистически пересчитываем линии краев прямоугольников, учитывая распределение точек относительно сторон прямоугольника по C[4].
5. Пересчитываем C[4] по результатам п.4.
Пп. 4-5 только для повышения точности, особенно если известно статистическое распределение точек.