trunk/src/segments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segments.c,v 1.30 2009-02-06 20: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 <string.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);

 if(!data)
    return(NULL);

 /* 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->xnumber=0;

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

 return(segmentsx);
}


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

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

void FreeSegmentList(SegmentsX *segmentsx)
{
 free(segmentsx->xdata);
 free(segmentsx->sdata);
 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->sdata[i]->segment,sizeof(Segment));

 CloseFile(fd);

 /* Free the fake Segments */

 free(segments);
}


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

  SegmentX **FindFirstSegmentX Returns a pointer to 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;

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

 /* 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->sdata[start]->node1) /* Check key is not before start */
    return(NULL);
 else if(node>segmentsx->sdata[end]->node1)   /* Check key is not after end */
    return(NULL);
 else
   {
    do
      {
       mid=(start+end)/2;                         /* Choose mid point */

       if(segmentsx->sdata[mid]->node1<node)      /* Mid point is too low */
          start=mid;
       else if(segmentsx->sdata[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->sdata[start]->node1==node)      /* Start is correct */
         {found=start; goto found;}

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

 return(NULL);

 found:

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

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


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

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

  SegmentsX* segmentsx The set of segments to process.

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

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

 if((next-segmentsx->sdata)==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,index_t node)
{
 index_t next;

 if(NODE(segment->node1)==node)
    next=segment->next1;
 else
    next=segment->next2;

 if(next==~0)
    return(NULL);
 else
    return(LookupSegment(segments,next));
}
 
 
/*++++++++++++++++++++++++++++++++++++++
  Append a segment to a segment list.

  Segment *AppendSegment 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->xnumber==segmentsx->alloced)
   {
    segmentsx->alloced+=INCREMENT_SEGMENTS;

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

 /* Insert the segment */

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

 memset(&segmentsx->xdata[segmentsx->xnumber].segment,0,sizeof(Segment));

 segmentsx->xnumber++;

 segmentsx->sorted=0;

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


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

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

void SortSegmentList(SegmentsX* segmentsx)
{
 int i;

 /* Allocate the arrays of pointers */

 if(segmentsx->sorted)
    segmentsx->sdata=realloc(segmentsx->sdata,segmentsx->xnumber*sizeof(SegmentX*));
 else
    segmentsx->sdata=malloc(segmentsx->xnumber*sizeof(SegmentX*));

 segmentsx->number=0;

 for(i=0;i<segmentsx->xnumber;i++)
    if(segmentsx->xdata[i].node1!=~0)
      {
       segmentsx->sdata[segmentsx->number]=&segmentsx->xdata[i];
       segmentsx->number++;
      }

 qsort(segmentsx->sdata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id);

 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;
 node_t b_id1=(*b)->node1;

 if(a_id1<b_id1)
    return(-1);
 else if(a_id1>b_id1)
    return(1);
 else /* if(a_id1==b_id1) */
   {
    node_t a_id2=(*a)->node2;
    node_t b_id2=(*b)->node2;

    if(a_id2<b_id2)
       return(-1);
    else if(a_id2>b_id2)
       return(1);
    else
      {
       distance_t a_distance=(*a)->segment.distance;
       distance_t b_distance=(*b)->segment.distance;

       if(a_distance<b_distance)
          return(-1);
       else if(a_distance>b_distance)
          return(1);
       else
          return(0);
      }
   }
}


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

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

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

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

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

    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->sdata[i]->node1);
    NodeX *node2=FindNodeX(nodesx,segmentsx->sdata[i]->node2);

    /* Set the distance but preserve the ONEWAY_* flags */

    segmentsx->sdata[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);
}


/*++++++++++++++++++++++++++++++++++++++
  Make the segments all point the same way (node1<node2).

  SegmentsX* segmentsx The set of segments to process.

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

void RotateSegments(SegmentsX* segmentsx,NodesX *nodesx)
{
 int i,rotated=0;

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

 for(i=0;i<segmentsx->number;i++)
   {
    if(segmentsx->sdata[i]->node1>segmentsx->sdata[i]->node2)
      {
       segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;
       segmentsx->sdata[i]->node2^=segmentsx->sdata[i]->node1;
       segmentsx->sdata[i]->node1^=segmentsx->sdata[i]->node2;

       if(segmentsx->sdata[i]->segment.distance&(ONEWAY_2TO1|ONEWAY_1TO2))
          segmentsx->sdata[i]->segment.distance^=ONEWAY_2TO1|ONEWAY_1TO2;

       rotated++;
      }

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

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


/*++++++++++++++++++++++++++++++++++++++
  Mark the duplicate segments.

  SegmentsX* segmentsx The set of segments to process.

  NodesX *nodesx The list of nodes to use.

  WaysX *waysx The list of ways to use.
  ++++++++++++++++++++++++++++++++++++++*/

void DeduplicateSegments(SegmentsX* segmentsx,NodesX *nodesx,WaysX *waysx)
{
 int i,duplicate=0;

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

 for(i=1;i<segmentsx->number;i++)
   {
    if(segmentsx->sdata[i]->node1==segmentsx->sdata[i-1]->node1 &&
       segmentsx->sdata[i]->node2==segmentsx->sdata[i-1]->node2 &&
       segmentsx->sdata[i]->segment.node1==segmentsx->sdata[i-1]->segment.node1 &&
       segmentsx->sdata[i]->segment.node2==segmentsx->sdata[i-1]->segment.node2 &&
       segmentsx->sdata[i]->segment.distance==segmentsx->sdata[i-1]->segment.distance)
      {
       WayX *wayx1=LookupWayX(waysx,segmentsx->sdata[i-1]->segment.way);
       WayX *wayx2=LookupWayX(waysx,segmentsx->sdata[i]->segment.way);

       if(wayx1==wayx2 ||
          (wayx1->way.type==wayx2->way.type && wayx1->way.allow==wayx2->way.allow && wayx1->way.limit==wayx2->way.limit))
         {
          segmentsx->sdata[i-1]->node1=~0;
          segmentsx->sdata[i-1]->node2=~0;

          duplicate++;
         }
      }

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

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


/*++++++++++++++++++++++++++++++++++++++
  Assign the nodes indexes to the segments.

  SegmentsX* segmentsx The set of segments to process.

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

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

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

 /* Index the segments */

 for(i=0;i<nodesx->number;i++)
   {
    SegmentX *segmentx=LookupSegmentX(segmentsx,SEGMENT(nodesx->gdata[i]->node.firstseg));

    do
      {
       if(segmentx->node1==nodesx->gdata[i]->id)
         {
          segmentx->segment.node1|=i;

          if(segmentx->segment.next1==~0)
             segmentx=NULL;
          else
             segmentx=LookupSegmentX(segmentsx,segmentx->segment.next1);
         }
       else
         {
          segmentx->segment.node2|=i;

          if(segmentx->segment.next2==~0)
             segmentx=NULL;
          else
             segmentx=LookupSegmentX(segmentsx,segmentx->segment.next2);
         }
      }
    while(segmentx);

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

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