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