Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Annotation of /trunk/src/prunex.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1122 - (hide annotations) (download) (as text)
Sat Nov 3 08:58:47 2012 UTC (12 years, 4 months ago) by amb
File MIME type: text/x-csrc
File size: 40108 byte(s)
Change the UnmapFile() function to take a pointer to the data instead of the
filename (like the CloseFile() function takes the file descriptor).

1 amb 949 /***************************************
2     Data pruning functions.
3    
4     Part of the Routino routing software.
5     ******************/ /******************
6     This file Copyright 2011-2012 Andrew M. Bishop
7    
8     This program is free software: you can redistribute it and/or modify
9     it under the terms of the GNU Affero General Public License as published by
10     the Free Software Foundation, either version 3 of the License, or
11     (at your option) any later version.
12    
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16     GNU Affero General Public License for more details.
17    
18     You should have received a copy of the GNU Affero General Public License
19     along with this program. If not, see <http://www.gnu.org/licenses/>.
20     ***************************************/
21    
22    
23     #include <stdlib.h>
24     #include <assert.h>
25    
26 amb 964 #include "types.h"
27     #include "segments.h"
28    
29 amb 955 #include "typesx.h"
30 amb 949 #include "nodesx.h"
31     #include "segmentsx.h"
32     #include "waysx.h"
33 amb 955
34 amb 949 #include "prunex.h"
35    
36     #include "files.h"
37     #include "logging.h"
38    
39    
40 amb 1117 /* Global variables */
41    
42     /*+ The command line '--tmpdir' option or its default value. +*/
43     extern char *option_tmpdirname;
44    
45 amb 949 /* Local functions */
46    
47 amb 960 static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx);
48 amb 949 static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2);
49    
50 amb 970 static void unlink_segment_node1_refs(SegmentsX *segmentsx,SegmentX *segmentx);
51     static void unlink_segment_node2_refs(SegmentsX *segmentsx,SegmentX *segmentx);
52 amb 949
53 amb 966 static double distance(double lat1,double lon1,double lat2,double lon2);
54 amb 949
55 amb 966
56 amb 949 /*++++++++++++++++++++++++++++++++++++++
57     Initialise the data structures needed for pruning.
58    
59     NodesX *nodesx The set of nodes to use.
60    
61     SegmentsX *segmentsx The set of segments to use.
62    
63     WaysX *waysx The set of ways to use.
64     ++++++++++++++++++++++++++++++++++++++*/
65    
66     void StartPruning(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
67     {
68     SegmentX segmentx;
69     index_t index=0,lastnode1=NO_NODE;
70    
71     /* Print the start message */
72    
73     printf_first("Adding Extra Segment Indexes: Segments=0");
74    
75     /* Allocate the array of next segment */
76    
77     segmentsx->next1=(index_t*)calloc(segmentsx->number,sizeof(index_t));
78    
79     assert(segmentsx->next1); /* Check malloc() worked */
80    
81     /* Open the file read-only */
82    
83 amb 1120 segmentsx->fd=ReOpenFile(segmentsx->filename_tmp);
84 amb 949
85     /* Read the on-disk image */
86    
87     while(!ReadFile(segmentsx->fd,&segmentx,sizeof(SegmentX)))
88     {
89     index_t node1=segmentx.node1;
90    
91 amb 953 if(index==0)
92     ;
93     else if(lastnode1==node1)
94     segmentsx->next1[index-1]=index;
95 amb 949 else
96 amb 953 segmentsx->next1[index-1]=NO_SEGMENT;
97 amb 949
98     lastnode1=node1;
99     index++;
100    
101     if(!(index%10000))
102     printf_middle("Added Extra Segment Indexes: Segments=%"Pindex_t,index);
103     }
104    
105 amb 953 segmentsx->next1[index-1]=NO_SEGMENT;
106 amb 949
107     /* Close the file */
108    
109     segmentsx->fd=CloseFile(segmentsx->fd);
110    
111     /* Print the final message */
112    
113     printf_last("Added Extra Segment Indexes: Segments=%"Pindex_t,segmentsx->number);
114     }
115    
116    
117     /*++++++++++++++++++++++++++++++++++++++
118     Delete the data structures needed for pruning.
119    
120     NodesX *nodesx The set of nodes to use.
121    
122     SegmentsX *segmentsx The set of segments to use.
123    
124     WaysX *waysx The set of ways to use.
125     ++++++++++++++++++++++++++++++++++++++*/
126    
127     void FinishPruning(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
128     {
129     free(segmentsx->next1);
130     segmentsx->next1=NULL;
131     }
132    
133    
134     /*++++++++++++++++++++++++++++++++++++++
135 amb 953 Prune out any groups of nodes and segments whose total length is less than a
136     specified minimum.
137    
138     NodesX *nodesx The set of nodes to use.
139    
140     SegmentsX *segmentsx The set of segments to use.
141    
142 amb 963 WaysX *waysx The set of ways to use.
143    
144 amb 953 distance_t minimum The minimum distance to keep.
145     ++++++++++++++++++++++++++++++++++++++*/
146    
147 amb 963 void PruneIsolatedRegions(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum)
148 amb 953 {
149 amb 1117 transport_t transport;
150 amb 953 BitMask *connected,*region;
151     index_t *regionsegments,*othersegments;
152     int nallocregionsegments,nallocothersegments;
153 amb 1117 char *newwayfilename;
154     index_t nnewways=0;
155     int fd;
156 amb 953
157     if(nodesx->number==0 || segmentsx->number==0)
158     return;
159    
160     /* Map into memory / open the files */
161    
162     #if !SLIM
163 amb 1120 nodesx->data=MapFile(nodesx->filename_tmp);
164     segmentsx->data=MapFileWriteable(segmentsx->filename_tmp);
165     waysx->data=MapFile(waysx->filename_tmp);
166 amb 953 #else
167 amb 1120 nodesx->fd=ReOpenFile(nodesx->filename_tmp);
168     segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp);
169     waysx->fd=ReOpenFile(waysx->filename_tmp);
170 amb 953 #endif
171    
172 amb 1117 newwayfilename=(char*)malloc(strlen(option_tmpdirname)+36);
173    
174     sprintf(newwayfilename,"%s/waysx.%p.new.tmp",option_tmpdirname,(void*)waysx);
175    
176     fd=OpenFileNew(newwayfilename);
177    
178 amb 953 connected=AllocBitMask(segmentsx->number);
179     region =AllocBitMask(segmentsx->number);
180    
181     assert(connected); /* Check AllocBitMask() worked */
182     assert(region); /* Check AllocBitMask() worked */
183    
184     regionsegments=(index_t*)malloc((nallocregionsegments=1024)*sizeof(index_t));
185     othersegments =(index_t*)malloc((nallocothersegments =1024)*sizeof(index_t));
186    
187     assert(regionsegments); /* Check malloc() worked */
188     assert(othersegments); /* Check malloc() worked */
189    
190 amb 1117 /* Loop through the transport types */
191 amb 953
192 amb 1117 for(transport=Transport_None+1;transport<Transport_Count;transport++)
193 amb 953 {
194 amb 1117 index_t i,j;
195     index_t nregions=0,npruned=0,nadjusted=0;
196     const char *transport_str=TransportName(transport);
197     transports_t transports=TRANSPORTS(transport);
198 amb 972
199 amb 1117 /* Print the start message */
200 amb 972
201 amb 1117 printf_first("Pruning Isolated Regions (%s): Segments=0 Adjusted=0 Pruned=0",transport_str);
202 amb 972
203 amb 1117 /* Loop through the segments and find the disconnected ones */
204 amb 977
205 amb 1117 ClearAllBits(connected,segmentsx->number);
206     ClearAllBits(region ,segmentsx->number);
207 amb 977
208 amb 1117 for(i=0;i<segmentsx->number;i++)
209 amb 953 {
210 amb 1117 int nregionsegments=0,nothersegments=0;
211     distance_t total=0;
212     SegmentX *segmentx;
213     WayX *wayx,tmpwayx;
214 amb 953
215 amb 1117 segmentx=LookupSegmentX(segmentsx,i,1);
216 amb 953
217 amb 1117 if(IsPrunedSegmentX(segmentx))
218     goto endloop;
219 amb 953
220 amb 1117 if(IsBitSet(connected,i))
221     goto endloop;
222 amb 953
223 amb 1117 if(segmentx->way<waysx->number)
224     wayx=LookupWayX(waysx,segmentx->way,1);
225     else
226     SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX));
227 amb 953
228 amb 1117 if(!(wayx->way.allow&transports))
229     goto endloop;
230 amb 953
231 amb 1117 othersegments[nothersegments++]=i;
232     SetBit(region,i);
233 amb 953
234 amb 1117 do
235 amb 977 {
236 amb 1117 index_t thissegment,nodes[2];
237 amb 953
238 amb 1117 thissegment=othersegments[--nothersegments];
239 amb 963
240 amb 1117 if(nregionsegments==nallocregionsegments)
241     regionsegments=(index_t*)realloc(regionsegments,(nallocregionsegments+=1024)*sizeof(index_t));
242 amb 977
243 amb 1117 regionsegments[nregionsegments++]=thissegment;
244    
245     segmentx=LookupSegmentX(segmentsx,thissegment,1);
246    
247     nodes[0]=segmentx->node1;
248     nodes[1]=segmentx->node2;
249     total+=DISTANCE(segmentx->distance);
250    
251     for(j=0;j<2;j++)
252 amb 953 {
253 amb 1117 NodeX *nodex=LookupNodeX(nodesx,nodes[j],1);
254 amb 963
255 amb 1117 if(!(nodex->allow&transports))
256     continue;
257    
258     segmentx=FirstSegmentX(segmentsx,nodes[j],1);
259    
260     while(segmentx)
261 amb 953 {
262 amb 1117 index_t segment=IndexSegmentX(segmentsx,segmentx);
263 amb 953
264 amb 1117 if(segment!=thissegment)
265 amb 953 {
266 amb 1117 if(segmentx->way<waysx->number)
267     wayx=LookupWayX(waysx,segmentx->way,1);
268     else
269     SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX));
270 amb 953
271 amb 1117 if(wayx->way.allow&transports)
272 amb 953 {
273 amb 1117 /* Already connected - finish */
274 amb 953
275 amb 1117 if(IsBitSet(connected,segment))
276     {
277     total=minimum;
278     goto foundconnection;
279     }
280 amb 963
281 amb 1117 /* Not in region - add to list */
282 amb 963
283 amb 1117 if(!IsBitSet(region,segment))
284     {
285     if(nothersegments==nallocothersegments)
286     othersegments=(index_t*)realloc(othersegments,(nallocothersegments+=1024)*sizeof(index_t));
287    
288     othersegments[nothersegments++]=segment;
289     SetBit(region,segment);
290     }
291 amb 953 }
292     }
293 amb 1117
294     segmentx=NextSegmentX(segmentsx,segmentx,nodes[j]);
295 amb 977 }
296 amb 953 }
297     }
298 amb 1117 while(nothersegments>0 && total<minimum);
299 amb 953
300 amb 1117 foundconnection:
301 amb 953
302 amb 1117 /* Prune the segments or mark them as connected */
303 amb 953
304 amb 1117 if(total<minimum) /* not connected - delete them */
305 amb 953 {
306 amb 1117 nregions++;
307 amb 953
308 amb 1117 for(j=0;j<nregionsegments;j++)
309     {
310     SegmentX *segmentx;
311     WayX *wayx,tmpwayx;
312 amb 953
313 amb 1117 SetBit(connected,regionsegments[j]); /* not really connected, but don't need to check again */
314     ClearBit(region,regionsegments[j]);
315 amb 953
316 amb 1117 segmentx=LookupSegmentX(segmentsx,regionsegments[j],1);
317    
318     if(segmentx->way<waysx->number)
319     wayx=LookupWayX(waysx,segmentx->way,1);
320     else
321     SeekReadFile(fd,(wayx=&tmpwayx),sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX));
322    
323     if(wayx->way.allow==transports)
324     {
325     prune_segment(segmentsx,segmentx);
326    
327     npruned++;
328     }
329     else
330     {
331     if(segmentx->way<waysx->number) /* create a new way */
332     {
333     tmpwayx=*wayx;
334    
335     tmpwayx.way.allow&=~transports;
336    
337     SeekWriteFile(fd,&tmpwayx,sizeof(WayX),nnewways*sizeof(WayX));
338    
339     segmentx->way=waysx->number+nnewways;
340    
341     nnewways++;
342    
343     PutBackSegmentX(segmentsx,segmentx);
344     }
345     else /* modify the existing one */
346     {
347     tmpwayx.way.allow&=~transports;
348    
349     SeekWriteFile(fd,&tmpwayx,sizeof(WayX),(segmentx->way-waysx->number)*sizeof(WayX));
350     }
351    
352     nadjusted++;
353     }
354     }
355 amb 953 }
356 amb 1117 else /* connected - mark as part of the main region */
357 amb 953 {
358 amb 1117 for(j=0;j<nregionsegments;j++)
359     {
360     SetBit(connected,regionsegments[j]);
361     ClearBit(region,regionsegments[j]);
362     }
363    
364     for(j=0;j<nothersegments;j++)
365     {
366     SetBit(connected,othersegments[j]);
367     ClearBit(region,othersegments[j]);
368     }
369 amb 977 }
370 amb 953
371 amb 1117 endloop:
372    
373     if(!((i+1)%10000))
374     printf_middle("Pruning Isolated Regions (%s): Segments=%"Pindex_t" Adjusted=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",transport_str,i+1,nadjusted,npruned,nregions);
375 amb 953 }
376    
377 amb 1117 /* Print the final message */
378 amb 977
379 amb 1117 printf_last("Pruned Isolated Regions (%s): Segments=%"Pindex_t" Adjusted=%"Pindex_t" Pruned=%"Pindex_t" (%"Pindex_t" Regions)",transport_str,segmentsx->number,nadjusted,npruned,nregions);
380 amb 953 }
381    
382     /* Unmap from memory / close the files */
383    
384     free(region);
385     free(connected);
386    
387     free(regionsegments);
388     free(othersegments);
389    
390     #if !SLIM
391 amb 1122 nodesx->data=UnmapFile(nodesx->data);
392     segmentsx->data=UnmapFile(segmentsx->data);
393     waysx->data=UnmapFile(waysx->data);
394 amb 953 #else
395     nodesx->fd=CloseFile(nodesx->fd);
396     segmentsx->fd=CloseFile(segmentsx->fd);
397 amb 963 waysx->fd=CloseFile(waysx->fd);
398 amb 953 #endif
399    
400 amb 1117 /* Append the new ways to the end of the existing ones */
401 amb 953
402 amb 1117 SeekFile(fd,0);
403    
404 amb 1120 waysx->fd=OpenFileAppend(waysx->filename_tmp);
405 amb 1117
406     for(;nnewways>0;nnewways--)
407     {
408     WayX wayx;
409    
410     ReadFile(fd,&wayx,sizeof(WayX));
411     WriteFile(waysx->fd,&wayx,sizeof(WayX));
412    
413     waysx->number++;
414     }
415    
416     waysx->fd=CloseFile(waysx->fd);
417    
418     CloseFile(fd);
419    
420     DeleteFile(newwayfilename);
421 amb 953 }
422    
423    
424     /*++++++++++++++++++++++++++++++++++++++
425 amb 964 Prune out any segments that are shorter than a specified minimum.
426    
427     NodesX *nodesx The set of nodes to use.
428    
429     SegmentsX *segmentsx The set of segments to use.
430    
431     WaysX *waysx The set of ways to use.
432    
433 amb 966 distance_t minimum The maximum length to remove or one less than the minimum length to keep.
434 amb 964 ++++++++++++++++++++++++++++++++++++++*/
435    
436     void PruneShortSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t minimum)
437     {
438     index_t i;
439     index_t nshort=0,npruned=0;
440    
441     if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
442     return;
443    
444     /* Print the start message */
445    
446     printf_first("Pruning Short Segments: Segments=0 Short=0 Pruned=0");
447    
448     /* Map into memory / open the files */
449    
450     #if !SLIM
451 amb 1120 nodesx->data=MapFileWriteable(nodesx->filename_tmp);
452     segmentsx->data=MapFileWriteable(segmentsx->filename_tmp);
453     waysx->data=MapFile(waysx->filename_tmp);
454 amb 964 #else
455 amb 1120 nodesx->fd=ReOpenFileWriteable(nodesx->filename_tmp);
456     segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp);
457     waysx->fd=ReOpenFile(waysx->filename_tmp);
458 amb 964 #endif
459    
460     /* Loop through the segments and find the short ones for possible modification */
461    
462     for(i=0;i<segmentsx->number;i++)
463     {
464     SegmentX *segmentx2=LookupSegmentX(segmentsx,i,2);
465    
466     if(IsPrunedSegmentX(segmentx2))
467 amb 966 goto endloop;
468 amb 964
469     /*
470     :
471     Initial state: ..N3 -------- N2
472     : S2
473    
474     :
475     Final state: ..N3 N2 --
476     : S2
477    
478     = OR =
479    
480     : :
481     Initial state: ..N1 -------- N2 ---- N3 -------- N4..
482     : S1 S2 S3 :
483    
484     : :
485     Final state: ..N1 ------------ N3 ------------ N4.. N2 --
486     : S1 S3 : S2
487    
488     Not if N1 is the same as N4.
489     Not if S2 has different one-way properties from S1 and S3.
490     Must combine N2, S2 and N3 disallowed transports into new N3.
491     Must not delete N2 or N3 if they are mini-roundabouts.
492     Must not delete N2 or N3 if they are part of turn relations.
493    
494     = OR =
495    
496     : :
497     Initial state: ..N1 -------- N2 ---- N3..
498     : S1 S2 :
499    
500     : :
501     Final state: ..N1 ------------ N3.. N2 --
502     : S1 : S2
503    
504     Not if N1 is the same as N3.
505     Not if S1 has different one-way properties from S2.
506     Not if S1 has different highway properties from S2.
507     Not if N2 disallows transports allowed on S1 and S2.
508     Not if N2 is a mini-roundabouts.
509     Not if N2 is involved in a turn restriction.
510     */
511    
512     if(DISTANCE(segmentx2->distance)<=minimum)
513     {
514 amb 973 index_t node1=NO_NODE,node2,node3,node4=NO_NODE;
515 amb 964 index_t segment1=NO_SEGMENT,segment2=i,segment3=NO_SEGMENT;
516     SegmentX *segmentx;
517     int segcount2=0,segcount3=0;
518    
519     nshort++;
520    
521     node2=segmentx2->node1;
522     node3=segmentx2->node2;
523    
524     /* Count the segments connected to N2 and N3 */
525    
526     segmentx=FirstSegmentX(segmentsx,node2,4);
527    
528     while(segmentx)
529     {
530     segcount2++;
531    
532     if(segment1==NO_SEGMENT)
533     {
534     index_t segment=IndexSegmentX(segmentsx,segmentx);
535    
536     if(segment!=segment2)
537     {
538     segment1=segment;
539     node1=OtherNode(segmentx,node2);
540     }
541     }
542    
543     segmentx=NextSegmentX(segmentsx,segmentx,node2);
544     }
545    
546     segmentx=FirstSegmentX(segmentsx,node3,4);
547    
548     while(segmentx)
549     {
550     segcount3++;
551    
552     if(segment3==NO_SEGMENT)
553     {
554     index_t segment=IndexSegmentX(segmentsx,segmentx);
555    
556     if(segment!=segment2)
557     {
558     segment3=segment;
559     node4=OtherNode(segmentx,node3);
560     }
561     }
562    
563     segmentx=NextSegmentX(segmentsx,segmentx,node3);
564     }
565    
566     /* Check which case we are handling (and canonicalise) */
567    
568     if(segcount2>2 && segcount3>2) /* none of the cases in diagram - too complicated */
569     {
570     goto endloop;
571     }
572     else if(segcount2==1 || segcount3==1) /* first case in diagram - prune segment */
573     {
574     prune_segment(segmentsx,segmentx2);
575     }
576     else if(segcount2==2 && segcount3==2) /* second case in diagram - modify one segment and prune segment */
577     {
578     SegmentX *segmentx1,*segmentx3;
579     WayX *wayx1,*wayx2,*wayx3;
580     NodeX *nodex2,*nodex3,*newnodex;
581     index_t newnode;
582     int join12=1,join23=1;
583    
584     /* Check if pruning would collapse a loop */
585    
586     if(node1==node4)
587     goto endloop;
588    
589     /* Check if allowed due to one-way properties */
590    
591     segmentx1=LookupSegmentX(segmentsx,segment1,1);
592     segmentx3=LookupSegmentX(segmentsx,segment3,3);
593    
594     if(!IsOneway(segmentx1) && !IsOneway(segmentx2))
595     ;
596     else if(IsOneway(segmentx1) && IsOneway(segmentx2))
597     {
598     if(IsOnewayTo(segmentx1,node2) && !IsOnewayFrom(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */
599     join12=0;
600    
601     if(IsOnewayFrom(segmentx1,node2) && !IsOnewayTo(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */
602     join12=0;
603     }
604     else
605     join12=0;
606    
607     if(!IsOneway(segmentx3) && !IsOneway(segmentx2))
608     ;
609     else if(IsOneway(segmentx3) && IsOneway(segmentx2))
610     {
611     if(IsOnewayTo(segmentx3,node3) && !IsOnewayFrom(segmentx2,node3)) /* S3 is one-way but S2 doesn't continue */
612     join23=0;
613    
614     if(IsOnewayFrom(segmentx3,node3) && !IsOnewayTo(segmentx2,node3)) /* S3 is one-way but S2 doesn't continue */
615     join23=0;
616     }
617     else
618     join23=0;
619    
620     if(!join12 && !join23)
621     goto endloop;
622    
623     /* Check if allowed due to mini-roundabout and turn restriction */
624    
625     nodex2=LookupNodeX(nodesx,node2,2);
626     nodex3=LookupNodeX(nodesx,node3,3);
627    
628     if(nodex2->flags&NODE_MINIRNDBT)
629     join12=0;
630    
631     if(nodex3->flags&NODE_MINIRNDBT)
632     join23=0;
633    
634     if(nodex2->flags&NODE_TURNRSTRCT2 || nodex2->flags&NODE_TURNRSTRCT)
635     join12=0;
636    
637     if(nodex3->flags&NODE_TURNRSTRCT2 || nodex3->flags&NODE_TURNRSTRCT)
638     join23=0;
639    
640     if(!join12 && !join23)
641     goto endloop;
642    
643     /* New node properties */
644    
645     if(join12)
646     {
647     newnode=node3;
648     newnodex=nodex3;
649     }
650     else /* if(join23) */
651     {
652     newnode=node2;
653     newnodex=nodex2;
654     }
655    
656     wayx1=LookupWayX(waysx,segmentx1->way,1);
657     wayx2=LookupWayX(waysx,segmentx2->way,2);
658     wayx3=LookupWayX(waysx,segmentx3->way,3);
659    
660     newnodex->allow=nodex2->allow&nodex3->allow; /* combine the restrictions of the two nodes */
661     newnodex->allow&=~((~wayx2->way.allow)&wayx3->way.allow); /* disallow anything blocked by segment2 */
662     newnodex->allow&=~((~wayx2->way.allow)&wayx1->way.allow); /* disallow anything blocked by segment2 */
663    
664     newnodex->latitude =(nodex2->latitude +nodex3->latitude )/2;
665     newnodex->longitude=(nodex2->longitude+nodex3->longitude)/2;
666    
667     PutBackNodeX(nodesx,newnodex);
668    
669     /* Modify segments */
670    
671     segmentx1->distance+=DISTANCE(segmentx2->distance)/2;
672     segmentx3->distance+=DISTANCE(segmentx2->distance)-DISTANCE(segmentx2->distance)/2;
673    
674     if(segmentx1->node1==node1)
675     {
676     if(segmentx1->node2!=newnode)
677     modify_segment(segmentsx,segmentx1,node1,newnode);
678 amb 1121 else
679     PutBackSegmentX(segmentsx,segmentx1);
680 amb 964 }
681     else /* if(segmentx1->node2==node1) */
682     {
683     if(segmentx1->node1!=newnode)
684     modify_segment(segmentsx,segmentx1,newnode,node1);
685 amb 1121 else
686     PutBackSegmentX(segmentsx,segmentx1);
687 amb 964 }
688    
689     if(segmentx3->node1==node4)
690     {
691     if(segmentx3->node2!=newnode)
692     modify_segment(segmentsx,segmentx3,node4,newnode);
693 amb 1121 else
694     PutBackSegmentX(segmentsx,segmentx3);
695 amb 964 }
696     else /* if(segmentx3->node2==node4) */
697     {
698     if(segmentx3->node1!=newnode)
699     modify_segment(segmentsx,segmentx3,newnode,node4);
700 amb 1121 else
701     PutBackSegmentX(segmentsx,segmentx3);
702 amb 964 }
703 amb 1121
704     ReLookupSegmentX(segmentsx,segmentx2);
705    
706     prune_segment(segmentsx,segmentx2);
707 amb 964 }
708     else /* third case in diagram - prune one segment */
709     {
710     SegmentX *segmentx1;
711     WayX *wayx1,*wayx2;
712     NodeX *nodex2;
713    
714     if(segcount3==2) /* not as in diagram, shuffle things round */
715     {
716     index_t temp;
717    
718     temp=segment1; segment1=segment3; segment3=temp;
719     temp=node1; node1=node4; node4=temp;
720     temp=node2; node2=node3; node3=temp;
721     }
722    
723     /* Check if pruning would collapse a loop */
724    
725     if(node1==node3)
726     goto endloop;
727    
728     /* Check if allowed due to one-way properties */
729    
730     segmentx1=LookupSegmentX(segmentsx,segment1,1);
731    
732     if(!IsOneway(segmentx1) && !IsOneway(segmentx2))
733     ;
734     else if(IsOneway(segmentx1) && IsOneway(segmentx2))
735     {
736     if(IsOnewayTo(segmentx1,node2) && !IsOnewayFrom(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */
737     goto endloop;
738    
739     if(IsOnewayFrom(segmentx1,node2) && !IsOnewayTo(segmentx2,node2)) /* S1 is one-way but S2 doesn't continue */
740     goto endloop;
741     }
742     else
743     goto endloop;
744    
745 amb 976 /* Check if allowed due to highway properties */
746    
747     wayx1=LookupWayX(waysx,segmentx1->way,1);
748     wayx2=LookupWayX(waysx,segmentx2->way,2);
749    
750     if(WaysCompare(&wayx1->way,&wayx2->way))
751     goto endloop;
752    
753 amb 964 /* Check if allowed due to mini-roundabout and turn restriction */
754    
755     nodex2=LookupNodeX(nodesx,node2,2);
756    
757     if(nodex2->flags&NODE_MINIRNDBT)
758     goto endloop;
759    
760     if(nodex2->flags&NODE_TURNRSTRCT2 || nodex2->flags&NODE_TURNRSTRCT)
761     goto endloop;
762    
763     /* Check if allowed due to node restrictions */
764    
765     if((nodex2->allow&wayx1->way.allow)!=wayx1->way.allow)
766     goto endloop;
767    
768     if((nodex2->allow&wayx2->way.allow)!=wayx2->way.allow)
769     goto endloop;
770    
771     /* Modify segments */
772    
773     segmentx1->distance+=DISTANCE(segmentx2->distance);
774    
775     if(segmentx1->node1==node1)
776     modify_segment(segmentsx,segmentx1,node1,node3);
777     else /* if(segmentx1->node2==node1) */
778     modify_segment(segmentsx,segmentx1,node3,node1);
779 amb 1121
780     ReLookupSegmentX(segmentsx,segmentx2);
781    
782     prune_segment(segmentsx,segmentx2);
783 amb 964 }
784    
785     npruned++;
786     }
787    
788     endloop:
789    
790     if(!((i+1)%10000))
791     printf_middle("Pruning Short Segments: Segments=%"Pindex_t" Short=%"Pindex_t" Pruned=%"Pindex_t,i+1,nshort,npruned);
792     }
793    
794     /* Unmap from memory / close the files */
795    
796     #if !SLIM
797 amb 1122 nodesx->data=UnmapFile(nodesx->data);
798     segmentsx->data=UnmapFile(segmentsx->data);
799     waysx->data=UnmapFile(waysx->data);
800 amb 964 #else
801     nodesx->fd=CloseFile(nodesx->fd);
802     segmentsx->fd=CloseFile(segmentsx->fd);
803     waysx->fd=CloseFile(waysx->fd);
804     #endif
805    
806     /* Print the final message */
807    
808     printf_last("Pruned Short Segments: Segments=%"Pindex_t" Short=%"Pindex_t" Pruned=%"Pindex_t,segmentsx->number,nshort,npruned);
809     }
810    
811    
812     /*++++++++++++++++++++++++++++++++++++++
813 amb 966 Prune out any nodes from straight highways where the introduced error is smaller than a specified maximum.
814    
815     NodesX *nodesx The set of nodes to use.
816    
817     SegmentsX *segmentsx The set of segments to use.
818    
819     WaysX *waysx The set of ways to use.
820    
821     distance_t maximum The maximum error to introduce.
822     ++++++++++++++++++++++++++++++++++++++*/
823    
824     void PruneStraightHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,distance_t maximum)
825     {
826     index_t i;
827     index_t npruned=0;
828     BitMask *checked;
829 amb 967 int nalloc;
830 amb 966 index_t *nodes,*segments;
831 amb 967 double *lats,*lons;
832 amb 966 double maximumf;
833    
834     if(nodesx->number==0 || segmentsx->number==0 || waysx->number==0)
835     return;
836    
837     maximumf=distance_to_km(maximum);
838    
839     /* Print the start message */
840    
841     printf_first("Pruning Straight Highway Nodes: Nodes=0 Pruned=0");
842    
843     /* Map into memory / open the files */
844    
845     #if !SLIM
846 amb 1120 nodesx->data=MapFile(nodesx->filename_tmp);
847     segmentsx->data=MapFileWriteable(segmentsx->filename_tmp);
848     waysx->data=MapFile(waysx->filename_tmp);
849 amb 966 #else
850 amb 1120 nodesx->fd=ReOpenFile(nodesx->filename_tmp);
851     segmentsx->fd=ReOpenFileWriteable(segmentsx->filename_tmp);
852     waysx->fd=ReOpenFile(waysx->filename_tmp);
853 amb 966 #endif
854    
855     checked=AllocBitMask(nodesx->number);
856    
857     assert(checked); /* Check AllocBitMask() worked */
858    
859     nodes =(index_t*)malloc((nalloc=1024)*sizeof(index_t));
860     segments=(index_t*)malloc( nalloc *sizeof(index_t));
861    
862     assert(nodes); /* Check malloc() worked */
863     assert(segments); /* Check malloc() worked */
864    
865 amb 967 lats=(double*)malloc(nalloc*sizeof(double));
866     lons=(double*)malloc(nalloc*sizeof(double));
867    
868     assert(lats); /* Check malloc() worked */
869     assert(lons); /* Check malloc() worked */
870    
871 amb 966 /* Loop through the nodes and find stretchs of simple highway for possible modification */
872    
873     for(i=0;i<nodesx->number;i++)
874     {
875 amb 976 int lowerbounded=0,upperbounded=0;
876 amb 966 index_t lower=nalloc/2,current=nalloc/2,upper=nalloc/2;
877    
878 amb 976 if(IsBitSet(checked,i))
879 amb 966 goto endloop;
880    
881 amb 976 if(segmentsx->firstnode[i]==NO_SEGMENT)
882 amb 966 goto endloop;
883    
884     /* Find all connected nodes */
885    
886     nodes[current]=i;
887    
888     do
889     {
890     index_t node1=NO_NODE,node2=NO_NODE;
891 amb 973 index_t segment1=NO_SEGMENT,segment2=NO_SEGMENT;
892     index_t way1=NO_WAY,way2=NO_WAY;
893 amb 966 int segcount=0;
894 amb 967 NodeX *nodex;
895 amb 966
896     if(!IsBitSet(checked,nodes[current]))
897     {
898     SegmentX *segmentx;
899    
900     /* Count the segments connected to the node */
901    
902     segmentx=FirstSegmentX(segmentsx,nodes[current],1);
903    
904     while(segmentx)
905     {
906     segcount++;
907    
908     if(node1==NO_NODE)
909     {
910     segment1=IndexSegmentX(segmentsx,segmentx);
911     node1=OtherNode(segmentx,nodes[current]);
912     way1=segmentx->way;
913     }
914     else if(node2==NO_NODE)
915     {
916     segment2=IndexSegmentX(segmentsx,segmentx);
917     node2=OtherNode(segmentx,nodes[current]);
918     way2=segmentx->way;
919     }
920    
921     segmentx=NextSegmentX(segmentsx,segmentx,nodes[current]);
922     }
923     }
924    
925     /* Perform more checks */
926    
927 amb 967 nodex=LookupNodeX(nodesx,nodes[current],1);
928    
929     lats[current]=latlong_to_radians(nodex->latitude);
930     lons[current]=latlong_to_radians(nodex->longitude);
931    
932     /* Check if allowed due to mini-roundabout and turn restriction */
933    
934     if(nodex->flags&NODE_MINIRNDBT)
935     segcount=0;
936    
937     if(nodex->flags&NODE_TURNRSTRCT2 || nodex->flags&NODE_TURNRSTRCT)
938     segcount=0;
939    
940     /* Check if allowed due to one-way properties */
941    
942 amb 966 if(segcount==2)
943     {
944     SegmentX *segmentx1,*segmentx2;
945    
946     segmentx1=LookupSegmentX(segmentsx,segment1,1);
947     segmentx2=LookupSegmentX(segmentsx,segment2,2);
948    
949     if(!IsOneway(segmentx1) && !IsOneway(segmentx2))
950     ;
951     else if(IsOneway(segmentx1) && IsOneway(segmentx2))
952     {
953     if(IsOnewayTo(segmentx1,nodes[current]) && !IsOnewayFrom(segmentx2,nodes[current])) /* S1 is one-way but S2 doesn't continue */
954     segcount=0;
955    
956     if(IsOnewayFrom(segmentx1,nodes[current]) && !IsOnewayTo(segmentx2,nodes[current])) /* S1 is one-way but S2 doesn't continue */
957     segcount=0;
958     }
959     else
960     segcount=0;
961     }
962    
963 amb 967 /* Check if allowed due to highway properties and node restrictions */
964    
965 amb 966 if(segcount==2)
966     {
967     WayX *wayx1,*wayx2;
968    
969     wayx1=LookupWayX(waysx,way1,1);
970     wayx2=LookupWayX(waysx,way2,2);
971    
972     if(WaysCompare(&wayx1->way,&wayx2->way))
973     segcount=0;
974    
975 amb 971 if(wayx1->way.name!=wayx2->way.name)
976     segcount=0;
977    
978 amb 966 if((nodex->allow&wayx1->way.allow)!=wayx1->way.allow)
979     segcount=0;
980    
981     if((nodex->allow&wayx2->way.allow)!=wayx2->way.allow)
982     segcount=0;
983     }
984    
985     /* Update the lists */
986    
987     if(segcount==2)
988     {
989 amb 970 if(upper==(nalloc-1))
990 amb 966 {
991     nodes =(index_t*)realloc(nodes ,(nalloc+=1024)*sizeof(index_t));
992     segments=(index_t*)realloc(segments, nalloc *sizeof(index_t));
993 amb 967
994     lats=(double*)realloc(lats,nalloc*sizeof(double));
995     lons=(double*)realloc(lons,nalloc*sizeof(double));
996 amb 966 }
997    
998     if(lower==0) /* move everything up by one */
999     {
1000 amb 1017 memmove(nodes+1 ,nodes ,(1+upper-lower)*sizeof(index_t));
1001     memmove(segments+1,segments,(1+upper-lower)*sizeof(index_t));
1002 amb 966
1003 amb 1017 memmove(lats+1,lats,(1+upper-lower)*sizeof(double));
1004     memmove(lons+1,lons,(1+upper-lower)*sizeof(double));
1005 amb 967
1006 amb 966 current++;
1007     lower++;
1008     upper++;
1009     }
1010    
1011     if(lower==upper) /* first */
1012     {
1013     lower--;
1014    
1015     nodes[lower]=node1;
1016     segments[lower]=segment1;
1017    
1018     upper++;
1019    
1020     nodes[upper]=node2;
1021     segments[upper-1]=segment2;
1022    
1023     current--;
1024     }
1025     else if(current==lower)
1026     {
1027     lower--;
1028    
1029     if(nodes[current+1]==node2)
1030     {
1031     nodes[lower]=node1;
1032     segments[lower]=segment1;
1033     }
1034     else /* if(nodes[current+1]==node1) */
1035     {
1036     nodes[lower]=node2;
1037     segments[lower]=segment2;
1038     }
1039    
1040     current--;
1041     }
1042     else /* if(current==upper) */
1043     {
1044     upper++;
1045    
1046     if(nodes[current-1]==node2)
1047     {
1048     nodes[upper]=node1;
1049     segments[upper-1]=segment1;
1050     }
1051     else /* if(nodes[current-1]==node1) */
1052     {
1053     nodes[upper]=node2;
1054     segments[upper-1]=segment2;
1055     }
1056    
1057     current++;
1058     }
1059    
1060     if(nodes[upper]==nodes[lower])
1061     {
1062     lowerbounded=1;
1063     upperbounded=1;
1064     }
1065     }
1066     else
1067     {
1068     if(current==upper)
1069     upperbounded=1;
1070    
1071     if(current==lower)
1072     {
1073     lowerbounded=1;
1074     current=upper;
1075     }
1076     }
1077     }
1078     while(!(lowerbounded && upperbounded));
1079    
1080 amb 967 /* Mark the nodes */
1081    
1082     for(current=lower;current<=upper;current++)
1083     SetBit(checked,nodes[current]);
1084    
1085 amb 966 /* Check for straight highway */
1086    
1087     while((upper-lower)>=2)
1088     {
1089 amb 967 index_t bestc=lower;
1090 amb 966
1091 amb 967 for(current=lower+2;current<=upper;current++)
1092 amb 966 {
1093 amb 967 double dist1,dist2,dist3,dist3a,dist3b,distp;
1094     index_t c;
1095 amb 966
1096 amb 967 dist3=distance(lats[lower],lons[lower],lats[current],lons[current]);
1097 amb 966
1098 amb 967 for(c=lower+1;c<current;c++)
1099 amb 966 {
1100 amb 967 dist1=distance(lats[lower] ,lons[lower] ,lats[c],lons[c]);
1101     dist2=distance(lats[current],lons[current],lats[c],lons[c]);
1102 amb 966
1103 amb 967 /* Use law of cosines (assume flat Earth) */
1104 amb 966
1105 amb 967 dist3a=(dist1*dist1-dist2*dist2+dist3*dist3)/(2.0*dist3);
1106     dist3b=dist3-dist3a;
1107 amb 966
1108 amb 967 if((dist1+dist2)<dist3)
1109     distp=0;
1110     else if(dist3a>=0 && dist3b>=0)
1111     distp=sqrt(dist1*dist1-dist3a*dist3a);
1112     else if(dist3a>0)
1113     distp=dist2;
1114     else /* if(dist3b>0) */
1115     distp=dist1;
1116 amb 966
1117 amb 967 if(distp>maximumf) /* gone too far */
1118     break;
1119     }
1120 amb 966
1121 amb 967 if(c>bestc)
1122     bestc=c;
1123 amb 966
1124 amb 967 if(bestc>c)
1125     c=bestc;
1126 amb 966
1127 amb 967 if(c==current && current!=upper) /* Can replace at least this far (not finished yet) */
1128     continue;
1129 amb 966
1130 amb 967 if((c-lower)<2) /* first three points are not straight */
1131     {
1132     lower=c;
1133     break;
1134     }
1135     else /* delete some segments and shift along */
1136     {
1137     SegmentX *segmentx;
1138     distance_t distance=0;
1139 amb 966
1140 amb 967 current=c;
1141 amb 966
1142 amb 967 for(c=lower+1;c<current;c++)
1143     {
1144     segmentx=LookupSegmentX(segmentsx,segments[c],1);
1145 amb 966
1146 amb 967 distance+=DISTANCE(segmentx->distance);
1147 amb 966
1148 amb 967 prune_segment(segmentsx,segmentx);
1149 amb 966
1150 amb 967 npruned++;
1151     }
1152 amb 966
1153 amb 967 segmentx=LookupSegmentX(segmentsx,segments[lower],1);
1154 amb 966
1155 amb 970 if(nodes[lower]==nodes[current]) /* loop; all within maximum distance */
1156     {
1157     prune_segment(segmentsx,segmentx);
1158 amb 966
1159 amb 970 npruned++;
1160     }
1161     else
1162     {
1163     segmentx->distance+=distance;
1164 amb 966
1165 amb 970 if(segmentx->node1==nodes[lower])
1166     modify_segment(segmentsx,segmentx,nodes[lower],nodes[current]);
1167     else /* if(segmentx->node2==nodes[lower]) */
1168     modify_segment(segmentsx,segmentx,nodes[current],nodes[lower]);
1169     }
1170    
1171 amb 967 lower=current;
1172     break;
1173 amb 966 }
1174     }
1175     }
1176    
1177     endloop:
1178    
1179     if(!((i+1)%10000))
1180     printf_middle("Pruning Straight Highway Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,i+1,npruned);
1181     }
1182    
1183     /* Unmap from memory / close the files */
1184    
1185     free(checked);
1186    
1187     free(nodes);
1188     free(segments);
1189    
1190 amb 967 free(lats);
1191     free(lons);
1192    
1193 amb 966 #if !SLIM
1194 amb 1122 nodesx->data=UnmapFile(nodesx->data);
1195     segmentsx->data=UnmapFile(segmentsx->data);
1196     waysx->data=UnmapFile(waysx->data);
1197 amb 966 #else
1198     nodesx->fd=CloseFile(nodesx->fd);
1199     segmentsx->fd=CloseFile(segmentsx->fd);
1200     waysx->fd=CloseFile(waysx->fd);
1201     #endif
1202    
1203     /* Print the final message */
1204    
1205     printf_last("Pruned Straight Highway Nodes: Nodes=%"Pindex_t" Pruned=%"Pindex_t,nodesx->number,npruned);
1206     }
1207    
1208    
1209     /*++++++++++++++++++++++++++++++++++++++
1210 amb 960 Prune a segment; unused nodes and ways will get marked for pruning later.
1211 amb 953
1212     SegmentsX *segmentsx The set of segments to use.
1213    
1214     SegmentX *segmentx The segment to be pruned.
1215     ++++++++++++++++++++++++++++++++++++++*/
1216    
1217 amb 960 static void prune_segment(SegmentsX *segmentsx,SegmentX *segmentx)
1218 amb 953 {
1219 amb 970 unlink_segment_node1_refs(segmentsx,segmentx);
1220 amb 1121
1221 amb 970 unlink_segment_node2_refs(segmentsx,segmentx);
1222 amb 953
1223     segmentx->node1=NO_NODE;
1224     segmentx->node2=NO_NODE;
1225     segmentx->next2=NO_SEGMENT;
1226    
1227     PutBackSegmentX(segmentsx,segmentx);
1228     }
1229    
1230    
1231     /*++++++++++++++++++++++++++++++++++++++
1232 amb 960 Modify a segment's nodes; unused nodes will get marked for pruning later.
1233 amb 949
1234     SegmentsX *segmentsx The set of segments to use.
1235    
1236     SegmentX *segmentx The segment to be modified.
1237    
1238     index_t newnode1 The new value of node1.
1239    
1240     index_t newnode2 The new value of node2.
1241     ++++++++++++++++++++++++++++++++++++++*/
1242    
1243     static void modify_segment(SegmentsX *segmentsx,SegmentX *segmentx,index_t newnode1,index_t newnode2)
1244     {
1245     index_t thissegment=IndexSegmentX(segmentsx,segmentx);
1246    
1247 amb 970 if(newnode1>newnode2) /* rotate the segment around */
1248 amb 949 {
1249 amb 968 index_t temp;
1250    
1251     if(segmentx->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
1252     segmentx->distance^=ONEWAY_2TO1|ONEWAY_1TO2;
1253    
1254     temp=newnode1;
1255     newnode1=newnode2;
1256     newnode2=temp;
1257 amb 970 }
1258 amb 968
1259 amb 970 if(newnode1!=segmentx->node1)
1260     unlink_segment_node1_refs(segmentsx,segmentx);
1261 amb 968
1262 amb 970 if(newnode2!=segmentx->node2)
1263     unlink_segment_node2_refs(segmentsx,segmentx);
1264 amb 949
1265 amb 968 if(newnode1!=segmentx->node1) /* only modify it if the node has changed */
1266     {
1267 amb 949 segmentx->node1=newnode1;
1268    
1269     segmentsx->next1[thissegment]=segmentsx->firstnode[newnode1];
1270     segmentsx->firstnode[newnode1]=thissegment;
1271     }
1272    
1273 amb 968 if(newnode2!=segmentx->node2) /* only modify it if the node has changed */
1274 amb 949 {
1275     segmentx->node2=newnode2;
1276    
1277     segmentx->next2=segmentsx->firstnode[newnode2];
1278     segmentsx->firstnode[newnode2]=thissegment;
1279 amb 1121 }
1280 amb 970
1281 amb 1121 PutBackSegmentX(segmentsx,segmentx);
1282 amb 949 }
1283    
1284    
1285     /*++++++++++++++++++++++++++++++++++++++
1286 amb 970 Unlink a node1 from a segment by modifying the linked list type arrangement of node references.
1287 amb 949
1288     SegmentsX *segmentsx The set of segments to use.
1289    
1290 amb 970 SegmentX *segmentx The segment to be modified.
1291 amb 949 ++++++++++++++++++++++++++++++++++++++*/
1292    
1293 amb 970 static void unlink_segment_node1_refs(SegmentsX *segmentsx,SegmentX *segmentx)
1294 amb 949 {
1295 amb 970 index_t segment,thissegment;
1296 amb 949
1297 amb 970 thissegment=IndexSegmentX(segmentsx,segmentx);
1298 amb 953
1299 amb 970 segment=segmentsx->firstnode[segmentx->node1];
1300    
1301 amb 949 if(segment==thissegment)
1302 amb 970 segmentsx->firstnode[segmentx->node1]=segmentsx->next1[thissegment];
1303 amb 949 else
1304     {
1305     do
1306     {
1307 amb 970 index_t nextsegment;
1308 amb 964 SegmentX *segx=LookupSegmentX(segmentsx,segment,4);
1309 amb 949
1310 amb 970 if(segx->node1==segmentx->node1)
1311 amb 949 {
1312     nextsegment=segmentsx->next1[segment];
1313    
1314 amb 970 if(nextsegment==thissegment)
1315     segmentsx->next1[segment]=segmentsx->next1[thissegment];
1316     }
1317     else /* if(segx->node2==segmentx->node1) */
1318     {
1319     nextsegment=segx->next2;
1320    
1321     if(nextsegment==thissegment)
1322 amb 949 {
1323 amb 970 segx->next2=segmentsx->next1[thissegment];
1324    
1325     PutBackSegmentX(segmentsx,segx);
1326 amb 949 }
1327     }
1328 amb 970
1329     segment=nextsegment;
1330     }
1331     while(segment!=thissegment && segment!=NO_SEGMENT);
1332     }
1333     }
1334    
1335    
1336     /*++++++++++++++++++++++++++++++++++++++
1337     Unlink a node2 from a segment by modifying the linked list type arrangement of node references.
1338    
1339     SegmentsX *segmentsx The set of segments to use.
1340    
1341     SegmentX *segmentx The segment to be modified.
1342     ++++++++++++++++++++++++++++++++++++++*/
1343    
1344     static void unlink_segment_node2_refs(SegmentsX *segmentsx,SegmentX *segmentx)
1345     {
1346     index_t segment,thissegment;
1347    
1348     thissegment=IndexSegmentX(segmentsx,segmentx);
1349    
1350     segment=segmentsx->firstnode[segmentx->node2];
1351    
1352     if(segment==thissegment)
1353     segmentsx->firstnode[segmentx->node2]=segmentx->next2;
1354     else
1355     {
1356     do
1357     {
1358     index_t nextsegment;
1359     SegmentX *segx=LookupSegmentX(segmentsx,segment,4);
1360    
1361     if(segx->node1==segmentx->node2)
1362 amb 949 {
1363 amb 970 nextsegment=segmentsx->next1[segment];
1364    
1365     if(nextsegment==thissegment)
1366     segmentsx->next1[segment]=segmentx->next2;
1367     }
1368     else /* if(segx->node2==segmentx->node2) */
1369     {
1370 amb 949 nextsegment=segx->next2;
1371    
1372 amb 970 if(nextsegment==thissegment)
1373 amb 949 {
1374 amb 970 segx->next2=segmentx->next2;
1375 amb 949
1376     PutBackSegmentX(segmentsx,segx);
1377     }
1378     }
1379    
1380     segment=nextsegment;
1381     }
1382 amb 953 while(segment!=thissegment && segment!=NO_SEGMENT);
1383 amb 949 }
1384     }
1385 amb 966
1386    
1387     /*++++++++++++++++++++++++++++++++++++++
1388     Calculate the distance between two locations.
1389    
1390     double distance Returns the distance between the locations.
1391    
1392     double lat1 The latitude of the first location.
1393    
1394     double lon1 The longitude of the first location.
1395    
1396     double lat2 The latitude of the second location.
1397    
1398     double lon2 The longitude of the second location.
1399     ++++++++++++++++++++++++++++++++++++++*/
1400    
1401     static double distance(double lat1,double lon1,double lat2,double lon2)
1402     {
1403     double dlon = lon1 - lon2;
1404     double dlat = lat1 - lat2;
1405    
1406     double a1,a2,a,sa,c,d;
1407    
1408     if(dlon==0 && dlat==0)
1409     return 0;
1410    
1411     a1 = sin (dlat / 2);
1412     a2 = sin (dlon / 2);
1413     a = (a1 * a1) + cos (lat1) * cos (lat2) * a2 * a2;
1414     sa = sqrt (a);
1415     if (sa <= 1.0)
1416     {c = 2 * asin (sa);}
1417     else
1418     {c = 2 * asin (1.0);}
1419     d = 6378.137 * c;
1420    
1421     return(d);
1422     }