Routino SVN Repository Browser

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

ViewVC logotype

Annotation of /trunk/src/fakes.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1291 - (hide annotations) (download) (as text)
Wed May 1 18:32:57 2013 UTC (11 years, 10 months ago) by amb
File MIME type: text/x-csrc
File size: 10797 byte(s)
The GetLatLong function takes a pointer to the node as an argument - must be an
optimisation for slim mode if not normal mode.

1 amb 455 /***************************************
2     Fake node and segment generation.
3    
4     Part of the Routino routing software.
5     ******************/ /******************
6 amb 1291 This file Copyright 2008-2013 Andrew M. Bishop
7 amb 455
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 amb 532 #include "fakes.h"
28 amb 455
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 amb 535 static Segment fake_segments[4*NWAYPOINTS+1];
36 amb 455
37 amb 608 /*+ A set of pointers to the real segments underlying the fake segments. +*/
38     static index_t real_segments[4*NWAYPOINTS+1];
39    
40 amb 455 /*+ A set of fake node latitudes and longitudes. +*/
41     static double fake_lon[NWAYPOINTS+1],fake_lat[NWAYPOINTS+1];
42    
43 amb 535 /*+ The previous waypoint. +*/
44     static int prevpoint=0;
45 amb 455
46 amb 535
47 amb 455 /*++++++++++++++++++++++++++++++++++++++
48 amb 680 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 amb 455
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 amb 608 Segments *segments The set of segments to use.
57    
58 amb 680 int point Which of the waypoints this is.
59 amb 455
60 amb 1078 Segment *segmentp The segment to split.
61 amb 455
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 amb 1168 distance_t dist1 The distance to the first node.
67 amb 455
68 amb 1168 distance_t dist2 The distance to the second node.
69 amb 455 ++++++++++++++++++++++++++++++++++++++*/
70    
71 amb 1168 index_t CreateFakes(Nodes *nodes,Segments *segments,int point,Segment *segmentp,index_t node1,index_t node2,distance_t dist1,distance_t dist2)
72 amb 455 {
73     index_t fakenode;
74     double lat1,lon1,lat2,lon2;
75    
76 amb 535 /* 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 amb 455 /* 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 amb 535 {
94     prevpoint=point;
95 amb 455 return(node1);
96 amb 535 }
97 amb 455
98     if(dist2<km_to_distance(MINSEGMENT) && dist1>km_to_distance(MINSEGMENT))
99 amb 535 {
100     prevpoint=point;
101 amb 455 return(node2);
102 amb 535 }
103 amb 455
104     if(dist1<km_to_distance(MINSEGMENT) && dist2<km_to_distance(MINSEGMENT))
105     {
106 amb 535 prevpoint=point;
107    
108 amb 455 if(dist1<dist2)
109     return(node1);
110     else
111     return(node2);
112     }
113    
114     /* Create the fake node */
115    
116 amb 471 fakenode=NODE_FAKE+point;
117 amb 455
118 amb 1291 GetLatLong(nodes,node1,NULL,&lat1,&lon1);
119     GetLatLong(nodes,node2,NULL,&lat2,&lon2);
120 amb 455
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 amb 631 /*
132     * node1 fakenode node2
133     * #----------*----------------------------# real_segments[4*point-{4,3}]
134     *
135     * #----------* fake_segments[4*point-4]
136     * *----------------------------# fake_segments[4*point-3]
137     *
138     *
139     * node1 fakenode[prevpoint] node2
140     * #----------*------------------%---------# real_segments[4*prevpoint-{4,3,1}], real_segments[4*point-{4,3,2}]
141     * fakenode[point]
142     * #----------* fake_segments[4*prevpoint-4]
143     * *----------------------------# fake_segments[4*prevpoint-3]
144     * *------------------% fake_segments[4*prevpoint-1]
145     * #-----------------------------% fake_segments[4*point-4]
146     * %---------# fake_segments[4*point-3]
147     * *------------------% fake_segments[4*point-2]
148     */
149    
150 amb 455 /* Create the first fake segment */
151    
152 amb 1078 fake_segments[4*point-4]=*segmentp;
153 amb 455
154 amb 535 fake_segments[4*point-4].node2=fakenode;
155 amb 455
156 amb 1168 fake_segments[4*point-4].distance=DISTANCE(dist1)|DISTFLAG(segmentp->distance);
157 amb 455
158 amb 1078 real_segments[4*point-4]=IndexSegment(segments,segmentp);
159 amb 608
160 amb 455 /* Create the second fake segment */
161    
162 amb 1078 fake_segments[4*point-3]=*segmentp;
163 amb 455
164 amb 535 fake_segments[4*point-3].node1=fakenode;
165 amb 455
166 amb 1168 fake_segments[4*point-3].distance=DISTANCE(dist2)|DISTFLAG(segmentp->distance);
167 amb 455
168 amb 1078 real_segments[4*point-3]=IndexSegment(segments,segmentp);
169 amb 608
170 amb 535 /* 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[4*prevpoint-4].node1==node1 && fake_segments[4*prevpoint-3].node2==node2)
173     {
174 amb 1168 if(DISTANCE(dist1)>DISTANCE(fake_segments[4*prevpoint-4].distance)) /* point is further from node1 than prevpoint */
175 amb 535 {
176 amb 725 fake_segments[4*point-2]=fake_segments[4*prevpoint-3];
177 amb 535
178 amb 631 fake_segments[4*point-2].node2=fakenode;
179 amb 535
180 amb 1168 fake_segments[4*point-2].distance=(DISTANCE(dist1)-DISTANCE(fake_segments[4*prevpoint-4].distance))|DISTFLAG(segmentp->distance);
181 amb 535 }
182     else
183     {
184 amb 725 fake_segments[4*point-2]=fake_segments[4*prevpoint-4];
185 amb 535
186 amb 631 fake_segments[4*point-2].node1=fakenode;
187 amb 535
188 amb 1168 fake_segments[4*point-2].distance=(DISTANCE(fake_segments[4*prevpoint-4].distance)-DISTANCE(dist1))|DISTFLAG(segmentp->distance);
189 amb 535 }
190    
191 amb 1078 real_segments[4*point-2]=IndexSegment(segments,segmentp);
192 amb 608
193 amb 535 fake_segments[4*prevpoint-1]=fake_segments[4*point-2];
194 amb 608
195     real_segments[4*prevpoint-1]=real_segments[4*point-2];
196 amb 535 }
197    
198     /* Return the fake node */
199    
200     prevpoint=point;
201    
202 amb 455 return(fakenode);
203     }
204    
205    
206     /*++++++++++++++++++++++++++++++++++++++
207     Lookup the latitude and longitude of a fake node.
208    
209 amb 680 index_t fakenode The fake node to lookup.
210 amb 455
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 amb 608 index_t whichnode=fakenode-NODE_FAKE;
219 amb 455
220 amb 608 *latitude =fake_lat[whichnode];
221     *longitude=fake_lon[whichnode];
222 amb 455 }
223    
224    
225     /*++++++++++++++++++++++++++++++++++++++
226     Finds the first fake segment associated to a fake node.
227    
228 amb 680 Segment *FirstFakeSegment Returns a pointer to the first fake segment.
229 amb 455
230 amb 680 index_t fakenode The fake node to lookup.
231 amb 455 ++++++++++++++++++++++++++++++++++++++*/
232    
233     Segment *FirstFakeSegment(index_t fakenode)
234     {
235 amb 608 index_t whichnode=fakenode-NODE_FAKE;
236 amb 455
237 amb 608 return(&fake_segments[4*whichnode-4]);
238 amb 455 }
239    
240    
241     /*++++++++++++++++++++++++++++++++++++++
242 amb 680 Finds the next fake segment associated to a fake node.
243 amb 455
244 amb 680 Segment *NextFakeSegment Returns a pointer to the next fake segment.
245 amb 455
246 amb 1078 Segment *fakesegmentp The first fake segment.
247 amb 455
248     index_t fakenode The node to lookup.
249     ++++++++++++++++++++++++++++++++++++++*/
250    
251 amb 1078 Segment *NextFakeSegment(Segment *fakesegmentp,index_t fakenode)
252 amb 455 {
253 amb 608 index_t whichnode=fakenode-NODE_FAKE;
254 amb 455
255 amb 1078 if(fakesegmentp==&fake_segments[4*whichnode-4])
256 amb 608 return(&fake_segments[4*whichnode-3]);
257 amb 535
258 amb 1078 if(fakesegmentp==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-2].node1!=NO_NODE)
259 amb 608 return(&fake_segments[4*whichnode-2]);
260 amb 535
261 amb 1078 if(fakesegmentp==&fake_segments[4*whichnode-3] && fake_segments[4*whichnode-1].node1!=NO_NODE)
262 amb 608 return(&fake_segments[4*whichnode-1]);
263 amb 535
264 amb 1078 if(fakesegmentp==&fake_segments[4*whichnode-2] && fake_segments[4*whichnode-1].node1!=NO_NODE)
265 amb 608 return(&fake_segments[4*whichnode-1]);
266 amb 535
267     return(NULL);
268 amb 455 }
269    
270    
271     /*++++++++++++++++++++++++++++++++++++++
272 amb 680 Finds the fake segment between a real node and a fake node.
273 amb 455
274     Segment *ExtraFakeSegment Returns a segment between the two specified nodes if it exists.
275    
276 amb 608 index_t realnode The real node.
277 amb 455
278 amb 608 index_t fakenode The fake node.
279 amb 455 ++++++++++++++++++++++++++++++++++++++*/
280    
281 amb 608 Segment *ExtraFakeSegment(index_t realnode,index_t fakenode)
282 amb 455 {
283 amb 608 index_t whichnode=fakenode-NODE_FAKE;
284 amb 455
285 amb 608 if(fake_segments[4*whichnode-4].node1==realnode || fake_segments[4*whichnode-4].node2==realnode)
286     return(&fake_segments[4*whichnode-4]);
287 amb 455
288 amb 608 if(fake_segments[4*whichnode-3].node1==realnode || fake_segments[4*whichnode-3].node2==realnode)
289     return(&fake_segments[4*whichnode-3]);
290 amb 455
291     return(NULL);
292     }
293    
294    
295     /*++++++++++++++++++++++++++++++++++++++
296     Lookup a fake segment given its index.
297    
298 amb 680 Segment *LookupFakeSegment Returns a pointer to the fake segment.
299 amb 455
300     index_t fakesegment The index of the fake segment.
301     ++++++++++++++++++++++++++++++++++++++*/
302    
303     Segment *LookupFakeSegment(index_t fakesegment)
304     {
305 amb 608 index_t whichsegment=fakesegment-SEGMENT_FAKE;
306 amb 455
307 amb 608 return(&fake_segments[whichsegment]);
308 amb 455 }
309    
310    
311     /*++++++++++++++++++++++++++++++++++++++
312     Find the fake index of a fake segment.
313    
314     index_t IndexFakeSegment Returns the fake segment.
315    
316 amb 1078 Segment *fakesegmentp The fake segment to look for.
317 amb 455 ++++++++++++++++++++++++++++++++++++++*/
318    
319 amb 1078 index_t IndexFakeSegment(Segment *fakesegmentp)
320 amb 455 {
321 amb 1078 index_t whichsegment=fakesegmentp-&fake_segments[0];
322 amb 455
323 amb 608 return(whichsegment+SEGMENT_FAKE);
324 amb 455 }
325 amb 608
326    
327     /*++++++++++++++++++++++++++++++++++++++
328     Find the real segment underlying a fake segment.
329    
330 amb 680 index_t IndexRealSegment Returns the index of the real segment.
331 amb 608
332 amb 680 index_t fakesegment The index of the fake segment.
333 amb 608 ++++++++++++++++++++++++++++++++++++++*/
334    
335     index_t IndexRealSegment(index_t fakesegment)
336     {
337     index_t whichsegment=fakesegment-SEGMENT_FAKE;
338    
339     return(real_segments[whichsegment]);
340     }
341 amb 727
342    
343     /*++++++++++++++++++++++++++++++++++++++
344     Determine if a route between two fake segments is valid or a U-turn.
345    
346     int IsFakeUTurn Returns true for a U-turn.
347    
348     index_t fakesegment1 The first fake segment.
349    
350     index_t fakesegment2 The second fake segment.
351     ++++++++++++++++++++++++++++++++++++++*/
352    
353     int IsFakeUTurn(index_t fakesegment1,index_t fakesegment2)
354     {
355     index_t whichsegment1=fakesegment1-SEGMENT_FAKE;
356     index_t whichsegment2=fakesegment2-SEGMENT_FAKE;
357    
358     if(fake_segments[whichsegment1].node1==fake_segments[whichsegment2].node1)
359     return(1);
360    
361     if(fake_segments[whichsegment1].node2==fake_segments[whichsegment2].node2)
362     return(1);
363    
364     return(0);
365     }

Properties

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