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 151 - (show annotations) (download) (as text)
Wed Apr 8 16:54:34 2009 UTC (15 years, 11 months ago) by amb
File MIME type: text/x-csrc
File size: 14583 byte(s) 
Changed the license to Affero GPLv3.
1 /***************************************
2 $Header: /home/amb/CVS/routino/src/nodesx.c,v 1.8 2009-04-08 16:54:34 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 return(NULL);
196 else if(id<nodesx->idata[start]->id) /* Check key is not before start */
197 return(NULL);
198 else if(id>nodesx->idata[end]->id) /* Check key is not after end */
199 return(NULL);
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 return(NULL);
223 }
224
225
226 /*++++++++++++++++++++++++++++++++++++++
227 Append a node to a newly created node list (unsorted).
228
229 Node *AppendNode Return a pointer to the new node.
230
231 NodesX* nodesx The set of nodes to process.
232
233 node_t id The node identification.
234
235 float latitude The latitude of the node.
236
237 float longitude The longitude of the node.
238 ++++++++++++++++++++++++++++++++++++++*/
239
240 Node *AppendNode(NodesX* nodesx,node_t id,float latitude,float longitude)
241 {
242 /* Check that the array has enough space. */
243
244 if(nodesx->xnumber==nodesx->alloced)
245 {
246 nodesx->alloced+=INCREMENT_NODES;
247
248 nodesx->xdata=(NodeX*)realloc((void*)nodesx->xdata,nodesx->alloced*sizeof(NodeX));
249 }
250
251 /* Insert the node */
252
253 nodesx->xdata[nodesx->xnumber].id=id;
254 nodesx->xdata[nodesx->xnumber].super=0;
255 nodesx->xdata[nodesx->xnumber].latitude =floorf(latitude *LAT_LONG_SCALE)/LAT_LONG_SCALE;
256 nodesx->xdata[nodesx->xnumber].longitude=floorf(longitude*LAT_LONG_SCALE)/LAT_LONG_SCALE;
257
258 memset(&nodesx->xdata[nodesx->xnumber].node,0,sizeof(Node));
259
260 nodesx->xnumber++;
261
262 nodesx->sorted=0;
263
264 return(&nodesx->xdata[nodesx->xnumber-1].node);
265 }
266
267
268 /*++++++++++++++++++++++++++++++++++++++
269 Sort the node list.
270
271 NodesX* nodesx The set of nodes to process.
272 ++++++++++++++++++++++++++++++++++++++*/
273
274 void SortNodeList(NodesX* nodesx)
275 {
276 int i;
277 int duplicate;
278
279 printf("Sorting Nodes"); fflush(stdout);
280
281 /* Allocate the arrays of pointers */
282
283 if(nodesx->sorted)
284 {
285 nodesx->gdata=realloc(nodesx->gdata,nodesx->xnumber*sizeof(NodeX*));
286 nodesx->idata=realloc(nodesx->idata,nodesx->xnumber*sizeof(NodeX*));
287 }
288 else
289 {
290 nodesx->gdata=malloc(nodesx->xnumber*sizeof(NodeX*));
291 nodesx->idata=malloc(nodesx->xnumber*sizeof(NodeX*));
292 }
293
294 sort_again:
295
296 nodesx->number=0;
297
298 for(i=0;i<nodesx->xnumber;i++)
299 if(nodesx->xdata[i].id!=~0)
300 {
301 nodesx->gdata[nodesx->number]=&nodesx->xdata[i];
302 nodesx->idata[nodesx->number]=&nodesx->xdata[i];
303 nodesx->number++;
304 }
305
306 nodesx->sorted=1;
307
308 /* Sort by id */
309
310 qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);
311
312 duplicate=0;
313
314 for(i=1;i<nodesx->number;i++)
315 {
316 if(nodesx->idata[i]->id==nodesx->idata[i-1]->id &&
317 nodesx->idata[i]->id!=~0)
318 {
319 nodesx->idata[i-1]->id=~0;
320 duplicate++;
321 }
322 }
323
324 if(duplicate)
325 {
326 printf(" - %d duplicates found; trying again.\nSorting Nodes",duplicate); fflush(stdout);
327 goto sort_again;
328 }
329
330 /* Sort geographically */
331
332 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_lat_long);
333
334 nodesx->lat_min=2;
335 nodesx->lat_max=-2;
336 nodesx->lon_min=4;
337 nodesx->lon_max=-4;
338
339 for(i=0;i<nodesx->number;i++)
340 {
341 int32_t lat=(int32_t)(nodesx->gdata[i]->latitude *LAT_LONG_SCALE);
342 int32_t lon=(int32_t)(nodesx->gdata[i]->longitude*LAT_LONG_SCALE);
343
344 nodesx->gdata[i]->node.latoffset=lat%LAT_LONG_BIN;
345 nodesx->gdata[i]->node.lonoffset=lon%LAT_LONG_BIN;
346
347 if(nodesx->gdata[i]->latitude<nodesx->lat_min)
348 nodesx->lat_min=nodesx->gdata[i]->latitude;
349 if(nodesx->gdata[i]->latitude>nodesx->lat_max)
350 nodesx->lat_max=nodesx->gdata[i]->latitude;
351 if(nodesx->gdata[i]->longitude<nodesx->lon_min)
352 nodesx->lon_min=nodesx->gdata[i]->longitude;
353 if(nodesx->gdata[i]->longitude>nodesx->lon_max)
354 nodesx->lon_max=nodesx->gdata[i]->longitude;
355 }
356
357 printf("\rSorted Nodes \n"); fflush(stdout);
358 }
359
360
361 /*++++++++++++++++++++++++++++++++++++++
362 Sort the nodes into id order.
363
364 int sort_by_id Returns the comparison of the id fields.
365
366 NodeX **a The first Node.
367
368 NodeX **b The second Node.
369 ++++++++++++++++++++++++++++++++++++++*/
370
371 static int sort_by_id(NodeX **a,NodeX **b)
372 {
373 node_t a_id=(*a)->id;
374 node_t b_id=(*b)->id;
375
376 if(a_id<b_id)
377 return(-1);
378 else if(a_id>b_id)
379 return(1);
380 else
381 return(0);
382 }
383
384
385 /*++++++++++++++++++++++++++++++++++++++
386 Sort the nodes into latitude and longitude order.
387
388 int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
389
390 NodeX **a The first Node.
391
392 NodeX **b The second Node.
393 ++++++++++++++++++++++++++++++++++++++*/
394
395 static int sort_by_lat_long(NodeX **a,NodeX **b)
396 {
397 int32_t a_lon=lat_long_to_bin((*a)->longitude);
398 int32_t b_lon=lat_long_to_bin((*b)->longitude);
399
400 if(a_lon<b_lon)
401 return(-1);
402 else if(a_lon>b_lon)
403 return(1);
404 else
405 {
406 int32_t a_lat=lat_long_to_bin((*a)->latitude);
407 int32_t b_lat=lat_long_to_bin((*b)->latitude);
408
409 if(a_lat<b_lat)
410 return(-1);
411 else if(a_lat>b_lat)
412 return(1);
413 else
414 return(0);
415 }
416 }
417
418
419 /*++++++++++++++++++++++++++++++++++++++
420 Remove any nodes that are not part of a highway.
421
422 NodesX *nodesx The complete node list.
423
424 SegmentsX *segmentsx The list of segments.
425 ++++++++++++++++++++++++++++++++++++++*/
426
427 void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
428 {
429 int i;
430 int highway=0,nothighway=0;
431
432 assert(!nodesx->sorted); /* Must not be sorted */
433
434 for(i=0;i<nodesx->xnumber;i++)
435 {
436 if(FindFirstSegmentX(segmentsx,nodesx->xdata[i].id))
437 highway++;
438 else
439 {
440 nodesx->xdata[i].id=~0;
441 nothighway++;
442 }
443
444 if(!((i+1)%10000))
445 {
446 printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
447 fflush(stdout);
448 }
449 }
450
451 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->xnumber,highway,nothighway);
452 fflush(stdout);
453 }
454
455
456 /*++++++++++++++++++++++++++++++++++++++
457 Mark super nodes.
458
459 NodesX* nodesx The set of nodes to process.
460
461 int iteration The final super-node / super-segment iteration number.
462 ++++++++++++++++++++++++++++++++++++++*/
463
464 void MarkSuperNodes(NodesX *nodesx,int iteration)
465 {
466 int i,nnodes=0;;
467
468 assert(nodesx->sorted); /* Must be sorted */
469
470 for(i=0;i<nodesx->number;i++)
471 {
472 if(nodesx->gdata[i]->super==iteration)
473 {
474 nodesx->gdata[i]->node.firstseg=SEGMENT(~0)|SUPER_FLAG;
475 nnodes++;
476 }
477 else
478 nodesx->gdata[i]->node.firstseg=SEGMENT(~0);
479
480 if(!((i+1)%10000))
481 {
482 printf("\rMarking Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
483 fflush(stdout);
484 }
485 }
486
487 printf("\rMarked Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
488 fflush(stdout);
489 }
490
491
492 /*++++++++++++++++++++++++++++++++++++++
493 Assign the segment indexes to the nodes.
494
495 NodesX *nodesx The list of nodes to process.
496
497 SegmentsX* segmentsx The set of segments to use.
498 ++++++++++++++++++++++++++++++++++++++*/
499
500 void IndexNodes(NodesX *nodesx,SegmentsX* segmentsx)
501 {
502 int i;
503
504 assert(nodesx->sorted); /* Must be sorted */
505 assert(segmentsx->sorted); /* Must be sorted */
506
507 /* Index the nodes */
508
509 for(i=0;i<segmentsx->number;i++)
510 {
511 NodeX *node1=FindNodeX(nodesx,segmentsx->sdata[i]->node1);
512 NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);
513
514 /* Check node1 */
515
516 if(SEGMENT(node1->node.firstseg)==SEGMENT(~0))
517 {
518 node1->node.firstseg^=SEGMENT(~0);
519 node1->node.firstseg|=i;
520 }
521 else
522 {
523 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node1->node.firstseg));
524
525 do
526 {
527 if((*segmentx)->node1==segmentsx->sdata[i]->node1)
528 {
529 segmentx++;
530
531 if((*segmentx)->node1!=segmentsx->sdata[i]->node1 || (segmentx-segmentsx->sdata)>=segmentsx->number)
532 segmentx=NULL;
533 }
534 else
535 {
536 if((*segmentx)->segment.next2==~0)
537 {
538 (*segmentx)->segment.next2=i;
539 segmentx=NULL;
540 }
541 else
542 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
543 }
544 }
545 while(segmentx);
546 }
547
548 /* Check node2 */
549
550 if(SEGMENT(node2->node.firstseg)==SEGMENT(~0))
551 {
552 node2->node.firstseg^=SEGMENT(~0);
553 node2->node.firstseg|=i;
554 }
555 else
556 {
557 SegmentX **segmentx=LookupSegmentX(segmentsx,SEGMENT(node2->node.firstseg));
558
559 do
560 {
561 if((*segmentx)->node1==segmentsx->sdata[i]->node2)
562 {
563 segmentx++;
564
565 if((*segmentx)->node1!=segmentsx->sdata[i]->node2 || (segmentx-segmentsx->sdata)>=segmentsx->number)
566 segmentx=NULL;
567 }
568 else
569 {
570 if((*segmentx)->segment.next2==~0)
571 {
572 (*segmentx)->segment.next2=i;
573 segmentx=NULL;
574 }
575 else
576 segmentx=LookupSegmentX(segmentsx,(*segmentx)->segment.next2);
577 }
578 }
579 while(segmentx);
580 }
581
582 if(!((i+1)%10000))
583 {
584 printf("\rIndexing Segments: Segments=%d",i+1);
585 fflush(stdout);
586 }
587 }
588
589 printf("\rIndexed Segments: Segments=%d \n",segmentsx->number);
590 fflush(stdout);
591 }

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.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