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
  (and will create an extra two fake segments if adjacent waypoints are on the
  same segment).

  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 this is.

  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;

 /*
  *    node1  fakenode                         node2
  *      #----------*----------------------------#     real_segments[4*point-{4,3}]
  *   
  *      #----------*                                  fake_segments[4*point-4]
  *                 *----------------------------#     fake_segments[4*point-3]
  *   
  *   
  *    node1  fakenode[prevpoint]              node2
  *      #----------*------------------%---------#     real_segments[4*prevpoint-{4,3,1}], real_segments[4*point-{4,3,2}]
  *                              fakenode[point]
  *      #----------*                                  fake_segments[4*prevpoint-4]
  *                 *----------------------------#     fake_segments[4*prevpoint-3]
  *                 *------------------%               fake_segments[4*prevpoint-1]
  *      #-----------------------------%               fake_segments[4*point-4]
  *                                    %---------#     fake_segments[4*point-3]
  *                 *------------------%               fake_segments[4*point-2]
  */

 /* 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*prevpoint-4];

       fake_segments[4*point-2].node2=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*prevpoint-3];

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

       fake_segments[4*point-2].distance=(DISTANCE(fake_segments[4*prevpoint-3].distance)-DISTANCE(dist2))|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 fake 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 a pointer to the first fake segment.

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

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

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


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

  Segment *NextFakeSegment Returns a pointer to the next fake segment.

  Segment *fakesegment 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 real 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 fake 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 index of the real segment.

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

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	(and will create an extra two fake segments if adjacent waypoints are on the
50	same segment).
51
52	index_t CreateFakes Returns the fake node index (or a real one in special cases).
53
54	Nodes *nodes The set of nodes to use.
55
56	Segments *segments The set of segments to use.
57
58	int point Which of the waypoints this is.
59
60	Segment *segment The segment to split.
61
62	index_t node1 The first node at the end of this segment.
63
64	index_t node2 The second node at the end of this segment.
65
66	distance_t dist1 The distance to the first node.
67
68	distance_t dist2 The distance to the second node.
69	++++++++++++++++++++++++++++++++++++++*/
70
71	index_t CreateFakes(Nodes nodes,Segments segments,int point,Segment *segment,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
72	{
73	index_t fakenode;
74	double lat1,lon1,lat2,lon2;
75
76	/* Initialise the segments to fake values */
77
78	fake_segments[4*point-4].node1=NO_NODE;
79	fake_segments[4*point-4].node2=NO_NODE;
80
81	fake_segments[4*point-3].node1=NO_NODE;
82	fake_segments[4*point-3].node2=NO_NODE;
83
84	fake_segments[4*point-2].node1=NO_NODE;
85	fake_segments[4*point-2].node2=NO_NODE;
86
87	fake_segments[4*point-1].node1=NO_NODE;
88	fake_segments[4*point-1].node2=NO_NODE;
89
90	/* Check if we are actually close enough to an existing node */
91
92	if(dist1<km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
93	{
94	prevpoint=point;
95	return(node1);
96	}
97
98	if(dist2<km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
99	{
100	prevpoint=point;
101	return(node2);
102	}
103
104	if(dist1<km_to_distance(MINSEGMENT) && dist2<km_to_distance(MINSEGMENT))
105	{
106	prevpoint=point;
107
108	if(dist1<dist2)
109	return(node1);
110	else
111	return(node2);
112	}
113
114	/* Create the fake node */
115
116	fakenode=NODE_FAKE+point;
117
118	GetLatLong(nodes,node1,&lat1,&lon1);
119	GetLatLong(nodes,node2,&lat2,&lon2);
120
121	if(lat1>3 && lat2<-3)
122	lat2+=2*M_PI;
123	else if(lat1<-3 && lat2>3)
124	lat1+=2*M_PI;
125
126	fake_lat[point]=lat1+(lat2-lat1)*(double)dist1/(double)(dist1+dist2);
127	fake_lon[point]=lon1+(lon2-lon1)*(double)dist1/(double)(dist1+dist2);
128
129	if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;
130
131	/*
132	* node1 fakenode node2
133	* #--------------------------------------# real_segments[4point-{4,3}]
134	*
135	* #----------* fake_segments[4*point-4]
136	* ----------------------------# fake_segments[4point-3]
137	*
138	*
139	* node1 fakenode[prevpoint] node2
140	* #----------------------------%---------# real_segments[4prevpoint-{4,3,1}], real_segments[4*point-{4,3,2}]
141	* fakenode[point]
142	* #----------* fake_segments[4*prevpoint-4]
143	* ----------------------------# fake_segments[4prevpoint-3]
144	* ------------------% fake_segments[4prevpoint-1]
145	* #-----------------------------% fake_segments[4*point-4]
146	* %---------# fake_segments[4*point-3]
147	* ------------------% fake_segments[4point-2]
148	*/
149
150	/* Create the first fake segment */
151
152	fake_segments[4point-4]=segment;
153
154	fake_segments[4*point-4].node2=fakenode;
155
156	fake_segments[4*point-4].distance=DISTANCE(dist1)\|DISTFLAG(segment->distance);
157
158	real_segments[4*point-4]=IndexSegment(segments,segment);
159
160	/* Create the second fake segment */
161
162	fake_segments[4point-3]=segment;
163
164	fake_segments[4*point-3].node1=fakenode;
165
166	fake_segments[4*point-3].distance=DISTANCE(dist2)\|DISTFLAG(segment->distance);
167
168	real_segments[4*point-3]=IndexSegment(segments,segment);
169
170	/* Create a third fake segment to join adjacent points if both are fake and on the same real segment */
171
172	if(prevpoint>0 && fake_segments[4prevpoint-4].node1==node1 && fake_segments[4prevpoint-3].node2==node2)
173	{
174	if(DISTANCE(dist1)>DISTANCE(fake_segments[4prevpoint-4].distance)) / closer to node2 */
175	{
176	fake_segments[4point-2]=fake_segments[4prevpoint-4];
177
178	fake_segments[4*point-2].node2=fakenode;
179
180	fake_segments[4point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4prevpoint-4].distance))\|DISTFLAG(segment->distance);
181	}
182	else
183	{
184	fake_segments[4point-2]=fake_segments[4prevpoint-3];
185
186	fake_segments[4*point-2].node1=fakenode;
187
188	fake_segments[4point-2].distance=(DISTANCE(fake_segments[4prevpoint-3].distance)-DISTANCE(dist2))\|DISTFLAG(segment->distance);
189	}
190
191	real_segments[4*point-2]=IndexSegment(segments,segment);
192
193	fake_segments[4prevpoint-1]=fake_segments[4point-2];
194
195	real_segments[4prevpoint-1]=real_segments[4point-2];
196	}
197
198	/* Return the fake node */
199
200	prevpoint=point;
201
202	return(fakenode);
203	}
204
205
206	/*++++++++++++++++++++++++++++++++++++++
207	Lookup the latitude and longitude of a fake node.
208
209	index_t fakenode The fake node to lookup.
210
211	double *latitude Returns the latitude
212
213	double *longitude Returns the longitude.
214	++++++++++++++++++++++++++++++++++++++*/
215
216	void GetFakeLatLong(index_t fakenode, double latitude,double longitude)
217	{
218	index_t whichnode=fakenode-NODE_FAKE;
219
220	*latitude =fake_lat[whichnode];
221	*longitude=fake_lon[whichnode];
222	}
223
224
225	/*++++++++++++++++++++++++++++++++++++++
226	Finds the first fake segment associated to a fake node.
227
228	Segment *FirstFakeSegment Returns a pointer to the first fake segment.
229
230	index_t fakenode The fake node to lookup.
231	++++++++++++++++++++++++++++++++++++++*/
232
233	Segment *FirstFakeSegment(index_t fakenode)
234	{
235	index_t whichnode=fakenode-NODE_FAKE;
236
237	return(&fake_segments[4*whichnode-4]);
238	}
239
240
241	/*++++++++++++++++++++++++++++++++++++++
242	Finds the next fake segment associated to a fake node.
243
244	Segment *NextFakeSegment Returns a pointer to the next fake segment.
245
246	Segment *fakesegment The first fake segment.
247
248	index_t fakenode The node to lookup.
249	++++++++++++++++++++++++++++++++++++++*/
250
251	Segment NextFakeSegment(Segment fakesegment,index_t fakenode)
252	{
253	index_t whichnode=fakenode-NODE_FAKE;
254
255	if(fakesegment==&fake_segments[4*whichnode-4])
256	return(&fake_segments[4*whichnode-3]);
257
258	if(fakesegment==&fake_segments[4whichnode-3] && fake_segments[4whichnode-2].node1!=NO_NODE)
259	return(&fake_segments[4*whichnode-2]);
260
261	if(fakesegment==&fake_segments[4whichnode-3] && fake_segments[4whichnode-1].node1!=NO_NODE)
262	return(&fake_segments[4*whichnode-1]);
263
264	if(fakesegment==&fake_segments[4whichnode-2] && fake_segments[4whichnode-1].node1!=NO_NODE)
265	return(&fake_segments[4*whichnode-1]);
266
267	return(NULL);
268	}
269
270
271	/*++++++++++++++++++++++++++++++++++++++
272	Finds the fake segment between a real node and a fake node.
273
274	Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
275
276	index_t realnode The real node.
277
278	index_t fakenode The fake node.
279	++++++++++++++++++++++++++++++++++++++*/
280
281	Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
282	{
283	index_t whichnode=fakenode-NODE_FAKE;
284
285	if(fake_segments[4whichnode-4].node1==realnode \|\| fake_segments[4whichnode-4].node2==realnode)
286	return(&fake_segments[4*whichnode-4]);
287
288	if(fake_segments[4whichnode-3].node1==realnode \|\| fake_segments[4whichnode-3].node2==realnode)
289	return(&fake_segments[4*whichnode-3]);
290
291	if(fake_segments[4whichnode-2].node1==realnode \|\| fake_segments[4whichnode-2].node2==realnode)
292	return(&fake_segments[4*whichnode-2]);
293
294	if(fake_segments[4whichnode-1].node1==realnode \|\| fake_segments[4whichnode-1].node2==realnode)
295	return(&fake_segments[4*whichnode-1]);
296
297	return(NULL);
298	}
299
300
301	/*++++++++++++++++++++++++++++++++++++++
302	Lookup a fake segment given its index.
303
304	Segment *LookupFakeSegment Returns a pointer to the fake segment.
305
306	index_t fakesegment The index of the fake segment.
307	++++++++++++++++++++++++++++++++++++++*/
308
309	Segment *LookupFakeSegment(index_t fakesegment)
310	{
311	index_t whichsegment=fakesegment-SEGMENT_FAKE;
312
313	return(&fake_segments[whichsegment]);
314	}
315
316
317	/*++++++++++++++++++++++++++++++++++++++
318	Find the fake index of a fake segment.
319
320	index_t IndexFakeSegment Returns the fake segment.
321
322	Segment *fakesegment The fake segment to look for.
323	++++++++++++++++++++++++++++++++++++++*/
324
325	index_t IndexFakeSegment(Segment *fakesegment)
326	{
327	index_t whichsegment=fakesegment-&fake_segments[0];
328
329	return(whichsegment+SEGMENT_FAKE);
330	}
331
332
333	/*++++++++++++++++++++++++++++++++++++++
334	Find the real segment underlying a fake segment.
335
336	index_t IndexRealSegment Returns the index of the real segment.
337
338	index_t fakesegment The index of the fake segment.
339	++++++++++++++++++++++++++++++++++++++*/
340
341	index_t IndexRealSegment(index_t fakesegment)
342	{
343	index_t whichsegment=fakesegment-SEGMENT_FAKE;
344
345	return(real_segments[whichsegment]);
346	}