134:. The winged-edge data structure is the oldest of the three, but manipulating it often requires complicated case distinctions. This is because edge references do not store the edge direction, and the directions of edges around a face need not be consistent. The halfedge data structure stores both orientations of an edge and links them properly, simplifying operations and the storage scheme. The Quadedge data structure stores both the planar subdivision and its dual simultaneously. Its records consist explicitly only of edge records, four for each edge, and in a simplified form it is suitable for storing PSLGs.
20:
110:. However, in discussions involving Euclidean graphs, the primary interest is their metric properties, i.e., distances between vertices, while for PSLGs the primary interest is the topological properties. For some graphs, such as
103:). Point-set triangulations are maximal PSLGs in the sense that it is impossible to add straight edges to them while keeping the graph planar. Triangulations have numerous applications in various areas.
152:. Find the overlay of two PSLGs (maps), which is the subdivision of the plane by the two simultaneously embedded PSLGs. In GIS this problem is known as "
149:
282:
229:
221:
211:
89:
301:
77:, with an assumption or assertion that subdivisions are polygonal rather than having curved boundaries.
166:
127:
306:
100:
311:
111:
35:
31:
96:
67:
8:
191:
63:
260:
195:
172:
278:
225:
217:
207:
252:
122:
There exist three well-known data structures for representing PSLGs, these are the
85:
264:
203:
107:
55:
143:
277:
Handbook of Data
Structures and Applications, D. P. Mehta and S. Sahni, 2005,
295:
153:
59:
256:
190:
123:
243:
Nagy, George; Wagle, Sharad (June 1979), "Geographic Data
Processing",
131:
70:(1948) states that every planar graph has this kind of embedding.
19:
16:
Planar graph embedding where edges map to straight-line segments
146:. For a query point, find which face of the PSLG it belongs to.
114:, both metric and topological properties are of importance.
66:
such that its edges are mapped into straight-line segments.
216:. 1st edition; 2nd printing, corrected and expanded, 1988:
81:
73:
In computational geometry, PSLGs have often been called
293:
80:PSLGs may serve as representations of various
137:
95:Special cases of PSLGs are triangulations (
242:
200:Computational Geometry - An Introduction
18:
106:PSLGs may be seen as a special kind of
294:
169:, a data structure to represent a PSLG
13:
117:
14:
323:
90:geographical information systems
270:
236:
184:
1:
224:; Russian translation, 1989:
178:
7:
160:
10:
328:
167:Doubly connected edge list
40:planar straight-line graph
25:planar straight-line graph
138:Problems in terms of PSLG
48:plane straight-line graph
44:straight-line plane graph
112:Delaunay triangulations
101:point-set triangulation
36:geometric graph theory
32:computational geometry
27:
257:10.1145/356770.356777
245:ACM Computing Surveys
97:polygon triangulation
22:
302:Geometric algorithms
192:Franco P. Preparata
75:planar subdivisions
196:Michael Ian Shamos
173:Local feature size
28:
86:geographical maps
319:
307:Geometric graphs
287:
274:
268:
267:
240:
234:
233:
188:
126:data structure,
108:Euclidean graphs
327:
326:
322:
321:
320:
318:
317:
316:
292:
291:
290:
275:
271:
241:
237:
214:
204:Springer-Verlag
189:
185:
181:
163:
140:
120:
118:Representations
17:
12:
11:
5:
325:
315:
314:
309:
304:
289:
288:
269:
251:(2): 139–181,
235:
212:
182:
180:
177:
176:
175:
170:
162:
159:
158:
157:
147:
144:Point location
139:
136:
119:
116:
68:Fáry's theorem
23:An example of
15:
9:
6:
4:
3:
2:
324:
313:
312:Planar graphs
310:
308:
305:
303:
300:
299:
297:
286:, chapter 17
285:
284:
283:1-58488-435-5
280:
273:
266:
262:
258:
254:
250:
246:
239:
231:
230:5-03-001041-6
227:
223:
222:3-540-96131-3
219:
215:
213:0-387-96131-3
209:
205:
201:
197:
193:
187:
183:
174:
171:
168:
165:
164:
155:
151:
148:
145:
142:
141:
135:
133:
129:
125:
115:
113:
109:
104:
102:
98:
93:
91:
87:
83:
78:
76:
71:
69:
65:
61:
57:
53:
49:
45:
41:
37:
33:
26:
21:
276:
272:
248:
244:
238:
199:
186:
154:thematic map
121:
105:
94:
79:
74:
72:
60:planar graph
51:
50:), in short
47:
43:
39:
29:
24:
150:Map overlay
124:Winged-edge
296:Categories
179:References
156:overlay".
56:embedding
198:(1985).
161:See also
132:Quadedge
128:Halfedge
84:, e.g.,
54:, is an
62:in the
281:
265:638860
263:
228:
220:
210:
130:, and
261:S2CID
64:plane
58:of a
46:, or
279:ISBN
226:ISBN
218:ISBN
208:ISBN
194:and
82:maps
52:PSLG
42:(or
38:, a
34:and
253:doi
88:in
30:In
298::
259:,
249:11
247:,
206:.
202:.
99:,
92:.
255::
232:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
