trunk/src/segmentsx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.1 2009-02-07 15:56:50 amb Exp $

 Extended 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 <stdio.h>

#include "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.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);


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