trunk/src/fakes.c

/***************************************
 Fake node and segment generation.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2011 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 "types.h"
#include "nodes.h"
#include "segments.h"

#include "fakes.h"


/*+ The minimum distance along a segment from a node to insert a fake node. (in km). +*/
#define MINSEGMENT 0.005


/*+ A set of fake segments to allow start/finish in the middle of a segment. +*/
static Segment fake_segments[4*NWAYPOINTS+1];

/*+ A set of pointers to the real segments underlying the fake segments. +*/
static index_t real_segments[4*NWAYPOINTS+1];

/*+ A set of fake node latitudes and longitudes. +*/
static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];

/*+ The previous waypoint. +*/
static int prevpoint=0;


/*++++++++++++++++++++++++++++++++++++++
  Create a pair of fake segments corresponding to the given segment split in two.

  index_t CreateFakes Returns the fake node index (or a real one in special cases).

  Nodes *nodes The set of nodes to use.

  Segments *segments The set of segments to use.

  int point Which of the waypoints is this.

  Segment *segment The segment to split.

  index_t node1 The first node at the end of this segment.

  index_t node2 The second node at the end of this segment.

  distance_t dist1 The distance to the first node.

  distance_t dist2 The distance to the second node.
  ++++++++++++++++++++++++++++++++++++++*/

