Найти контур фигуры

[роман11]

Здравствуйте, вот задачка: Задано n прямоугольников на плоскости. Найти контур их объединения - минимальный многоугольник, охватывающий все заданные прямоугольники. Задача для паскаля в модуле Graph. Помогите пожалуйста.

[NetSpace]

попытался нарисовать на листе 5 прямоугольников: в столбик, а линию, в кучу... и понял, что математически там придётся повозиться, а ещё в паскаль перекладывать.
а если ещё и 5< N взять прямоугольников.... до какого числа тебе эту экзаменационную задачку надо сдать? если нет наработок своих, то хоть за денюжку - во Фриланс иди

[Smogg]

1. берется первый много угольник.
2. перебираются все точки прочих n-угольников.
3. 1. если точка внутри - берем следующую точку
3. 2. иначе расширяем "охватыватель"
3. 2. 1. добавляем точку в контур "охватывателя"
3. 2. 2. проверяем "охватыватель" на выпуклость, при необходимости - удаляем ненужные точки.

Как правильно определить, в какое место в упорядоченном наборе точек "охватывателя" надо вставить новую точку, чтоб не получалась "самопересекающаяся звезда".... Ну, предположим, что центр будет в центре прямоугольника, в который вписывается "охватыватель", все равно координаты истинного центра масс надо знать лишь примерно, ведь подойдет любая точка, лишь бы однозначно лежала внутри фигуры. То есть, надо предусмотреть что допущение про центр фигуры не верно, и проверять, а действительно ли точка внутри? Или теоретически удостовериться, что центр любого описанного четырехугольника ВСЕГДА лежит внутри вписанного многоугольника. Теперь от этой внутрилежащей точки строим отрезок до рассматриваемой добавляемой вершины и проверяем, с какой гранью он пересекся. Вот между точками этой грани новую вершину и вставляем. А уже после проверяемся на выпуклость.

А хотя, проще по другому: ведь у нас известен знак обхода проверки на "внутрилежащность", достаточно просто найти грань, относительно которой знак проверки будет равен "знаку внележащности".

[Sibedir]

Безымянный.bmp

Решаем в лоб
1. Ищем самые верхние точки
2. Выбираем из них самую левую (идти будем по часовой стрелке) - это наша отправная точка T[1].
3. Angle := 0;
// Не помню как там у нормальных людей.
// В данном посте отсчитываю угол по часовой стрелке.
// За ноль взял 3 часа
// Но сути это не меняет
4. Count := 1;
5. Выбираем из них самую правую - Tтекущая.
. 6. Inc (Count); T[Count] := Tтекущая;
. 7. Ищем точки угол поворота до которых больше Angle, но минимален (Их может быть несколько). Это и есть новый Angle
. 8. Выбираем самую дальнюю - это новая Tтекущая.
9. Если Tтекущая <> T[1] возврат на п.6

Комментарии
1. Можно оптимизировать задачу заранее отсортировав точки и по X и по Y. Зная направление движения можно не обрабатывать заведомо ненужные точки.

2. В задании написано: "Задано n прямоугольников". Видимо это подсказка на способ отсечения ненужных обработок. За один ход при любом раскладе мы не сможем повернуть более чем на 90 градусов. А точнее: мы обязательно посетим 0, 90, 180 и 270.
Например: Если мы шли СТРОГО ВВЕРХ, то на следующем шаге нас интересуют только точки не ниже (не сможем переволить через ортогонали не отметившись) и не левее (мы же по часовой стрелке идем).

3. Еще. Если мы движемся вниз - нас интересуют только правые грани. Если влево - только нижние. Ну и так далее.

[Smitt&Wesson]

Вот тут и обход по контуру и формирование регионов из изображений произвольной конфигурации:

[роман11]

большое спасибо