CGAL Arrangement：曲面中的面

Question

使用CGAL中的2D Arrangements软件包，在聚合插入大量封闭的，可能相交的曲线后，是否可以快速识别给定闭合曲线内部的哪些面？

Answer 1

您首先需要有一个布尔每个人脸来知道它是否已被标记（这可以是一个扩展脸型或简单地std::set）。 您还需要处理一个面的队列。

然后从无界面开始并将其标记为已访问。 对于每个孔，取相反的半边（跟踪对应于半边的曲线内的事实），将面标记为已访问并将其添加到队列中。

对于队列中的每个面，对于其外边界的每个半边，采取相反的半边。如果相应的脸部尚未标记，则标记它并考虑交叉边缘。将该面添加到队列中。当你完成外部边界时，你可以考虑每个孔一个半边。

当队列为空时，就完成了。

请注意，包含当前面部的曲线需要使用包含该面部的曲面。因此，我建议队列存储每个面的一个半边（这样可以直接访问已经处理的包含面）。