Как объединить несколько фигур, оставив только внешние границы?

Question

[buzzi888]

Как слить несколько пересекающихся полигонов?

Answer 1

[Андрей]

Алгоритмом заливки залить каждый полигон в отдельности, объединить по ИЛИ, получив объединенную фигуру, а затем пройтись любым алгоритмом выделения границы.

Или интересуют более быстрые алгоритмы ?

Comments

[buzzi888]

Заливка, объединение и выделение границ - кажется, будут проблемы со скоростью, учитывая, что пересчитывать нужно каждый кадр(как в игре).

[Андрей]

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

[buzzi888]

Спасибо за ответы!
Есть два варианта: полигоны - замкнутые фигуры свободных форм и размеров - тут у меня мыслей нет, как это сделать и когда полигоны - окружности, тут проще, как мне кажется.

С кругами сделал так: ищем точки пересечения окружностей и рисуем только нужный сегмент. Например, см. картинку, самый левый круг отрисовываем не целиком, а только дугу начиная с 30 градусов, по 320 град.(грубо говоря), следующий за ним - две дуги(сверху и снизу) и тд.
Примерно так. Это очень удобно для отрисовки - для каждого круга есть массив точек окружности, допустим их 360 по числу градусов, тогда в механизм отрисовки достаточно передать два индекса массива - от и до( с 30-го элемента по 320-й) и получится дуга. Велосипед с квадратными колесами, конечно, но работает)

Answer 2

[Даниил Басманов]

Заливать ничего не надо, для работы с полигонами есть специальные библиотеки:
www.angusj.com/delphi/clipper.php
Для частного случая с окружностями, когда с контуром не нужны никакие манипуляции, можно простым перебором искать сегменты, которые находятся в какой-либо окружности, и не рисовать их.

Comments

[buzzi888]

Спасибо! Нашел похожую либу для js. Отличный совет с окружностями - при отрисовке каждой точки окружности(сегмента) просто проверять находится ли она внутри другой окружности, если да - не рисовать эту часть.