Как разделить / разбить полигоны на существующие регионы?
Я сталкиваюсь с проблемой, касающейся "разбиения"/ поднабора полигонов на регионы (большие полигоны), чтобы в каждом регионе были непересекающиеся значимые элементы.
Например, у нас есть следующие регионы / полигоны. В данный момент времени мы знаем только форму одного региона (скажем, пока R1). Понятно, что L3 будет принадлежать R1. Как насчет L1, L2 и P1? Я думал о создании ограничивающих рамок вокруг них и проверке, принадлежит ли юго-восточная координата ( minX и minY) R1. Таким образом, L1 будет принадлежать R2, даже если он даже не пересекает R2.
У вас есть какая-то конкретная идея, на что мне обратить внимание в отношении таких алгоритмов или как решить эту проблему разделения пространства?
1 ответ
Если все ваши регионы и полигоны описаны как полигоны (дискретные последовательности вершин), вы можете прибегнуть к доступным методам отсечения полигонов.
В частности, взгляните на методы Сазерленда-Ходжмана и Вейлера-Атертона.
Некоторая оптимизация возможна, если разрешена предварительная обработка окон (когда для одних и тех же окон имеется много полигонов объектов) с использованием методов сканирования. Это немного сложнее.
Случай с линейными сегментами немного проще.