Используя пакет 2D Arrangements от CGAL, можно ли быстро определить, какие грани являются внутренними по отношению к данной замкнутой кривой, после совокупной вставки большого количества замкнутых, возможно, пересекающихся кривых?
Расположение CGAL: грани в кривых
Ответы (1)
Сначала вам нужно иметь логическое значение для каждого лица, чтобы знать, было ли оно уже помечено (это может быть расширенный тип лица или просто std::set
). Вам также понадобится очередь лиц для обработки.
Затем начните с неограниченного лица и отметьте его как посещенное. Для каждого отверстия возьмите противоположный полуребр (следите за тем, чтобы вы оказались внутри кривой, соответствующей полуребру), пометьте лицо как посещенное и добавьте его в очередь.
Для каждой грани в очереди, для каждой половины ее внешней границы возьмите противоположную половину кромки. Если соответствующая грань еще не помечена, то пометьте ее и учитывайте пересеченное ребро. Добавьте это лицо в очередь. Когда вы закончите с внешней границей, вы можете рассмотреть одну половину кромки на отверстие.
Когда очередь пуста, все готово.
Обратите внимание на то, что кривые, содержащие текущее лицо, должны использовать кривые из лица, содержащего его. Таким образом, я предлагаю в очереди хранить по одному полуребру для каждого лица (таким образом у вас будет прямой доступ к содержащему его лицу, которое уже было обработано).