набор прямоугольников -> polygon ?

[Drakosha]

имеется набор прямоугольников, известно что его можно описать простым (не пересекаюсчим самим себя) полигоном.
прямоугольники не пересекающиеся, они касающиеся

Как этот полигон (эффективно) найти?

10XXX!

[/7y3uK]

А что значит найти? Имхо нужно найти вертексы по которым будет строиться полигон? А он может быть выпуклый или невыпуклый? Если так, то исходные прямоугольники могут и пересекаться... ты поставь задачку по конкретнее - мож чем поможем

[Drakosha]

нужно найти вертексы или точки - не важно. Полигон может быть и выпуклый и невыпуклый. Исходные прямоугольники НЕ могут пересекаться - ето дано.

[/7y3uK]

Вобщем ИМХО у тебя есть один стандартный алгоритм из графики - метод отсечения Вейлера Азертона, только модифицировать его нужно маленько, там все зависит от обхода вершин каждого полигона в отдельности. И исче - не знаю как он поведет себя в случае не пересекающихся полигонов. Если не поможет - можно попробовать двумерную трассировку луча.

[CEO]

Алгоритм отсечения многоугольника Вейлера-Азертона

Предполагается, что каждый из многоугольников задан списком вершин, причем таким образом, что при движении по списку вершин в порядке их задания внутренняя область многоугольника находится справа от границы.

В случае пересечения границ и отсекаемого многоугольника и окна возникают точки двух типов:

1) входные точки, когда ориентированное ребро отсекаемого многоугольника входит в окно,

2) выходные точки, когда ребро отсекаемого многоугольника идет с внутренней на внешнюю стороны окна.

Общая схема алгоритма Вейлера-Азертона для определения части отсекаемого многоугольника, попавшей в окно, следующая:

1. Строятся списки вершин отсекаемого многоугольника и окна.

2. Отыскиваются все точки пересечения. При этом расчете касания не считаются пересечением, т.е. когда вершина или ребро отсекаемого многоугольника инцидентна или совпадает со стороной окна (рис. 10 и 11).

3. Списки координат вершин отсекаемого многоугольника и окна дополняются новыми вершинами - координатами точек пересечения. Причем если точка пересечения Pk находится на ребре, соединяющем вершины Vi, Vj, то последовательность точек Vi, Vj превращается в последовательность Vi, Pk, Vj. При этом устанавливаются двухсторонние связи между одноименными точками пересечения в списках вершин отсекаемого многоугольника и окна.
Входные и выходные точки пересечения образуют отдельные подсписки входных и выходных точек в списках вершин.

4. Определение части обрабатываемого многоугольника, попавшей в окно выполняется следующим образом:
Если не исчерпан список входных точек пересечения, то выбираем очередную входную точку.
Двигаемся по вершинам отсекаемого многоугольника пока не обнаружится следующая точка пересечения; все пройденные точки, не включая прервавшую просмотр, заносим в результат; используя двухстороннюю связь точек пересечения, переключаемся на просмотр списка вершин окна.
Двигаемся по вершинам окна до обнаружения следующей точки пересечения; все пройденные точки, не включая последнюю, прервавшую просмотр, заносим в результат.
Используя двухстороннюю связь точек пересечения, переключаемся на список вершин обрабатываемого многоугольника.
Эти действия повторяем пока не будет достигнута исходная вершина - очередная часть отсекаемого многоугольника, попавшая в окно, замкнулась. Переходим на выбор следующей входной точки в списке отсекаемого многоугольника.

Такой алгоритм для решения поставленной задачи мне представляется не самым простым и быстрым. Кроме того его нужно модифицировать.

Вот, насколько мне удалось понять, более оптимальное решение:
http://program.rin.ru/cgi-bin/print.pl?id=649

[Drakosha]

10XX! vote on the way....

[Drakosha]

вроде нашел почти полное решение:

http://mf.grsu.by/UchProc/ztasks/olimp/geom/z21