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
1
vote
0
answers
48
views
When Triangulating monotone polygons, how can diagonals be added to a DCEL in constant time?
I am working on the polygon triangulation algorithms from "Computational Geometry - Algorithms and applications 3rd ed", chapter 4.
I've managed to turn polygons into y-monotone polygons ...
- 11
2
votes
1
answer
75
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 ...
- 177
4
votes
1
answer
384
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 ...
- 43
3
votes
0
answers
141
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
2
votes
1
answer
243
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, ...
- 189
2
votes
1
answer
1k
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 ...
user20691
0
votes
1
answer
945
views
How do you find out if the polygon lies to the right of a regular vertex?
In section 3.2 of the book Computational Geometry: Algorithms and Applications (by Berg et al.), the authors describe a procedure to make a polygon y-monotone. The algorithm distinguishes vertices ...
0
votes
1
answer
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 ...
12
votes
1
answer
11k
views
How do I construct a doubly connected edge list given a set of line segments?
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 \...
- 3,179