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

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