trunk/src/segmentsx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/segmentsx.c,v 1.27 2009-07-12 09:01:48 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 <stdlib.h>
#include <stdio.h>

#include "types.h"
#include "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"
#include "nodes.h"
#include "segments.h"
#include "ways.h"


/* Constants */

/*+ The array size increment for SegmentsX (UK is ~14.1M raw segments, this is ~53 increments). +*/
#define INCREMENT_SEGMENTSX (256*1024)


/* Local Functions */

static int sort_by_id_and_distance(SegmentX **a,SegmentX **b);
static distance_t DistanceX(NodeX *nodex1,NodeX *nodex2);


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

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

SegmentsX *NewSegmentList(void)
{
 SegmentsX *segmentsx;

 segmentsx=(SegmentsX*)calloc(1,sizeof(SegmentsX));

 segmentsx->row=-1;

 return(segmentsx);
}


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

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

void FreeSegmentList(SegmentsX *segmentsx)
{
 if(segmentsx->xdata)
   {
    int i;
    for(i=0;i<=segmentsx->row;i++)
       free(segmentsx->xdata[i]);
    free(segmentsx->xdata);
   }

 if(segmentsx->ndata)
    free(segmentsx->ndata);

 if(segmentsx->sdata)
    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)
{
 index_t i;
 int fd;
 Segments *segments=calloc(1,sizeof(Segments));

 assert(segmentsx->sorted);     /* Must be sorted */
 assert(segmentsx->sdata);      /* Must have sdata filled in */

 printf("Writing Segments: Segments=0");
 fflush(stdout);

 /* 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<segments->number;i++)
   {
    WriteFile(fd,&segmentsx->sdata[i],sizeof(Segment));

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

 printf("\rWrote Segments: Segments=%d  \n",segments->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 */
 assert(segmentsx->ndata);      /* Must have ndata filled in */

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

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

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

 return(NULL);

 found:

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

 return(&segmentsx->ndata[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->ndata)==segmentsx->number)
    return(NULL);

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

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

  SegmentsX* segmentsx The set of segments to process.

  way_t way The way that the segment belongs to.

  node_t node1 The first node in the segment.

  node_t node2 The second node in the segment.

  distance_t distance The distance between the nodes (or just the flags).
  ++++++++++++++++++++++++++++++++++++++*/

void AppendSegment(SegmentsX* segmentsx,way_t way,node_t node1,node_t node2,distance_t distance)
{
 /* Check that the array has enough space. */

 if(segmentsx->row==-1 || segmentsx->col==INCREMENT_SEGMENTSX)
   {
    segmentsx->row++;
    segmentsx->col=0;

    if((segmentsx->row%16)==0)
       segmentsx->xdata=(SegmentX**)realloc((void*)segmentsx->xdata,(segmentsx->row+16)*sizeof(SegmentX*));

    segmentsx->xdata[segmentsx->row]=(SegmentX*)malloc(INCREMENT_SEGMENTSX*sizeof(SegmentX));
   }

 /* Insert the segment */

 segmentsx->xdata[segmentsx->row][segmentsx->col].way=way;
 segmentsx->xdata[segmentsx->row][segmentsx->col].node1=node1;
 segmentsx->xdata[segmentsx->row][segmentsx->col].node2=node2;
 segmentsx->xdata[segmentsx->row][segmentsx->col].distance=distance;

 segmentsx->col++;

 segmentsx->sorted=0;
}


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

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

void SortSegmentList(SegmentsX* segmentsx)
{
 index_t i;

 assert(segmentsx->xdata);      /* Must have xdata filled in */

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

 /* Allocate the array of pointers and sort them */

 segmentsx->ndata=(SegmentX**)realloc(segmentsx->ndata,(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col)*sizeof(SegmentX*));

 segmentsx->number=0;

 for(i=0;i<(segmentsx->row*INCREMENT_SEGMENTSX+segmentsx->col);i++)
    if(segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX].node1!=NO_NODE)
      {
       segmentsx->ndata[segmentsx->number]=&segmentsx->xdata[i/INCREMENT_SEGMENTSX][i%INCREMENT_SEGMENTSX];
       segmentsx->number++;
      }

 qsort(segmentsx->ndata,segmentsx->number,sizeof(SegmentX*),(int (*)(const void*,const void*))sort_by_id_and_distance);

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

 segmentsx->sorted=1;
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the segments into id order and then distance order.

  int sort_by_id_and_distance Returns the comparison of the node fields.

  SegmentX **a The first Segment.

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

static int sort_by_id_and_distance(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=DISTANCE((*a)->distance);
       distance_t b_distance=DISTANCE((*b)->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).

  NodesX *nodesx The nodes to check.

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

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

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 printf("Checking: Segments=0 Duplicate=0 Loop=0 Missing-Node=0");
 fflush(stdout);

 for(i=0;i<segmentsx->number;i++)
   {
    if(i && segmentsx->ndata[i]->node1==segmentsx->ndata[i-1]->node1 &&
            segmentsx->ndata[i]->node2==segmentsx->ndata[i-1]->node2)
      {
       duplicate++;
       segmentsx->ndata[i-1]->node1=NO_NODE;
      }
    else if(segmentsx->ndata[i]->node1==segmentsx->ndata[i]->node2)
      {
       loop++;
       segmentsx->ndata[i]->node1=NO_NODE;
      }
    else if(!FindNodeX(nodesx,segmentsx->ndata[i]->node1) ||
            !FindNodeX(nodesx,segmentsx->ndata[i]->node2))
      {
       missing++;
       segmentsx->ndata[i]->node1=NO_NODE;
      }

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

 printf("\rChecked: Segments=%d Duplicate=%d Loop=%d Missing-Node=%d \n",segmentsx->number,duplicate,loop,missing);
 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)
{
 index_t i;

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 printf("Measuring Segments: Segments=0");
 fflush(stdout);

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

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

    segmentsx->ndata[i]->distance|=DISTANCE(DistanceX(*nodex1,*nodex2));

    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.
  ++++++++++++++++++++++++++++++++++++++*/

void RotateSegments(SegmentsX* segmentsx)
{
 index_t i;
 int rotated=0;

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 printf("Rotating Segments: Segments=0 Rotated=0");
 fflush(stdout);

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

       if(segmentsx->ndata[i]->distance&(ONEWAY_2TO1|ONEWAY_1TO2))
          segmentsx->ndata[i]->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.

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

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

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 printf("Deduplicating Segments: Segments=0 Duplicate=0");
 fflush(stdout);

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

       if(!WaysCompare(wayx1->way,wayx2->way))
         {
          segmentsx->ndata[i-1]->node1=NO_NODE;
          segmentsx->ndata[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);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the real segments data.

  SegmentsX* segmentsx The set of segments to use.

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

void CreateRealSegments(SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i;

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 printf("Creating Real Segments: Segments=0");
 fflush(stdout);

 /* Allocate the memory */

 segmentsx->sdata=(Segment*)malloc(segmentsx->number*sizeof(Segment));

 /* Loop through and allocate. */

 for(i=0;i<segmentsx->number;i++)
   {
    WayX *wayx=FindWayX(waysx,segmentsx->ndata[i]->way);

    segmentsx->sdata[i].node1=0;
    segmentsx->sdata[i].node2=0;
    segmentsx->sdata[i].next2=NO_NODE;
    segmentsx->sdata[i].way=IndexWayInWaysX(waysx,wayx);
    segmentsx->sdata[i].distance=segmentsx->ndata[i]->distance;

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

 printf("\rCreating Real Segments: Segments=%d \n",segmentsx->number);
 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)
{
 index_t i;

 assert(segmentsx->sorted);     /* Must be sorted */
 assert(segmentsx->ndata);      /* Must have ndata filled in */
 assert(segmentsx->sdata);      /* Must have sdata filled in */
 assert(nodesx->sorted);        /* Must be sorted */
 assert(nodesx->gdata);         /* Must have gdata filled in */

 printf("Indexing Nodes: Nodes=0");
 fflush(stdout);

 /* Index the segments */

 for(i=0;i<nodesx->number;i++)
   {
    NodeX **nodex=FindNodeX(nodesx,nodesx->gdata[i]->id);
    Node   *node =&nodesx->ndata[nodex-nodesx->idata];
    index_t index=SEGMENT(node->firstseg);

    do
      {
       if(segmentsx->ndata[index]->node1==nodesx->gdata[i]->id)
         {
          segmentsx->sdata[index].node1=i;

          index++;

          if(index>=segmentsx->number || segmentsx->ndata[index]->node1!=nodesx->gdata[i]->id)
             break;
         }
       else
         {
          segmentsx->sdata[index].node2=i;

          if(segmentsx->sdata[index].next2==NO_NODE)
             break;
          else
             index=segmentsx->sdata[index].next2;
         }
      }
    while(1);

    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.
  ++++++++++++++++++++++++++++++++++++++*/

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