trunk/src/fakes.c

/***************************************
 $Header: /home/amb/CVS/routino/src/fakes.c,v 1.4 2010-11-28 14:29:26 amb Exp $

 Fake node and segment generation.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008-2010 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 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.

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

 /* 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);

 /* 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);
      }

    fake_segments[4*prevpoint-1]=fake_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 realnode=fakenode-NODE_FAKE;

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


/*++++++++++++++++++++++++++++++++++++++
  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 realnode=fakenode-NODE_FAKE;

 return(&fake_segments[4*realnode-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 *segment,index_t fakenode)
{
 index_t realnode=fakenode-NODE_FAKE;

 if(segment==&fake_segments[4*realnode-4])
    return(&fake_segments[4*realnode-3]);

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

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

 if(segment==&fake_segments[4*realnode-2] && fake_segments[4*realnode-1].node1!=NO_NODE)
    return(&fake_segments[4*realnode-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 node The real node.

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

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

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

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

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

 if(fake_segments[4*realnode-1].node1==node || fake_segments[4*realnode-1].node2==node)
    return(&fake_segments[4*realnode-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 realsegment=fakesegment-SEGMENT_FAKE;

 return(&fake_segments[realsegment]);
}


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

  index_t IndexFakeSegment Returns the fake segment.

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

index_t IndexFakeSegment(Segment *segment)
{
 index_t realsegment=segment-&fake_segments[0];

 return(realsegment+SEGMENT_FAKE);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/fakes.c,v 1.4 2010-11-28 14:29:26 amb Exp $
3
4	Fake node and segment generation.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008-2010 Andrew M. Bishop
9
10	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	***************************************/
23
24
25	#include "types.h"
26	#include "nodes.h"
27	#include "segments.h"
28
29	#include "fakes.h"
30
31
32	/+ The minimum distance along a segment from a node to insert a fake node. (in km). +/
33	#define MINSEGMENT 0.005
34
35
36	/+ A set of fake segments to allow start/finish in the middle of a segment. +/
37	static Segment fake_segments[4*NWAYPOINTS+1];
38
39	/+ A set of fake node latitudes and longitudes. +/
40	static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];
41
42	/+ The previous waypoint. +/
43	static int prevpoint=0;
44
45
46	/*++++++++++++++++++++++++++++++++++++++
47	Create a pair of fake segments corresponding to the given segment split in two.
48
49	index_t CreateFakes Returns the fake node index (or a real one in special cases).
50
51	Nodes *nodes The set of nodes to use.
52
53	int point Which of the waypoints is this.
54
55	Segment *segment The segment to split.
56
57	index_t node1 The first node at the end of this segment.
58
59	index_t node2 The second node at the end of this segment.
60
61	distance_t dist1 The distance to the first node.
62
63	distance_t dist2 The distance to the second node.
64	++++++++++++++++++++++++++++++++++++++*/
65
66	index_t CreateFakes(Nodes nodes,int point,Segment segment,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
67	{
68	index_t fakenode;
69	double lat1,lon1,lat2,lon2;
70
71	/* Initialise the segments to fake values */
72
73	fake_segments[4*point-4].node1=NO_NODE;
74	fake_segments[4*point-4].node2=NO_NODE;
75
76	fake_segments[4*point-3].node1=NO_NODE;
77	fake_segments[4*point-3].node2=NO_NODE;
78
79	fake_segments[4*point-2].node1=NO_NODE;
80	fake_segments[4*point-2].node2=NO_NODE;
81
82	fake_segments[4*point-1].node1=NO_NODE;
83	fake_segments[4*point-1].node2=NO_NODE;
84
85	/* Check if we are actually close enough to an existing node */
86
87	if(dist1<km_to_distance(MINSEGMENT) && dist2>km_to_distance(MINSEGMENT))
88	{
89	prevpoint=point;
90	return(node1);
91	}
92
93	if(dist2<km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
94	{
95	prevpoint=point;
96	return(node2);
97	}
98
99	if(dist1<km_to_distance(MINSEGMENT) && dist2<km_to_distance(MINSEGMENT))
100	{
101	prevpoint=point;
102
103	if(dist1<dist2)
104	return(node1);
105	else
106	return(node2);
107	}
108
109	/* Create the fake node */
110
111	fakenode=NODE_FAKE+point;
112
113	GetLatLong(nodes,node1,&lat1,&lon1);
114	GetLatLong(nodes,node2,&lat2,&lon2);
115
116	if(lat1>3 && lat2<-3)
117	lat2+=2*M_PI;
118	else if(lat1<-3 && lat2>3)
119	lat1+=2*M_PI;
120
121	fake_lat[point]=lat1+(lat2-lat1)*(double)dist1/(double)(dist1+dist2);
122	fake_lon[point]=lon1+(lon2-lon1)*(double)dist1/(double)(dist1+dist2);
123
124	if(fake_lat[point]>M_PI) fake_lat[point]-=2*M_PI;
125
126	/* Create the first fake segment */
127
128	fake_segments[4point-4]=segment;
129
130	fake_segments[4*point-4].node2=fakenode;
131
132	fake_segments[4*point-4].distance=DISTANCE(dist1)\|DISTFLAG(segment->distance);
133
134	/* Create the second fake segment */
135
136	fake_segments[4point-3]=segment;
137
138	fake_segments[4*point-3].node1=fakenode;
139
140	fake_segments[4*point-3].distance=DISTANCE(dist2)\|DISTFLAG(segment->distance);
141
142	/* Create a third fake segment to join adjacent points if both are fake and on the same real segment */
143
144	if(prevpoint>0 && fake_segments[4prevpoint-4].node1==node1 && fake_segments[4prevpoint-3].node2==node2)
145	{
146	if(DISTANCE(dist1)>DISTANCE(fake_segments[4prevpoint-4].distance)) / closer to node2 */
147	{
148	fake_segments[4point-2]=fake_segments[4point-4];
149
150	fake_segments[4*point-2].node1=fakenode;
151
152	fake_segments[4point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4prevpoint-4].distance))\|DISTFLAG(segment->distance);
153	}
154	else
155	{
156	fake_segments[4point-2]=fake_segments[4point-2];
157
158	fake_segments[4*point-2].node2=fakenode;
159
160	fake_segments[4point-2].distance=(DISTANCE(fake_segments[4prevpoint-4].distance)-DISTANCE(dist1))\|DISTFLAG(segment->distance);
161	}
162
163	fake_segments[4prevpoint-1]=fake_segments[4point-2];
164	}
165
166	/* Return the fake node */
167
168	prevpoint=point;
169
170	return(fakenode);
171	}
172
173
174	/*++++++++++++++++++++++++++++++++++++++
175	Lookup the latitude and longitude of a fake node.
176
177	index_t fakenode The node to lookup.
178
179	double *latitude Returns the latitude
180
181	double *longitude Returns the longitude.
182	++++++++++++++++++++++++++++++++++++++*/
183
184	void GetFakeLatLong(index_t fakenode, double latitude,double longitude)
185	{
186	index_t realnode=fakenode-NODE_FAKE;
187
188	*latitude =fake_lat[realnode];
189	*longitude=fake_lon[realnode];
190	}
191
192
193	/*++++++++++++++++++++++++++++++++++++++
194	Finds the first fake segment associated to a fake node.
195
196	Segment *FirstFakeSegment Returns the first fake segment.
197
198	index_t fakenode The node to lookup.
199	++++++++++++++++++++++++++++++++++++++*/
200
201	Segment *FirstFakeSegment(index_t fakenode)
202	{
203	index_t realnode=fakenode-NODE_FAKE;
204
205	return(&fake_segments[4*realnode-4]);
206	}
207
208
209	/*++++++++++++++++++++++++++++++++++++++
210	Finds the next (there can only be two) fake segment associated to a fake node.
211
212	Segment *NextFakeSegment Returns the second fake segment.
213
214	Segment *segment The first fake segment.
215
216	index_t fakenode The node to lookup.
217	++++++++++++++++++++++++++++++++++++++*/
218
219	Segment NextFakeSegment(Segment segment,index_t fakenode)
220	{
221	index_t realnode=fakenode-NODE_FAKE;
222
223	if(segment==&fake_segments[4*realnode-4])
224	return(&fake_segments[4*realnode-3]);
225
226	if(segment==&fake_segments[4realnode-3] && fake_segments[4realnode-2].node1!=NO_NODE)
227	return(&fake_segments[4*realnode-2]);
228
229	if(segment==&fake_segments[4realnode-3] && fake_segments[4realnode-1].node1!=NO_NODE)
230	return(&fake_segments[4*realnode-1]);
231
232	if(segment==&fake_segments[4realnode-2] && fake_segments[4realnode-1].node1!=NO_NODE)
233	return(&fake_segments[4*realnode-1]);
234
235	return(NULL);
236	}
237
238
239	/*++++++++++++++++++++++++++++++++++++++
240	Finds the fake segment between a node and a fake node.
241
242	Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
243
244	index_t node The real node.
245
246	index_t fakenode The fake node to lookup.
247	++++++++++++++++++++++++++++++++++++++*/
248
249	Segment *ExtraFakeSegment(index_t node,index_t fakenode)
250	{
251	index_t realnode=fakenode-NODE_FAKE;
252
253	if(fake_segments[4realnode-4].node1==node \|\| fake_segments[4realnode-4].node2==node)
254	return(&fake_segments[4*realnode-4]);
255
256	if(fake_segments[4realnode-3].node1==node \|\| fake_segments[4realnode-3].node2==node)
257	return(&fake_segments[4*realnode-3]);
258
259	if(fake_segments[4realnode-2].node1==node \|\| fake_segments[4realnode-2].node2==node)
260	return(&fake_segments[4*realnode-2]);
261
262	if(fake_segments[4realnode-1].node1==node \|\| fake_segments[4realnode-1].node2==node)
263	return(&fake_segments[4*realnode-1]);
264
265	return(NULL);
266	}
267
268
269	/*++++++++++++++++++++++++++++++++++++++
270	Lookup a fake segment given its index.
271
272	Segment *LookupFakeSegment Returns a pointer to the segment.
273
274	index_t fakesegment The index of the fake segment.
275	++++++++++++++++++++++++++++++++++++++*/
276
277	Segment *LookupFakeSegment(index_t fakesegment)
278	{
279	index_t realsegment=fakesegment-SEGMENT_FAKE;
280
281	return(&fake_segments[realsegment]);
282	}
283
284
285	/*++++++++++++++++++++++++++++++++++++++
286	Find the fake index of a fake segment.
287
288	index_t IndexFakeSegment Returns the fake segment.
289
290	Segment *segment The segment to look for.
291	++++++++++++++++++++++++++++++++++++++*/
292
293	index_t IndexFakeSegment(Segment *segment)
294	{
295	index_t realsegment=segment-&fake_segments[0];
296
297	return(realsegment+SEGMENT_FAKE);
298	}