trunk/src/nodes.c

/***************************************
 $Header: /home/amb/CVS/routino/src/nodes.c,v 1.17 2009-02-04 18:23:32 amb Exp $

 Node 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 <stdlib.h>

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


/* Constants */

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

/*+ The latitude and longitude conversion factor from float to integer. +*/
#define LAT_LONG_SCALE  (1024*1024)

/*+ The latitude and longitude integer range within each bin. +*/
#define LAT_LONG_BIN    65536

/*+ The latitude and longitude number of bins per degree. +*/
#define LAT_LONG_DEGBIN (LAT_LONG_SCALE/LAT_LONG_BIN)


/* Functions */

static int sort_by_id(NodeX **a,NodeX **b);
static int sort_by_lat_long(NodeX *a,NodeX *b);


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

  Nodes* LoadNodeList Returns the node list.

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

Nodes *LoadNodeList(const char *filename)
{
 void *data;
 Nodes *nodes;

 nodes=(Nodes*)malloc(sizeof(Nodes));

 data=MapFile(filename);

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

 *nodes=*((Nodes*)data);

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

 nodes->data=data;
 nodes->offsets=(index_t*)(data+(off_t)nodes->offsets);
 nodes->nodes=(Node*)(data+(off_t)nodes->nodes);

 return(nodes);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a node given its latitude and longitude.

  Node *FindNode Returns the node.

  Nodes* nodes The set of nodes to search.

  float latitude The latitude to look for.

  float longitude The longitude to look for.
  ++++++++++++++++++++++++++++++++++++++*/

Node *FindNode(Nodes* nodes,float latitude,float longitude)
{
 int32_t latbin=(int32_t)((latitude-nodes->latzero)*LAT_LONG_DEGBIN);
 int32_t lonbin=(int32_t)((longitude-nodes->lonzero)*LAT_LONG_DEGBIN);
 int llbin=lonbin*nodes->latbins+latbin;
 int i,best;
 float distance=1000000;

 for(i=nodes->offsets[llbin];i<nodes->offsets[llbin+1];i++)
   {
    float lat=nodes->latzero+(double)latbin/(double)LAT_LONG_DEGBIN+(double)nodes->nodes[i].latoffset/(double)LAT_LONG_SCALE;
    float lon=nodes->lonzero+(double)lonbin/(double)LAT_LONG_DEGBIN+(double)nodes->nodes[i].lonoffset/(double)LAT_LONG_SCALE;

    float dist=Distance(lat,lon,latitude,longitude);

    if(dist<distance)
      {best=i; distance=dist;}
   }

 return(&nodes->nodes[best]);
}


/*++++++++++++++++++++++++++++++++++++++
  Get the latitude and longitude associated with a node.

  Nodes *nodes The set of nodes.

  Node *node The node.

  float *latitude Returns the latitude.

  float *longitude Returns the logitude.
  ++++++++++++++++++++++++++++++++++++++*/

void GetLatLong(Nodes *nodes,Node *node,float *latitude,float *longitude)
{
 index_t index=IndexNode(nodes,node);
 int latbin=-1,lonbin=-1;
 int start,end,mid;

 /* Binary search - search key closest below is required.
  *
  *  # <- start  |  Check mid and move start or end if it doesn't match
  *  #           |
  *  #           |  Since an inexact match is wanted we must set end=mid-1
  *  # <- mid    |  or start=mid 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.
  */

 /* Search for longitude */

 start=0;
 end=nodes->lonbins-1;

 do
   {
    mid=(start+end)/2;                                 /* Choose mid point */

    if(nodes->offsets[nodes->latbins*mid]<index)       /* Mid point is too low */
       start=mid;
    else if(nodes->offsets[nodes->latbins*mid]>index)  /* Mid point is too high */
       end=mid-1;
    else                                               /* Mid point is correct */
      {lonbin=mid;break;}
   }
 while((end-start)>1);

 if(lonbin==-1)
   {
    if(nodes->offsets[nodes->latbins*end]>index)
       lonbin=start;
    else
       lonbin=end;
   }

 while(lonbin<nodes->lonbins && nodes->offsets[lonbin*nodes->latbins]==nodes->offsets[(lonbin+1)*nodes->latbins])
    lonbin++;

 /* Search for latitude */

 start=0;
 end=nodes->latbins-1;

 do
   {
    mid=(start+end)/2;                                       /* Choose mid point */

    if(nodes->offsets[lonbin*nodes->latbins+mid]<index)      /* Mid point is too low */
       start=mid;
    else if(nodes->offsets[lonbin*nodes->latbins+mid]>index) /* Mid point is too high */
       end=mid-1;
    else                                                     /* Mid point is correct */
      {latbin=mid;break;}
   }
 while((end-start)>1);

 if(latbin==-1)
   {
    if(nodes->offsets[lonbin*nodes->latbins+end]>index)
       latbin=start;
    else
       latbin=end;
   }

 while(latbin<nodes->latbins && nodes->offsets[lonbin*nodes->latbins+latbin]==nodes->offsets[lonbin*nodes->latbins+latbin+1])
    latbin++;

 /* Return the values */

 *latitude =nodes->latzero+(double)latbin/(double)LAT_LONG_DEGBIN+(double)node->latoffset/(double)LAT_LONG_SCALE;
 *longitude=nodes->lonzero+(double)lonbin/(double)LAT_LONG_DEGBIN+(double)node->lonoffset/(double)LAT_LONG_SCALE;
}


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

  NodesX *NewNodeList Returns the node list.
  ++++++++++++++++++++++++++++++++++++++*/

NodesX *NewNodeList(void)
{
 NodesX *nodesx;

 nodesx=(NodesX*)malloc(sizeof(NodesX));

 nodesx->alloced=INCREMENT_NODES;
 nodesx->number=0;
 nodesx->sorted=0;

 nodesx->gdata=(NodeX*)malloc(nodesx->alloced*sizeof(NodeX));
 nodesx->idata=NULL;

 return(nodesx);
}


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

  NodesX* nodesx The set of nodes to save.

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

void SaveNodeList(NodesX* nodesx,const char *filename)
{
 int i;
 int fd;
 Nodes *nodes=calloc(1,sizeof(Nodes));
 index_t *offsets;
 float lat_min,lat_max,lon_min,lon_max;
 int latbins,lonbins,latlonbin;

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

 /* Work out the offsets (careful with the rounding) */

 lat_min=-180.0+(float)((int32_t)((180.0+nodesx->lat_min)*LAT_LONG_DEGBIN))/LAT_LONG_DEGBIN;
 lon_min=-180.0+(float)((int32_t)((180.0+nodesx->lon_min)*LAT_LONG_DEGBIN))/LAT_LONG_DEGBIN;
 lat_max=-180.0+(float)((int32_t)((180.0+nodesx->lat_max)*LAT_LONG_DEGBIN+1))/LAT_LONG_DEGBIN;
 lon_max=-180.0+(float)((int32_t)((180.0+nodesx->lon_max)*LAT_LONG_DEGBIN+1))/LAT_LONG_DEGBIN;

 latbins=(lat_max-lat_min)*LAT_LONG_DEGBIN;
 lonbins=(lon_max-lon_min)*LAT_LONG_DEGBIN;

 offsets=malloc((latbins*lonbins+1)*sizeof(index_t));

 latlonbin=0;

 for(i=0;i<nodesx->number;i++)
   {
    int32_t latbin=(int32_t)((nodesx->gdata[i].latitude-lat_min)*LAT_LONG_DEGBIN);
    int32_t lonbin=(int32_t)((nodesx->gdata[i].longitude-lon_min)*LAT_LONG_DEGBIN);
    int llbin=lonbin*latbins+latbin;

    for(;latlonbin<=llbin;latlonbin++)
       offsets[latlonbin]=i;
   }

 for(;latlonbin<=(latbins*lonbins);latlonbin++)
    offsets[latlonbin]=nodesx->number;

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

 nodes->number=nodesx->number;

 nodes->latbins=latbins;
 nodes->lonbins=lonbins;

 nodes->latzero=lat_min;
 nodes->lonzero=lon_min;

 nodes->data=NULL;
 nodes->offsets=(void*)sizeof(Nodes);
 nodes->nodes=(void*)sizeof(Nodes)+(latbins*lonbins+1)*sizeof(index_t);

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

 fd=OpenFile(filename);

 WriteFile(fd,nodes,sizeof(Nodes));

 WriteFile(fd,offsets,(latbins*lonbins+1)*sizeof(index_t));

 for(i=0;i<nodesx->number;i++)
    WriteFile(fd,&nodesx->gdata[i].node,sizeof(Node));

 CloseFile(fd);

 /* Free the fake Nodes */

 free(nodes);
 free(offsets);
}


/*++++++++++++++++++++++++++++++++++++++
  Find a particular node.

  NodeX *FindNodeX Returns the extended node with the specified id.

  NodesX* nodesx The set of nodes to process.

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

NodeX *FindNodeX(NodesX* nodesx,node_t id)
{
 int start=0;
 int end=nodesx->number-1;
 int mid;

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

       if(nodesx->idata[mid]->id<id)      /* Mid point is too low */
          start=mid+1;
       else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
          end=mid-1;
       else                               /* Mid point is correct */
          return(nodesx->idata[mid]);
      }
    while((end-start)>1);

    if(nodesx->idata[start]->id==id)      /* Start is correct */
       return(nodesx->idata[start]);

    if(nodesx->idata[end]->id==id)        /* End is correct */
       return(nodesx->idata[end]);
   }

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Append a node to a newly created node list (unsorted).

  Node *AppendNode Return a pointer to the new node.

  NodesX* nodesx The set of nodes to process.

  node_t id The node identification.

  float latitude The latitude of the node.

  float longitude The longitude of the node.
  ++++++++++++++++++++++++++++++++++++++*/

