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 246 - (show annotations) (download) (as text)
Tue Aug 25 18:00:05 2009 UTC (15 years, 7 months ago) by amb
File MIME type: text/x-csrc
File size: 17156 byte(s) 
Fix for assert statement.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.30 2009-08-25 18:00:05 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 <stdio.h>
28
29 #include "types.h"
30 #include "functions.h"
31 #include "nodesx.h"
32 #include "segmentsx.h"
33 #include "waysx.h"
34 #include "segments.h"
35 #include "nodes.h"
36
37
38 /* Constants */
39
40 /*+ The array size increment for NodesX (UK is ~10.3M raw nodes, this is ~78 increments). +*/
41 #define INCREMENT_NODESX (128*1024)
42
43
44 /* Functions */
45
46 static int sort_by_id(NodeX **a,NodeX **b);
47 static int sort_by_lat_long(NodeX **a,NodeX **b);
48
49
50 /*++++++++++++++++++++++++++++++++++++++
51 Allocate a new node list.
52
53 NodesX *NewNodeList Returns the node list.
54 ++++++++++++++++++++++++++++++++++++++*/
55
56 NodesX *NewNodeList(void)
57 {
58 NodesX *nodesx;
59
60 nodesx=(NodesX*)calloc(1,sizeof(NodesX));
61
62 assert(nodesx); /* Check calloc() worked */
63
64 nodesx->row=-1;
65
66 return(nodesx);
67 }
68
69
70 /*++++++++++++++++++++++++++++++++++++++
71 Free a node list.
72
73 NodesX *nodesx The list to be freed.
74 ++++++++++++++++++++++++++++++++++++++*/
75
76 void FreeNodeList(NodesX *nodesx)
77 {
78 if(nodesx->xdata)
79 {
80 int i;
81 for(i=0;i<=nodesx->row;i++)
82 free(nodesx->xdata[i]);
83 free(nodesx->xdata);
84 }
85
86 if(nodesx->gdata)
87 free(nodesx->gdata);
88 if(nodesx->idata)
89 free(nodesx->idata);
90
91 if(nodesx->ndata)
92 free(nodesx->ndata);
93
94 free(nodesx);
95 }
96
97
98 /*++++++++++++++++++++++++++++++++++++++
99 Save the node list to a file.
100
101 NodesX* nodesx The set of nodes to save.
102
103 const char *filename The name of the file to save.
104 ++++++++++++++++++++++++++++++++++++++*/
105
106 void SaveNodeList(NodesX* nodesx,const char *filename)
107 {
108 index_t i;
109 int fd;
110 Nodes *nodes;
111 index_t *offsets;
112 ll_bin_t lat_min_bin,lat_max_bin,lon_min_bin,lon_max_bin;
113 latlong_t lat_min,lat_max,lon_min,lon_max;
114 int latbins,lonbins,latlonbin;
115 int super_number=0;
116
117 assert(nodesx->gdata); /* Must have gdata filled in => sorted geographically */
118 assert(nodesx->ndata); /* Must have ndata filled in => real nodes exist */
119 assert(nodesx->idata); /* Must have idata filled in => sorted by id */
120
121 printf("Writing Nodes: Nodes=0");
122 fflush(stdout);
123
124 /* Work out the range of data */
125
126 lat_min=radians_to_latlong( 2);
127 lat_max=radians_to_latlong(-2);
128 lon_min=radians_to_latlong( 4);
129 lon_max=radians_to_latlong(-4);
130
131 for(i=0;i<nodesx->number;i++)
132 {
133 if(nodesx->idata[i]->latitude<lat_min)
134 lat_min=nodesx->idata[i]->latitude;
135 if(nodesx->idata[i]->latitude>lat_max)
136 lat_max=nodesx->idata[i]->latitude;
137 if(nodesx->idata[i]->longitude<lon_min)
138 lon_min=nodesx->idata[i]->longitude;
139 if(nodesx->idata[i]->longitude>lon_max)
140 lon_max=nodesx->idata[i]->longitude;
141
142 if(nodesx->ndata[i].firstseg&NODE_SUPER)
143 super_number++;
144 }
145
146 /* Work out the offsets */
147
148 lat_min_bin=latlong_to_bin(lat_min);
149 lon_min_bin=latlong_to_bin(lon_min);
150 lat_max_bin=latlong_to_bin(lat_max);
151 lon_max_bin=latlong_to_bin(lon_max);
152
153 latbins=(lat_max_bin-lat_min_bin)+1;
154 lonbins=(lon_max_bin-lon_min_bin)+1;
155
156 offsets=(index_t*)malloc((latbins*lonbins+1)*sizeof(index_t));
157
158 latlonbin=0;
159
160 for(i=0;i<nodesx->number;i++)
161 {
162 ll_bin_t latbin=latlong_to_bin(nodesx->gdata[i]->latitude )-lat_min_bin;
163 ll_bin_t lonbin=latlong_to_bin(nodesx->gdata[i]->longitude)-lon_min_bin;
164 int llbin=lonbin*latbins+latbin;
165
166 for(;latlonbin<=llbin;latlonbin++)
167 offsets[latlonbin]=i;
168 }
169
170 for(;latlonbin<=(latbins*lonbins);latlonbin++)
171 offsets[latlonbin]=nodesx->number;
172
173 /* Fill in a Nodes structure with the offset of the real data in the file after
174 the Node structure itself. */
175
176 nodes=calloc(1,sizeof(Nodes));
177
178 assert(nodes); /* Check calloc() worked */
179
180 nodes->number=nodesx->number;
181 nodes->snumber=super_number;
182
183 nodes->latbins=latbins;
184 nodes->lonbins=lonbins;
185
186 nodes->latzero=lat_min_bin;
187 nodes->lonzero=lon_min_bin;
188
189 nodes->data=NULL;
190
191 nodes->offsets=(void*)sizeof(Nodes);
192 nodes->nodes=(void*)(sizeof(Nodes)+(latbins*lonbins+1)*sizeof(index_t));
193
194 /* Write out the Nodes structure and then the real data. */
195
196 fd=OpenFile(filename);
197
198 WriteFile(fd,nodes,sizeof(Nodes));
199
200 WriteFile(fd,offsets,(latbins*lonbins+1)*sizeof(index_t));
201
202 for(i=0;i<nodes->number;i++)
203 {
204 NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
205 Node *node =&nodesx->ndata[nodex-nodesx->idata];
206
207 WriteFile(fd,node,sizeof(Node));
208
209 if(!((i+1)%10000))
210 {
211 printf("\rWriting Nodes: Nodes=%d",i+1);
212 fflush(stdout);
213 }
214 }
215
216 printf("\rWrote Nodes: Nodes=%d \n",nodes->number);
217 fflush(stdout);
218
219 CloseFile(fd);
220
221 /* Free the fake Nodes */
222
223 free(nodes);
224 free(offsets);
225 }
226
227
228 /*++++++++++++++++++++++++++++++++++++++
229 Find a particular node.
230
231 NodeX **FindNodeX Returns a pointer to the extended node with the specified id.
232
233 NodesX* nodesx The set of nodes to process.
234
235 node_t id The node id to look for.
236 ++++++++++++++++++++++++++++++++++++++*/
237
238 NodeX **FindNodeX(NodesX* nodesx,node_t id)
239 {
240 int start=0;
241 int end=nodesx->number-1;
242 int mid;
243
244 assert(nodesx->idata); /* Must have idata filled in => sorted by id */
245
246 /* Binary search - search key exact match only is required.
247 *
248 * # <- start | Check mid and move start or end if it doesn't match
249 * # |
250 * # | Since an exact match is wanted we can set end=mid-1
251 * # <- mid | or start=mid+1 because we know that mid doesn't match.
252 * # |
253 * # | Eventually either end=start or end=start+1 and one of
254 * # <- end | start or end is the wanted one.
255 */
256
257 if(end<start) /* There are no nodes */
258 return(NULL);
259 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
260 return(NULL);
261 else if(id>nodesx->idata[end]->id) /* Check key is not after end */
262 return(NULL);
263 else
264 {
265 do
266 {
267 mid=(start+end)/2; /* Choose mid point */
268
269 if(nodesx->idata[mid]->id<id) /* Mid point is too low */
270 start=mid+1;
271 else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
272 end=mid-1;
273 else /* Mid point is correct */
274 return(&nodesx->idata[mid]);
275 }
276 while((end-start)>1);
277
278 if(nodesx->idata[start]->id==id) /* Start is correct */
279 return(&nodesx->idata[start]);
280
281 if(nodesx->idata[end]->id==id) /* End is correct */
282 return(&nodesx->idata[end]);
283 }
284
285 return(NULL);
286 }
287
288
289 /*++++++++++++++++++++++++++++++++++++++
290 Append a node to a newly created node list (unsorted).
291
292 NodesX* nodesx The set of nodes to process.
293
294 node_t id The node identification.
295
296 double latitude The latitude of the node.
297
298 double longitude The longitude of the node.
299 ++++++++++++++++++++++++++++++++++++++*/
300
301 void AppendNode(NodesX* nodesx,node_t id,double latitude,double longitude)
302 {
303 assert(!nodesx->idata); /* Must not have idata filled in => unsorted */
304
305 /* Check that the array has enough space. */
306
307 if(nodesx->row==-1 || nodesx->col==INCREMENT_NODESX)
308 {
309 nodesx->row++;
310 nodesx->col=0;
311
312 if((nodesx->row%16)==0)
313 {
314 nodesx->xdata=(NodeX**)realloc((void*)nodesx->xdata,(nodesx->row+16)*sizeof(NodeX*));
315
316 assert(nodesx->xdata); /* Check realloc() worked */
317 }
318
319 nodesx->xdata[nodesx->row]=(NodeX*)malloc(INCREMENT_NODESX*sizeof(NodeX));
320
321 assert(nodesx->xdata[nodesx->row]); /* Check malloc() worked */
322 }
323
324 /* Insert the node */
325
326 nodesx->xdata[nodesx->row][nodesx->col].id=id;
327 nodesx->xdata[nodesx->row][nodesx->col].super=0;
328 nodesx->xdata[nodesx->row][nodesx->col].latitude =radians_to_latlong(latitude);
329 nodesx->xdata[nodesx->row][nodesx->col].longitude=radians_to_latlong(longitude);
330
331 nodesx->col++;
332 }
333
334
335 /*++++++++++++++++++++++++++++++++++++++
336 Sort the node list.
337
338 NodesX* nodesx The set of nodes to process.
339 ++++++++++++++++++++++++++++++++++++++*/
340
341 void SortNodeList(NodesX* nodesx)
342 {
343 index_t i;
344 int duplicate;
345
346 assert(nodesx->xdata); /* Must have xdata filled in => data exists */
347
348 printf("Sorting Nodes");
349 fflush(stdout);
350
351 /* Allocate the array of pointers and sort them */
352
353 nodesx->idata=(NodeX**)realloc(nodesx->idata,(nodesx->row*INCREMENT_NODESX+nodesx->col)*sizeof(NodeX*));
354
355 assert(nodesx->idata); /* Check realloc() worked */
356
357 do
358 {
359 nodesx->number=0;
360
361 for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
362 if(nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id!=NO_NODE)
363 {
364 nodesx->idata[nodesx->number]=&nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX];
365 nodesx->number++;
366 }
367
368 qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);
369
370 duplicate=0;
371
372 for(i=1;i<nodesx->number;i++)
373 {
374 if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
375 nodesx->idata[i]->id!=NO_NODE)
376 {
377 nodesx->idata[i-1]->id=NO_NODE;
378 duplicate++;
379 }
380 }
381
382 if(duplicate)
383 {
384 printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate);
385 fflush(stdout);
386 }
387 }
388 while(duplicate);
389
390 printf("\rSorted Nodes \n");
391 fflush(stdout);
392 }
393
394
395 /*++++++++++++++++++++++++++++++++++++++
396 Sort the nodes into id order.
397
398 int sort_by_id Returns the comparison of the id fields.
399
400 NodeX **a The first Node.
401
402 NodeX **b The second Node.
403 ++++++++++++++++++++++++++++++++++++++*/
404
405 static int sort_by_id(NodeX **a,NodeX **b)
406 {
407 node_t a_id=(*a)->id;
408 node_t b_id=(*b)->id;
409
410 if(a_id<b_id)
411 return(-1);
412 else if(a_id>b_id)
413 return(1);
414 else
415 return(0);
416 }
417
418
419 /*++++++++++++++++++++++++++++++++++++++
420 Sort the node list geographically.
421
422 NodesX* nodesx The set of nodes to process.
423 ++++++++++++++++++++++++++++++++++++++*/
424
425 void SortNodeListGeographically(NodesX* nodesx)
426 {
427 index_t i;
428
429 assert(nodesx->idata); /* Must have idata filled in => sorted by id */
430 assert(!nodesx->gdata); /* Must not have gdata filled in => unsorted geographically */
431
432 printf("Sorting Nodes Geographically");
433 fflush(stdout);
434
435 /* Allocate the array of pointers and sort them */
436
437 nodesx->gdata=(NodeX**)malloc(nodesx->number*sizeof(NodeX*));
438
439 assert(nodesx->gdata); /* Check malloc() worked */
440
441 for(i=0;i<nodesx->number;i++)
442 nodesx->gdata[i]=nodesx->idata[i];
443
444 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);
445
446 printf("\rSorted Nodes Geographically \n");
447 fflush(stdout);
448 }
449
450
451 /*++++++++++++++++++++++++++++++++++++++
452 Sort the nodes into latitude and longitude order.
453
454 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
455
456 NodeX **a The first Node.
457
458 NodeX **b The second Node.
459 ++++++++++++++++++++++++++++++++++++++*/
460
461 static int sort_by_lat_long(NodeX **a,NodeX **b)
462 {
463 ll_bin_t a_lon=latlong_to_bin((*a)->longitude);
464 ll_bin_t b_lon=latlong_to_bin((*b)->longitude);
465
466 if(a_lon<b_lon)
467 return(-1);
468 else if(a_lon>b_lon)
469 return(1);
470 else
471 {
472 ll_bin_t a_lat=latlong_to_bin((*a)->latitude);
473 ll_bin_t b_lat=latlong_to_bin((*b)->latitude);
474
475 if(a_lat<b_lat)
476 return(-1);
477 else if(a_lat>b_lat)
478 return(1);
479 else
480 return(0);
481 }
482 }
483
484
485 /*++++++++++++++++++++++++++++++++++++++
486 Remove any nodes that are not part of a highway.
487
488 NodesX *nodesx The complete node list.
489
490 SegmentsX *segmentsx The list of segments.
491 ++++++++++++++++++++++++++++++++++++++*/
492
493 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
494 {
495 index_t i;
496 int highway=0,nothighway=0;
497
498 assert(nodesx->xdata); /* Must have xdata filled in => data exists */
499
500 printf("Checking: Nodes=0");
501 fflush(stdout);
502
503 for(i=0;i<(nodesx->row*INCREMENT_NODESX+nodesx->col);i++)
504 {
505 if(FindFirstSegmentX(segmentsx,nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id))
506 highway++;
507 else
508 {
509 nodesx->xdata[i/INCREMENT_NODESX][i%INCREMENT_NODESX].id=NO_NODE;
510 nothighway++;
511 }
512
513 if(!((i+1)%10000))
514 {
515 printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
516 fflush(stdout);
517 }
518 }
519
520 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",i,highway,nothighway);
521 fflush(stdout);
522 }
523
524
525 /*++++++++++++++++++++++++++++++++++++++
526 Create the real node data.
527
528 NodesX *nodesx The set of nodes to use.
529
530 int iteration The final super-node iteration.
531 ++++++++++++++++++++++++++++++++++++++*/
532
533 void CreateRealNodes(NodesX *nodesx,int iteration)
534 {
535 index_t i;
536
537 assert(nodesx->idata); /* Must have idata filled in => sorted by id */
538 assert(!nodesx->ndata); /* Must not have ndata filled in => no real nodes */
539
540 printf("Creating Real Nodes: Nodes=0");
541 fflush(stdout);
542
543 /* Allocate the memory */
544
545 nodesx->ndata=(Node*)malloc(nodesx->number*sizeof(Node));
546
547 assert(nodesx->ndata); /* Check malloc() worked */
548
549 /* Loop through and allocate. */
550
551 for(i=0;i<nodesx->number;i++)
552 {
553 nodesx->ndata[i].latoffset=latlong_to_off(nodesx->idata[i]->latitude);
554 nodesx->ndata[i].lonoffset=latlong_to_off(nodesx->idata[i]->longitude);
555
556 nodesx->ndata[i].firstseg=SEGMENT(NO_SEGMENT);
557
558 if(nodesx->idata[i]->super==iteration)
559 nodesx->ndata[i].firstseg|=NODE_SUPER;
560
561 if(!((i+1)%10000))
562 {
563 printf("\rCreating Real Nodes: Nodes=%d",i+1);
564 fflush(stdout);
565 }
566 }
567
568 printf("\rCreating Real Nodes: Nodes=%d \n",nodesx->number);
569 fflush(stdout);
570 }
571
572
573 /*++++++++++++++++++++++++++++++++++++++
574 Assign the segment indexes to the nodes.
575
576 NodesX *nodesx The list of nodes to process.
577
578 SegmentsX* segmentsx The set of segments to use.
579 ++++++++++++++++++++++++++++++++++++++*/
580
581 void IndexNodes(NodesX *nodesx,SegmentsX *segmentsx)
582 {
583 index_t i;
584
585 assert(nodesx->idata); /* Must have idata filled in => sorted */
586 assert(nodesx->ndata); /* Must have ndata filled in => real nodes exist */
587 assert(segmentsx->n1data); /* Must have n1data filled in => sorted */
588 assert(segmentsx->sdata); /* Must have sdata filled in => real segments exist */
589
590 printf("Indexing Segments: Segments=0");
591 fflush(stdout);
592
593 /* Index the nodes */
594
595 for(i=0;i<segmentsx->number;i++)
596 {
597 NodeX **nodex1=FindNodeX(nodesx,segmentsx->n1data[i]->node1);
598 NodeX **nodex2=FindNodeX(nodesx,segmentsx->n1data[i]->node2);
599 Node *node1=&nodesx->ndata[nodex1-nodesx->idata];
600 Node *node2=&nodesx->ndata[nodex2-nodesx->idata];
601
602 /* Check node1 */
603
604 if(SEGMENT(node1->firstseg)==SEGMENT(NO_SEGMENT))
605 {
606 node1->firstseg^=SEGMENT(NO_SEGMENT);
607 node1->firstseg|=i;
608 }
609 else
610 {
611 index_t index=SEGMENT(node1->firstseg);
612
613 do
614 {
615 if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node1)
616 {
617 index++;
618
619 if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node1)
620 break;
621 }
622 else
623 {
624 if(segmentsx->sdata[index].next2==NO_NODE)
625 {
626 segmentsx->sdata[index].next2=i;
627 break;
628 }
629 else
630 index=segmentsx->sdata[index].next2;
631 }
632 }
633 while(1);
634 }
635
636 /* Check node2 */
637
638 if(SEGMENT(node2->firstseg)==SEGMENT(NO_SEGMENT))
639 {
640 node2->firstseg^=SEGMENT(NO_SEGMENT);
641 node2->firstseg|=i;
642 }
643 else
644 {
645 index_t index=SEGMENT(node2->firstseg);
646
647 do
648 {
649 if(segmentsx->n1data[index]->node1==segmentsx->n1data[i]->node2)
650 {
651 index++;
652
653 if(index>=segmentsx->number || segmentsx->n1data[index]->node1!=segmentsx->n1data[i]->node2)
654 break;
655 }
656 else
657 {
658 if(segmentsx->sdata[index].next2==NO_NODE)
659 {
660 segmentsx->sdata[index].next2=i;
661 break;
662 }
663 else
664 index=segmentsx->sdata[index].next2;
665 }
666 }
667 while(1);
668 }
669
670 if(!((i+1)%10000))
671 {
672 printf("\rIndexing Segments: Segments=%d",i+1);
673 fflush(stdout);
674 }
675 }
676
677 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
678 fflush(stdout);
679 }

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