88:
116:
Each vertex contains the coordinates of the vertex and also stores a pointer to an arbitrary edge that has the vertex as its origin. Each face stores a pointer to some half-edge of its outer boundary (if the face is unbounded then pointer is null). It also has a list of half-edges, one for each hole
112:
half-edges associated with a face are clockwise or counter-clockwise. For example, in the picture on the right, all half-edges associated with the middle face (i.e. the "internal" half-edges) are counter-clockwise. A half-edge has a pointer to the next half-edge and previous half-edge of the same
107:
of the subdivision. Each record may contain additional information, for example, a face may contain the name of the area. Each edge usually bounds two faces and it is, therefore, convenient to regard each edge as two "half-edges" (which are represented by the two edges with opposite directions,
113:
face. To reach the other face, we can go to the twin of the half-edge and then traverse the other face. Each half-edge also has a pointer to its origin vertex (the destination vertex can be obtained by querying the origin of its twin, or of the next half-edge).
117:
that may be incident within the face. If the vertices or faces do not hold any interesting information, there is no need to store them, thus saving space and reducing the data structure's complexity.
52:. This data structure provides efficient manipulation of the topological information associated with the objects in question (vertices, edges, faces). It is used in many
213:
108:
between two vertices, in the picture on the right). Each half-edge is "associated" with a single face and thus has a pointer to that face.
79:, but the DCEL structure may be extended to handle disconnected graphs as well by introducing dummy edges between disconnected components.
245:
240:
235:
61:
126:
131:
49:
57:
100:
96:
71:
This data structure was originally suggested by Muller and
Preparata for representations of 3D
209:
141:
184:
174:
87:
72:
41:
104:
76:
65:
33:
29:
229:
179:
162:
37:
136:
75:. Simplified versions of the data structure, as described here, only consider
53:
91:
Each half-edge has exactly one previous half-edge, next half-edge and twin.
204:
de Berg, Mark; Cheong, Otfried; van
Kreveld, Marc; Overmars, Mark (2008).
45:
99:
of edges. In the general case, a DCEL contains a record for each edge,
189:
86:
60:
to handle polygonal subdivisions of the plane, commonly called
68:
is commonly represented by a DCEL inside a bounding box.
206:
Computational
Geometry, Algorithms and Applications
163:"Finding the Intersection of Two Convex Polyhedra"
8:
208:(3rd ed.). Springer. pp. 29–33.
188:
178:
161:Muller, D. E.; Preparata, F. P. (1978).
153:
7:
14:
1:
180:10.1016/0304-3975(78)90051-8
167:Theoretical Computer Science
62:planar straight-line graphs
262:
18:doubly connected edge list
246:Geometric data structures
95:DCEL is more than just a
127:Quad-edge data structure
26:half-edge data structure
132:Doubly linked face list
64:(PSLG). For example, a
241:Geometric graph theory
92:
58:computational geometry
236:Graph data structures
90:
97:doubly linked list
93:
215:978-3-540-77973-5
142:Combinatorial map
24:), also known as
253:
220:
219:
201:
195:
194:
192:
182:
158:
77:connected graphs
73:convex polyhedra
32:to represent an
261:
260:
256:
255:
254:
252:
251:
250:
226:
225:
224:
223:
216:
203:
202:
198:
160:
159:
155:
150:
123:
85:
66:Voronoi diagram
12:
11:
5:
259:
257:
249:
248:
243:
238:
228:
227:
222:
221:
214:
196:
173:(2): 217–236.
152:
151:
149:
146:
145:
144:
139:
134:
129:
122:
119:
84:
83:Data structure
81:
30:data structure
13:
10:
9:
6:
4:
3:
2:
258:
247:
244:
242:
239:
237:
234:
233:
231:
217:
211:
207:
200:
197:
191:
186:
181:
176:
172:
168:
164:
157:
154:
147:
143:
140:
138:
135:
133:
130:
128:
125:
124:
120:
118:
114:
111:
106:
102:
98:
89:
82:
80:
78:
74:
69:
67:
63:
59:
55:
51:
47:
43:
39:
35:
31:
27:
23:
19:
205:
199:
170:
166:
156:
115:
109:
94:
70:
38:planar graph
25:
21:
17:
15:
137:Winged edge
230:Categories
190:2142/74093
148:References
54:algorithms
46:polytopes
34:embedding
121:See also
40:in the
28:, is a
212:
101:vertex
44:, and
42:plane
36:of a
210:ISBN
105:face
103:and
22:DCEL
16:The
185:hdl
175:doi
110:All
56:of
48:in
232::
183:.
169:.
165:.
50:3D
218:.
193:.
187::
177::
171:7
20:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
