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 133 - (show annotations) (download) (as text)
Sat Feb 28 19:01:43 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 13703 byte(s) 
Round the node location to avoid if falling into the wrong bin.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.6 2009-02-28 19:01:43 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 {
134 WriteFile(fd,&nodesx->gdata[i]->node,sizeof(Node));
135
136 if(!((i+1)%10000))
137 {
138 printf("\rWriting Nodes: Nodes=%d",i+1);
139 fflush(stdout);
140 }
141 }
142
143 printf("\rWrote Nodes: Nodes=%d \n",nodesx->number);
144 fflush(stdout);
145
146 CloseFile(fd);
147
148 /* Free the fake Nodes */
149
150 free(nodes);
151 free(offsets);
152 }
153
154
155 /*++++++++++++++++++++++++++++++++++++++
156 Find a particular node.
157
158 NodeX *FindNodeX Returns the extended node with the specified id.
159
160 NodesX* nodesx The set of nodes to process.
161
162 node_t id The node id to look for.
163 ++++++++++++++++++++++++++++++++++++++*/
164
165 NodeX *FindNodeX(NodesX* nodesx,node_t id)
166 {
167 int start=0;
168 int end=nodesx->number-1;
169 int mid;
170
171 assert(nodesx->sorted); /* Must be sorted */
172
173 /* Binary search - search key exact match only is required.
174 *
175 * # <- start | Check mid and move start or end if it doesn't match
176 * # |
177 * # | Since an exact match is wanted we can set end=mid-1
178 * # <- mid | or start=mid+1 because we know that mid doesn't match.
179 * # |
180 * # | Eventually either end=start or end=start+1 and one of
181 * # <- end | start or end is the wanted one.
182 */
183
184 if(end<start) /* There are no nodes */
185 return(NULL);
186 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
187 return(NULL);
188 else if(id>nodesx->idata[end]->id) /* Check key is not after end */
189 return(NULL);
190 else
191 {
192 do
193 {
194 mid=(start+end)/2; /* Choose mid point */
195
196 if(nodesx->idata[mid]->id<id) /* Mid point is too low */
197 start=mid+1;
198 else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
199 end=mid-1;
200 else /* Mid point is correct */
201 return(nodesx->idata[mid]);
202 }
203 while((end-start)>1);
204
205 if(nodesx->idata[start]->id==id) /* Start is correct */
206 return(nodesx->idata[start]);
207
208 if(nodesx->idata[end]->id==id) /* End is correct */
209 return(nodesx->idata[end]);
210 }
211
212 return(NULL);
213 }
214
215
216 /*++++++++++++++++++++++++++++++++++++++
217 Append a node to a newly created node list (unsorted).
218
219 Node *AppendNode Return a pointer to the new node.
220
221 NodesX* nodesx The set of nodes to process.
222
223 node_t id The node identification.
224
225 float latitude The latitude of the node.
226
227 float longitude The longitude of the node.
228 ++++++++++++++++++++++++++++++++++++++*/
229
230 Node *AppendNode(NodesX* nodesx,node_t id,float latitude,float longitude)
231 {
232 /* Check that the array has enough space. */
233
234 if(nodesx->xnumber==nodesx->alloced)
235 {
236 nodesx->alloced+=INCREMENT_NODES;
237
238 nodesx->xdata=(NodeX*)realloc((void*)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
239 }
240
241 /* Insert the node */
242
243 nodesx->xdata[nodesx->xnumber].id=id;
244 nodesx->xdata[nodesx->xnumber].super=0;
245 nodesx->xdata[nodesx->xnumber].latitude =floorf(latitude *LAT_LONG_SCALE)/LAT_LONG_SCALE;
246 nodesx->xdata[nodesx->xnumber].longitude=floorf(longitude*LAT_LONG_SCALE)/LAT_LONG_SCALE;
247
248 memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));
249
250 nodesx->xnumber++;
251
252 nodesx->sorted=0;
253
254 return(&nodesx->xdata[nodesx->xnumber-1].node);
255 }
256
257
258 /*++++++++++++++++++++++++++++++++++++++
259 Sort the node list.
260
261 NodesX* nodesx The set of nodes to process.
262 ++++++++++++++++++++++++++++++++++++++*/
263
264 void SortNodeList(NodesX* nodesx)
265 {
266 int i;
267
268 printf("Sorting Nodes"); fflush(stdout);
269
270 /* Allocate the arrays of pointers */
271
272 if(nodesx->sorted)
273 {
274 nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumber*sizeof(NodeX*));
275 nodesx->idata=realloc(nodesx->idata,nodesx->xnumber*sizeof(NodeX*));
276 }
277 else
278 {
279 nodesx->gdata=malloc(nodesx->xnumber*sizeof(NodeX*));
280 nodesx->idata=malloc(nodesx->xnumber*sizeof(NodeX*));
281 }
282
283 nodesx->number=0;
284
285 for(i=0;i<nodesx->xnumber;i++)
286 if(nodesx->xdata[i].id!=~0)
287 {
288 nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
289 nodesx->idata[nodesx->number]=&nodesx->xdata[i];
290 nodesx->number++;
291 }
292
293 /* Sort geographically */
294
295 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);
296
297 nodesx->lat_min=2;
298 nodesx->lat_max=-2;
299 nodesx->lon_min=4;
300 nodesx->lon_max=-4;
301
302 for(i=0;i<nodesx->number;i++)
303 {
304 int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
305 int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);
306
307 nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
308 nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;
309
310 if(nodesx->gdata[i]->latitude<nodesx->lat_min)
311 nodesx->lat_min=nodesx->gdata[i]->latitude;
312 if(nodesx->gdata[i]->latitude>nodesx->lat_max)
313 nodesx->lat_max=nodesx->gdata[i]->latitude;
314 if(nodesx->gdata[i]->longitude<nodesx->lon_min)
315 nodesx->lon_min=nodesx->gdata[i]->longitude;
316 if(nodesx->gdata[i]->longitude>nodesx->lon_max)
317 nodesx->lon_max=nodesx->gdata[i]->longitude;
318 }
319
320 /* Sort by id */
321
322 qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);
323
324 nodesx->sorted=1;
325
326 printf("\rSorted Nodes \n"); fflush(stdout);
327 }
328
329
330 /*++++++++++++++++++++++++++++++++++++++
331 Sort the nodes into id order.
332
333 int sort_by_id Returns the comparison of the id fields.
334
335 NodeX **a The first Node.
336
337 NodeX **b The second Node.
338 ++++++++++++++++++++++++++++++++++++++*/
339
340 static int sort_by_id(NodeX **a,NodeX **b)
341 {
342 node_t a_id=(*a)->id;
343 node_t b_id=(*b)->id;
344
345 if(a_id<b_id)
346 return(-1);
347 else
348 return(1);
349 }
350
351
352 /*++++++++++++++++++++++++++++++++++++++
353 Sort the nodes into latitude and longitude order.
354
355 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
356
357 NodeX **a The first Node.
358
359 NodeX **b The second Node.
360 ++++++++++++++++++++++++++++++++++++++*/
361
362 static int sort_by_lat_long(NodeX **a,NodeX **b)
363 {
364 int32_t a_lon=lat_long_to_bin((*a)->longitude);
365 int32_t b_lon=lat_long_to_bin((*b)->longitude);
366
367 if(a_lon<b_lon)
368 return(-1);
369 else if(a_lon>b_lon)
370 return(1);
371 else
372 {
373 int32_t a_lat=lat_long_to_bin((*a)->latitude);
374 int32_t b_lat=lat_long_to_bin((*b)->latitude);
375
376 if(a_lat<b_lat)
377 return(-1);
378 else if(a_lat>b_lat)
379 return(1);
380 else
381 return(0);
382 }
383 }
384
385
386 /*++++++++++++++++++++++++++++++++++++++
387 Remove any nodes that are not part of a highway.
388
389 NodesX *nodesx The complete node list.
390
391 SegmentsX *segmentsx The list of segments.
392 ++++++++++++++++++++++++++++++++++++++*/
393
394 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
395 {
396 int i;
397 int highway=0,nothighway=0;
398
399 assert(!nodesx->sorted); /* Must not be sorted */
400
401 for(i=0;i<nodesx->xnumber;i++)
402 {
403 if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
404 highway++;
405 else
406 {
407 nodesx->xdata[i].id=~0;
408 nothighway++;
409 }
410
411 if(!((i+1)%10000))
412 {
413 printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
414 fflush(stdout);
415 }
416 }
417
418 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
419 fflush(stdout);
420 }
421
422
423 /*++++++++++++++++++++++++++++++++++++++
424 Mark super nodes.
425
426 NodesX* nodesx The set of nodes to process.
427
428 int iteration The final super-node / super-segment iteration number.
429 ++++++++++++++++++++++++++++++++++++++*/
430
431 void MarkSuperNodes(NodesX *nodesx,int iteration)
432 {
433 int i,nnodes=0;;
434
435 assert(nodesx->sorted); /* Must be sorted */
436
437 for(i=0;i<nodesx->number;i++)
438 {
439 if(nodesx->gdata[i]->super==iteration)
440 {
441 nodesx->gdata[i]->node.firstseg=SEGMENT(~0)|SUPER_FLAG;
442 nnodes++;
443 }
444 else
445 nodesx->gdata[i]->node.firstseg=SEGMENT(~0);
446
447 if(!((i+1)%10000))
448 {
449 printf("\rMarking Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
450 fflush(stdout);
451 }
452 }
453
454 printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
455 fflush(stdout);
456 }
457
458
459 /*++++++++++++++++++++++++++++++++++++++
460 Assign the segment indexes to the nodes.
461
462 NodesX *nodesx The list of nodes to process.
463
464 SegmentsX* segmentsx The set of segments to use.
465 ++++++++++++++++++++++++++++++++++++++*/
466
467 void IndexNodes(NodesX *nodesx,SegmentsX* segmentsx)
468 {
469 int i;
470
471 assert(nodesx->sorted); /* Must be sorted */
472 assert(segmentsx->sorted); /* Must be sorted */
473
474 /* Index the nodes */
475
476 for(i=0;i<segmentsx->number;i++)
477 {
478 NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
479 NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
480
481 /* Check node1 */
482
483 if(SEGMENT(node1->node.firstseg)==SEGMENT(~0))
484 {
485 node1->node.firstseg^=SEGMENT(~0);
486 node1->node.firstseg|=i;
487 }
488 else
489 {
490 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));
491
492 do
493 {
494 if((*segmentx)->node1==segmentsx->sdata[i]->node1)
495 {
496 segmentx++;
497
498 if((*segmentx)->node1!=segmentsx->sdata[i]->node1 || (segmentx-segmentsx->sdata)>=segmentsx->number)
499 segmentx=NULL;
500 }
501 else
502 {
503 if((*segmentx)->segment.next2==~0)
504 {
505 (*segmentx)->segment.next2=i;
506 segmentx=NULL;
507 }
508 else
509 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
510 }
511 }
512 while(segmentx);
513 }
514
515 /* Check node2 */
516
517 if(SEGMENT(node2->node.firstseg)==SEGMENT(~0))
518 {
519 node2->node.firstseg^=SEGMENT(~0);
520 node2->node.firstseg|=i;
521 }
522 else
523 {
524 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));
525
526 do
527 {
528 if((*segmentx)->node1==segmentsx->sdata[i]->node2)
529 {
530 segmentx++;
531
532 if((*segmentx)->node1!=segmentsx->sdata[i]->node2 || (segmentx-segmentsx->sdata)>=segmentsx->number)
533 segmentx=NULL;
534 }
535 else
536 {
537 if((*segmentx)->segment.next2==~0)
538 {
539 (*segmentx)->segment.next2=i;
540 segmentx=NULL;
541 }
542 else
543 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
544 }
545 }
546 while(segmentx);
547 }
548
549 if(!((i+1)%10000))
550 {
551 printf("\rIndexing Segments: Segments=%d",i+1);
552 fflush(stdout);
553 }
554 }
555
556 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
557 fflush(stdout);
558 }

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