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