Routino SVN Repository Browser

Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino

ViewVC logotype

Contents of /trunk/src/fakes.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 608 - (show annotations) (download) (as text)
Sat Jan 29 16:00:10 2011 UTC (14 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 9184 byte(s)
When finding a normal route check for turn relations (considering previous segment).
When finding turn relations convert fake segments into real ones.

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[4*point-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[4*point-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[4*prevpoint-4].node1==node1 && fake_segments[4*prevpoint-3].node2==node2)
152 {
153 if(DISTANCE(dist1)>DISTANCE(fake_segments[4*prevpoint-4].distance)) /* closer to node2 */
154 {
155 fake_segments[4*point-2]=fake_segments[4*point-4];
156
157 fake_segments[4*point-2].node1=fakenode;
158
159 fake_segments[4*point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4*prevpoint-4].distance))|DISTFLAG(segment->distance);
160 }
161 else
162 {
163 fake_segments[4*point-2]=fake_segments[4*point-2];
164
165 fake_segments[4*point-2].node2=fakenode;
166
167 fake_segments[4*point-2].distance=(DISTANCE(fake_segments[4*prevpoint-4].distance)-DISTANCE(dist1))|DISTFLAG(segment->distance);
168 }
169
170 real_segments[4*point-2]=IndexSegment(segments,segment);
171
172 fake_segments[4*prevpoint-1]=fake_segments[4*point-2];
173
174 real_segments[4*prevpoint-1]=real_segments[4*point-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[4*whichnode-3] && fake_segments[4*whichnode-2].node1!=NO_NODE)
238 return(&fake_segments[4*whichnode-2]);
239
240 if(fakesegment==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-1].node1!=NO_NODE)
241 return(&fake_segments[4*whichnode-1]);
242
243 if(fakesegment==&fake_segments[4*whichnode-2] && fake_segments[4*whichnode-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[4*whichnode-4].node1==realnode || fake_segments[4*whichnode-4].node2==realnode)
265 return(&fake_segments[4*whichnode-4]);
266
267 if(fake_segments[4*whichnode-3].node1==realnode || fake_segments[4*whichnode-3].node2==realnode)
268 return(&fake_segments[4*whichnode-3]);
269
270 if(fake_segments[4*whichnode-2].node1==realnode || fake_segments[4*whichnode-2].node2==realnode)
271 return(&fake_segments[4*whichnode-2]);
272
273 if(fake_segments[4*whichnode-1].node1==realnode || fake_segments[4*whichnode-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 }

Properties

Name Value
cvs:description Move the fake nodes and segments to a new file.