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