# Questions tagged [doubly-connected-edge-list]

A doubly-connected edge list (DCEL) is an edge-centered data structure capable of maintaining incidence information of vertices, edges and faces, for example for planar maps.

9 questions
Filter by
Sorted by
Tagged with
99 views

### Given a DCEL, how do you identify the unbounded face

I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?. This correctly identifies all faces, however I'm struggling ...
51 views

### Sort half-edges around common vertex in 3d

I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure. Say I have non-manifold geometry where two ...
40 views

### When computing Monotone Polygon Triangulation, how do I store the formed diagonals in the DCEL?

It's my understanding that a DCEL have the following structs ...
759 views

### How do I visit all edges incident to a vertex in a DCEL data structure?

In a doubly-connected edge list (DCEL) data structure, each vertex v stores a pointer to one arbitrary half-edge, v.inc, which ...
1k views

### Problem with storing an existing triangulation in a DCEL

I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure. Using the algorithm described in this answer, I was able to store a part ...
93 views

### DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely? I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
131 views

### DCEL operations on quad-edges, Twin, Next, and Prev

Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (twin, next, ...
For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \{ e_1,...,e_m \right \}$, each segment $e_i$ is represented by its endpoints \$\left \{ L_i,R_i \...