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.

CDT with edges in rectangles

  • $\begingroup$ By CDT I am assuming every point must lie on one of the rectangles, and every rectangle corner must contain a point. Also for nesting purposes, every rectangle is disjoint except for the super-rectangle that bounds everything. Is this correct? $\endgroup$ – Chad Brewbaker Feb 11 '14 at 20:59
  • $\begingroup$ Well every point in the constraints. The triangulation will of course have points outside of these rectangles that are the results of the unconstrained edges. The rectangles are just 4 vertex constraints with 4 edge constraints to connect these vertices together. $\endgroup$ – zaloo Feb 11 '14 at 21:03
  • $\begingroup$ Just curious. some of this depends on your data structure (half-edge?), but why would removing edges from inside the rectangles be more than linear time ? you go through each rectangle vertex, you have the edges in cyclic order, and so you can identify edges "between" rectangle edges. $\endgroup$ – Suresh Venkat Feb 12 '14 at 0:26
  • $\begingroup$ Damn that's smart. I didn't think about ordering the edges in cyclic order. I guess you'd find all the "rectangle edges" and then you automatically have the rest from the cyclic ordering of edges from a vertex $\endgroup$ – zaloo Feb 12 '14 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.