trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.28 2009-02-04 18:23:33 amb Exp $

 Segment data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


#include <assert.h>
#include <math.h>
#include <stdlib.h>

#include "nodes.h"
#include "segments.h"
#include "functions.h"


/* Constants */

/*+ The array size increment for segments - expect ~8,000,000 segments. +*/
#define INCREMENT_SEGMENTS 1024*1024


/* Functions */

static int sort_by_id(SegmentX *a,SegmentX *b);


/*++++++++++++++++++++++++++++++++++++++
  Load in a segment list from a file.

  Segments* SaveSegmentList Returns the segment list that has just been loaded.

  const char *filename The name of the file to load.
  ++++++++++++++++++++++++++++++++++++++*/

Segments *LoadSegmentList(const char *filename)
{
 void *data;
 Segments *segments;

 segments=(Segments*)malloc(sizeof(Segments));

 data=MapFile(filename);

 /* Copy the Segments structure from the loaded data */

 *segments=*((Segments*)data);

 /* Adjust the pointers in the Segments structure. */

 segments->data =data;
 segments->segments=(Segment*)(data+(off_t)segments->segments);

 return(segments);
}


/*++++++++++++++++++++++++++++++++++++++
  Allocate a new segment list.

  SegmentsX *NewSegmentList Returns the segment list.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsX *NewSegmentList(void)
{
 SegmentsX *segmentsx;

 segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));

 segmentsx->sorted=0;
 segmentsx->alloced=INCREMENT_SEGMENTS;
 segmentsx->number=0;

 segmentsx->xdata=(SegmentX*)malloc(segmentsx->alloced*sizeof(SegmentX));

 return(segmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Free a segment list.

  SegmentsX *segmentsx The list to be freed.
  ++++++++++++++++++++++++++++++++++++++*/

