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 1166 - (hide annotations) (download) (as text)
Tue Nov 20 16:12:08 2012 UTC (12 years, 3 months ago) by amb
File MIME type: text/x-csrc
File size: 39995 byte(s)
Replace all assert statements with a custom error message that explains the
cause and suggests a solution.

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