Using the 2D Arrangements package from CGAL, is it possible to quickly identify which faces are internal to a given closed curve, after aggregately inserting a large number of closed, possibly intersecting curves?
You first need to have a boolean per face to know if it was already tagged (this can be an extended face type or simply a std::set).
You'll also need a queue of faces to process.
Then start from the unbounded face and tagged it as visited. For each hole, take the opposite halfedge (keep track of the fact that you're inside the curve corresponding to the halfedge), tag the face as visited and add it to the queue.
For each face in the queue, for each halfedge of its outer boundary, take the opposite halfedge. If the corresponding face is not yet tag, then tag it and take into account the crossed edge. Add that face to a queue. When you're done with the outer boundary, you can consider one halfedge per hole.
When the queue is empty, you're done.
Note that the curves containing the current face need to use those from the face containing it. Thus I suggest the queue to store one halfedge per face (that way you have a direct access to the containing face that has been already processed).