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