Всем доброго времени суток!

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

Вот пример:
 ==> 

Стоит также сказать, что некоторые контуры могут совпадать друг с другом до 100% (т.е. алгоритм не должен давать сбой в таком случае).

Количество вершин в каждом контуре - не менее 4, но не больше 2000.

Почитал я "Обзор алгоритмов построения оверлеев многоугольников" (О.В. Ченцов, А.В. Скворцов), если правильно понял, то мне вполне подойдет линейно-узловой алгоритм, хотя тут могу быть не прав.

Ну и собственно сам вопрос - есть ли готовые реализации подобных алгоритмов. Если будут еще и с объяснениями, то будет просто супер.

Всем откликнувшимся заранее большое спасибо!

У меня есть идея: тупая, но рабочая.

Делаем все в бинарном растре. Берем белый фон и просто рисуем на белом фоне черные залитые фигуры. Потом заливаем белым все черные пиксели, которые не граничат с белыми. Получаем контур; внутренние контуры не теряются.
  

_Y_, идея конечно крутая, но не подходит   

У меня была другая идея - взять один основной контур, самый большой, и проверить все отрезки, которые составляют контур на пересечение с отрезками других контуров. Если бы отрезок пересекался, то в основном контуре генерировалась бы новая вершина, равная точке пересечения. Далее из всех второстепенных контуров удалялись бы вершины, находящиеся внутри основного контура или совпадающие с вершинами основного контура, а потом в основной остается добавить все оставшиеся вершины. Конечно внутренний контур бы потерялся, но его наличие желательно, но не обязательно...
Но я так и не понял как после всех этих операций собрать новый контур - там может обход какой-то нужен, например против часовой стрелки от какой-нибудь вершины и проверять остальные вершины, на их положение относительно начальной.

Dementor, 

Лично я бы не стал доверять авторам у которых ошибка даже в название. 


Кроме вас никто не знает, то что вам нужно.  А во вторых вы же не платье выбираете что-бы спрашивать подойдет не подойдет.

По поводу готовых реализаций ищите геометрические библиотеки там есть. Язык вы не уточнили поэтому помочь  более конкретно не могу.

Pavia, нашел я библиотеку clipper (версия 6.1.3a). Но к сожалению на C++ Builder она не запускается (кто бы сомневался). Буду сидеть и смотреть чего они там наворотили, для реализации всего этого дела - может все-таки смогу разобраться и запустить на BCB.

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

http://www.complex-a5.ru/polyboolean/downl...olybool_eng.pdf

если с++, то http://www.boost.org/doc/libs/1_55_0/libs/...n/doc/index.htm, http://www.complex-a5.ru/polyboolean/index.html

Lipetsk, 
baldina,
Большое спасибо за ссылки и советы - буду разбираться!