I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside of the rectangles that define the constraints.
I want to be able to create a graph without the edges within any of the rectangles that are the constraints (with the exception of the large boundary of course) but removing these edges in the triangulation that is given to me takes longer than O(nlog(n)) time at least and that's not good for what I need.
What I'm asking is, is there any quick way to get a CDT to keep edges from appearing within some polygon? I want the rectangles to be empty of edges but I'm not sure how to quickly do that.
In case this helps, the library I'm using is TriPath by Marcello Kallmann (http://graphics.ucmerced.edu/software/tripath/).
Here's an image to help you visualize what I'm trying to describe. This CDT is built with the black lines being constraints. As you can see, each constrained edge is part of a rectangle. The blue lines are unconstrained Delaunay edges. I am trying to remove any blue unconstrained Delaunay edges from within the black constrained rectangles.