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

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