#computational-geometry
Вопрос:
У меня есть несколько полигонов, где некоторые из них разного цвета, а некоторые одинакового цвета. Я хочу сгруппировать их в области (например, новые полигоны), которые полностью содержат все полигоны одного цвета.
Посмотрите два простых примера, которые оба удовлетворяли бы этим условиям. Пунктирные красные линии-это желаемый результат.
Первый пример разделяет всю плоскость, второй-нет. Мне все равно, пока все полигоны одного цвета сгруппированы.
Можно предположить, что решение существует, т. е. не будет многоугольника синего цвета, полностью закрытого многоугольником черного цвета. Кроме того, полигоны не пересекаются, но могут иметь общую границу, как в примере. Однако могут возникнуть крайние случаи, подобные этому:
Я ищу алгоритм, который может это сделать. Первый пример напомнил мне диаграммы Вороного, но он отличается тем, что у меня есть полигоны, а не отдельные точки.
Примером этого в реальном мире было бы разделение города на районы, основанные на жилых кварталах.
Комментарии:
1. Подсказка: возьмите точку в каждом черном многоугольнике и свяжите их с помощью алгоритма планирования пути, который позволяет избежать всех нечерных многоугольников. Повторите с другими цветами, сохраняя ранее установленные связи.
Ответ №1:
Что я в итоге сделал, так это применил эти шаги итеративно:
- Используйте буферный алгоритм для увеличения всех полигонов.
- Объедините те, которые имеют одинаковый цвет, с помощью операции объединения.
- Повторите все полученные фигуры и вычитайте из них все остальные фигуры, чтобы избавиться от перекрывающихся областей. Эту итерацию необходимо выполнять попеременно с начала и до конца, иначе фигуры будут расти неравномерно.
Эти шаги повторяются до тех пор, пока результат не станет визуально приятным. Эта процедура не обрабатывает особый случай, упомянутый на второй картинке вопроса (она изолирует два синих полигона), но в конце концов это был приемлемый компромисс для моего варианта использования.