Node *AppendNode(NodesX* nodesx,node_t id,float latitude,float longitude)
{
 /* Check that the array has enough space. */

 if(nodesx->number==nodesx->alloced)
   {
    nodesx->alloced+=INCREMENT_NODES;

    nodesx->gdata=(NodeX*)realloc((void*)nodesx->gdata,nodesx->alloced*sizeof(NodeX));
   }

 /* Insert the node */

 nodesx->gdata[nodesx->number].id=id;
 nodesx->gdata[nodesx->number].super=0;
 nodesx->gdata[nodesx->number].latitude=latitude;
 nodesx->gdata[nodesx->number].longitude=longitude;

 nodesx->number++;

 nodesx->sorted=0;

 return(&nodesx->gdata[nodesx->number-1].node);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the node list.

  NodesX* nodesx The set of nodes to process.
  ++++++++++++++++++++++++++++++++++++++*/

void SortNodeList(NodesX* nodesx)
{
 int i;

 qsort(nodesx->gdata,nodesx->number,sizeof(NodeX),(int (*)(const void*,const void*))sort_by_lat_long);

 while(nodesx->gdata[nodesx->number-1].id==~0)
    nodesx->number--;

 nodesx->idata=malloc(nodesx->number*sizeof(NodeX*));

 nodesx->lat_min=90;
 nodesx->lat_max=-90;
 nodesx->lon_min=180;
 nodesx->lon_max=-180;

 for(i=0;i<nodesx->number;i++)
   {
    int32_t lat=(int32_t)(nodesx->gdata[i].latitude*LAT_LONG_SCALE);
    int32_t lon=(int32_t)(nodesx->gdata[i].longitude*LAT_LONG_SCALE);

    nodesx->gdata[i].node.latoffset=lat%LAT_LONG_BIN;
    nodesx->gdata[i].node.lonoffset=lon%LAT_LONG_BIN;

    if(nodesx->gdata[i].latitude<nodesx->lat_min)
       nodesx->lat_min=nodesx->gdata[i].latitude;
    if(nodesx->gdata[i].latitude>nodesx->lat_max)
       nodesx->lat_max=nodesx->gdata[i].latitude;
    if(nodesx->gdata[i].longitude<nodesx->lon_min)
       nodesx->lon_min=nodesx->gdata[i].longitude;
    if(nodesx->gdata[i].longitude>nodesx->lon_max)
       nodesx->lon_max=nodesx->gdata[i].longitude;

    nodesx->idata[i]=&nodesx->gdata[i];
   }

 qsort(nodesx->idata,nodesx->number,sizeof(NodeX*),(int (*)(const void*,const void*))sort_by_id);

 nodesx->sorted=1;
}


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

  int sort_by_id Returns the comparison of the id fields.

  NodeX **a The first Node.

  NodeX **b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_id(NodeX **a,NodeX **b)
{
 node_t a_id=(*a)->id;
 node_t b_id=(*b)->id;

 if(a_id<b_id)
    return(-1);
 else
    return(1);
}


/*++++++++++++++++++++++++++++++++++++++
  Sort the nodes into latitude and longitude order.

  int sort_by_lat_long Returns the comparison of the latitude and longitude fields.

  NodeX *a The first Node.

  NodeX *b The second Node.
  ++++++++++++++++++++++++++++++++++++++*/

static int sort_by_lat_long(NodeX *a,NodeX *b)
{
 node_t a_id=a->id;
 node_t b_id=b->id;
 int32_t a_lat=(int32_t)(a->latitude*LAT_LONG_DEGBIN);
 int32_t a_lon=(int32_t)(a->longitude*LAT_LONG_DEGBIN);
 int32_t b_lat=(int32_t)(b->latitude*LAT_LONG_DEGBIN);
 int32_t b_lon=(int32_t)(b->longitude*LAT_LONG_DEGBIN);

 if(a_id==~0)
    return(1);
 if(b_id==~0)
    return(-1);

 if(a_lon<b_lon)
    return(-1);
 else if(a_lon>b_lon)
    return(1);
 else
   {
    if(a_lat<b_lat)
       return(-1);
    else if(a_lat>b_lat)
       return(1);
    else
       return(0);
   }
}


/*++++++++++++++++++++++++++++++++++++++
  Remove any nodes that are not part of a highway.

  NodesX *nodesx The complete node list.

  SegmentsX *segmentsx The list of segments.
  ++++++++++++++++++++++++++++++++++++++*/

void RemoveNonHighwayNodes(NodesX *nodesx,SegmentsX *segmentsx)
{
 int i;
 int highway=0,nothighway=0;

 for(i=0;i<nodesx->number;i++)
   {
    if(FindFirstSegmentX(segmentsx,nodesx->gdata[i].id))
       highway++;
    else
      {
       nodesx->gdata[i].id=~0;
       nothighway++;
      }

    if(!((i+1)%10000))
      {
       printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
       fflush(stdout);
      }
   }

 printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d  \n",nodesx->number,highway,nothighway);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Fix the node indexes to the segments.

  NodesX* nodesx The set of nodes to process.

  SegmentsX *segmentsx The list of segments to use.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

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

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

 for(i=0;i<nodesx->number;i++)
   {
    SegmentX *firstseg=FindFirstSegmentX(segmentsx,nodesx->gdata[i].id);

    nodesx->gdata[i].node.firstseg=IndexSegmentX(segmentsx,firstseg);

    if(nodesx->gdata[i].super==iteration)
       nodesx->gdata[i].node.firstseg|=SUPER_FLAG;

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

 printf("\rFixed Nodes: Nodes=%d \n",nodesx->number);
 fflush(stdout);
}
1	amb	2	/***************************************
2	amb	99	$Header: /home/amb/CVS/routino/src/nodes.c,v 1.17 2009-02-04 18:23:32 amb Exp $
3	amb	2
4			Node data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8	amb	4	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	2	It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15	amb	8	#include <assert.h>
16	amb	2	#include <stdlib.h>
17
18			#include "functions.h"
19	amb	17	#include "nodes.h"
20	amb	2
21
22	amb	96	/* Constants */
23
24			/+ The array size increment for nodes - expect ~8,000,000 nodes. +/
25			#define INCREMENT_NODES 1024*1024
26
27	amb	99	/+ The latitude and longitude conversion factor from float to integer. +/
28			#define LAT_LONG_SCALE (1024*1024)
29	amb	96
30	amb	99	/+ The latitude and longitude integer range within each bin. +/
31			#define LAT_LONG_BIN 65536
32
33			/+ The latitude and longitude number of bins per degree. +/
34			#define LAT_LONG_DEGBIN (LAT_LONG_SCALE/LAT_LONG_BIN)
35
36
37	amb	17	/* Functions */
38	amb	2
39	amb	99	static int sort_by_id(NodeX a,NodeX b);
40			static int sort_by_lat_long(NodeX a,NodeX b);
41	amb	2
42	amb	8
43	amb	17	/*++++++++++++++++++++++++++++++++++++++
44	amb	2	Load in a node list from a file.
45
46	amb	19	Nodes* LoadNodeList Returns the node list.
47	amb	17
48	amb	2	const char *filename The name of the file to load.
49			++++++++++++++++++++++++++++++++++++++*/
50
51	amb	19	Nodes LoadNodeList(const char filename)
52	amb	2	{
53	amb	88	void *data;
54			Nodes *nodes;
55
56			nodes=(Nodes*)malloc(sizeof(Nodes));
57
58			data=MapFile(filename);
59
60			/* Copy the Nodes structure from the loaded data */
61
62			nodes=((Nodes*)data);
63
64			/* Adjust the pointers in the Nodes structure. */
65
66	amb	99	nodes->data=data;
67			nodes->offsets=(index_t*)(data+(off_t)nodes->offsets);
68	amb	88	nodes->nodes=(Node*)(data+(off_t)nodes->nodes);
69
70			return(nodes);
71	amb	2	}
72
73
74			/*++++++++++++++++++++++++++++++++++++++
75	amb	99	Find a node given its latitude and longitude.
76
77			Node *FindNode Returns the node.
78
79			Nodes* nodes The set of nodes to search.
80
81			float latitude The latitude to look for.
82
83			float longitude The longitude to look for.
84			++++++++++++++++++++++++++++++++++++++*/
85
86			Node FindNode(Nodes nodes,float latitude,float longitude)
87			{
88			int32_t latbin=(int32_t)((latitude-nodes->latzero)*LAT_LONG_DEGBIN);
89			int32_t lonbin=(int32_t)((longitude-nodes->lonzero)*LAT_LONG_DEGBIN);
90			int llbin=lonbin*nodes->latbins+latbin;
91			int i,best;
92			float distance=1000000;
93
94			for(i=nodes->offsets[llbin];i<nodes->offsets[llbin+1];i++)
95			{
96			float lat=nodes->latzero+(double)latbin/(double)LAT_LONG_DEGBIN+(double)nodes->nodes[i].latoffset/(double)LAT_LONG_SCALE;
97			float lon=nodes->lonzero+(double)lonbin/(double)LAT_LONG_DEGBIN+(double)nodes->nodes[i].lonoffset/(double)LAT_LONG_SCALE;
98
99			float dist=Distance(lat,lon,latitude,longitude);
100
101			if(dist<distance)
102			{best=i; distance=dist;}
103			}
104
105			return(&nodes->nodes[best]);
106			}
107
108
109			/*++++++++++++++++++++++++++++++++++++++
110			Get the latitude and longitude associated with a node.
111
112			Nodes *nodes The set of nodes.
113
114			Node *node The node.
115
116			float *latitude Returns the latitude.
117
118			float *longitude Returns the logitude.
119			++++++++++++++++++++++++++++++++++++++*/
120
121			void GetLatLong(Nodes nodes,Node node,float latitude,float longitude)
122			{
123			index_t index=IndexNode(nodes,node);
124			int latbin=-1,lonbin=-1;
125			int start,end,mid;
126
127			/* Binary search - search key closest below is required.
128			*
129			* # <- start \| Check mid and move start or end if it doesn't match
130			* # \|
131			* # \| Since an inexact match is wanted we must set end=mid-1
132			* # <- mid \| or start=mid because we know that mid doesn't match.
133			* # \|
134			* # \| Eventually either end=start or end=start+1 and one of
135			* # <- end \| start or end is the wanted one.
136			*/
137
138			/* Search for longitude */
139
140			start=0;
141			end=nodes->lonbins-1;
142
143			do
144			{
145			mid=(start+end)/2; /* Choose mid point */
146
147			if(nodes->offsets[nodes->latbinsmid]<index) / Mid point is too low */
148			start=mid;
149			else if(nodes->offsets[nodes->latbinsmid]>index) / Mid point is too high */
150			end=mid-1;
151			else /* Mid point is correct */
152			{lonbin=mid;break;}
153			}
154			while((end-start)>1);
155
156			if(lonbin==-1)
157			{
158			if(nodes->offsets[nodes->latbins*end]>index)
159			lonbin=start;
160			else
161			lonbin=end;
162			}
163
164			while(lonbin<nodes->lonbins && nodes->offsets[lonbinnodes->latbins]==nodes->offsets[(lonbin+1)nodes->latbins])
165			lonbin++;
166
167			/* Search for latitude */
168
169			start=0;
170			end=nodes->latbins-1;
171
172			do
173			{
174			mid=(start+end)/2; /* Choose mid point */
175
176			if(nodes->offsets[lonbinnodes->latbins+mid]<index) / Mid point is too low */
177			start=mid;
178			else if(nodes->offsets[lonbinnodes->latbins+mid]>index) / Mid point is too high */
179			end=mid-1;
180			else /* Mid point is correct */
181			{latbin=mid;break;}
182			}
183			while((end-start)>1);
184
185			if(latbin==-1)
186			{
187			if(nodes->offsets[lonbin*nodes->latbins+end]>index)
188			latbin=start;
189			else
190			latbin=end;
191			}
192
193			while(latbin<nodes->latbins && nodes->offsets[lonbinnodes->latbins+latbin]==nodes->offsets[lonbinnodes->latbins+latbin+1])
194			latbin++;
195
196			/* Return the values */
197
198			*latitude =nodes->latzero+(double)latbin/(double)LAT_LONG_DEGBIN+(double)node->latoffset/(double)LAT_LONG_SCALE;
199			*longitude=nodes->lonzero+(double)lonbin/(double)LAT_LONG_DEGBIN+(double)node->lonoffset/(double)LAT_LONG_SCALE;
200			}
201
202
203			/*++++++++++++++++++++++++++++++++++++++
204	amb	97	Allocate a new node list.
205
206			NodesX *NewNodeList Returns the node list.
207			++++++++++++++++++++++++++++++++++++++*/
208
209			NodesX *NewNodeList(void)
210			{
211			NodesX *nodesx;
212
213			nodesx=(NodesX*)malloc(sizeof(NodesX));
214
215			nodesx->alloced=INCREMENT_NODES;
216			nodesx->number=0;
217			nodesx->sorted=0;
218
219	amb	99	nodesx->gdata=(NodeX)malloc(nodesx->allocedsizeof(NodeX));
220			nodesx->idata=NULL;
221	amb	97
222			return(nodesx);
223			}
224
225
226			/*++++++++++++++++++++++++++++++++++++++
227	amb	2	Save the node list to a file.
228
229	amb	97	NodesX* nodesx The set of nodes to save.
230	amb	17
231	amb	2	const char *filename The name of the file to save.
232			++++++++++++++++++++++++++++++++++++++*/
233
234	amb	97	void SaveNodeList(NodesX* nodesx,const char *filename)
235	amb	2	{
236	amb	88	int i;
237			int fd;
238			Nodes *nodes=calloc(1,sizeof(Nodes));
239	amb	99	index_t *offsets;
240			float lat_min,lat_max,lon_min,lon_max;
241			int latbins,lonbins,latlonbin;
242	amb	2
243	amb	97	assert(nodesx->sorted); /* Must be sorted */
244	amb	2
245	amb	99	/* Work out the offsets (careful with the rounding) */
246
247			lat_min=-180.0+(float)((int32_t)((180.0+nodesx->lat_min)*LAT_LONG_DEGBIN))/LAT_LONG_DEGBIN;
248			lon_min=-180.0+(float)((int32_t)((180.0+nodesx->lon_min)*LAT_LONG_DEGBIN))/LAT_LONG_DEGBIN;
249			lat_max=-180.0+(float)((int32_t)((180.0+nodesx->lat_max)*LAT_LONG_DEGBIN+1))/LAT_LONG_DEGBIN;
250			lon_max=-180.0+(float)((int32_t)((180.0+nodesx->lon_max)*LAT_LONG_DEGBIN+1))/LAT_LONG_DEGBIN;
251
252			latbins=(lat_max-lat_min)*LAT_LONG_DEGBIN;
253			lonbins=(lon_max-lon_min)*LAT_LONG_DEGBIN;
254
255			offsets=malloc((latbinslonbins+1)sizeof(index_t));
256
257			latlonbin=0;
258
259			for(i=0;i<nodesx->number;i++)
260			{
261			int32_t latbin=(int32_t)((nodesx->gdata[i].latitude-lat_min)*LAT_LONG_DEGBIN);
262			int32_t lonbin=(int32_t)((nodesx->gdata[i].longitude-lon_min)*LAT_LONG_DEGBIN);
263			int llbin=lonbin*latbins+latbin;
264
265			for(;latlonbin<=llbin;latlonbin++)
266			offsets[latlonbin]=i;
267			}
268
269			for(;latlonbin<=(latbins*lonbins);latlonbin++)
270			offsets[latlonbin]=nodesx->number;
271
272	amb	88	/* Fill in a Nodes structure with the offset of the real data in the file after
273			the Node structure itself. */
274
275	amb	97	nodes->number=nodesx->number;
276	amb	99
277			nodes->latbins=latbins;
278			nodes->lonbins=lonbins;
279
280			nodes->latzero=lat_min;
281			nodes->lonzero=lon_min;
282
283	amb	88	nodes->data=NULL;
284	amb	99	nodes->offsets=(void*)sizeof(Nodes);
285			nodes->nodes=(void)sizeof(Nodes)+(latbinslonbins+1)*sizeof(index_t);
286	amb	88
287			/* Write out the Nodes structure and then the real data. */
288
289			fd=OpenFile(filename);
290
291	amb	97	WriteFile(fd,nodes,sizeof(Nodes));
292	amb	88
293	amb	99	WriteFile(fd,offsets,(latbinslonbins+1)sizeof(index_t));
294
295	amb	97	for(i=0;i<nodesx->number;i++)
296	amb	99	WriteFile(fd,&nodesx->gdata[i].node,sizeof(Node));
297	amb	88
298	amb	97	CloseFile(fd);
299	amb	88
300	amb	89	/* Free the fake Nodes */
301	amb	88
302	amb	19	free(nodes);
303	amb	99	free(offsets);
304	amb	2	}
305
306
307			/*++++++++++++++++++++++++++++++++++++++
308			Find a particular node.
309
310	amb	98	NodeX *FindNodeX Returns the extended node with the specified id.
311	amb	2
312	amb	97	NodesX* nodesx The set of nodes to process.
313	amb	17
314	amb	2	node_t id The node id to look for.
315			++++++++++++++++++++++++++++++++++++++*/
316
317	amb	98	NodeX FindNodeX(NodesX nodesx,node_t id)
318	amb	2	{
319	amb	88	int start=0;
320	amb	97	int end=nodesx->number-1;
321	amb	2	int mid;
322
323			/* Binary search - search key exact match only is required.
324			*
325			* # <- start \| Check mid and move start or end if it doesn't match
326			* # \|
327			* # \| Since an exact match is wanted we can set end=mid-1
328			* # <- mid \| or start=mid+1 because we know that mid doesn't match.
329			* # \|
330			* # \| Eventually either end=start or end=start+1 and one of
331			* # <- end \| start or end is the wanted one.
332			*/
333
334	amb	99	if(end<start) /* There are no nodes */
335	amb	89	return(NULL);
336	amb	99	else if(id<nodesx->idata[start]->id) /* Check key is not before start */
337	amb	89	return(NULL);
338	amb	99	else if(id>nodesx->idata[end]->id) /* Check key is not after end */
339	amb	89	return(NULL);
340	amb	2	else
341			{
342			do
343			{
344	amb	99	mid=(start+end)/2; /* Choose mid point */
345	amb	2
346	amb	99	if(nodesx->idata[mid]->id<id) /* Mid point is too low */
347	amb	2	start=mid+1;
348	amb	99	else if(nodesx->idata[mid]->id>id) /* Mid point is too high */
349	amb	2	end=mid-1;
350	amb	99	else /* Mid point is correct */
351			return(nodesx->idata[mid]);
352	amb	2	}
353			while((end-start)>1);
354
355	amb	99	if(nodesx->idata[start]->id==id) /* Start is correct */
356			return(nodesx->idata[start]);
357	amb	2
358	amb	99	if(nodesx->idata[end]->id==id) /* End is correct */
359			return(nodesx->idata[end]);
360	amb	2	}
361
362	amb	89	return(NULL);
363	amb	2	}
364
365
366			/*++++++++++++++++++++++++++++++++++++++
367			Append a node to a newly created node list (unsorted).
368
369	amb	98	Node *AppendNode Return a pointer to the new node.
370	amb	32
371	amb	97	NodesX* nodesx The set of nodes to process.
372	amb	17
373	amb	2	node_t id The node identification.
374
375	amb	98	float latitude The latitude of the node.
376	amb	2
377	amb	98	float longitude The longitude of the node.
378	amb	2	++++++++++++++++++++++++++++++++++++++*/
379
380	amb	98	Node AppendNode(NodesX nodesx,node_t id,float latitude,float longitude)
381	amb	2	{
382	amb	19	/* Check that the array has enough space. */
383	amb	8
384	amb	97	if(nodesx->number==nodesx->alloced)
385	amb	4	{
386	amb	97	nodesx->alloced+=INCREMENT_NODES;
387	amb	4
388	amb	99	nodesx->gdata=(NodeX)realloc((void)nodesx->gdata,nodesx->alloced*sizeof(NodeX));
389	amb	4	}
390
391			/* Insert the node */
392
393	amb	99	nodesx->gdata[nodesx->number].id=id;
394			nodesx->gdata[nodesx->number].super=0;
395			nodesx->gdata[nodesx->number].latitude=latitude;
396			nodesx->gdata[nodesx->number].longitude=longitude;
397	amb	2
398	amb	97	nodesx->number++;
399	amb	2
400	amb	97	nodesx->sorted=0;
401	amb	32
402	amb	99	return(&nodesx->gdata[nodesx->number-1].node);
403	amb	2	}
404
405
406			/*++++++++++++++++++++++++++++++++++++++
407			Sort the node list.
408	amb	17
409	amb	97	NodesX* nodesx The set of nodes to process.
410	amb	2	++++++++++++++++++++++++++++++++++++++*/
411
412	amb	97	void SortNodeList(NodesX* nodesx)
413	amb	2	{
414	amb	99	int i;
415	amb	40
416	amb	99	qsort(nodesx->gdata,nodesx->number,sizeof(NodeX),(int ()(const void,const void*))sort_by_lat_long);
417
418			while(nodesx->gdata[nodesx->number-1].id==~0)
419	amb	97	nodesx->number--;
420	amb	8
421	amb	99	nodesx->idata=malloc(nodesx->numbersizeof(NodeX));
422
423			nodesx->lat_min=90;
424			nodesx->lat_max=-90;
425			nodesx->lon_min=180;
426			nodesx->lon_max=-180;
427
428			for(i=0;i<nodesx->number;i++)
429			{
430			int32_t lat=(int32_t)(nodesx->gdata[i].latitude*LAT_LONG_SCALE);
431			int32_t lon=(int32_t)(nodesx->gdata[i].longitude*LAT_LONG_SCALE);
432
433			nodesx->gdata[i].node.latoffset=lat%LAT_LONG_BIN;
434			nodesx->gdata[i].node.lonoffset=lon%LAT_LONG_BIN;
435
436			if(nodesx->gdata[i].latitude<nodesx->lat_min)
437			nodesx->lat_min=nodesx->gdata[i].latitude;
438			if(nodesx->gdata[i].latitude>nodesx->lat_max)
439			nodesx->lat_max=nodesx->gdata[i].latitude;
440			if(nodesx->gdata[i].longitude<nodesx->lon_min)
441			nodesx->lon_min=nodesx->gdata[i].longitude;
442			if(nodesx->gdata[i].longitude>nodesx->lon_max)
443			nodesx->lon_max=nodesx->gdata[i].longitude;
444
445			nodesx->idata[i]=&nodesx->gdata[i];
446			}
447
448			qsort(nodesx->idata,nodesx->number,sizeof(NodeX),(int ()(const void,const void))sort_by_id);
449
450	amb	97	nodesx->sorted=1;
451	amb	2	}
452
453
454			/*++++++++++++++++++++++++++++++++++++++
455			Sort the nodes into id order.
456
457			int sort_by_id Returns the comparison of the id fields.
458
459	amb	99	NodeX **a The first Node.
460
461			NodeX **b The second Node.
462			++++++++++++++++++++++++++++++++++++++*/
463
464			static int sort_by_id(NodeX a,NodeX b)
465			{
466			node_t a_id=(*a)->id;
467			node_t b_id=(*b)->id;
468
469			if(a_id<b_id)
470			return(-1);
471			else
472			return(1);
473			}
474
475
476			/*++++++++++++++++++++++++++++++++++++++
477			Sort the nodes into latitude and longitude order.
478
479			int sort_by_lat_long Returns the comparison of the latitude and longitude fields.
480
481	amb	97	NodeX *a The first Node.
482	amb	2
483	amb	97	NodeX *b The second Node.
484	amb	2	++++++++++++++++++++++++++++++++++++++*/
485
486	amb	99	static int sort_by_lat_long(NodeX a,NodeX b)
487	amb	2	{
488			node_t a_id=a->id;
489			node_t b_id=b->id;
490	amb	99	int32_t a_lat=(int32_t)(a->latitude*LAT_LONG_DEGBIN);
491			int32_t a_lon=(int32_t)(a->longitude*LAT_LONG_DEGBIN);
492			int32_t b_lat=(int32_t)(b->latitude*LAT_LONG_DEGBIN);
493			int32_t b_lon=(int32_t)(b->longitude*LAT_LONG_DEGBIN);
494	amb	2
495	amb	99	if(a_id==~0)
496			return(1);
497			if(b_id==~0)
498	amb	40	return(-1);
499	amb	99
500			if(a_lon<b_lon)
501			return(-1);
502			else if(a_lon>b_lon)
503			return(1);
504	amb	88	else
505	amb	99	{
506			if(a_lat<b_lat)
507			return(-1);
508			else if(a_lat>b_lat)
509			return(1);
510			else
511			return(0);
512			}
513	amb	2	}
514	amb	40
515
516			/*++++++++++++++++++++++++++++++++++++++
517	amb	88	Remove any nodes that are not part of a highway.
518	amb	40
519	amb	97	NodesX *nodesx The complete node list.
520	amb	40
521	amb	97	SegmentsX *segmentsx The list of segments.
522	amb	40	++++++++++++++++++++++++++++++++++++++*/
523
524	amb	97	void RemoveNonHighwayNodes(NodesX nodesx,SegmentsX segmentsx)
525	amb	40	{
526			int i;
527	amb	66	int highway=0,nothighway=0;
528	amb	40
529	amb	97	for(i=0;i<nodesx->number;i++)
530	amb	40	{
531	amb	99	if(FindFirstSegmentX(segmentsx,nodesx->gdata[i].id))
532	amb	89	highway++;
533			else
534	amb	40	{
535	amb	99	nodesx->gdata[i].id=~0;
536	amb	88	nothighway++;
537	amb	40	}
538
539			if(!((i+1)%10000))
540			{
541	amb	66	printf("\rChecking: Nodes=%d Highway=%d not-Highway=%d",i+1,highway,nothighway);
542	amb	40	fflush(stdout);
543			}
544			}
545
546	amb	97	printf("\rChecked: Nodes=%d Highway=%d not-Highway=%d \n",nodesx->number,highway,nothighway);
547	amb	40	fflush(stdout);
548	amb	88	}
549	amb	66
550	amb	88
551			/*++++++++++++++++++++++++++++++++++++++
552			Fix the node indexes to the segments.
553
554	amb	97	NodesX* nodesx The set of nodes to process.
555	amb	88
556	amb	97	SegmentsX *segmentsx The list of segments to use.
557	amb	90
558			int iteration The current super-node / super-segment iteration number.
559	amb	88	++++++++++++++++++++++++++++++++++++++*/
560
561	amb	97	void FixupNodes(NodesX nodesx,SegmentsX segmentsx,int iteration)
562	amb	88	{
563			int i;
564
565	amb	97	assert(nodesx->sorted); /* Must be sorted */
566	amb	88
567	amb	97	for(i=0;i<nodesx->number;i++)
568	amb	88	{
569	amb	99	SegmentX *firstseg=FindFirstSegmentX(segmentsx,nodesx->gdata[i].id);
570	amb	88
571	amb	99	nodesx->gdata[i].node.firstseg=IndexSegmentX(segmentsx,firstseg);
572	amb	88
573	amb	99	if(nodesx->gdata[i].super==iteration)
574			nodesx->gdata[i].node.firstseg\|=SUPER_FLAG;
575	amb	90
576	amb	88	if(!((i+1)%10000))
577			{
578			printf("\rFixing Nodes: Nodes=%d",i+1);
579			fflush(stdout);
580			}
581			}
582
583	amb	97	printf("\rFixed Nodes: Nodes=%d \n",nodesx->number);
584	amb	88	fflush(stdout);
585	amb	40	}