Булевые операции с многоугольниками

[SBJoker]

Интересуют способы реализации булевых операций с многоугольниками на плоскости.
Где многоугольники определены последовательным набором точек {x, y}, многоугольники не выпуклые хотя в частном случае могут ими быть.

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

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

Буду рад ссылкам по теме или конкретным алгоритмам.

[Dzirt]

Крайне заинтересовало написать самому на блитце....уже есть маленькие успехи.Завтра к вечору выложу пример.

[Dzirt]

Черт...єто сложнее чем я сначала подумал(. Пример я конечно тебе нашол,но свой наверное допишу не скоро(хотя если подумать,зачем тебе моя халтура ).

bool.zip

[Venom]

Сообщение от SBJoker

Буду рад ссылкам по теме или конкретным алгоритмам.

http://davis.wpi.edu/~matt/courses/clipping/

[SBJoker]

Спасибо, примерно так я уже и решил проблему.

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

После чего находим все пересечения граней. И вновь созданные точки помещаем в порядки обхода вершин всех многоугольников причастных к её появлению (чаще всего их 2).

Потом с точки любого многоугольника не лежащей внутри любого другого многоугольника (это важно), начинаем обход вершин по-порядку.

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

Делая обход пройденные вершины добавляем в новым многоугольник,который и будет результатом СЛОЖЕНИЯ. Завершаем обход встретив отправную точку.

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

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

Число пересечений всегда кратно 2м.

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

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

Ну и т.д.