Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

/[routino]/trunk/src/nodesx.c
ViewVC logotype

Contents of /trunk/src/nodesx.c

Parent Directory Parent Directory | Revision Log Revision Log

Revision 121 - (show annotations) (download) (as text)
Sun Feb 15 14:30:11 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 13575 byte(s) 
Store radians rather than degrees.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.3 2009-02-15 14:30:11 amb Exp $
3
4 Extented Node data type functions.
5 ******************/ /******************
6 Written by Andrew M. Bishop
7
8 This file Copyright 2008,2009 Andrew M. Bishop
9 It may be distributed under the GNU Public License, version 2, or
10 any higher version. See section COPYING of the GNU Public license
11 for conditions under which this file may be redistributed.
12 ***************************************/
13
14
15 #include <assert.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <stdio.h>
19 #include <math.h>
20
21 #include "types.h"
22 #include "functions.h"
23 #include "nodesx.h"
24 #include "segmentsx.h"
25
26
27 /* Constants */
28
29 /*+ The array size increment for nodes - expect ~8,000,000 nodes. +*/
30 #define INCREMENT_NODES 1024*1024
31
32
33 /* Functions */
34
35 static int sort_by_id(NodeX **a,NodeX **b);
36 static int sort_by_lat_long(NodeX **a,NodeX **b);
37
38
39 /*++++++++++++++++++++++++++++++++++++++
40 Allocate a new node list.
41
42 NodesX *NewNodeList Returns the node list.
43 ++++++++++++++++++++++++++++++++++++++*/
44
45 NodesX *NewNodeList(void)
46 {
47 NodesX *nodesx;
48
49 nodesx=(NodesX*)malloc(sizeof(NodesX));
50
51 nodesx->alloced=INCREMENT_NODES;
52 nodesx->xnumber=0;
53 nodesx->sorted=0;
54
55 nodesx->xdata=(NodeX*)malloc(nodesx->alloced*sizeof(NodeX));
56 nodesx->gdata=NULL;
57 nodesx->idata=NULL;
58
59 return(nodesx);
60 }
61
62
63 /*++++++++++++++++++++++++++++++++++++++
64 Save the node list to a file.
65
66 NodesX* nodesx The set of nodes to save.
67
68 const char *filename The name of the file to save.
69 ++++++++++++++++++++++++++++++++++++++*/
70
71 void SaveNodeList(NodesX* nodesx,const char *filename)
72 {
73 int i;
74 int fd;
75 Nodes *nodes=calloc(1,sizeof(Nodes));
76 index_t *offsets;
77 int32_t lat_min,lat_max,lon_min,lon_max;
78 int latbins,lonbins,latlonbin;
79
80 assert(nodesx->sorted); /* Must be sorted */
81
82 /* Work out the offsets */
83
84 lat_min=lat_long_to_bin(nodesx->lat_min);
85 lon_min=lat_long_to_bin(nodesx->lon_min);
86 lat_max=lat_long_to_bin(nodesx->lat_max);
87 lon_max=lat_long_to_bin(nodesx->lon_max);
88
89 latbins=(lat_max-lat_min)+1;
90 lonbins=(lon_max-lon_min)+1;
91
92 offsets=malloc((latbins*lonbins+1)*sizeof(index_t));
93
94 latlonbin=0;
95
96 for(i=0;i<nodesx->number;i++)
97 {
98 int32_t latbin=lat_long_to_bin(nodesx->gdata[i]->latitude )-lat_min;
99 int32_t lonbin=lat_long_to_bin(nodesx->gdata[i]->longitude)-lon_min;
100 int llbin=lonbin*latbins+latbin;
101
102 for(;latlonbin<=llbin;latlonbin++)
103 offsets[latlonbin]=i;
104 }
105
106 for(;latlonbin<=(latbins*lonbins);latlonbin++)
107 offsets[latlonbin]=nodesx->number;
108
109 /* Fill in a Nodes structure with the offset of the real data in the file after
110 the Node structure itself. */
111
112 nodes->number=nodesx->number;
113
114 nodes->latbins=latbins;
115 nodes->lonbins=lonbins;
116
117 nodes->latzero=lat_min;
118 nodes->lonzero=lon_min;
119
120 nodes->data=NULL;
121 nodes->offsets=(void*)sizeof(Nodes);
122 nodes->nodes=(void*)sizeof(Nodes)+(latbins*lonbins+1)*sizeof(index_t);
123
124 /* Write out the Nodes structure and then the real data. */
125
126 fd=OpenFile(filename);
127
128 WriteFile(fd,nodes,sizeof(Nodes));
129
130 WriteFile(fd,offsets,(latbins*lonbins+1)*sizeof(index_t));
131
132 for(i=0;i<nodesx->number;i++)
133 WriteFile(fd,&nodesx->gdata[i]->node,sizeof(Node));
134
135 CloseFile(fd);
136
137 /* Free the fake Nodes */
138
139 free(nodes);
140 free(offsets);
141 }
142
143
144 /*++++++++++++++++++++++++++++++++++++++
145 Find a particular node.
146
147 NodeX *FindNodeX Returns the extended node with the specified id.
148
149 NodesX* nodesx The set of nodes to process.
150
151 node_t id The node id to look for.
152 ++++++++++++++++++++++++++++++++++++++*/
153
154 NodeX *FindNodeX(NodesX* nodesx,node_t id)
155 {
156 int start=0;
157 int end=nodesx->number-1;
158 int mid;
159
160 assert(nodesx->sorted); /* Must be sorted */
161
162 /* Binary search - search key exact match only is required.
163 *
164 * # <- start | Check mid and move start or end if it doesn't match
165 * # |
166 * # | Since an exact match is wanted we can set end=mid-1
167 * # <- mid | or start=mid+1 because we know that mid doesn't match.
168 * # |
169 * # | Eventually either end=start or end=start+1 and one of
170 * # <- end | start or end is the wanted one.
171 */
172
173 if(end<start) /* There are no nodes */
174 return(NULL);
175 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
176 return(NULL);
177 else if(id>nodesx->idata[end]->id) /* Check key is not after end */
178 return(NULL);
179 else
180 {
181 do
182 {
183 mid=(start+end)/2; /* Choose mid point */
184
185 if(nodesx->idata[mid]->id<id) /* Mid point is too low */
186 start=mid+1;
187 else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
188 end=mid-1;
189 else /* Mid point is correct */
190 return(nodesx->idata[mid]);
191 }
192 while((end-start)>1);
193
194 if(nodesx->idata[start]->id==id) /* Start is correct */
195 return(nodesx->idata[start]);
196
197 if(nodesx->idata[end]->id==id) /* End is correct */
198 return(nodesx->idata[end]);
199 }
200
201 return(NULL);
202 }
203
204
205 /*++++++++++++++++++++++++++++++++++++++
206 Append a node to a newly created node list (unsorted).
207
208 Node *AppendNode Return a pointer to the new node.
209
210 NodesX* nodesx The set of nodes to process.
211
212 node_t id The node identification.
213
214 float latitude The latitude of the node.
215
216 float longitude The longitude of the node.
217 ++++++++++++++++++++++++++++++++++++++*/
218
219 Node *AppendNode(NodesX* nodesx,node_t id,float latitude,float longitude)
220 {
221 /* Check that the array has enough space. */
222
223 if(nodesx->xnumber==nodesx->alloced)
224 {
225 nodesx->alloced+=INCREMENT_NODES;
226
227 nodesx->xdata=(NodeX*)realloc((void*)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
228 }
229
230 /* Insert the node */
231
232 nodesx->xdata[nodesx->xnumber].id=id;
233 nodesx->xdata[nodesx->xnumber].super=0;
234 nodesx->xdata[nodesx->xnumber].latitude=latitude;
235 nodesx->xdata[nodesx->xnumber].longitude=longitude;
236
237 memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));
238
239 nodesx->xnumber++;
240
241 nodesx->sorted=0;
242
243 return(&nodesx->xdata[nodesx->xnumber-1].node);
244 }
245
246
247 /*++++++++++++++++++++++++++++++++++++++
248 Sort the node list.
249
250 NodesX* nodesx The set of nodes to process.
251 ++++++++++++++++++++++++++++++++++++++*/
252
253 void SortNodeList(NodesX* nodesx)
254 {
255 int i;
256
257 /* Allocate the arrays of pointers */
258
259 if(nodesx->sorted)
260 {
261 nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumber*sizeof(NodeX*));
262 nodesx->idata=realloc(nodesx->idata,nodesx->xnumber*sizeof(NodeX*));
263 }
264 else
265 {
266 nodesx->gdata=malloc(nodesx->xnumber*sizeof(NodeX*));
267 nodesx->idata=malloc(nodesx->xnumber*sizeof(NodeX*));
268 }
269
270 nodesx->number=0;
271
272 for(i=0;i<nodesx->xnumber;i++)
273 if(nodesx->xdata[i].id!=~0)
274 {
275 nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
276 nodesx->idata[nodesx->number]=&nodesx->xdata[i];
277 nodesx->number++;
278 }
279
280 /* Sort geographically */
281
282 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);
283
284 nodesx->lat_min=2;
285 nodesx->lat_max=-2;
286 nodesx->lon_min=4;
287 nodesx->lon_max=-4;
288
289 for(i=0;i<nodesx->number;i++)
290 {
291 int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
292 int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);
293
294 nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
295 nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;
296
297 if(nodesx->gdata[i]->latitude<nodesx->lat_min)
298 nodesx->lat_min=nodesx->gdata[i]->latitude;
299 if(nodesx->gdata[i]->latitude>nodesx->lat_max)
300 nodesx->lat_max=nodesx->gdata[i]->latitude;
301 if(nodesx->gdata[i]->longitude<nodesx->lon_min)
302 nodesx->lon_min=nodesx->gdata[i]->longitude;
303 if(nodesx->gdata[i]->longitude>nodesx->lon_max)
304 nodesx->lon_max=nodesx->gdata[i]->longitude;
305 }
306
307 /* Sort by id */
308
309 qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);
310
311 nodesx->sorted=1;
312 }
313
314
315 /*++++++++++++++++++++++++++++++++++++++
316 Sort the nodes into id order.
317
318 int sort_by_id Returns the comparison of the id fields.
319
320 NodeX **a The first Node.
321
322 NodeX **b The second Node.
323 ++++++++++++++++++++++++++++++++++++++*/
324
325 static int sort_by_id(NodeX **a,NodeX **b)
326 {
327 node_t a_id=(*a)->id;
328 node_t b_id=(*b)->id;
329
330 if(a_id<b_id)
331 return(-1);
332 else
333 return(1);
334 }
335
336
337 /*++++++++++++++++++++++++++++++++++++++
338 Sort the nodes into latitude and longitude order.
339
340 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
341
342 NodeX **a The first Node.
343
344 NodeX **b The second Node.
345 ++++++++++++++++++++++++++++++++++++++*/
346
347 static int sort_by_lat_long(NodeX **a,NodeX **b)
348 {
349 int32_t a_lon=lat_long_to_bin((*a)->longitude);
350 int32_t b_lon=lat_long_to_bin((*b)->longitude);
351
352 if(a_lon<b_lon)
353 return(-1);
354 else if(a_lon>b_lon)
355 return(1);
356 else
357 {
358 int32_t a_lat=lat_long_to_bin((*a)->latitude);
359 int32_t b_lat=lat_long_to_bin((*b)->latitude);
360
361 if(a_lat<b_lat)
362 return(-1);
363 else if(a_lat>b_lat)
364 return(1);
365 else
366 return(0);
367 }
368 }
369
370
371 /*++++++++++++++++++++++++++++++++++++++
372 Remove any nodes that are not part of a highway.
373
374 NodesX *nodesx The complete node list.
375
376 SegmentsX *segmentsx The list of segments.
377 ++++++++++++++++++++++++++++++++++++++*/
378
379 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
380 {
381 int i;
382 int highway=0,nothighway=0;
383
384 assert(!nodesx->sorted); /* Must not be sorted */
385
386 for(i=0;i<nodesx->xnumber;i++)
387 {
388 if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
389 highway++;
390 else
391 {
392 nodesx->xdata[i].id=~0;
393 nothighway++;
394 }
395
396 if(!((i+1)%10000))
397 {
398 printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
399 fflush(stdout);
400 }
401 }
402
403 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
404 fflush(stdout);
405 }
406
407
408 /*++++++++++++++++++++++++++++++++++++++
409 Mark super nodes.
410
411 NodesX* nodesx The set of nodes to process.
412
413 int iteration The final super-node / super-segment iteration number.
414 ++++++++++++++++++++++++++++++++++++++*/
415
416 void MarkSuperNodes(NodesX *nodesx,int iteration)
417 {
418 int i,nnodes=0;;
419
420 assert(nodesx->sorted); /* Must be sorted */
421
422 for(i=0;i<nodesx->number;i++)
423 {
424 if(nodesx->gdata[i]->super==iteration)
425 {
426 nodesx->gdata[i]->node.firstseg=SEGMENT(~0)|SUPER_FLAG;
427 nnodes++;
428 }
429 else
430 nodesx->gdata[i]->node.firstseg=SEGMENT(~0);
431
432 if(!((i+1)%10000))
433 {
434 printf("\rMarking Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
435 fflush(stdout);
436 }
437 }
438
439 printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
440 fflush(stdout);
441 }
442
443
444 /*++++++++++++++++++++++++++++++++++++++
445 Assign the segment indexes to the nodes.
446
447 NodesX *nodesx The list of nodes to process.
448
449 SegmentsX* segmentsx The set of segments to use.
450 ++++++++++++++++++++++++++++++++++++++*/
451
452 void IndexNodes(NodesX *nodesx,SegmentsX* segmentsx)
453 {
454 int i;
455
456 assert(nodesx->sorted); /* Must be sorted */
457 assert(segmentsx->sorted); /* Must be sorted */
458
459 /* Index the nodes */
460
461 for(i=0;i<segmentsx->number;i++)
462 {
463 NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
464 NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
465
466 /* Check node1 */
467
468 if(SEGMENT(node1->node.firstseg)==SEGMENT(~0))
469 {
470 node1->node.firstseg^=SEGMENT(~0);
471 node1->node.firstseg|=i;
472 }
473 else
474 {
475 SegmentX *segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));
476
477 do
478 {
479 if(segmentx->node1==segmentsx->sdata[i]->node1)
480 {
481 if(SEGMENT(segmentx->segment.next1)==SEGMENT(~0))
482 {
483 segmentx->segment.next1=i;
484 segmentx=NULL;
485 }
486 else
487 segmentx=LookupSegmentX(segmentsx,SEGMENT(segmentx->segment.next1));
488 }
489 else
490 {
491 if(SEGMENT(segmentx->segment.next2)==SEGMENT(~0))
492 {
493 segmentx->segment.next2=i;
494 segmentx=NULL;
495 }
496 else
497 segmentx=LookupSegmentX(segmentsx,SEGMENT(segmentx->segment.next2));
498 }
499 }
500 while(segmentx);
501 }
502
503 /* Check node2 */
504
505 if(SEGMENT(node2->node.firstseg)==SEGMENT(~0))
506 {
507 node2->node.firstseg^=SEGMENT(~0);
508 node2->node.firstseg|=i;
509 }
510 else
511 {
512 SegmentX *segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));
513
514 do
515 {
516 if(segmentx->node1==segmentsx->sdata[i]->node2)
517 {
518 if(SEGMENT(segmentx->segment.next1)==SEGMENT(~0))
519 {
520 segmentx->segment.next1=i;
521 segmentx=NULL;
522 }
523 else
524 segmentx=LookupSegmentX(segmentsx,SEGMENT(segmentx->segment.next1));
525 }
526 else
527 {
528 if(SEGMENT(segmentx->segment.next2)==SEGMENT(~0))
529 {
530 segmentx->segment.next2=i;
531 segmentx=NULL;
532 }
533 else
534 segmentx=LookupSegmentX(segmentsx,SEGMENT(segmentx->segment.next2));
535 }
536 }
537 while(segmentx);
538 }
539
540 if(!((i+1)%10000))
541 {
542 printf("\rIndexing Segments: Segments=%d",i+1);
543 fflush(stdout);
544 }
545 }
546
547 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
548 fflush(stdout);
549 }

