Check out the latest version of Routino: svn co http://routino.org/svn/trunk routino
Contents of /trunk/src/supersegments.c
Parent Directory
|
Revision Log
Revision 68 -
(show annotations)
(download)
(as text)
Thu Jan 22 19:39:30 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 6915 byte(s)
Thu Jan 22 19:39:30 2009 UTC (16 years, 1 month ago) by amb
File MIME type: text/x-csrc
File size: 6915 byte(s)
Removed the Way_TYPE() macro.
1 | /*************************************** |
2 | $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.14 2009-01-22 19:39:30 amb Exp $ |
3 | |
4 | Super-Segment data type functions. |
5 | ******************/ /****************** |
6 | Written by Andrew M. Bishop |
7 | |
8 | This file Copyright 2008,2009 Andrew M. Bishop |
9 | 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 | #include <assert.h> |
16 | #include <math.h> |
17 | #include <stdlib.h> |
18 | |
19 | #include "nodes.h" |
20 | #include "ways.h" |
21 | #include "segments.h" |
22 | #include "functions.h" |
23 | |
24 | |
25 | /*++++++++++++++++++++++++++++++++++++++ |
26 | Select the super-segments from the list of segments. |
27 | |
28 | NodesMem *ChooseSuperNodes Returns the list of super-nodes. |
29 | |
30 | Nodes *nodes The nodes. |
31 | |
32 | Segments *segments The existing segments. |
33 | |
34 | Ways *ways The ways. |
35 | ++++++++++++++++++++++++++++++++++++++*/ |
36 | |
37 | NodesMem *ChooseSuperNodes(Nodes *nodes,Segments *segments,Ways *ways) |
38 | { |
39 | int i; |
40 | int segcount=0,difference=0; |
41 | node_t node=0; |
42 | speed_t limit=0; |
43 | waytype_t type=0; |
44 | wayallow_t allow=0; |
45 | NodesMem *supernodes; |
46 | |
47 | /* Create super-nodes */ |
48 | |
49 | supernodes=NewNodeList(); |
50 | |
51 | /* Find super-nodes */ |
52 | |
53 | node=segments->segments[0].node1; |
54 | |
55 | for(i=0;i<segments->number;i++) |
56 | { |
57 | Segment *segment=&segments->segments[i]; |
58 | Way *way=FindWay(ways,segment->way); |
59 | |
60 | if(segment->node1!=node) |
61 | { |
62 | /* Store the node if there is a difference in the ways that could affect routing. |
63 | Store the node if it is not a dead-end and if it isn't just the middle of a way. */ |
64 | |
65 | if(difference || segcount>2) |
66 | { |
67 | Node *oldnode=FindNode(nodes,node); |
68 | |
69 | AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude); |
70 | } |
71 | |
72 | segcount=1; |
73 | difference=0; |
74 | |
75 | node=segment->node1; |
76 | type=way->type; |
77 | limit=way->limit; |
78 | allow=way->allow; |
79 | } |
80 | else /* Same starting node */ |
81 | { |
82 | if(way->type!=type) |
83 | difference=1; |
84 | |
85 | if(way->limit!=limit) |
86 | difference=1; |
87 | |
88 | if(way->allow!=allow) |
89 | difference=1; |
90 | |
91 | segcount+=1; |
92 | } |
93 | |
94 | if(!((i+1)%10000)) |
95 | { |
96 | printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number); |
97 | fflush(stdout); |
98 | } |
99 | } |
100 | |
101 | printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number); |
102 | fflush(stdout); |
103 | |
104 | return(supernodes); |
105 | } |
106 | |
107 | |
108 | /*++++++++++++++++++++++++++++++++++++++ |
109 | Create the super-segments. |
110 | |
111 | SegmentsMem *CreateSuperSegments Returns the set of super-segments. |
112 | |
113 | Nodes *nodes The list of nodes. |
114 | |
115 | Segments *segments The list of segments. |
116 | |
117 | Ways *ways The list of ways. |
118 | |
119 | Nodes *supernodes The list of super-nodes. |
120 | |
121 | int iteration The iteration number of super-segment generation. |
122 | ++++++++++++++++++++++++++++++++++++++*/ |
123 | |
124 | SegmentsMem *CreateSuperSegments(Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes,int iteration) |
125 | { |
126 | SegmentsMem *supersegments; |
127 | int i,j; |
128 | |
129 | /* Create super-segments */ |
130 | |
131 | supersegments=NewSegmentList(); |
132 | |
133 | /* Create super-segments for each super-node. */ |
134 | |
135 | for(i=0;i<supernodes->number;i++) |
136 | { |
137 | Segment *segment,*first; |
138 | |
139 | segment=first=FindFirstSegment(segments,supernodes->nodes[i].id); |
140 | |
141 | while(segment) |
142 | { |
143 | Way *way=FindWay(ways,segment->way); |
144 | |
145 | /* Check that this type of way hasn't already been routed */ |
146 | |
147 | if(segment!=first) |
148 | { |
149 | Segment *othersegment=first; |
150 | |
151 | while(othersegment && othersegment!=segment) |
152 | { |
153 | Way *otherway=FindWay(ways,othersegment->way); |
154 | |
155 | if(otherway->type ==way->type && |
156 | otherway->allow==way->allow && |
157 | otherway->limit==way->limit) |
158 | { |
159 | way=NULL; |
160 | break; |
161 | } |
162 | |
163 | othersegment=FindNextSegment(segments,othersegment); |
164 | } |
165 | } |
166 | |
167 | /* Route the way and store the super-segments. */ |
168 | |
169 | if(way) |
170 | { |
171 | Results *results=FindRoutesWay(nodes,segments,ways,supernodes->nodes[i].id,supernodes,way,iteration); |
172 | |
173 | for(j=0;j<results->number;j++) |
174 | if(results->results[j].node!=supernodes->nodes[i].id && FindNode(supernodes,results->results[j].node)) |
175 | { |
176 | Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,way->id); |
177 | |
178 | supersegment->distance=results->results[j].shortest.distance; |
179 | |
180 | if(way->type&Way_OneWay) |
181 | { |
182 | supersegment=AppendSegment(supersegments,results->results[j].node,supernodes->nodes[i].id,way->id); |
183 | |
184 | supersegment->distance=INVALID_DISTANCE; |
185 | } |
186 | } |
187 | |
188 | FreeResultsList(results); |
189 | } |
190 | |
191 | segment=FindNextSegment(segments,segment); |
192 | } |
193 | |
194 | if(!((i+1)%1000)) |
195 | { |
196 | printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number); |
197 | fflush(stdout); |
198 | } |
199 | } |
200 | |
201 | printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number); |
202 | fflush(stdout); |
203 | |
204 | return(supersegments); |
205 | } |
206 | |
207 | |
208 | /*++++++++++++++++++++++++++++++++++++++ |
209 | Create the Super-Ways from the Super-Segments. |
210 | |
211 | WaysMem *CreateSuperWays Returns the set of super-ways. |
212 | |
213 | Ways *ways The list of ways. |
214 | |
215 | SegmentsMem *supersegments The list of super-segments. |
216 | ++++++++++++++++++++++++++++++++++++++*/ |
217 | |
218 | WaysMem *CreateSuperWays(Ways *ways,SegmentsMem *supersegments) |
219 | { |
220 | WaysMem *superways; |
221 | int i,j; |
222 | |
223 | /* Create super-ways */ |
224 | |
225 | superways=NewWayList(); |
226 | |
227 | /* Create a new super-way to replace each existing way. */ |
228 | |
229 | for(i=0;i<supersegments->segments->number;i++) |
230 | { |
231 | Way *way=FindWay(ways,supersegments->segments->segments[i].way); |
232 | |
233 | supersegments->segments->segments[i].way=0; |
234 | |
235 | for(j=0;j<superways->number;j++) |
236 | if(superways->ways->ways[j].type ==way->type && |
237 | superways->ways->ways[j].allow==way->allow && |
238 | superways->ways->ways[j].limit==way->limit) |
239 | { |
240 | supersegments->segments->segments[i].way=superways->ways->ways[j].id; |
241 | break; |
242 | } |
243 | |
244 | if(!supersegments->segments->segments[i].way) |
245 | { |
246 | Way *newway=AppendWay(superways,superways->number+1,"Super-Way"); |
247 | |
248 | newway->limit=way->limit; |
249 | newway->type =way->type; |
250 | newway->allow=way->allow; |
251 | |
252 | supersegments->segments->segments[i].way=newway->id; |
253 | } |
254 | |
255 | if(!((i+1)%10000)) |
256 | { |
257 | printf("\rCreating Super-Ways: Super-Segments=%d Super-Ways=%d",i+1,superways->number); |
258 | fflush(stdout); |
259 | } |
260 | } |
261 | |
262 | printf("\rCreated Super-Ways: Super-Segments=%d Super-Ways=%d \n",supersegments->number,superways->number); |
263 | fflush(stdout); |
264 | |
265 | return(superways); |
266 | } |
Properties
Name | Value |
---|---|
cvs:description | SuperSegments data type. |