<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>In case this helps, the library I'm using is TriPath by Marcello Kallmann (<a href="http://graphics.ucmerced.edu/software/tripath/" rel="nofollow noreferrer">http://graphics.ucmerced.edu/software/tripath/</a>).</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/FoEQ8.png" alt="CDT with edges in rectangles"></p>

CC BY-SA 3.0
2014-02-11T20:59:45.860Z
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?
Chad Brewbaker
CC BY-SA 3.0
2014-02-11T21:03:25.817Z
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.
zaloo
CC BY-SA 3.0
2014-02-12T00:26:16.027Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-02-12T01:03:03.793Z
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
zaloo
<graph-theory><graph-algorithms><planar-graphs><delaunay-triangulation><computational-geometry>
Rectangular constraints in Delaunay Triangulation without edges within
zaloo
# Rectangular constraints in Delaunay Triangulation without edges within

(Asked by: username_0 on 2014-02-11)

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](https://i.sstatic.net/FoEQ8.png)

**Tags:** graph-theory, graph-algorithms, planar-graphs, delaunay-triangulation, computational-geometry

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: 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  

---

## 0 answers