Properties

Name Value
cvs:description Extended nodes functions.
Index: This Site Routino Software Download Source Code Documentation XML Files Links
Index: View SVN Development Recent changes Development (destination-access branch) Version 3.4.2 (destination-access branch) Version 3.4.2 Version 3.4.1 (destination-access branch) Version 3.4.1 Version 3.4 (destination-access branch) Version 3.4 Version 3.3.3 (destination-access branch) Version 3.3.3 Version 3.3.2 (destination-access branch) Version 3.3.2 Version 3.3.1 (destination-access branch) Version 3.3.1 Version 3.3 (destination-access branch) Version 3.3 Version 3.2 Version 3.1.1 Version 3.1 Version 3.0 Version 2.7.3 Version 2.7.2 Version 2.7.1 Version 2.7 Version 2.6 Version 2.5.1 Version 2.5 Version 2.4.1 Version 2.4 Version 2.3.2 Version 2.3.1 Version 2.3 Version 2.2 Version 2.1.2 Version 2.1.1 Version 2.1 Version 2.0.3 Version 2.0.2 Version 2.0.1 Version 2.0 Version 1.5.1 Version 1.5 Version 1.4.1 Version 1.4 Version 1.3 Version 1.2 Version 1.1 Version 1.0
Powered by ViewVC 1.3.0-dev ViewVC Help
© Andrew M. Bishop = < amb @ ... >
Root