index_t CreateFakes(Nodes *nodes,Segments *segments,int point,Segment *segment,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
{
 index_t fakenode;
 double lat1,lon1,lat2,lon2;

 /* Initialise the segments to fake values */

 fake_segments[4*point-4].node1=NO_NODE;
 fake_segments[4*point-4].node2=NO_NODE;

 fake_segments[4*point-3].node1=NO_NODE;
 fake_segments[4*point-3].node2=NO_NODE;

 fake_segments[4*point-2].node1=NO_NODE;
 fake_segments[4*point-2].node2=NO_NODE;

 fake_segments[4*point-1].node1=NO_NODE;
 fake_segments[4*point-1].node2=NO_NODE;

 /* Check if we are actually close enough to an existing node */

 if(dist1<km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
   {
    prevpoint=point;
    return(node1);
   }

 if(dist2<km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
   {
    prevpoint=point;
    return(node2);
   }

 if(dist1<km_to_distance(MINSEGMENT) && dist2<km_to_distance(MINSEGMENT))
   {
    prevpoint=point;

    if(dist1<dist2)
       return(node1);
    else
       return(node2);
   }

 /* Create the fake node */

 fakenode=NODE_FAKE+point;

 GetLatLong(nodes,node1,&lat1,&lon1);
 GetLatLong(nodes,node2,&lat2,&lon2);

 if(lat1>3 && lat2<-3)
    lat2+=2*M_PI;
 else if(lat1<-3 && lat2>3)
    lat1+=2*M_PI;

 fake_lat[point]=lat1+(lat2-lat1)*(double)dist1/(double)(dist1+dist2);
 fake_lon[point]=lon1+(lon2-lon1)*(double)dist1/(double)(dist1+dist2);

 if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;

 /* Create the first fake segment */

 fake_segments[4*point-4]=*segment;

 fake_segments[4*point-4].node2=fakenode;

 fake_segments[4*point-4].distance=DISTANCE(dist1)|DISTFLAG(segment->distance);

 real_segments[4*point-4]=IndexSegment(segments,segment);

 /* Create the second fake segment */

 fake_segments[4*point-3]=*segment;

 fake_segments[4*point-3].node1=fakenode;

 fake_segments[4*point-3].distance=DISTANCE(dist2)|DISTFLAG(segment->distance);

 real_segments[4*point-3]=IndexSegment(segments,segment);

 /* Create a third fake segment to join adjacent points if both are fake and on the same real segment */

 if(prevpoint>0 && fake_segments[4*prevpoint-4].node1==node1 && fake_segments[4*prevpoint-3].node2==node2)
   {
    if(DISTANCE(dist1)>DISTANCE(fake_segments[4*prevpoint-4].distance)) /* closer to node2 */
      {
       fake_segments[4*point-2]=fake_segments[4*point-4];

       fake_segments[4*point-2].node1=fakenode;

       fake_segments[4*point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4*prevpoint-4].distance))|DISTFLAG(segment->distance);
      }
    else
      {
       fake_segments[4*point-2]=fake_segments[4*point-2];

       fake_segments[4*point-2].node2=fakenode;

       fake_segments[4*point-2].distance=(DISTANCE(fake_segments[4*prevpoint-4].distance)-DISTANCE(dist1))|DISTFLAG(segment->distance);
      }

    real_segments[4*point-2]=IndexSegment(segments,segment);

    fake_segments[4*prevpoint-1]=fake_segments[4*point-2];

    real_segments[4*prevpoint-1]=real_segments[4*point-2];
   }

 /* Return the fake node */

 prevpoint=point;

 return(fakenode);
}


/*++++++++++++++++++++++++++++++++++++++
  Lookup the latitude and longitude of a fake node.

  index_t fakenode The node to lookup.

  double *latitude Returns the latitude

  double *longitude Returns the longitude.
  ++++++++++++++++++++++++++++++++++++++*/

void GetFakeLatLong(index_t fakenode, double *latitude,double *longitude)
{
 index_t whichnode=fakenode-NODE_FAKE;

 *latitude =fake_lat[whichnode];
 *longitude=fake_lon[whichnode];
}


/*++++++++++++++++++++++++++++++++++++++
  Finds the first fake segment associated to a fake node.

  Segment *FirstFakeSegment Returns the first fake segment.

  index_t fakenode The node to lookup.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *FirstFakeSegment(index_t fakenode)
{
 index_t whichnode=fakenode-NODE_FAKE;

 return(&fake_segments[4*whichnode-4]);
}


/*++++++++++++++++++++++++++++++++++++++
  Finds the next (there can only be two) fake segment associated to a fake node.

  Segment *NextFakeSegment Returns the second fake segment.

  Segment *segment The first fake segment.

  index_t fakenode The node to lookup.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *NextFakeSegment(Segment *fakesegment,index_t fakenode)
{
 index_t whichnode=fakenode-NODE_FAKE;

 if(fakesegment==&fake_segments[4*whichnode-4])
    return(&fake_segments[4*whichnode-3]);

 if(fakesegment==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-2].node1!=NO_NODE)
    return(&fake_segments[4*whichnode-2]);

 if(fakesegment==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-1].node1!=NO_NODE)
    return(&fake_segments[4*whichnode-1]);

 if(fakesegment==&fake_segments[4*whichnode-2] && fake_segments[4*whichnode-1].node1!=NO_NODE)
    return(&fake_segments[4*whichnode-1]);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Finds the fake segment between a node and a fake node.

  Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.

  index_t realnode The real node.

  index_t fakenode The fake node.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
{
 index_t whichnode=fakenode-NODE_FAKE;

 if(fake_segments[4*whichnode-4].node1==realnode || fake_segments[4*whichnode-4].node2==realnode)
    return(&fake_segments[4*whichnode-4]);

 if(fake_segments[4*whichnode-3].node1==realnode || fake_segments[4*whichnode-3].node2==realnode)
    return(&fake_segments[4*whichnode-3]);

 if(fake_segments[4*whichnode-2].node1==realnode || fake_segments[4*whichnode-2].node2==realnode)
    return(&fake_segments[4*whichnode-2]);

 if(fake_segments[4*whichnode-1].node1==realnode || fake_segments[4*whichnode-1].node2==realnode)
    return(&fake_segments[4*whichnode-1]);

 return(NULL);
}


/*++++++++++++++++++++++++++++++++++++++
  Lookup a fake segment given its index.

  Segment *LookupFakeSegment Returns a pointer to the segment.

  index_t fakesegment The index of the fake segment.
  ++++++++++++++++++++++++++++++++++++++*/

Segment *LookupFakeSegment(index_t fakesegment)
{
 index_t whichsegment=fakesegment-SEGMENT_FAKE;

 return(&fake_segments[whichsegment]);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the fake index of a fake segment.

  index_t IndexFakeSegment Returns the fake segment.

  Segment *fakesegment The fake segment to look for.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexFakeSegment(Segment *fakesegment)
{
 index_t whichsegment=fakesegment-&fake_segments[0];

 return(whichsegment+SEGMENT_FAKE);
}


/*++++++++++++++++++++++++++++++++++++++
  Find the real segment underlying a fake segment.

  index_t IndexRealSegment Returns the real segment.

  index_t fakesegment The fake segment index to look for.
  ++++++++++++++++++++++++++++++++++++++*/

index_t IndexRealSegment(index_t fakesegment)
{
 index_t whichsegment=fakesegment-SEGMENT_FAKE;

 return(real_segments[whichsegment]);
}
1	/***************************************
2	Fake node and segment generation.
3
4	Part of the Routino routing software.
5	****************/ /****************
6	This file Copyright 2008-2011 Andrew M. Bishop
7
8	This program is free software: you can redistribute it and/or modify
9	it under the terms of the GNU Affero General Public License as published by
10	the Free Software Foundation, either version 3 of the License, or
11	(at your option) any later version.
12
13	This program is distributed in the hope that it will be useful,
14	but WITHOUT ANY WARRANTY; without even the implied warranty of
15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16	GNU Affero General Public License for more details.
17
18	You should have received a copy of the GNU Affero General Public License
19	along with this program. If not, see <http://www.gnu.org/licenses/>.
20	***************************************/
21
22
23	#include "types.h"
24	#include "nodes.h"
25	#include "segments.h"
26
27	#include "fakes.h"
28
29
30	/+ The minimum distance along a segment from a node to insert a fake node. (in km). +/
31	#define MINSEGMENT 0.005
32
33
34	/+ A set of fake segments to allow start/finish in the middle of a segment. +/
35	static Segment fake_segments[4*NWAYPOINTS+1];
36
37	/+ A set of pointers to the real segments underlying the fake segments. +/
38	static index_t real_segments[4*NWAYPOINTS+1];
39
40	/+ A set of fake node latitudes and longitudes. +/
41	static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];
42
43	/+ The previous waypoint. +/
44	static int prevpoint=0;
45
46
47	/*++++++++++++++++++++++++++++++++++++++
48	Create a pair of fake segments corresponding to the given segment split in two.
49
50	index_t CreateFakes Returns the fake node index (or a real one in special cases).
51
52	Nodes *nodes The set of nodes to use.
53
54	Segments *segments The set of segments to use.
55
56	int point Which of the waypoints is this.
57
58	Segment *segment The segment to split.
59
60	index_t node1 The first node at the end of this segment.
61
62	index_t node2 The second node at the end of this segment.
63
64	distance_t dist1 The distance to the first node.
65
66	distance_t dist2 The distance to the second node.
67	++++++++++++++++++++++++++++++++++++++*/
68
69	index_t CreateFakes(Nodes nodes,Segments segments,int point,Segment *segment,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
70	{
71	index_t fakenode;
72	double lat1,lon1,lat2,lon2;
73
74	/* Initialise the segments to fake values */
75
76	fake_segments[4*point-4].node1=NO_NODE;
77	fake_segments[4*point-4].node2=NO_NODE;
78
79	fake_segments[4*point-3].node1=NO_NODE;
80	fake_segments[4*point-3].node2=NO_NODE;
81
82	fake_segments[4*point-2].node1=NO_NODE;
83	fake_segments[4*point-2].node2=NO_NODE;
84
85	fake_segments[4*point-1].node1=NO_NODE;
86	fake_segments[4*point-1].node2=NO_NODE;
87
88	/* Check if we are actually close enough to an existing node */
89
90	if(dist1<km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
91	{
92	prevpoint=point;
93	return(node1);
94	}
95
96	if(dist2<km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
97	{
98	prevpoint=point;
99	return(node2);
100	}
101
102	if(dist1<km_to_distance(MINSEGMENT) && dist2<km_to_distance(MINSEGMENT))
103	{
104	prevpoint=point;
105
106	if(dist1<dist2)
107	return(node1);
108	else
109	return(node2);
110	}
111
112	/* Create the fake node */
113
114	fakenode=NODE_FAKE+point;
115
116	GetLatLong(nodes,node1,&lat1,&lon1);
117	GetLatLong(nodes,node2,&lat2,&lon2);
118
119	if(lat1>3 && lat2<-3)
120	lat2+=2*M_PI;
121	else if(lat1<-3 && lat2>3)
122	lat1+=2*M_PI;
123
124	fake_lat[point]=lat1+(lat2-lat1)*(double)dist1/(double)(dist1+dist2);
125	fake_lon[point]=lon1+(lon2-lon1)*(double)dist1/(double)(dist1+dist2);
126
127	if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;
128
129	/* Create the first fake segment */
130
131	fake_segments[4point-4]=segment;
132
133	fake_segments[4*point-4].node2=fakenode;
134
135	fake_segments[4*point-4].distance=DISTANCE(dist1)\|DISTFLAG(segment->distance);
136
137	real_segments[4*point-4]=IndexSegment(segments,segment);
138
139	/* Create the second fake segment */
140
141	fake_segments[4point-3]=segment;
142
143	fake_segments[4*point-3].node1=fakenode;
144
145	fake_segments[4*point-3].distance=DISTANCE(dist2)\|DISTFLAG(segment->distance);
146
147	real_segments[4*point-3]=IndexSegment(segments,segment);
148
149	/* Create a third fake segment to join adjacent points if both are fake and on the same real segment */
150
151	if(prevpoint>0 && fake_segments[4prevpoint-4].node1==node1 && fake_segments[4prevpoint-3].node2==node2)
152	{
153	if(DISTANCE(dist1)>DISTANCE(fake_segments[4prevpoint-4].distance)) / closer to node2 */
154	{
155	fake_segments[4point-2]=fake_segments[4point-4];
156
157	fake_segments[4*point-2].node1=fakenode;
158
159	fake_segments[4point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4prevpoint-4].distance))\|DISTFLAG(segment->distance);
160	}
161	else
162	{
163	fake_segments[4point-2]=fake_segments[4point-2];
164
165	fake_segments[4*point-2].node2=fakenode;
166
167	fake_segments[4point-2].distance=(DISTANCE(fake_segments[4prevpoint-4].distance)-DISTANCE(dist1))\|DISTFLAG(segment->distance);
168	}
169
170	real_segments[4*point-2]=IndexSegment(segments,segment);
171
172	fake_segments[4prevpoint-1]=fake_segments[4point-2];
173
174	real_segments[4prevpoint-1]=real_segments[4point-2];
175	}
176
177	/* Return the fake node */
178
179	prevpoint=point;
180
181	return(fakenode);
182	}
183
184
185	/*++++++++++++++++++++++++++++++++++++++
186	Lookup the latitude and longitude of a fake node.
187
188	index_t fakenode The node to lookup.
189
190	double *latitude Returns the latitude
191
192	double *longitude Returns the longitude.
193	++++++++++++++++++++++++++++++++++++++*/
194
195	void GetFakeLatLong(index_t fakenode, double latitude,double longitude)
196	{
197	index_t whichnode=fakenode-NODE_FAKE;
198
199	*latitude =fake_lat[whichnode];
200	*longitude=fake_lon[whichnode];
201	}
202
203
204	/*++++++++++++++++++++++++++++++++++++++
205	Finds the first fake segment associated to a fake node.
206
207	Segment *FirstFakeSegment Returns the first fake segment.
208
209	index_t fakenode The node to lookup.
210	++++++++++++++++++++++++++++++++++++++*/
211
212	Segment *FirstFakeSegment(index_t fakenode)
213	{
214	index_t whichnode=fakenode-NODE_FAKE;
215
216	return(&fake_segments[4*whichnode-4]);
217	}
218
219
220	/*++++++++++++++++++++++++++++++++++++++
221	Finds the next (there can only be two) fake segment associated to a fake node.
222
223	Segment *NextFakeSegment Returns the second fake segment.
224
225	Segment *segment The first fake segment.
226
227	index_t fakenode The node to lookup.
228	++++++++++++++++++++++++++++++++++++++*/
229
230	Segment NextFakeSegment(Segment fakesegment,index_t fakenode)
231	{
232	index_t whichnode=fakenode-NODE_FAKE;
233
234	if(fakesegment==&fake_segments[4*whichnode-4])
235	return(&fake_segments[4*whichnode-3]);
236
237	if(fakesegment==&fake_segments[4whichnode-3] && fake_segments[4whichnode-2].node1!=NO_NODE)
238	return(&fake_segments[4*whichnode-2]);
239
240	if(fakesegment==&fake_segments[4whichnode-3] && fake_segments[4whichnode-1].node1!=NO_NODE)
241	return(&fake_segments[4*whichnode-1]);
242
243	if(fakesegment==&fake_segments[4whichnode-2] && fake_segments[4whichnode-1].node1!=NO_NODE)
244	return(&fake_segments[4*whichnode-1]);
245
246	return(NULL);
247	}
248
249
250	/*++++++++++++++++++++++++++++++++++++++
251	Finds the fake segment between a node and a fake node.
252
253	Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
254
255	index_t realnode The real node.
256
257	index_t fakenode The fake node.
258	++++++++++++++++++++++++++++++++++++++*/
259
260	Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
261	{
262	index_t whichnode=fakenode-NODE_FAKE;
263
264	if(fake_segments[4whichnode-4].node1==realnode \|\| fake_segments[4whichnode-4].node2==realnode)
265	return(&fake_segments[4*whichnode-4]);
266
267	if(fake_segments[4whichnode-3].node1==realnode \|\| fake_segments[4whichnode-3].node2==realnode)
268	return(&fake_segments[4*whichnode-3]);
269
270	if(fake_segments[4whichnode-2].node1==realnode \|\| fake_segments[4whichnode-2].node2==realnode)
271	return(&fake_segments[4*whichnode-2]);
272
273	if(fake_segments[4whichnode-1].node1==realnode \|\| fake_segments[4whichnode-1].node2==realnode)
274	return(&fake_segments[4*whichnode-1]);
275
276	return(NULL);
277	}
278
279
280	/*++++++++++++++++++++++++++++++++++++++
281	Lookup a fake segment given its index.
282
283	Segment *LookupFakeSegment Returns a pointer to the segment.
284
285	index_t fakesegment The index of the fake segment.
286	++++++++++++++++++++++++++++++++++++++*/
287
288	Segment *LookupFakeSegment(index_t fakesegment)
289	{
290	index_t whichsegment=fakesegment-SEGMENT_FAKE;
291
292	return(&fake_segments[whichsegment]);
293	}
294
295
296	/*++++++++++++++++++++++++++++++++++++++
297	Find the fake index of a fake segment.
298
299	index_t IndexFakeSegment Returns the fake segment.
300
301	Segment *fakesegment The fake segment to look for.
302	++++++++++++++++++++++++++++++++++++++*/
303
304	index_t IndexFakeSegment(Segment *fakesegment)
305	{
306	index_t whichsegment=fakesegment-&fake_segments[0];
307
308	return(whichsegment+SEGMENT_FAKE);
309	}
310
311
312	/*++++++++++++++++++++++++++++++++++++++
313	Find the real segment underlying a fake segment.
314
315	index_t IndexRealSegment Returns the real segment.
316
317	index_t fakesegment The fake segment index to look for.
318	++++++++++++++++++++++++++++++++++++++*/
319
320	index_t IndexRealSegment(index_t fakesegment)
321	{
322	index_t whichsegment=fakesegment-SEGMENT_FAKE;
323
324	return(real_segments[whichsegment]);
325	}