Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Annotation of /trunk/src/segments.c
Parent Directory
|
Revision Log
Revision 84 -
(hide annotations)
(download)
(as text)
Sun Jan 25 12:09:15 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 11215 byte(s)
Sun Jan 25 12:09:15 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 11215 byte(s)
Change the segment->way so that it contains the index of the way, not the id.
1 | amb | 2 | /*************************************** |
2 | amb | 84 | $Header: /home/amb/CVS/routino/src/segments.c,v 1.18 2009-01-25 12:09:15 amb Exp $ |
3 | amb | 2 | |
4 | Segment data type functions. | ||
5 | ******************/ /****************** | ||
6 | Written by Andrew M. Bishop | ||
7 | |||
8 | amb | 4 | This file Copyright 2008,2009 Andrew M. Bishop |
9 | amb | 2 | It may be distributed under the GNU Public License, version 2, or |
10 | any higher version. See section COPYING of the GNU Public license | ||
11 | for conditions under which this file may be redistributed. | ||
12 | ***************************************/ | ||
13 | |||
14 | |||
15 | amb | 8 | #include <assert.h> |
16 | amb | 2 | #include <math.h> |
17 | #include <stdlib.h> | ||
18 | |||
19 | amb | 39 | #include "nodes.h" |
20 | amb | 26 | #include "segments.h" |
21 | amb | 2 | #include "functions.h" |
22 | |||
23 | |||
24 | amb | 23 | /* Functions */ |
25 | amb | 2 | |
26 | amb | 23 | static int sort_by_id(Segment *a,Segment *b); |
27 | amb | 2 | |
28 | amb | 8 | |
29 | amb | 23 | /*++++++++++++++++++++++++++++++++++++++ |
30 | Allocate a new segment list. | ||
31 | amb | 8 | |
32 | amb | 23 | SegmentsMem *NewSegmentList Returns the segment list. |
33 | ++++++++++++++++++++++++++++++++++++++*/ | ||
34 | amb | 2 | |
35 | amb | 23 | SegmentsMem *NewSegmentList(void) |
36 | { | ||
37 | SegmentsMem *segments; | ||
38 | amb | 2 | |
39 | amb | 23 | segments=(SegmentsMem*)malloc(sizeof(SegmentsMem)); |
40 | amb | 2 | |
41 | amb | 23 | segments->alloced=INCREMENT_SEGMENTS; |
42 | segments->number=0; | ||
43 | segments->sorted=0; | ||
44 | |||
45 | segments->segments=(Segments*)malloc(sizeof(Segments)+segments->alloced*sizeof(Segment)); | ||
46 | |||
47 | return(segments); | ||
48 | } | ||
49 | |||
50 | |||
51 | amb | 2 | /*++++++++++++++++++++++++++++++++++++++ |
52 | Load in a segment list from a file. | ||
53 | |||
54 | amb | 23 | Segments* SaveSegmentList Returns the segment list that has just been loaded. |
55 | |||
56 | amb | 2 | const char *filename The name of the file to load. |
57 | ++++++++++++++++++++++++++++++++++++++*/ | ||
58 | |||
59 | amb | 23 | Segments *LoadSegmentList(const char *filename) |
60 | amb | 2 | { |
61 | amb | 23 | return((Segments*)MapFile(filename)); |
62 | amb | 2 | } |
63 | |||
64 | |||
65 | /*++++++++++++++++++++++++++++++++++++++ | ||
66 | Save the segment list to a file. | ||
67 | |||
68 | amb | 23 | Segments* SaveSegmentList Returns the segment list that has just been saved. |
69 | |||
70 | SegmentsMem* segments The set of segments to save. | ||
71 | |||
72 | amb | 2 | const char *filename The name of the file to save. |
73 | ++++++++++++++++++++++++++++++++++++++*/ | ||
74 | |||
75 | amb | 23 | Segments *SaveSegmentList(SegmentsMem* segments,const char *filename) |
76 | amb | 2 | { |
77 | amb | 23 | assert(segments->sorted); /* Must be sorted */ |
78 | amb | 2 | |
79 | amb | 23 | if(WriteFile(filename,(void*)segments->segments,sizeof(Segments)-sizeof(segments->segments->segments)+segments->number*sizeof(Segment))) |
80 | assert(0); | ||
81 | |||
82 | free(segments->segments); | ||
83 | free(segments); | ||
84 | |||
85 | return(LoadSegmentList(filename)); | ||
86 | amb | 2 | } |
87 | |||
88 | |||
89 | /*++++++++++++++++++++++++++++++++++++++ | ||
90 | Find the first segment with a particular starting node. | ||
91 | |||
92 | Segment *FindFirstSegment Returns a pointer to the first segment with the specified id. | ||
93 | |||
94 | amb | 23 | Segments* segments The set of segments to process. |
95 | |||
96 | amb | 2 | node_t node The node to look for. |
97 | ++++++++++++++++++++++++++++++++++++++*/ | ||
98 | |||
99 | amb | 23 | Segment *FindFirstSegment(Segments* segments,node_t node) |
100 | amb | 2 | { |
101 | amb | 23 | int bin=node%NBINS_SEGMENTS; |
102 | int start=segments->offset[bin]; | ||
103 | amb | 65 | int end=segments->offset[bin+1]-1; /* &offset[NBINS+1] == &number */ |
104 | amb | 2 | int mid; |
105 | int found; | ||
106 | |||
107 | /* Binary search - search key exact match only is required. | ||
108 | * | ||
109 | * # <- start | Check mid and move start or end if it doesn't match | ||
110 | * # | | ||
111 | * # | Since an exact match is wanted we can set end=mid-1 | ||
112 | * # <- mid | or start=mid+1 because we know that mid doesn't match. | ||
113 | * # | | ||
114 | * # | Eventually either end=start or end=start+1 and one of | ||
115 | * # <- end | start or end is the wanted one. | ||
116 | */ | ||
117 | |||
118 | amb | 23 | if(end<start) /* There are no nodes */ |
119 | amb | 2 | return(NULL); |
120 | amb | 23 | else if(node<segments->segments[start].node1) /* Check key is not before start */ |
121 | amb | 2 | return(NULL); |
122 | amb | 23 | else if(node>segments->segments[end].node1) /* Check key is not after end */ |
123 | amb | 2 | return(NULL); |
124 | else | ||
125 | { | ||
126 | do | ||
127 | { | ||
128 | amb | 23 | mid=(start+end)/2; /* Choose mid point */ |
129 | amb | 2 | |
130 | amb | 23 | if(segments->segments[mid].node1<node) /* Mid point is too low */ |
131 | amb | 2 | start=mid; |
132 | amb | 23 | else if(segments->segments[mid].node1>node) /* Mid point is too high */ |
133 | amb | 2 | end=mid; |
134 | amb | 23 | else /* Mid point is correct */ |
135 | amb | 2 | {found=mid; goto found;} |
136 | } | ||
137 | while((end-start)>1); | ||
138 | |||
139 | amb | 23 | if(segments->segments[start].node1==node) /* Start is correct */ |
140 | amb | 2 | {found=start; goto found;} |
141 | |||
142 | amb | 23 | if(segments->segments[end].node1==node) /* End is correct */ |
143 | amb | 2 | {found=end; goto found;} |
144 | } | ||
145 | |||
146 | return(NULL); | ||
147 | |||
148 | found: | ||
149 | |||
150 | amb | 23 | while(found>0 && segments->segments[found-1].node1==node) |
151 | amb | 2 | found--; |
152 | |||
153 | amb | 23 | return(&segments->segments[found]); |
154 | amb | 2 | } |
155 | |||
156 | |||
157 | /*++++++++++++++++++++++++++++++++++++++ | ||
158 | Find the next segment with a particular starting node. | ||
159 | |||
160 | amb | 23 | Segment *FindNextSegment Returns a pointer to the next segment with the same id. |
161 | amb | 2 | |
162 | amb | 23 | Segments* segments The set of segments to process. |
163 | |||
164 | amb | 2 | Segment *segment The current segment. |
165 | ++++++++++++++++++++++++++++++++++++++*/ | ||
166 | |||
167 | amb | 23 | Segment *FindNextSegment(Segments* segments,Segment *segment) |
168 | amb | 2 | { |
169 | Segment *next=segment+1; | ||
170 | |||
171 | amb | 23 | if((next-segments->segments)==segments->number) |
172 | return(NULL); | ||
173 | amb | 2 | |
174 | if(next->node1==segment->node1) | ||
175 | return(next); | ||
176 | |||
177 | return(NULL); | ||
178 | } | ||
179 | |||
180 | |||
181 | /*++++++++++++++++++++++++++++++++++++++ | ||
182 | Append a segment to a newly created segment list (unsorted). | ||
183 | |||
184 | amb | 31 | Segment *AppendSegment Returns the appended segment. |
185 | |||
186 | amb | 23 | SegmentsMem* segments The set of segments to process. |
187 | |||
188 | amb | 2 | node_t node1 The first node in the segment. |
189 | |||
190 | node_t node2 The second node in the segment. | ||
191 | |||
192 | amb | 5 | way_t way The way that the pair of segments are connected by. |
193 | amb | 2 | ++++++++++++++++++++++++++++++++++++++*/ |
194 | |||
195 | amb | 31 | Segment *AppendSegment(SegmentsMem* segments,node_t node1,node_t node2,way_t way) |
196 | amb | 2 | { |
197 | amb | 23 | /* Check that the array has enough space. */ |
198 | amb | 8 | |
199 | amb | 23 | if(segments->number==segments->alloced) |
200 | amb | 4 | { |
201 | amb | 23 | segments->alloced+=INCREMENT_SEGMENTS; |
202 | amb | 4 | |
203 | amb | 23 | segments->segments=(Segments*)realloc((void*)segments->segments,sizeof(Segments)+segments->alloced*sizeof(Segment)); |
204 | amb | 4 | } |
205 | |||
206 | /* Insert the segment */ | ||
207 | |||
208 | amb | 23 | segments->segments->segments[segments->number].node1=node1; |
209 | segments->segments->segments[segments->number].node2=node2; | ||
210 | segments->segments->segments[segments->number].way=way; | ||
211 | segments->segments->segments[segments->number].distance=0; | ||
212 | amb | 2 | |
213 | amb | 23 | segments->number++; |
214 | amb | 2 | |
215 | amb | 23 | segments->sorted=0; |
216 | amb | 31 | |
217 | return(&segments->segments->segments[segments->number-1]); | ||
218 | amb | 2 | } |
219 | |||
220 | |||
221 | /*++++++++++++++++++++++++++++++++++++++ | ||
222 | Sort the segment list. | ||
223 | amb | 23 | |
224 | SegmentsMem* segments The set of segments to process. | ||
225 | amb | 2 | ++++++++++++++++++++++++++++++++++++++*/ |
226 | |||
227 | amb | 23 | void SortSegmentList(SegmentsMem* segments) |
228 | amb | 2 | { |
229 | amb | 39 | int i,bin=0; |
230 | |||
231 | amb | 23 | qsort(segments->segments->segments,segments->number,sizeof(Segment),(int (*)(const void*,const void*))sort_by_id); |
232 | amb | 8 | |
233 | amb | 39 | while(segments->segments->segments[segments->number-1].node1==~0) |
234 | segments->number--; | ||
235 | |||
236 | amb | 23 | segments->sorted=1; |
237 | amb | 39 | |
238 | /* Make it searchable */ | ||
239 | |||
240 | segments->segments->number=segments->number; | ||
241 | |||
242 | for(i=0;i<segments->number;i++) | ||
243 | for(;bin<=(segments->segments->segments[i].node1%NBINS_SEGMENTS);bin++) | ||
244 | segments->segments->offset[bin]=i; | ||
245 | |||
246 | amb | 65 | for(;bin<NBINS_SEGMENTS;bin++) |
247 | amb | 39 | segments->segments->offset[bin]=segments->number; |
248 | amb | 2 | } |
249 | |||
250 | |||
251 | /*++++++++++++++++++++++++++++++++++++++ | ||
252 | Sort the segments into id order. | ||
253 | |||
254 | int sort_by_id Returns the comparison of the node fields. | ||
255 | |||
256 | Segment *a The first Segment. | ||
257 | |||
258 | Segment *b The second Segment. | ||
259 | ++++++++++++++++++++++++++++++++++++++*/ | ||
260 | |||
261 | static int sort_by_id(Segment *a,Segment *b) | ||
262 | { | ||
263 | node_t a_id1=a->node1,a_id2=a->node2; | ||
264 | node_t b_id1=b->node1,b_id2=b->node2; | ||
265 | |||
266 | amb | 23 | int a_bin=a->node1%NBINS_SEGMENTS; |
267 | int b_bin=b->node1%NBINS_SEGMENTS; | ||
268 | |||
269 | if(a_bin!=b_bin) | ||
270 | return(a_bin-b_bin); | ||
271 | |||
272 | amb | 39 | if(a_id1<b_id1) |
273 | return(-1); | ||
274 | else if(a_id1>b_id1) | ||
275 | return(1); | ||
276 | else /* if(a_id1==b_id1) */ | ||
277 | { | ||
278 | if(a_id2<b_id2) | ||
279 | return(-1); | ||
280 | else if(a_id2>b_id2) | ||
281 | return(1); | ||
282 | else | ||
283 | return(0); | ||
284 | } | ||
285 | amb | 2 | } |
286 | |||
287 | |||
288 | /*++++++++++++++++++++++++++++++++++++++ | ||
289 | amb | 39 | Remove bad segments (zero length or duplicated). |
290 | |||
291 | SegmentsMem *segments The segments to modify. | ||
292 | ++++++++++++++++++++++++++++++++++++++*/ | ||
293 | |||
294 | void RemoveBadSegments(SegmentsMem *segments) | ||
295 | { | ||
296 | int i; | ||
297 | int duplicate=0,loop=0; | ||
298 | node_t node1=~0,node2=~0; | ||
299 | |||
300 | for(i=0;i<segments->number;i++) | ||
301 | { | ||
302 | Segment *segment=&segments->segments->segments[i]; | ||
303 | |||
304 | if(segment->node1==node1 && segment->node2==node2) | ||
305 | { | ||
306 | duplicate++; | ||
307 | segment->node1=~0; | ||
308 | } | ||
309 | else if(segment->node1==segment->node2) | ||
310 | { | ||
311 | loop++; | ||
312 | segment->node1=~0; | ||
313 | } | ||
314 | |||
315 | node1=segment->node1; | ||
316 | node2=segment->node2; | ||
317 | |||
318 | if(!((i+1)%10000)) | ||
319 | { | ||
320 | printf("\rChecking: Segments=%d Duplicate=%d Loop=%d",i+1,duplicate,loop); | ||
321 | fflush(stdout); | ||
322 | } | ||
323 | } | ||
324 | |||
325 | printf("\rChecked: Segments=%d Duplicate=%d Loop=%d \n",segments->number,duplicate,loop); | ||
326 | fflush(stdout); | ||
327 | } | ||
328 | |||
329 | |||
330 | /*++++++++++++++++++++++++++++++++++++++ | ||
331 | amb | 8 | Assign the lengths and durations to all of the segments. |
332 | amb | 23 | |
333 | SegmentsMem* segments The set of segments to process. | ||
334 | |||
335 | Nodes *nodes The list of nodes to use. | ||
336 | |||
337 | Ways *ways The list of ways to use. | ||
338 | amb | 8 | ++++++++++++++++++++++++++++++++++++++*/ |
339 | amb | 2 | |
340 | amb | 23 | void FixupSegmentLengths(SegmentsMem* segments,Nodes *nodes,Ways *ways) |
341 | amb | 8 | { |
342 | int i; | ||
343 | amb | 2 | |
344 | amb | 23 | assert(segments->sorted); /* Must be sorted */ |
345 | amb | 8 | |
346 | amb | 23 | for(i=0;i<segments->number;i++) |
347 | amb | 8 | { |
348 | amb | 23 | Node *node1=FindNode(nodes,segments->segments->segments[i].node1); |
349 | Node *node2=FindNode(nodes,segments->segments->segments[i].node2); | ||
350 | amb | 8 | |
351 | amb | 82 | /* Set the distance but preserve the ONEWAY_OPPOSITE flag */ |
352 | amb | 8 | |
353 | amb | 69 | segments->segments->segments[i].distance|=Distance(node1,node2); |
354 | |||
355 | amb | 54 | if(!((i+1)%10000)) |
356 | { | ||
357 | printf("\rMeasuring Segments: Segments=%d",i+1); | ||
358 | fflush(stdout); | ||
359 | } | ||
360 | amb | 8 | } |
361 | amb | 54 | |
362 | printf("\rMeasured Segments: Segments=%d \n",segments->number); | ||
363 | fflush(stdout); | ||
364 | amb | 8 | } |
365 | |||
366 | |||
367 | /*++++++++++++++++++++++++++++++++++++++ | ||
368 | amb | 84 | Change the segment to contain the index of the way, not the id. |
369 | |||
370 | SegmentsMem* segments The set of segments to process. | ||
371 | |||
372 | Ways *ways The list of ways to use. | ||
373 | ++++++++++++++++++++++++++++++++++++++*/ | ||
374 | |||
375 | void LinkSegmentToWay(SegmentsMem* segments,Ways *ways) | ||
376 | { | ||
377 | int i; | ||
378 | |||
379 | for(i=0;i<segments->number;i++) | ||
380 | { | ||
381 | Way *way=FindWay(ways,segments->segments->segments[i].way); | ||
382 | |||
383 | segments->segments->segments[i].way=IndexWay(ways,way); | ||
384 | } | ||
385 | } | ||
386 | |||
387 | |||
388 | /*++++++++++++++++++++++++++++++++++++++ | ||
389 | amb | 8 | Calculate the distance between two nodes. |
390 | |||
391 | distance_t Distance Returns the distance between the nodes. | ||
392 | |||
393 | amb | 2 | Node *node1 The starting node. |
394 | |||
395 | Node *node2 The end node. | ||
396 | ++++++++++++++++++++++++++++++++++++++*/ | ||
397 | |||
398 | amb | 8 | distance_t Distance(Node *node1,Node *node2) |
399 | amb | 2 | { |
400 | double radiant = M_PI / 180; | ||
401 | |||
402 | double dlon = radiant * (node1->longitude - node2->longitude); | ||
403 | double dlat = radiant * (node1->latitude - node2->latitude); | ||
404 | |||
405 | double a1,a2,a,sa,c,d; | ||
406 | |||
407 | if(dlon==0 && dlat==0) | ||
408 | return 0; | ||
409 | |||
410 | a1 = sin (dlat / 2); | ||
411 | a2 = sin (dlon / 2); | ||
412 | a = (a1 * a1) + cos (node1->latitude * radiant) * cos (node2->latitude * radiant) * a2 * a2; | ||
413 | sa = sqrt (a); | ||
414 | if (sa <= 1.0) | ||
415 | {c = 2 * asin (sa);} | ||
416 | else | ||
417 | {c = 2 * asin (1.0);} | ||
418 | amb | 5 | d = 6378.137 * c; |
419 | amb | 2 | |
420 | amb | 5 | return km_to_distance(d); |
421 | amb | 2 | } |
422 | amb | 63 | |
423 | |||
424 | /*++++++++++++++++++++++++++++++++++++++ | ||
425 | Calculate the duration of segment. | ||
426 | |||
427 | duration_t Duration Returns the duration of travel between the nodes. | ||
428 | |||
429 | Segment *segment The segment to traverse. | ||
430 | |||
431 | Way *way The way that the segment belongs to. | ||
432 | |||
433 | amb | 82 | Profile *profile The profile of the transport being used. |
434 | amb | 63 | ++++++++++++++++++++++++++++++++++++++*/ |
435 | |||
436 | amb | 82 | duration_t Duration(Segment *segment,Way *way,Profile *profile) |
437 | amb | 63 | { |
438 | amb | 82 | speed_t speed=profile->speed[HIGHWAY(way->type)]; |
439 | amb | 63 | distance_t distance=segment->distance; |
440 | |||
441 | return hours_to_duration(distance_to_km(distance)/speed); | ||
442 | } |
Properties
Name | Value |
---|---|
cvs:description | Segment data type. |