trunk/src/segmentsx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.8 2009-05-14 18:02:30 amb Exp $

 Extended Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#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));

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

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

 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;

 printf("Sorting Segments"); fflush(stdout);

 /* 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!=NO_NODE)
      {
       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;

 printf("\rSorted Segments \n"); fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  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=NO_NODE;
      }
    else if(segmentsx->sdata[i]->node1==segmentsx->sdata[i]->node2)
      {
       loop++;
       segmentsx->sdata[i]->node1=NO_NODE;
      }

    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 || WaysSame(&wayx1->way,&wayx2->way))
         {
          segmentsx->sdata[i-1]->node1=NO_NODE;
          segmentsx->sdata[i-1]->node2=NO_NODE;

          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;

          segmentx++;

          if((*segmentx)->node1!=nodesx->gdata[i]->id || (segmentx-segmentsx->sdata)>=segmentsx->number)
             segmentx=NULL;
         }
       else
         {
          (*segmentx)->segment.node2|=i;

          if((*segmentx)->segment.next2==NO_NODE)
             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)
{
 float dlon = nodex1->longitude - nodex2->longitude;
 float dlat = nodex1->latitude  - nodex2->latitude;

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

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

 a1 = sinf (dlat / 2);
 a2 = sinf (dlon / 2);
 a = (a1 * a1) + cosf (nodex1->latitude) * cosf (nodex2->latitude) * a2 * a2;
 sa = sqrtf (a);
 if (sa <= 1.0)
   {c = 2 * asinf (sa);}
 else
   {c = 2 * asinf (1.0);}
 d = 6378.137 * c;

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