void FreeSegmentList(SegmentsX *segmentsx)
{
 free(segmentsx->xdata);
 free(segmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Save the segment list to a file.

  SegmentsX* segmentsx The set of segments to save.

  const char *filename The name of the file to save.
  ++++++++++++++++++++++++++++++++++++++*/

void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
{
 int i;
 int fd;
 Segments *segments=calloc(1,sizeof(Segments));

 assert(segmentsx->sorted);      /* Must be sorted */

 /* Fill in a Segments structure with the offset of the real data in the file after
    the Segment structure itself. */

 segments->number=segmentsx->number;
 segments->data=NULL;
 segments->segments=(void*)sizeof(Segments);

 /* Write out the Segments structure and then the real data. */

 fd=OpenFile(filename);

 WriteFile(fd,segments,sizeof(Segments));

 for(i=0;i<segmentsx->number;i++)
    WriteFile(fd,&segmentsx->xdata[i].segment,sizeof(Segment));

 CloseFile(fd);

 /* Free the fake Segments */

 free(segments);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the first segment with a particular starting node.

  SegmentX *FindFirstSegmentX Returns the first extended segment with the specified id.

  SegmentsX* segmentsx The set of segments to process.

  node_t node The node to look for.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentX *FindFirstSegmentX(SegmentsX* segmentsx,node_t node)
{
 int start=0;
 int end=segmentsx->number-1;
 int mid;
 int found;

 /* Binary search - search key exact match only is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an exact match is wanted we can set end=mid-1
  *  # <- mid    |  or start=mid+1 because we know that mid doesn't match.
  *  #           |
  *  #           |  Eventually either end=start or end=start+1 and one of
  *  # <- end    |  start or end is the wanted one.
  */

 if(end<start)                                 /* There are no nodes */
    return(NULL);
 else if(node<segmentsx->xdata[start].node1) /* Check key is not before start */
    return(NULL);
 else if(node>segmentsx->xdata[end].node1)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                          /* Choose mid point */

       if(segmentsx->xdata[mid].node1<node)      /* Mid point is too low */
          start=mid;
       else if(segmentsx->xdata[mid].node1>node) /* Mid point is too high */
          end=mid;
       else                                        /* Mid point is correct */
         {found=mid; goto found;}
      }
    while((end-start)>1);

    if(segmentsx->xdata[start].node1==node)      /* Start is correct */
         {found=start; goto found;}

    if(segmentsx->xdata[end].node1==node)        /* End is correct */
         {found=end; goto found;}
   }

 return(NULL);

 found:

 while(found>0 && segmentsx->xdata[found-1].node1==node)
    found--;

 return(&segmentsx->xdata[found]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the next segment with a particular starting node.

  SegmentX *FindNextSegmentX Returns a pointer to the next segment with the same id.

  SegmentsX* segmentss The set of segments to process.

  SegmentX *segmentx The current segment.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentX *FindNextSegmentX(SegmentsX* segmentsx,SegmentX *segmentx)
{
 SegmentX *next=segmentx+1;

 if(IndexSegmentX(segmentsx,next)==segmentsx->number)
    return(NULL);

 if(next->node1==segmentx->node1)
    return(next);

 return(NULL);
}
 
 
/*++++++++++++++++++++++++++++++++++++++
  Find the next segment with a particular starting node.

  Segment *NextSegment Returns a pointer to the next segment with the same id.

  Segments* segments The set of segments to process.

  Segment *segment The current segment.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *NextSegment(Segments* segments,Segment *segment)
{
 Segment *next=segment+1;

 if(IndexSegment(segments,next)==segments->number)
    return(NULL);

 if(NODE(next->node1)==NODE(segment->node1))
    return(next);

 return(NULL);
}
 
 
/*++++++++++++++++++++++++++++++++++++++
  Append a segment to a segment list.

  Segment *AppendSegmentX Returns the appended segment.

  SegmentsX* segmentsx The set of segments to process.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *AppendSegment(SegmentsX* segmentsx,node_t node1,node_t node2)
{
 /* Check that the array has enough space. */

 if(segmentsx->number==segmentsx->alloced)
   {
    segmentsx->alloced+=INCREMENT_SEGMENTS;

    segmentsx->xdata=(SegmentX*)realloc((void*)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
   }

 /* Insert the segment */

 segmentsx->xdata[segmentsx->number].node1=node1;
 segmentsx->xdata[segmentsx->number].node2=node2;

 segmentsx->xdata[segmentsx->number].segment.distance=0;

 segmentsx->number++;

 segmentsx->sorted=0;

 return(&segmentsx->xdata[segmentsx->number-1].segment);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the segment list.

  SegmentsX* segmentsx The set of segments to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortSegmentList(SegmentsX* segmentsx)
{
 qsort(segmentsx->xdata,segmentsx->number,sizeof(SegmentX),(int (*)(const void*,const void*))sort_by_id);

 while(segmentsx->xdata[segmentsx->number-1].node1==~0)
    segmentsx->number--;

 segmentsx->sorted=1;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the segments into id order.

  int sort_by_id Returns the comparison of the node fields.

  SegmentX *a The first Segment.

  SegmentX *b The second Segment.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(SegmentX *a,SegmentX *b)
{
 node_t a_id1=a->node1,a_id2=a->node2;
 node_t b_id1=b->node1,b_id2=b->node2;

 if(a_id1<b_id1)
    return(-1);
 else if(a_id1>b_id1)
    return(1);
 else /* if(a_id1==b_id1) */
   {
    if(a_id2<b_id2)
       return(-1);
    else
       return(1);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Remove bad segments (zero length or duplicated).

  SegmentsX *segmentsx The segments to modify.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveBadSegments(SegmentsX *segmentsx)
{
 int i;
 int duplicate=0,loop=0;
 node_t node1=~0,node2=~0;

 for(i=0;i<segmentsx->number;i++)
   {
    if(segmentsx->xdata[i].node1==node1 && segmentsx->xdata[i].node2==node2)
      {
       duplicate++;
       segmentsx->xdata[i].node1=~0;
      }
    else if(segmentsx->xdata[i].node1==segmentsx->xdata[i].node2)
      {
       loop++;
       segmentsx->xdata[i].node1=~0;
      }

    node1=segmentsx->xdata[i].node1;
    node2=segmentsx->xdata[i].node2;

    if(!((i+1)%10000))
      {
       printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
       fflush(stdout);
      }
   }

 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d  \n",segmentsx->number,duplicate,loop);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Measure the segments.

  SegmentsX* segmentsx The set of segments to process.

  NodesX *nodesx The list of nodes to use.
  ++++++++++++++++++++++++++++++++++++++*/

void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
{
 int i;

 assert(segmentsx->sorted);   /* Must be sorted */

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX *node1=FindNodeX(nodesx,segmentsx->xdata[i].node1);
    NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);

    /* Set the distance but preserve the ONEWAY_OPPOSITE flag */

    segmentsx->xdata[i].segment.distance|=DistanceX(node1,node2);

    if(!((i+1)%10000))
      {
       printf("\rMeasuring Segments: Segments=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Fix the segment indexes to the nodes.

  SegmentsX* segmentsx The set of segments to process.

  NodesX *nodesx The list of nodes to use.

  SegmentsX* supersegmentsx The set of super-segments to append.
  ++++++++++++++++++++++++++++++++++++++*/

void FixupSegments(SegmentsX* segmentsx,NodesX *nodesx,SegmentsX* supersegmentsx)
{
 int i,j,n;

 assert(segmentsx->sorted);   /* Must be sorted */
 assert(supersegmentsx->sorted);   /* Must be sorted */

 for(i=0;i<segmentsx->number;i++)
   {
    NodeX *node1=FindNodeX(nodesx,segmentsx->xdata[i].node1);
    NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);

    segmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1)|SUPER_FLAG;
    segmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2);

    if(!((i+1)%10000))
      {
       printf("\rFixing Segments: Segments=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rFixed Segments: Segments=%d \n",segmentsx->number);
 fflush(stdout);

 for(i=0;i<supersegmentsx->number;i++)
   {
    NodeX *node1=FindNodeX(nodesx,supersegmentsx->xdata[i].node1);
    NodeX *node2=FindNodeX(nodesx,supersegmentsx->xdata[i].node2);

    supersegmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1);
    supersegmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2)|SUPER_FLAG;

    if(!((i+1)%10000))
      {
       printf("\rFixing Super-Segments: Super-Segments=%d",i+1);
       fflush(stdout);
      }
   }

 printf("\rFixed Super-Segments: Super-Segments=%d \n",supersegmentsx->number);
 fflush(stdout);

 n=segmentsx->number;

 for(i=0,j=0;i<n;i++)
   {
    while(j<supersegmentsx->number)
      {
       if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
          segmentsx->xdata[i].node2==supersegmentsx->xdata[j].node2)
         {
          segmentsx->xdata[i].segment.node2|=SUPER_FLAG;
          j++;
          break;
         }
       else if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
               segmentsx->xdata[i].node2>supersegmentsx->xdata[j].node2)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);

          *supersegment=supersegmentsx->xdata[j].segment;
         }
       else if(segmentsx->xdata[i].node1>supersegmentsx->xdata[j].node1)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);

          *supersegment=supersegmentsx->xdata[j].segment;
         }
       else
          break;

       j++;
      }

    if(!((i+1)%10000))
      {
       printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
       fflush(stdout);
      }
   }

 printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->number);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the distance between two locations.

  float Distance Returns the distance between the locations.

  float lat1 The latitude of the first location.

  float lon1 The longitude of the first location.

  float lat2 The latitude of the second location.

  float lon2 The longitude of the second location.
  ++++++++++++++++++++++++++++++++++++++*/

float Distance(float lat1,float lon1,float lat2,float lon2)
{
 double radiant = M_PI / 180;

 double dlon = radiant * (lon1 - lon2);
 double dlat = radiant * (lat1 - lat2);

 double a1,a2,a,sa,c,d;

 if(dlon==0 && dlat==0)
   return 0;

 a1 = sin (dlat / 2);
 a2 = sin (dlon / 2);
 a = (a1 * a1) + cos (lat1 * radiant) * cos (lat2 * radiant) * a2 * a2;
 sa = sqrt (a);
 if (sa <= 1.0)
   {c = 2 * asin (sa);}
 else
   {c = 2 * asin (1.0);}
 d = 6378.137 * c;

 return d;
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the distance between two nodes.

  distance_t DistanceX Returns the distance between the extended nodes.

  NodeX *nodex1 The starting node.

  NodeX *nodex2 The end node.
  ++++++++++++++++++++++++++++++++++++++*/

distance_t DistanceX(NodeX *nodex1,NodeX *nodex2)
{
 double radiant = M_PI / 180;

 double dlon = radiant * (nodex1->longitude - nodex2->longitude);
 double dlat = radiant * (nodex1->latitude  - nodex2->latitude);

 double a1,a2,a,sa,c,d;

 if(dlon==0 && dlat==0)
   return 0;

 a1 = sin (dlat / 2);
 a2 = sin (dlon / 2);
 a = (a1 * a1) + cos (nodex1->latitude * radiant) * cos (nodex2->latitude * radiant) * a2 * a2;
 sa = sqrt (a);
 if (sa <= 1.0)
   {c = 2 * asin (sa);}
 else
   {c = 2 * asin (1.0);}
 d = 6378.137 * c;

 return km_to_distance(d);
}


/*++++++++++++++++++++++++++++++++++++++
  Calculate the duration of segment.

  duration_t Duration Returns the duration of travel between the nodes.

  Segment *segment The segment to traverse.

  Way *way The way that the segment belongs to.

  Profile *profile The profile of the transport being used.
  ++++++++++++++++++++++++++++++++++++++*/

duration_t Duration(Segment *segment,Way *way,Profile *profile)
{
 speed_t    speed=profile->speed[HIGHWAY(way->type)];
 distance_t distance=DISTANCE(segment->distance);

 return distance_speed_to_duration(distance,speed);
}
1	amb	2	/***************************************
2	amb	99	$Header: /home/amb/CVS/routino/src/segments.c,v 1.28 2009-02-04 18:23:33 amb Exp $
3	amb	2
4			Segment data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8	amb	4	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	2	It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15	amb	8	#include <assert.h>
16	amb	2	#include <math.h>
17			#include <stdlib.h>
18
19	amb	39	#include "nodes.h"
20	amb	26	#include "segments.h"
21	amb	2	#include "functions.h"
22
23
24	amb	96	/* Constants */
25
26			/+ The array size increment for segments - expect ~8,000,000 segments. +/
27			#define INCREMENT_SEGMENTS 1024*1024
28
29
30	amb	23	/* Functions */
31	amb	2
32	amb	97	static int sort_by_id(SegmentX a,SegmentX b);
33	amb	2
34	amb	8
35	amb	23	/*++++++++++++++++++++++++++++++++++++++
36	amb	2	Load in a segment list from a file.
37
38	amb	23	Segments* SaveSegmentList Returns the segment list that has just been loaded.
39
40	amb	2	const char *filename The name of the file to load.
41			++++++++++++++++++++++++++++++++++++++*/
42
43	amb	23	Segments LoadSegmentList(const char filename)
44	amb	2	{
45	amb	88	void *data;
46			Segments *segments;
47
48			segments=(Segments*)malloc(sizeof(Segments));
49
50			data=MapFile(filename);
51
52			/* Copy the Segments structure from the loaded data */
53
54			segments=((Segments*)data);
55
56			/* Adjust the pointers in the Segments structure. */
57
58			segments->data =data;
59			segments->segments=(Segment*)(data+(off_t)segments->segments);
60
61			return(segments);
62	amb	2	}
63
64
65			/*++++++++++++++++++++++++++++++++++++++
66	amb	97	Allocate a new segment list.
67
68			SegmentsX *NewSegmentList Returns the segment list.
69			++++++++++++++++++++++++++++++++++++++*/
70
71			SegmentsX *NewSegmentList(void)
72			{
73			SegmentsX *segmentsx;
74
75			segmentsx=(SegmentsX*)malloc(sizeof(SegmentsX));
76
77			segmentsx->sorted=0;
78			segmentsx->alloced=INCREMENT_SEGMENTS;
79			segmentsx->number=0;
80
81			segmentsx->xdata=(SegmentX)malloc(segmentsx->allocedsizeof(SegmentX));
82
83			return(segmentsx);
84			}
85
86
87			/*++++++++++++++++++++++++++++++++++++++
88			Free a segment list.
89
90			SegmentsX *segmentsx The list to be freed.
91			++++++++++++++++++++++++++++++++++++++*/
92
93			void FreeSegmentList(SegmentsX *segmentsx)
94			{
95			free(segmentsx->xdata);
96			free(segmentsx);
97			}
98
99
100			/*++++++++++++++++++++++++++++++++++++++
101	amb	2	Save the segment list to a file.
102
103	amb	97	SegmentsX* segmentsx The set of segments to save.
104	amb	23
105	amb	2	const char *filename The name of the file to save.
106			++++++++++++++++++++++++++++++++++++++*/
107
108	amb	97	void SaveSegmentList(SegmentsX* segmentsx,const char *filename)
109	amb	2	{
110	amb	88	int i;
111			int fd;
112			Segments *segments=calloc(1,sizeof(Segments));
113	amb	2
114	amb	97	assert(segmentsx->sorted); /* Must be sorted */
115	amb	23
116	amb	88	/* Fill in a Segments structure with the offset of the real data in the file after
117			the Segment structure itself. */
118
119	amb	97	segments->number=segmentsx->number;
120	amb	88	segments->data=NULL;
121			segments->segments=(void*)sizeof(Segments);
122
123			/* Write out the Segments structure and then the real data. */
124
125			fd=OpenFile(filename);
126
127	amb	97	WriteFile(fd,segments,sizeof(Segments));
128	amb	88
129	amb	97	for(i=0;i<segmentsx->number;i++)
130			WriteFile(fd,&segmentsx->xdata[i].segment,sizeof(Segment));
131	amb	88
132	amb	97	CloseFile(fd);
133	amb	88
134	amb	89	/* Free the fake Segments */
135	amb	88
136	amb	23	free(segments);
137	amb	2	}
138
139
140			/*++++++++++++++++++++++++++++++++++++++
141			Find the first segment with a particular starting node.
142
143	amb	98	SegmentX *FindFirstSegmentX Returns the first extended segment with the specified id.
144	amb	2
145	amb	97	SegmentsX* segmentsx The set of segments to process.
146	amb	23
147	amb	2	node_t node The node to look for.
148			++++++++++++++++++++++++++++++++++++++*/
149
150	amb	98	SegmentX FindFirstSegmentX(SegmentsX segmentsx,node_t node)
151	amb	2	{
152	amb	88	int start=0;
153	amb	97	int end=segmentsx->number-1;
154	amb	2	int mid;
155			int found;
156
157			/* Binary search - search key exact match only is required.
158			*
159			* # <- start \| Check mid and move start or end if it doesn't match
160			* # \|
161			* # \| Since an exact match is wanted we can set end=mid-1
162			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
163			* # \|
164			* # \| Eventually either end=start or end=start+1 and one of
165			* # <- end \| start or end is the wanted one.
166			*/
167
168	amb	23	if(end<start) /* There are no nodes */
169	amb	89	return(NULL);
170	amb	97	else if(node<segmentsx->xdata[start].node1) /* Check key is not before start */
171	amb	89	return(NULL);
172	amb	97	else if(node>segmentsx->xdata[end].node1) /* Check key is not after end */
173	amb	89	return(NULL);
174	amb	2	else
175			{
176			do
177			{
178	amb	23	mid=(start+end)/2; /* Choose mid point */
179	amb	2
180	amb	97	if(segmentsx->xdata[mid].node1<node) /* Mid point is too low */
181	amb	2	start=mid;
182	amb	97	else if(segmentsx->xdata[mid].node1>node) /* Mid point is too high */
183	amb	2	end=mid;
184	amb	23	else /* Mid point is correct */
185	amb	2	{found=mid; goto found;}
186			}
187			while((end-start)>1);
188
189	amb	97	if(segmentsx->xdata[start].node1==node) /* Start is correct */
190	amb	2	{found=start; goto found;}
191
192	amb	97	if(segmentsx->xdata[end].node1==node) /* End is correct */
193	amb	2	{found=end; goto found;}
194			}
195
196	amb	89	return(NULL);
197	amb	2
198			found:
199
200	amb	97	while(found>0 && segmentsx->xdata[found-1].node1==node)
201	amb	2	found--;
202
203	amb	97	return(&segmentsx->xdata[found]);
204	amb	2	}
205
206
207			/*++++++++++++++++++++++++++++++++++++++
208			Find the next segment with a particular starting node.
209
210	amb	98	SegmentX *FindNextSegmentX Returns a pointer to the next segment with the same id.
211	amb	89
212	amb	98	SegmentsX* segmentss The set of segments to process.
213	amb	89
214	amb	98	SegmentX *segmentx The current segment.
215	amb	89	++++++++++++++++++++++++++++++++++++++*/
216
217	amb	98	SegmentX FindNextSegmentX(SegmentsX segmentsx,SegmentX *segmentx)
218	amb	89	{
219	amb	98	SegmentX *next=segmentx+1;
220	amb	89
221	amb	97	if(IndexSegmentX(segmentsx,next)==segmentsx->number)
222	amb	89	return(NULL);
223
224	amb	98	if(next->node1==segmentx->node1)
225	amb	89	return(next);
226
227			return(NULL);
228			}
229
230
231			/*++++++++++++++++++++++++++++++++++++++
232			Find the next segment with a particular starting node.
233
234	amb	88	Segment *NextSegment Returns a pointer to the next segment with the same id.
235	amb	2
236	amb	23	Segments* segments The set of segments to process.
237
238	amb	2	Segment *segment The current segment.
239			++++++++++++++++++++++++++++++++++++++*/
240
241	amb	88	Segment NextSegment(Segments segments,Segment *segment)
242	amb	2	{
243			Segment *next=segment+1;
244
245	amb	89	if(IndexSegment(segments,next)==segments->number)
246	amb	23	return(NULL);
247	amb	2
248	amb	90	if(NODE(next->node1)==NODE(segment->node1))
249	amb	2	return(next);
250
251			return(NULL);
252	amb	89	}
253	amb	88
254
255	amb	2	/*++++++++++++++++++++++++++++++++++++++
256	amb	98	Append a segment to a segment list.
257	amb	2
258	amb	98	Segment *AppendSegmentX Returns the appended segment.
259	amb	31
260	amb	97	SegmentsX* segmentsx The set of segments to process.
261	amb	23
262	amb	2	node_t node1 The first node in the segment.
263
264			node_t node2 The second node in the segment.
265			++++++++++++++++++++++++++++++++++++++*/
266
267	amb	98	Segment AppendSegment(SegmentsX segmentsx,node_t node1,node_t node2)
268	amb	2	{
269	amb	23	/* Check that the array has enough space. */
270	amb	8
271	amb	97	if(segmentsx->number==segmentsx->alloced)
272	amb	4	{
273	amb	97	segmentsx->alloced+=INCREMENT_SEGMENTS;
274	amb	4
275	amb	97	segmentsx->xdata=(SegmentX)realloc((void)segmentsx->xdata,segmentsx->alloced*sizeof(SegmentX));
276	amb	4	}
277
278			/* Insert the segment */
279
280	amb	97	segmentsx->xdata[segmentsx->number].node1=node1;
281			segmentsx->xdata[segmentsx->number].node2=node2;
282	amb	98
283	amb	97	segmentsx->xdata[segmentsx->number].segment.distance=0;
284	amb	2
285	amb	97	segmentsx->number++;
286	amb	2
287	amb	97	segmentsx->sorted=0;
288	amb	31
289	amb	98	return(&segmentsx->xdata[segmentsx->number-1].segment);
290	amb	2	}
291
292
293			/*++++++++++++++++++++++++++++++++++++++
294			Sort the segment list.
295	amb	23
296	amb	97	SegmentsX* segmentsx The set of segments to process.
297	amb	2	++++++++++++++++++++++++++++++++++++++*/
298
299	amb	97	void SortSegmentList(SegmentsX* segmentsx)
300	amb	2	{
301	amb	97	qsort(segmentsx->xdata,segmentsx->number,sizeof(SegmentX),(int ()(const void,const void*))sort_by_id);
302	amb	39
303	amb	97	while(segmentsx->xdata[segmentsx->number-1].node1==~0)
304			segmentsx->number--;
305	amb	8
306	amb	97	segmentsx->sorted=1;
307	amb	2	}
308
309
310			/*++++++++++++++++++++++++++++++++++++++
311			Sort the segments into id order.
312
313			int sort_by_id Returns the comparison of the node fields.
314
315	amb	97	SegmentX *a The first Segment.
316	amb	2
317	amb	97	SegmentX *b The second Segment.
318	amb	2	++++++++++++++++++++++++++++++++++++++*/
319
320	amb	97	static int sort_by_id(SegmentX a,SegmentX b)
321	amb	2	{
322			node_t a_id1=a->node1,a_id2=a->node2;
323			node_t b_id1=b->node1,b_id2=b->node2;
324
325	amb	39	if(a_id1<b_id1)
326			return(-1);
327			else if(a_id1>b_id1)
328			return(1);
329			else /* if(a_id1==b_id1) */
330			{
331			if(a_id2<b_id2)
332			return(-1);
333	amb	88	else
334	amb	39	return(1);
335			}
336	amb	2	}
337
338
339			/*++++++++++++++++++++++++++++++++++++++
340	amb	39	Remove bad segments (zero length or duplicated).
341
342	amb	97	SegmentsX *segmentsx The segments to modify.
343	amb	39	++++++++++++++++++++++++++++++++++++++*/
344
345	amb	97	void RemoveBadSegments(SegmentsX *segmentsx)
346	amb	39	{
347			int i;
348			int duplicate=0,loop=0;
349			node_t node1=~0,node2=~0;
350
351	amb	97	for(i=0;i<segmentsx->number;i++)
352	amb	39	{
353	amb	97	if(segmentsx->xdata[i].node1==node1 && segmentsx->xdata[i].node2==node2)
354	amb	39	{
355			duplicate++;
356	amb	97	segmentsx->xdata[i].node1=~0;
357	amb	39	}
358	amb	97	else if(segmentsx->xdata[i].node1==segmentsx->xdata[i].node2)
359	amb	39	{
360			loop++;
361	amb	97	segmentsx->xdata[i].node1=~0;
362	amb	39	}
363
364	amb	97	node1=segmentsx->xdata[i].node1;
365			node2=segmentsx->xdata[i].node2;
366	amb	39
367			if(!((i+1)%10000))
368			{
369			printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop);
370			fflush(stdout);
371			}
372			}
373
374	amb	97	printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segmentsx->number,duplicate,loop);
375	amb	39	fflush(stdout);
376			}
377
378
379			/*++++++++++++++++++++++++++++++++++++++
380	amb	89	Measure the segments.
381	amb	23
382	amb	97	SegmentsX* segmentsx The set of segments to process.
383	amb	23
384	amb	97	NodesX *nodesx The list of nodes to use.
385	amb	8	++++++++++++++++++++++++++++++++++++++*/
386	amb	2
387	amb	97	void MeasureSegments(SegmentsX* segmentsx,NodesX *nodesx)
388	amb	8	{
389			int i;
390	amb	2
391	amb	97	assert(segmentsx->sorted); /* Must be sorted */
392	amb	8
393	amb	97	for(i=0;i<segmentsx->number;i++)
394	amb	8	{
395	amb	98	NodeX *node1=FindNodeX(nodesx,segmentsx->xdata[i].node1);
396			NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);
397	amb	8
398	amb	82	/* Set the distance but preserve the ONEWAY_OPPOSITE flag */
399	amb	8
400	amb	99	segmentsx->xdata[i].segment.distance\|=DistanceX(node1,node2);
401	amb	69
402	amb	54	if(!((i+1)%10000))
403			{
404	amb	89	printf("\rMeasuring Segments: Segments=%d",i+1);
405			fflush(stdout);
406			}
407			}
408
409	amb	97	printf("\rMeasured Segments: Segments=%d \n",segmentsx->number);
410	amb	89	fflush(stdout);
411			}
412
413
414			/*++++++++++++++++++++++++++++++++++++++
415			Fix the segment indexes to the nodes.
416
417	amb	97	SegmentsX* segmentsx The set of segments to process.
418	amb	89
419	amb	97	NodesX *nodesx The list of nodes to use.
420	amb	90
421	amb	97	SegmentsX* supersegmentsx The set of super-segments to append.
422	amb	89	++++++++++++++++++++++++++++++++++++++*/
423
424	amb	97	void FixupSegments(SegmentsX* segmentsx,NodesX nodesx,SegmentsX supersegmentsx)
425	amb	89	{
426	amb	90	int i,j,n;
427	amb	89
428	amb	97	assert(segmentsx->sorted); /* Must be sorted */
429			assert(supersegmentsx->sorted); /* Must be sorted */
430	amb	89
431	amb	97	for(i=0;i<segmentsx->number;i++)
432	amb	89	{
433	amb	98	NodeX *node1=FindNodeX(nodesx,segmentsx->xdata[i].node1);
434			NodeX *node2=FindNodeX(nodesx,segmentsx->xdata[i].node2);
435	amb	89
436	amb	97	segmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1)\|SUPER_FLAG;
437			segmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2);
438	amb	89
439			if(!((i+1)%10000))
440			{
441	amb	88	printf("\rFixing Segments: Segments=%d",i+1);
442	amb	54	fflush(stdout);
443			}
444	amb	8	}
445	amb	54
446	amb	97	printf("\rFixed Segments: Segments=%d \n",segmentsx->number);
447	amb	54	fflush(stdout);
448	amb	90
449	amb	97	for(i=0;i<supersegmentsx->number;i++)
450	amb	90	{
451	amb	98	NodeX *node1=FindNodeX(nodesx,supersegmentsx->xdata[i].node1);
452			NodeX *node2=FindNodeX(nodesx,supersegmentsx->xdata[i].node2);
453	amb	90
454	amb	97	supersegmentsx->xdata[i].segment.node1=IndexNodeX(nodesx,node1);
455			supersegmentsx->xdata[i].segment.node2=IndexNodeX(nodesx,node2)\|SUPER_FLAG;
456	amb	90
457			if(!((i+1)%10000))
458			{
459			printf("\rFixing Super-Segments: Super-Segments=%d",i+1);
460			fflush(stdout);
461			}
462			}
463
464	amb	97	printf("\rFixed Super-Segments: Super-Segments=%d \n",supersegmentsx->number);
465	amb	90	fflush(stdout);
466
467	amb	97	n=segmentsx->number;
468	amb	90
469			for(i=0,j=0;i<n;i++)
470			{
471	amb	97	while(j<supersegmentsx->number)
472	amb	90	{
473	amb	97	if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
474			segmentsx->xdata[i].node2==supersegmentsx->xdata[j].node2)
475	amb	90	{
476	amb	97	segmentsx->xdata[i].segment.node2\|=SUPER_FLAG;
477	amb	90	j++;
478			break;
479			}
480	amb	97	else if(segmentsx->xdata[i].node1==supersegmentsx->xdata[j].node1 &&
481			segmentsx->xdata[i].node2>supersegmentsx->xdata[j].node2)
482	amb	90	{
483	amb	98	Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);
484	amb	90
485	amb	98	*supersegment=supersegmentsx->xdata[j].segment;
486	amb	90	}
487	amb	97	else if(segmentsx->xdata[i].node1>supersegmentsx->xdata[j].node1)
488	amb	90	{
489	amb	98	Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->xdata[j].node1,supersegmentsx->xdata[j].node2);
490	amb	90
491	amb	98	*supersegment=supersegmentsx->xdata[j].segment;
492	amb	90	}
493			else
494			break;
495
496			j++;
497			}
498
499			if(!((i+1)%10000))
500			{
501	amb	97	printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->number);
502	amb	90	fflush(stdout);
503			}
504			}
505
506	amb	97	printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->number);
507	amb	90	fflush(stdout);
508	amb	8	}
509
510
511			/*++++++++++++++++++++++++++++++++++++++
512	amb	99	Calculate the distance between two locations.
513
514			float Distance Returns the distance between the locations.
515
516			float lat1 The latitude of the first location.
517
518			float lon1 The longitude of the first location.
519
520			float lat2 The latitude of the second location.
521
522			float lon2 The longitude of the second location.
523			++++++++++++++++++++++++++++++++++++++*/
524
525			float Distance(float lat1,float lon1,float lat2,float lon2)
526			{
527			double radiant = M_PI / 180;
528
529			double dlon = radiant * (lon1 - lon2);
530			double dlat = radiant * (lat1 - lat2);
531
532			double a1,a2,a,sa,c,d;
533
534			if(dlon==0 && dlat==0)
535			return 0;
536
537			a1 = sin (dlat / 2);
538			a2 = sin (dlon / 2);
539			a = (a1 * a1) + cos (lat1 * radiant) * cos (lat2 * radiant) * a2 * a2;
540			sa = sqrt (a);
541			if (sa <= 1.0)
542			{c = 2 * asin (sa);}
543			else
544			{c = 2 * asin (1.0);}
545			d = 6378.137 * c;
546
547			return d;
548			}
549
550
551			/*++++++++++++++++++++++++++++++++++++++
552	amb	8	Calculate the distance between two nodes.
553
554	amb	99	distance_t DistanceX Returns the distance between the extended nodes.
555	amb	8
556	amb	98	NodeX *nodex1 The starting node.
557	amb	2
558	amb	98	NodeX *nodex2 The end node.
559	amb	2	++++++++++++++++++++++++++++++++++++++*/
560
561	amb	99	distance_t DistanceX(NodeX nodex1,NodeX nodex2)
562	amb	2	{
563			double radiant = M_PI / 180;
564
565	amb	99	double dlon = radiant * (nodex1->longitude - nodex2->longitude);
566			double dlat = radiant * (nodex1->latitude - nodex2->latitude);
567	amb	2
568			double a1,a2,a,sa,c,d;
569
570			if(dlon==0 && dlat==0)
571			return 0;
572
573			a1 = sin (dlat / 2);
574			a2 = sin (dlon / 2);
575	amb	99	a = (a1 * a1) + cos (nodex1->latitude * radiant) * cos (nodex2->latitude * radiant) * a2 * a2;
576	amb	2	sa = sqrt (a);
577			if (sa <= 1.0)
578			{c = 2 * asin (sa);}
579			else
580			{c = 2 * asin (1.0);}
581	amb	5	d = 6378.137 * c;
582	amb	2
583	amb	5	return km_to_distance(d);
584	amb	2	}
585	amb	63
586
587			/*++++++++++++++++++++++++++++++++++++++
588			Calculate the duration of segment.
589
590			duration_t Duration Returns the duration of travel between the nodes.
591
592			Segment *segment The segment to traverse.
593
594			Way *way The way that the segment belongs to.
595
596	amb	82	Profile *profile The profile of the transport being used.
597	amb	63	++++++++++++++++++++++++++++++++++++++*/
598
599	amb	82	duration_t Duration(Segment segment,Way way,Profile *profile)
600	amb	63	{
601	amb	82	speed_t speed=profile->speed[HIGHWAY(way->type)];
602	amb	90	distance_t distance=DISTANCE(segment->distance);
603	amb	63
604	amb	86	return distance_speed_to_duration(distance,speed);
605	amb	63	}