Алгоритм вычисления оставшегося многоугольника после вычитания

Question

У меня большой многоугольник (Pa). Внутри многоугольника есть много маленьких «дырок», как показано:

Вот несколько условий для отверстий:

1. Отверстия не могут перекрывать друг друга
2. Отверстия не могут выходить за пределы внешнего многоугольника
3. Однако отверстия могут касаться внешнего края многоугольника

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

Редактировать: Я не спрашиваю о том, как выполнить алгоритм обрезки (или вычитания) полигонов! На самом деле это то, что я бы сделал грубой силой. Я спрашиваю в дополнение к методу обрезки полигонов (возьмите основной полигон и затем постепенно вырежьте отверстия), есть ли другой более эффективный способ?

Answer 1

Это очень сложно сделать в общем виде.Вы можете найти исходный код решения здесь:

General Polygon Clipper (GPC)

Answer 2

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

Единственное, что вам следует учесть, это то, что если какая-то вершина или ребро отверстия может коснуться края Pa, вам придется выполнить там некоторое упрощение.

Другая проблема заключается в преобразовании этого многоугольника в растровое изображение!

Answer 3

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

Сам алгоритм не очень сложен, и это хорошо объясняется в Обучении заливки полигоновИнструмент .

Answer 4

Вы можете сделать это так.

1. Нарисуйте основной многоугольник с цветом в растровом изображении.
2. Нарисуйте отверстия с другим цветом в том же растровом изображении.
3. Затем извлеките многоугольник, запустив маршалгоритм квадрата с основным цветом полигонов в качестве порога.
4. Выходные данные будут содержать все точки, которые принадлежат этому полигону.
5. Вы можете сортировать точки, если хотите, чтобы они были непрерывным замкнутым многоугольником.