22:
138:
225:
Each quad-edge contains four references to adjacent quad-edges. Each of the four references points to the next edge counter-clockwise around either a vertex or a face. Each of these references represent either the origin vertex of the edge, the right face, the destination vertex, or the left face.
275:
Using a quad-edge structure, iterating through the topology is quite easy. Often, the interface to quad-edge topologies is through directed edges. This allows the two vertices to have explicit names (start and end), and this gives faces explicit names as well (left and right, relative to a person
252:
The quad-edge structure gets its name from the general mechanism by which they are stored. A single Edge structure conceptually stores references to up to two faces, two vertices, and 4 edges. The four edges stored are the edges starting with the two vertices that are attached to the two stored
276:
standing on start and looking in the direction of end). The four edges are also given names, based on the vertices and faces: start-left, start-right, end-left, and end-right. A directed edge can be reversed to generate the edge in the opposite direction.
148:
The quad-edge data structure represents an edge, along with the edges it is connected to around the adjacent vertices and faces to encode the topology of the graph. An example implementation of the quad-edge data-type is as follows
279:
Iterating around a particular face only requires having a single directed edge to which that face is on the left (by convention) and then walking through all of the start-left edges until the original edge is reached.
145:
The fundamental idea behind the quad-edge structure is the recognition that a single edge, in a closed polygonal mesh topology, sits between exactly two faces and exactly two vertices.
51:
398:
73:
240:
the dual of the graph can be obtained simply by reversing the convention on what is a vertex and what is a face; and
44:
363:
393:
373:
226:
Each quad-edge reference points to a quad-edge and the rotation (from 0 to 3) of the 'arm' it points at.
299:
34:
377:
38:
30:
321:"Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams"
55:
243:
can represent the most general form of a map, admitting vertices and faces of degree 1 and 2.
272:. The mesh itself does not need to be closed in order to form a valid quad-edge structure.
266:
8:
342:
294:
122:
114:
346:
332:
90:
387:
364:
https://www.cs.cmu.edu/afs/andrew/scs/cs/15-463/2001/pub/src/a2/quadedge.html
265:, quad-edge structures are used in programs to store the topology of a 2D or
269:
118:
110:
337:
320:
289:
262:
126:
234:
106:
374:
http://www.ic.unicamp.br/~stolfi/EXPORT/software/c/2000-05-04/libquad/
102:
98:
94:
367:
137:
319:Stolfi, Jorge; Guibas, Leonidas J. (April 1985).
385:
43:but its sources remain unclear because it lacks
318:
229:Due to this representation, the quad-edge:
336:
74:Learn how and when to remove this message
136:
386:
15:
13:
14:
410:
399:Computer graphics data structures
357:
125:. It is a variant of the earlier
20:
376:A quad-edge implementation in
366:A quad-edge implementation in
312:
1:
305:
325:ACM Transactions on Graphics
141:The Quad-Edge Data Structure
117:. It was first described by
7:
283:
132:
10:
415:
300:Doubly connected edge list
247:
233:represents a graph, its
151:
29:This article includes a
256:
237:, and its mirror image.
58:more precise citations.
142:
97:representation of the
394:Computer-aided design
338:10.1145/282918.282923
140:
105:or three-dimensional
113:drawn on a (closed)
295:Combinatorial maps
143:
123:Leonidas J. Guibas
31:list of references
84:
83:
76:
406:
351:
350:
340:
316:
221:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
185:
182:
179:
176:
173:
170:
167:
164:
161:
158:
155:
129:data structure.
79:
72:
68:
65:
59:
54:this article by
45:inline citations
24:
23:
16:
414:
413:
409:
408:
407:
405:
404:
403:
384:
383:
360:
355:
354:
317:
313:
308:
286:
259:
250:
223:
222:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
186:
183:
180:
177:
174:
171:
168:
165:
162:
159:
156:
153:
135:
103:two-dimensional
80:
69:
63:
60:
49:
35:related reading
25:
21:
12:
11:
5:
412:
402:
401:
396:
382:
381:
371:
359:
358:External links
356:
353:
352:
310:
309:
307:
304:
303:
302:
297:
292:
285:
282:
270:polygonal mesh
258:
255:
249:
246:
245:
244:
241:
238:
152:
134:
131:
91:data structure
82:
81:
39:external links
28:
26:
19:
9:
6:
4:
3:
2:
411:
400:
397:
395:
392:
391:
389:
379:
375:
372:
369:
365:
362:
361:
348:
344:
339:
334:
331:(2): 74‒169.
330:
326:
322:
315:
311:
301:
298:
296:
293:
291:
288:
287:
281:
277:
273:
271:
268:
264:
254:
242:
239:
236:
232:
231:
230:
227:
150:
146:
139:
130:
128:
124:
120:
116:
112:
109:, that is, a
108:
104:
100:
96:
92:
89:
78:
75:
67:
57:
53:
47:
46:
40:
36:
32:
27:
18:
17:
328:
324:
314:
278:
274:
260:
251:
228:
224:
217:quadedge_ref
163:quadedge_ref
147:
144:
119:Jorge Stolfi
87:
85:
70:
64:January 2021
61:
50:Please help
42:
290:Winged edge
263:Winged Edge
127:winged edge
56:introducing
388:Categories
306:References
261:Much like
88:quad-edge
347:52852815
284:See also
202:unsigned
190:quadedge
175:quadedge
133:Overview
99:topology
95:computer
253:faces.
248:Details
181:typedef
154:typedef
115:surface
52:improve
345:
184:struct
157:struct
343:S2CID
111:graph
101:of a
93:is a
37:, or
257:Uses
235:dual
196:next
121:and
368:C++
333:doi
208:rot
205:int
107:map
390::
341:.
327:.
323:.
267:3D
86:A
41:,
33:,
380:.
378:C
370:.
349:.
335::
329:4
220:;
214:}
211:;
199:;
193:*
187:{
178:;
172:}
169:;
166:e
160:{
77:)
71:(
66:)
62:(
48:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
