Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/fakes.c
Parent Directory
|
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)
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. |