Routino SVN Repository Browser

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

ViewVC logotype

Contents of /trunk/src/supersegments.c

Parent Directory Parent Directory | Revision Log 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)
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.