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

Буду благодарен любой информации.
Спасибо!

Соколинский БорисВ принципе доточить под свои требования, но для этого их нужно сформулировать - в каких случаях нужно достраивать вогнутые области, а в каких нет.
мне кажется алгоритм выпуклой оболочки тут в принципе не подойдет, там же как правило отбор ведется по правилу самая правая при движении против часовой или дополнить расстоянием и отбирать самую близкую правую

AkinaНепонятен критерий, по которому выполняется обрисовка... глядя на скрины 2 и 3, я бы провёл контур как-то так
отмена, cancel - был описан частный случай, решил не заморачиваться, согласен вариации могут быть

maytonЧто тебе надо на самом деле сделать? Продемонстрировать преподавателю как ты хорошо выучил ГИГМ ?
Или реально сделать боевую задачу ? Это разные подходы будут.
это боевая задача, я не студент

maytonxMailer, на каком языке собираешся кодить свою боевую задачу?
серверный, пока php. Если Вы про использование opencv - растровый путь не рассматриваю.

Парни, ТС не слился, я тут и читаю периодически данный пост, дел просто за гланды, не нужно меня ругать.
Пока думаю над данным вопросом.

AklinxMailer2. группировка всех координат, координаты с кол-вом однократным повторений в наборе - являются вершины, да работает, но возможно наличие не соприкасаемых прямоугольников, скрин 4 и тогда не будет работатьсамое забавное, что это простейшее из решений, и его нужно лишь допилить под случай с несвязанными областями и только.
я уже выше писал, что отказался от учета не соприкасаемых прямоугольников.
Поэтому пока сделал как группировка, только изменил группировку на поиск по расстоянию, другими словами: берем точку и расчитываем расстояние до остальных точек, если встречаем расстояние меньше определенного, прерываемся и выкидываем точку, в итоге у нас остаются все угловые точки. НО опять уперся: получив unsorted точки контура мне нужно из выстроить опять же по контуру, отсортировать по часовой. Упорядочить вершины по полярному кругу не получилось.

maytonНикакая у него не выпуклая оболочка. Если ему скрин 3 не подходит значит у него просто - многогранник
которые соединяет экстремальные точки контура всех прямоугольников.
Вот постановка вопроса.

Координаты вещественные и сильно.

maytonДано - груз прямоугольных ящиков. Расчитать длину брезента чтоб обмотать груз ящиков
плотно. Чтоб не болталось на ветру.
Так?
интересно, да, так. Есть типовой подход, типа задачи коммивояжёра.

exp98xMailerУпорядочить вершины по полярному кругу не получилось. а) Почему?
центр для определения угла я определил как
xc = sum(x)/count(x)
yc = sum(y)/count(y)
вес для сортировки относительно центра
angle = atan2(cx - x, cy - y)

Такого рода сортировка будет корректно работать если центр xc,yc находится в примерном центре, в случае выгнутости фигуры у меня не заработало.

Отверстий в фигуре в данной задаче не предусматривается