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