/[zanavi_public1]/navit/navit/route.c
ZANavi

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 27 - (show annotations) (download)
Mon Apr 9 21:27:36 2012 UTC (10 years, 7 months ago) by zoff99
File MIME type: text/plain
File size: 104560 byte(s)
lots of new stuff, tranlsations, bug fixes ...
1 /**
2 * Navit, a modular navigation system.
3 * Copyright (C) 2005-2008 Navit Team
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 /** @file
21 * @brief Contains code related to finding a route from a position to a destination
22 *
23 * Routing uses segments, points and items. Items are items from the map: Streets, highways, etc.
24 * Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item
25 * can be represented by more than one segment - in that case it is "segmented". Each segment has an
26 * "offset" associated, that indicates at which position in a segmented item this segment is - a
27 * segment representing a not-segmented item always has the offset 1.
28 * A point is located at the end of segments, often connecting several segments.
29 *
30 * The code in this file will make navit find a route between a position and a destination.
31 * It accomplishes this by first building a "route graph". This graph contains segments and
32 * points.
33 *
34 * After building this graph in route_graph_build(), the function route_graph_flood() assigns every
35 * point and segment a "value" which represents the "costs" of traveling from this point to the
36 * destination. This is done by Dijkstra's algorithm.
37 *
38 * When the graph is built a "route path" is created, which is a path in this graph from a given
39 * position to the destination determined at time of building the graph.
40 */
41
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #if 0
46 #include <math.h>
47 #include <assert.h>
48 #include <unistd.h>
49 #include <sys/time.h>
50 #endif
51 #include "glib_slice.h"
52 #include "config.h"
53 #include "point.h"
54 #include "graphics.h"
55 #include "profile.h"
56 #include "coord.h"
57 #include "projection.h"
58 #include "item.h"
59 #include "map.h"
60 #include "mapset.h"
61 #include "route.h"
62 #include "track.h"
63 #include "transform.h"
64 #include "plugin.h"
65 #include "fib.h"
66 #include "event.h"
67 #include "callback.h"
68 #include "vehicle.h"
69 #include "vehicleprofile.h"
70 #include "roadprofile.h"
71 #include "debug.h"
72
73 #include "navit.h"
74
75 struct map_priv
76 {
77 struct route *route;
78 };
79
80 int debug_route = 0;
81
82 /**
83 * @brief A point in the route graph
84 *
85 * This represents a point in the route graph. A point usually connects two or more segments,
86 * but there are also points which don't do that (e.g. at the end of a dead-end).
87 */
88 struct route_graph_point
89 {
90 struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
91 struct route_graph_segment *start; /**< Pointer to a list of segments of which this point is the start. The links
92 * of this linked-list are in route_graph_segment->start_next.*/
93 struct route_graph_segment *end; /**< Pointer to a list of segments of which this pointer is the end. The links
94 * of this linked-list are in route_graph_segment->end_next. */
95 struct route_graph_segment *seg; /**< Pointer to the segment one should use to reach the destination at
96 * least costs */
97 struct fibheap_el *el; /**< When this point is put on a Fibonacci heap, this is a pointer
98 * to this point's heap-element */
99 int value; /**< The cost at which one can reach the destination from this point on */
100 struct coord c; /**< Coordinates of this point */
101 int flags; /**< Flags for this point (eg traffic distortion) */
102 };
103
104 #define RP_TRAFFIC_DISTORTION 1
105 #define RP_TURN_RESTRICTION 2
106 #define RP_TURN_RESTRICTION_RESOLVED 4
107
108 /**
109 * @brief A segment in the route graph or path
110 *
111 * This is a segment in the route graph or path. A segment represents a driveable way.
112 */
113
114 struct route_segment_data
115 {
116 struct item item; /**< The item (e.g. street) that this segment represents. */
117 int flags;
118 int len; /**< Length of this segment */
119 /*NOTE: After a segment, various fields may follow, depending on what flags are set. Order of fields:
120 1.) maxspeed Maximum allowed speed on this segment. Present if AF_SPEED_LIMIT is set.
121 2.) offset If the item is segmented (i.e. represented by more than one segment), this
122 indicates the position of this segment in the item. Present if AF_SEGMENTED is set.
123 */
124 };
125
126 struct size_weight_limit
127 {
128 int width;
129 int length;
130 int height;
131 int weight;
132 int axle_weight;
133 };
134
135 #define RSD_OFFSET(x) *((int *)route_segment_data_field_pos((x), attr_offset))
136 #define RSD_MAXSPEED(x) *((int *)route_segment_data_field_pos((x), attr_maxspeed))
137 #define RSD_SIZE_WEIGHT(x) *((struct size_weight_limit *)route_segment_data_field_pos((x), attr_vehicle_width))
138 #define RSD_DANGEROUS_GOODS(x) *((int *)route_segment_data_field_pos((x), attr_vehicle_dangerous_goods))
139
140 struct route_graph_segment_data
141 {
142 struct item *item;
143 int offset;
144 int flags;
145 int len;
146 int maxspeed;
147 struct size_weight_limit size_weight;
148 int dangerous_goods;
149 };
150
151 /**
152 * @brief A segment in the route graph
153 *
154 * This is a segment in the route graph. A segment represents a driveable way.
155 */
156 struct route_graph_segment
157 {
158 struct route_graph_segment *next; /**< Linked-list pointer to a list of all route_graph_segments */
159 struct route_graph_segment *start_next; /**< Pointer to the next element in the list of segments that start at the
160 * same point. Start of this list is in route_graph_point->start. */
161 struct route_graph_segment *end_next; /**< Pointer to the next element in the list of segments that end at the
162 * same point. Start of this list is in route_graph_point->end. */
163 struct route_graph_point *start; /**< Pointer to the point this segment starts at. */
164 struct route_graph_point *end; /**< Pointer to the point this segment ends at. */
165 struct route_segment_data data; /**< The segment data */
166 };
167
168 /**
169 * @brief A traffic distortion
170 *
171 * This is distortion in the traffic where you can't drive as fast as usual or have to wait for some time
172 */
173 struct route_traffic_distortion
174 {
175 int maxspeed; /**< Maximum speed possible in km/h */
176 int delay; /**< Delay in tenths of seconds */
177 };
178
179 /**
180 * @brief A segment in the route path
181 *
182 * This is a segment in the route path.
183 */
184 struct route_path_segment
185 {
186 struct route_path_segment *next; /**< Pointer to the next segment in the path */
187 struct route_segment_data *data; /**< The segment data */
188 int direction; /**< Order in which the coordinates are ordered. >0 means "First
189 * coordinate of the segment is the first coordinate of the item", <=0
190 * means reverse. */
191 unsigned ncoords; /**< How many coordinates does this segment have? */
192 struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
193 /* WARNING: There will be coordinates following here, so do not create new fields after c! */
194 };
195
196
197 /**
198 * @brief A complete route path
199 *
200 * This structure describes a whole routing path
201 */
202 struct route_path
203 {
204 int in_use; /**< The path is in use and can not be updated */
205 int update_required; /**< The path needs to be updated after it is no longer in use */
206 int updated; /**< The path has only been updated */
207 int path_time; /**< Time to pass the path */
208 int path_len; /**< Length of the path */
209 struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
210 * drive in next */
211 struct route_path_segment *path_last; /**< The last segment in the path */
212 /* XXX: path_hash is not necessery now */
213 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
214 struct route_path *next; /**< Next route path in case of intermediate destinations */
215 };
216
217 /**
218 * @brief A complete route
219 *
220 * This struct holds all information about a route.
221 */
222
223 /**
224 * @brief A complete route graph
225 *
226 * This structure describes a whole routing graph
227 */
228 struct route_graph
229 {
230 int busy; /**< The graph is being built */
231 struct map_selection *sel; /**< The rectangle selection for the graph */
232 struct mapset_handle *h; /**< Handle to the mapset */
233 struct map *m; /**< Pointer to the currently active map */
234 struct map_rect *mr; /**< Pointer to the currently active map rectangle */
235 struct vehicleprofile *vehicleprofile; /**< The vehicle profile */
236 struct callback *idle_cb; /**< Idle callback to process the graph */
237 struct callback *done_cb; /**< Callback when graph is done */
238 struct event_idle *idle_ev; /**< The pointer to the idle event */
239 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
240 #define HASH_SIZE 8192
241 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
242 };
243
244 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
245
246 /**
247 * @brief Iterator to iterate through all route graph segments in a route graph point
248 *
249 * This structure can be used to iterate through all route graph segments connected to a
250 * route graph point. Use this with the rp_iterator_* functions.
251 */
252 struct route_graph_point_iterator
253 {
254 struct route_graph_point *p; /**< The route graph point whose segments should be iterated */
255 int end; /**< Indicates if we have finished iterating through the "start" segments */
256 struct route_graph_segment *next; /**< The next segment to be returned */
257 };
258
259 struct attr_iter
260 {
261 union
262 {
263 GList *list;
264 } u;
265 };
266
267 static struct route_info * route_find_nearest_street(
268 struct vehicleprofile *vehicleprofile, struct mapset *ms,
269 struct pcoord *c);
270 static struct route_graph_point *route_graph_get_point(
271 struct route_graph *this, struct coord *c);
272 static void route_graph_update(struct route *this, struct callback *cb,
273 int async);
274 static void route_graph_build_done(struct route_graph *rg, int cancel);
275 static struct route_path *route_path_new(struct route_graph *this,
276 struct route_path *oldpath, struct route_info *pos,
277 struct route_info *dst, struct vehicleprofile *profile);
278 static void route_process_street_graph(struct route_graph *this,
279 struct item *item, struct vehicleprofile *profile);
280 //static void route_graph_destroy(struct route_graph *this);
281 static void route_path_update(struct route *this, int cancel, int async);
282 static int route_time_seg(struct vehicleprofile *profile,
283 struct route_segment_data *over, struct route_traffic_distortion *dist);
284 static void route_graph_flood(struct route_graph *this, struct route_info *dst,
285 struct vehicleprofile *profile, struct callback *cb);
286 static void route_graph_reset(struct route_graph *this);
287
288 /**
289 * @brief Returns the projection used for this route
290 *
291 * @param route The route to return the projection for
292 * @return The projection used for this route
293 */
294 static enum projection route_projection(struct route *route)
295 {
296 struct street_data *street;
297 struct route_info *dst = route_get_dst(route);
298 if (!route->pos && !dst)
299 return projection_none;
300 street = route->pos ? route->pos->street : dst->street;
301 if (!street || !street->item.map)
302 return projection_none;
303 return map_projection(street->item.map);
304 }
305
306 /**
307 * @brief Creates a new graph point iterator
308 *
309 * This function creates a new route graph point iterator, that can be used to
310 * iterate through all segments connected to the point.
311 *
312 * @param p The route graph point to create the iterator from
313 * @return A new iterator.
314 */
315 static struct route_graph_point_iterator rp_iterator_new(
316 struct route_graph_point *p)
317 {
318 struct route_graph_point_iterator it;
319
320 it.p = p;
321 if (p->start)
322 {
323 it.next = p->start;
324 it.end = 0;
325 }
326 else
327 {
328 it.next = p->end;
329 it.end = 1;
330 }
331
332 return it;
333 }
334
335 /**
336 * @brief Gets the next segment connected to a route graph point from an iterator
337 *
338 * @param it The route graph point iterator to get the segment from
339 * @return The next segment or NULL if there are no more segments
340 */
341 static struct route_graph_segment *rp_iterator_next(
342 struct route_graph_point_iterator *it)
343 {
344 struct route_graph_segment *ret;
345
346 ret = it->next;
347 if (!ret)
348 {
349 return NULL;
350 }
351
352 if (!it->end)
353 {
354 if (ret->start_next)
355 {
356 it->next = ret->start_next;
357 }
358 else
359 {
360 it->next = it->p->end;
361 it->end = 1;
362 }
363 }
364 else
365 {
366 it->next = ret->end_next;
367 }
368
369 return ret;
370 }
371
372 /**
373 * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
374 *
375 * @param it The route graph point iterator to be checked
376 * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
377 */
378 static int rp_iterator_end(struct route_graph_point_iterator *it)
379 {
380 if (it->end && (it->next != it->p->end))
381 {
382 return 1;
383 }
384 else
385 {
386 return 0;
387 }
388 }
389
390 /**
391 * @brief Destroys a route_path
392 *
393 * @param this The route_path to be destroyed
394 */
395 void route_path_destroy(struct route_path *this, int recurse)
396 {
397 struct route_path_segment *c, *n;
398 struct route_path *next;
399 while (this)
400 {
401 next = this->next;
402 if (this->path_hash)
403 {
404 item_hash_destroy(this->path_hash);
405 this->path_hash = NULL;
406 }
407 c = this->path;
408 while (c)
409 {
410 n = c->next;
411 g_free(c);
412 c = n;
413 }
414 this->in_use--;
415 if (!this->in_use)
416 g_free(this);
417 if (!recurse)
418 break;
419 this = next;
420 }
421 }
422
423 /**
424 * @brief Creates a completely new route structure
425 *
426 * @param attrs Not used
427 * @return The newly created route
428 */
429 struct route *
430 route_new(struct attr *parent, struct attr **attrs)
431 {
432 struct route *this=g_new0(struct route, 1);
433 struct attr dest_attr;
434
435 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance,
436 &dest_attr, NULL))
437 {
438 this->destination_distance = dest_attr.u.num;
439 }
440 else
441 {
442 this->destination_distance = 50; // Default value
443 }
444 this->cbl2 = callback_list_new();
445
446 return this;
447 }
448
449 /**
450 * @brief Checks if a segment is part of a roundabout
451 *
452 * This function checks if a segment is part of a roundabout.
453 *
454 * @param seg The segment to be checked
455 * @param level How deep to scan the route graph
456 * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
457 * @param origin Used internally, set to NULL
458 * @return 1 If a roundabout was detected, 0 otherwise
459 */
460 static int route_check_roundabout(struct route_graph_segment *seg, int level,
461 int direction, struct route_graph_segment *origin)
462 {
463 struct route_graph_point_iterator it, it2;
464 struct route_graph_segment *cur;
465 int count = 0;
466
467 if (!level)
468 {
469 return 0;
470 }
471 if (!direction && !(seg->data.flags & AF_ONEWAY))
472 {
473 return 0;
474 }
475 if (direction && !(seg->data.flags & AF_ONEWAYREV))
476 {
477 return 0;
478 }
479 if (seg->data.flags & AF_ROUNDABOUT_VALID)
480 return 0;
481
482 if (!origin)
483 {
484 origin = seg;
485 }
486
487 if (!direction)
488 {
489 it = rp_iterator_new(seg->end);
490 }
491 else
492 {
493 it = rp_iterator_new(seg->start);
494 }
495 it2 = it;
496
497 while ((cur = rp_iterator_next(&it2)))
498 count++;
499
500 if (count > 3)
501 return 0;
502 cur = rp_iterator_next(&it);
503 while (cur)
504 {
505 if (cur == seg)
506 {
507 cur = rp_iterator_next(&it);
508 continue;
509 }
510
511 if (cur->data.item.type != origin->data.item.type)
512 {
513 // This street is of another type, can't be part of the roundabout
514 cur = rp_iterator_next(&it);
515 continue;
516 }
517
518 if (cur == origin)
519 {
520 seg->data.flags |= AF_ROUNDABOUT;
521 return 1;
522 }
523
524 if (route_check_roundabout(cur, (level - 1), rp_iterator_end(&it),
525 origin))
526 {
527 seg->data.flags |= AF_ROUNDABOUT;
528 return 1;
529 }
530
531 cur = rp_iterator_next(&it);
532 }
533
534 return 0;
535 }
536
537 /**
538 * @brief Sets the mapset of the route passwd
539 *
540 * @param this The route to set the mapset for
541 * @param ms The mapset to set for this route
542 */
543 void route_set_mapset(struct route *this, struct mapset *ms)
544 {
545 this->ms = ms;
546 }
547
548 /**
549 * @brief Sets the vehicle profile of a route
550 *
551 * @param this The route to set the profile for
552 * @param prof The vehicle profile
553 */
554
555 void route_set_profile(struct route *this, struct vehicleprofile *prof)
556 {
557 if (this->vehicleprofile != prof)
558 {
559 this->vehicleprofile = prof;
560 route_path_update(this, 1, 1);
561 }
562 }
563
564 /**
565 * @brief Returns the mapset of the route passed
566 *
567 * @param this The route to get the mapset of
568 * @return The mapset of the route passed
569 */
570 struct mapset *
571 route_get_mapset(struct route *this)
572 {
573 return this->ms;
574 }
575
576 /**
577 * @brief Returns the current position within the route passed
578 *
579 * @param this The route to get the position for
580 * @return The position within the route passed
581 */
582 struct route_info *
583 route_get_pos(struct route *this)
584 {
585 return this->pos;
586 }
587
588 /**
589 * @brief Returns the destination of the route passed
590 *
591 * @param this The route to get the destination for
592 * @return The destination of the route passed
593 */
594 struct route_info *
595 route_get_dst(struct route *this)
596 {
597 struct route_info *dst = NULL;
598
599 if (this->destinations)
600 dst = g_list_last(this->destinations)->data;
601 return dst;
602 }
603
604 /**
605 * @brief Checks if the path is calculated for the route passed
606 *
607 * @param this The route to check
608 * @return True if the path is calculated, false if not
609 */
610 int route_get_path_set(struct route *this)
611 {
612 return this->path2 != NULL;
613 }
614
615 /**
616 * @brief Checks if the route passed contains a certain item within the route path
617 *
618 * This function checks if a certain items exists in the path that navit will guide
619 * the user to his destination. It does *not* check if this item exists in the route
620 * graph!
621 *
622 * @param this The route to check for this item
623 * @param item The item to search for
624 * @return True if the item was found, false if the item was not found or the route was not calculated
625 */
626 int route_contains(struct route *this, struct item *item)
627 {
628 if (!this->path2 || !this->path2->path_hash)
629 return 0;
630 if (item_hash_lookup(this->path2->path_hash, item))
631 return 1;
632 if (!this->pos || !this->pos->street)
633 return 0;
634 return item_is_equal(this->pos->street->item, *item);
635
636 }
637
638 static struct route_info *
639 route_next_destination(struct route *this)
640 {
641 if (!this->destinations)
642 return NULL;
643 return this->destinations->data;
644 }
645
646 /**
647 * @brief Checks if a route has reached its destination
648 *
649 * @param this The route to be checked
650 * @return True if the destination is "reached", false otherwise.
651 */
652 int route_destination_reached(struct route *this)
653 {
654 struct street_data *sd = NULL;
655 enum projection pro;
656 struct route_info *dst = route_next_destination(this);
657
658 if (!this->pos)
659 return 0;
660 if (!dst)
661 return 0;
662
663 sd = this->pos->street;
664
665 if (!this->path2)
666 {
667 return 0;
668 }
669
670 if (!item_is_equal(this->pos->street->item, dst->street->item))
671 {
672 return 0;
673 }
674
675 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= dst->lenneg))
676 { // We would have to drive against the one-way road
677 return 0;
678 }
679 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= dst->lenpos))
680 {
681 return 0;
682 }
683 pro = route_projection(this);
684 if (pro == projection_none)
685 return 0;
686
687 if (transform_distance(pro, &this->pos->c, &dst->lp)
688 > this->destination_distance)
689 {
690 return 0;
691 }
692
693 if (g_list_next(this->destinations))
694 return 1;
695 else
696 return 2;
697 }
698
699 static struct route_info *
700 route_previous_destination(struct route *this)
701 {
702 GList *l = g_list_find(this->destinations, this->current_dst);
703 if (!l)
704 return this->pos;
705 l = g_list_previous(l);
706 if (!l)
707 return this->pos;
708 return l->data;
709 }
710
711 static void route_path_update_done(struct route *this, int new_graph)
712 {
713 struct route_path *oldpath = this->path2;
714 struct attr route_status;
715 struct route_info *prev_dst;
716 route_status.type = attr_route_status;
717 if (this->path2 && (this->path2->in_use > 1))
718 {
719 this->path2->update_required = 1 + new_graph;
720 return;
721 }
722 route_status.u.num = route_status_building_path;
723 route_set_attr(this, &route_status);
724 prev_dst = route_previous_destination(this);
725 if (this->link_path)
726 {
727 this->path2 = route_path_new(this->graph, NULL, prev_dst,
728 this->current_dst, this->vehicleprofile);
729 if (this->path2)
730 this->path2->next = oldpath;
731 }
732 else
733 {
734 this->path2 = route_path_new(this->graph, oldpath, prev_dst,
735 this->current_dst, this->vehicleprofile);
736 if (oldpath && this->path2)
737 {
738 this->path2->next = oldpath->next;
739 route_path_destroy(oldpath, 0);
740 }
741 }
742 if (this->path2)
743 {
744 struct route_path_segment *seg = this->path2->path;
745 int path_time = 0, path_len = 0;
746 while (seg)
747 {
748 /* FIXME */
749 int seg_time =
750 route_time_seg(this->vehicleprofile, seg->data, NULL);
751 if (seg_time == INT_MAX)
752 {
753 dbg(1, "error\n");
754 }
755 else
756 path_time += seg_time;
757 path_len += seg->data->len;
758 seg = seg->next;
759 }
760 this->path2->path_time = path_time;
761 this->path2->path_len = path_len;
762 if (prev_dst != this->pos)
763 {
764 this->link_path = 1;
765 this->current_dst = prev_dst;
766 route_graph_reset(this->graph);
767 route_graph_flood(this->graph, this->current_dst,
768 this->vehicleprofile, this->route_graph_flood_done_cb);
769 return;
770 }
771 if (!new_graph && this->path2->updated)
772 {
773 route_status.u.num = route_status_path_done_incremental;
774 }
775 else
776 {
777 route_status.u.num = route_status_path_done_new;
778 }
779 }
780 else
781 {
782 route_status.u.num = route_status_not_found;
783 dbg(0, "try harder\n");
784 // Try to rebuild the graph with smaller roads
785 if (this->try_harder == 0)
786 {
787 this->try_harder = 1;
788 route_graph_destroy(this->graph);
789 this->graph = NULL;
790 route_path_update(this, 1, 1);
791 }
792 }
793 this->link_path = 0;
794 route_set_attr(this, &route_status);
795 }
796
797 /**
798 * @brief Updates the route graph and the route path if something changed with the route
799 *
800 * This will update the route graph and the route path of the route if some of the
801 * route's settings (destination, position) have changed.
802 *
803 * @attention For this to work the route graph has to be destroyed if the route's
804 * @attention destination is changed somewhere!
805 *
806 * @param this The route to update
807 */
808 static void route_path_update(struct route *this, int cancel, int async)
809 {
810 //dbg(1, "enter %d\n", cancel);
811 if (!this->pos || !this->destinations)
812 {
813 //dbg(1, "destroy\n");
814 route_path_destroy(this->path2, 1);
815 this->path2 = NULL;
816 return;
817 }
818 if (cancel)
819 {
820 route_graph_destroy(this->graph);
821 this->graph = NULL;
822 }
823 /* the graph is destroyed when setting the destination */
824 if (this->graph)
825 {
826 if (this->graph->busy)
827 {
828 //dbg(1, "busy building graph\n");
829 return;
830 }
831 // we can try to update
832 //dbg(1, "try update\n");
833 route_path_update_done(this, 0);
834 }
835 else
836 {
837 route_path_destroy(this->path2, 1);
838 this->path2 = NULL;
839 }
840 if (!this->graph || !this->path2)
841 {
842 //dbg(1, "rebuild graph\n");
843 if (!this->route_graph_flood_done_cb)
844 {
845 this->route_graph_flood_done_cb = callback_new_2(
846 callback_cast(route_path_update_done), this, (long) 1);
847 }
848 //dbg(1, "route_graph_update\n");
849 route_graph_update(this, this->route_graph_flood_done_cb, async);
850 }
851 }
852
853 /**
854 * @brief This will calculate all the distances stored in a route_info
855 *
856 * @param ri The route_info to calculate the distances for
857 * @param pro The projection used for this route
858 */
859 static void route_info_distances(struct route_info *ri, enum projection pro)
860 {
861 int npos = ri->pos + 1;
862 struct street_data *sd = ri->street;
863 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
864 ri->lenextra = transform_distance(pro, &ri->lp, &ri->c);
865 ri->lenneg = transform_polyline_length(pro, sd->c, npos)
866 + transform_distance(pro, &sd->c[ri->pos], &ri->lp);
867 ri->lenpos = transform_polyline_length(pro, sd->c + npos, sd->count - npos)
868 + transform_distance(pro, &sd->c[npos], &ri->lp);
869 if (ri->lenneg || ri->lenpos)
870 ri->percent = (ri->lenneg * 100) / (ri->lenneg + ri->lenpos);
871 else
872 ri->percent = 50;
873 }
874
875 /**
876 * @brief This sets the current position of the route passed
877 *
878 * This will set the current position of the route passed to the street that is nearest to the
879 * passed coordinates. It also automatically updates the route.
880 *
881 * @param this The route to set the position of
882 * @param pos Coordinates to set as position
883 */
884 void route_set_position(struct route *this, struct pcoord *pos)
885 {
886 if (this->pos)
887 route_info_free(this->pos);
888 this->pos = NULL;
889 this->pos = route_find_nearest_street(this->vehicleprofile, this->ms, pos);
890
891 // If there is no nearest street, bail out.
892 if (!this->pos)
893 return;
894
895 this->pos->street_direction = 0;
896 //dbg(1, "this->pos=%p\n", this->pos);
897 route_info_distances(this->pos, pos->pro);
898 route_path_update(this, 0, 1);
899 }
900
901 /**
902 * @brief Sets a route's current position based on coordinates from tracking
903 *
904 * @param this The route to set the current position of
905 * @param tracking The tracking to get the coordinates from
906 */
907 void route_set_position_from_tracking(struct route *this,
908 struct tracking *tracking, enum projection pro)
909 {
910 struct coord *c;
911 struct route_info *ret;
912 struct street_data *sd;
913
914 //dbg(2, "enter\n");
915 c = tracking_get_pos(tracking);
916 ret=g_new0(struct route_info, 1);
917 if (!ret)
918 {
919 printf("%s:Out of memory\n", __FUNCTION__);
920 return;
921 }
922 if (this->pos)
923 route_info_free(this->pos);
924 this->pos = NULL;
925 ret->c = *c;
926 ret->lp = *c;
927 ret->pos = tracking_get_segment_pos(tracking);
928 ret->street_direction = tracking_get_street_direction(tracking);
929 sd = tracking_get_street_data(tracking);
930 if (sd)
931 {
932 ret->street = street_data_dup(sd);
933 route_info_distances(ret, pro);
934 }
935 //dbg(
936 // 3,
937 // "position 0x%x,0x%x item 0x%x,0x%x direction %d pos %d lenpos %d lenneg %d\n",
938 // c->x, c->y, sd ? sd->item.id_hi : 0, sd ? sd->item.id_lo : 0,
939 // ret->street_direction, ret->pos, ret->lenpos, ret->lenneg);
940 //dbg(3, "c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y,
941 // ret->pos, ret->street ? ret->street->item.id_hi : 0,
942 // ret->street ? ret->street->item.id_lo : 0);
943 //dbg(3, "street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n",
944 // ret->street ? ret->street->c[0].x : 0,
945 // ret->street ? ret->street->c[0].y : 0,
946 // ret->street ? ret->street->count - 1 : 0,
947 // ret->street ? ret->street->c[ret->street->count - 1].x : 0,
948 // ret->street ? ret->street->c[ret->street->count - 1].y : 0);
949 this->pos = ret;
950 if (this->destinations)
951 route_path_update(this, 0, 1);
952 //dbg(2, "ret\n");
953 }
954
955 /* Used for debuging of route_rect, what routing sees */
956 struct map_selection *route_selection;
957
958 /**
959 * @brief Returns a single map selection
960 */
961 struct map_selection *
962 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
963 {
964 int dx, dy, sx = 1, sy = 1, d, m;
965 struct map_selection *sel=g_new(struct map_selection, 1);
966 if (!sel)
967 {
968 printf("%s:Out of memory\n", __FUNCTION__);
969 return sel;
970 }
971 sel->order = order;
972 sel->range.min = route_item_first;
973 sel->range.max = route_item_last;
974 dbg(1, "%p %p\n", c1, c2);
975 dx = c1->x - c2->x;
976 dy = c1->y - c2->y;
977 if (dx < 0)
978 {
979 sx = -1;
980 sel->u.c_rect.lu.x = c1->x;
981 sel->u.c_rect.rl.x = c2->x;
982 }
983 else
984 {
985 sel->u.c_rect.lu.x = c2->x;
986 sel->u.c_rect.rl.x = c1->x;
987 }
988 if (dy < 0)
989 {
990 sy = -1;
991 sel->u.c_rect.lu.y = c2->y;
992 sel->u.c_rect.rl.y = c1->y;
993 }
994 else
995 {
996 sel->u.c_rect.lu.y = c1->y;
997 sel->u.c_rect.rl.y = c2->y;
998 }
999 if (dx * sx > dy * sy)
1000 d = dx * sx;
1001 else
1002 d = dy * sy;
1003 m = d * rel / 100 + abs;
1004 sel->u.c_rect.lu.x -= m;
1005 sel->u.c_rect.rl.x += m;
1006 sel->u.c_rect.lu.y += m;
1007 sel->u.c_rect.rl.y -= m;
1008 sel->next = NULL;
1009 return sel;
1010 }
1011
1012 /**
1013 * @brief Returns a list of map selections useable to create a route graph
1014 *
1015 * Returns a list of map selections useable to get a map rect from which items can be
1016 * retrieved to build a route graph. The selections are a rectangle with
1017 * c1 and c2 as two corners.
1018 *
1019 * @param c1 Corner 1 of the rectangle
1020 * @param c2 Corder 2 of the rectangle
1021 */
1022 static struct map_selection *
1023 route_calc_selection(struct coord *c, int count, int try_harder)
1024 {
1025 struct map_selection *ret, *sel;
1026 int i;
1027 struct coord_rect r;
1028
1029 if (!count)
1030 return NULL;
1031 r.lu = c[0];
1032 r.rl = c[0];
1033 for (i = 1; i < count; i++)
1034 {
1035 coord_rect_extend(&r, &c[i]);
1036 }
1037
1038 if (routing_mode == 0)
1039 {
1040 // normal highway routing
1041 // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1042 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1043 }
1044 else if (routing_mode == 1)
1045 {
1046 // normal roads routing (should take longer and use more roads)
1047 // sel=route_rect(6, &r.lu, &r.rl, 25, 0);
1048 sel = route_rect(try_harder ? 7 : 6, &r.lu, &r.rl, 25, 0);
1049 }
1050 else
1051 {
1052 // DEFAULT setting
1053 // normal highway routing
1054 // sel=route_rect(4, &r.lu, &r.rl, 25, 0);
1055 sel = route_rect(try_harder ? 6 : 4, &r.lu, &r.rl, 25, 0);
1056 }
1057
1058 ret = sel;
1059 for (i = 0; i < count; i++)
1060 {
1061 sel->next = route_rect(8, &c[i], &c[i], 0, 40000);
1062 sel = sel->next;
1063 sel->next = route_rect(18, &c[i], &c[i], 0, 10000);
1064 sel = sel->next;
1065 }
1066 /* route_selection=ret; */
1067 return ret;
1068 }
1069
1070 /**
1071 * @brief Destroys a list of map selections
1072 *
1073 * @param sel Start of the list to be destroyed
1074 */
1075 static void route_free_selection(struct map_selection *sel)
1076 {
1077 struct map_selection *next;
1078 while (sel)
1079 {
1080 next = sel->next;
1081 g_free(sel);
1082 sel = next;
1083 }
1084 }
1085
1086 static void route_clear_destinations(struct route *this_)
1087 {
1088 g_list_foreach(this_->destinations, (GFunc) route_info_free, NULL);
1089 g_list_free(this_->destinations);
1090 this_->destinations = NULL;
1091 }
1092
1093 /**
1094 * @brief Sets the destination of a route
1095 *
1096 * This sets the destination of a route to the street nearest to the coordinates passed
1097 * and updates the route.
1098 *
1099 * @param this The route to set the destination for
1100 * @param dst Coordinates to set as destination
1101 * @param count: Number of destinations (last one is final)
1102 * @param async: If set, do routing asynchronously
1103 */
1104
1105 void route_set_destinations(struct route *this, struct pcoord *dst, int count, int async)
1106 {
1107 struct attr route_status;
1108 struct route_info *dsti;
1109 int i;
1110 route_status.type = attr_route_status;
1111
1112 //profile(0,NULL);
1113 route_clear_destinations(this);
1114
1115 if (dst && count)
1116 {
1117 for (i = 0; i < count; i++)
1118 {
1119 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[i]);
1120 if (dsti)
1121 {
1122 //dbg(0, "1: x y: %i %i\n", dst[i].x, dst[i].y);
1123 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1124 route_info_distances(dsti, dst->pro);
1125 this->destinations = g_list_append(this->destinations, dsti);
1126 }
1127 }
1128 route_status.u.num = route_status_destination_set;
1129 }
1130 else
1131 {
1132 route_status.u.num = route_status_no_destination;
1133 }
1134 callback_list_call_attr_1(this->cbl2, attr_destination, this);
1135 route_set_attr(this, &route_status);
1136 //profile(1,"find_nearest_street");
1137
1138 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1139 route_graph_destroy(this->graph);
1140 this->graph = NULL;
1141 this->current_dst = route_get_dst(this);
1142 this->try_harder = 0;
1143 route_path_update(this, 1, async);
1144 //profile(0,"end");
1145 }
1146
1147 void route_add_destination(struct route *this, struct pcoord *dst, int async)
1148 {
1149 struct attr route_status;
1150 struct route_info *dsti;
1151 route_status.type = attr_route_status;
1152
1153 dsti = route_find_nearest_street(this->vehicleprofile, this->ms, &dst[0]);
1154 if (dsti)
1155 {
1156 //dbg(0, "1: x y: %i %i\n", dst[0].x, dst[0].y);
1157 //dbg(0, "2: x y: %i %i\n", dsti->c.x, dsti->c.y);
1158
1159 route_info_distances(dsti, dst->pro);
1160 this->destinations = g_list_append(this->destinations, dsti);
1161
1162 route_status.u.num = route_status_destination_set;
1163 }
1164
1165 callback_list_call_attr_1(this->cbl2, attr_destination, this);
1166 route_set_attr(this, &route_status);
1167
1168 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
1169 route_graph_destroy(this->graph);
1170 this->graph = NULL;
1171 this->current_dst = route_get_dst(this);
1172 this->try_harder = 0;
1173 route_path_update(this, 1, async);
1174 }
1175
1176 int route_get_destinations(struct route *this, struct pcoord *pc, int count)
1177 {
1178 int ret = 0;
1179 GList *l = this->destinations;
1180 while (l && ret < count)
1181 {
1182 struct route_info *dst = l->data;
1183 pc->x = dst->c.x;
1184 pc->y = dst->c.y;
1185 pc->pro = projection_mg; /* FIXME */
1186 pc++;
1187 ret++;
1188 l = g_list_next(l);
1189 }
1190 return ret;
1191 }
1192
1193 void route_set_destination(struct route *this, struct pcoord *dst, int async)
1194 {
1195 route_set_destinations(this, dst, dst ? 1 : 0, async);
1196 }
1197
1198 void route_remove_waypoint(struct route *this)
1199 {
1200 struct route_path *path = this->path2;
1201 this->destinations = g_list_remove(this->destinations,
1202 this->destinations->data);
1203 this->path2 = this->path2->next;
1204 route_path_destroy(path, 0);
1205 if (!this->destinations)
1206 return;
1207 route_graph_reset(this->graph);
1208 this->current_dst = this->destinations->data;
1209 route_graph_flood(this->graph, this->current_dst, this->vehicleprofile,
1210 this->route_graph_flood_done_cb);
1211
1212 }
1213
1214 /**
1215 * @brief Gets the route_graph_point with the specified coordinates
1216 *
1217 * @param this The route in which to search
1218 * @param c Coordinates to search for
1219 * @param last The last route graph point returned to iterate over multiple points with the same coordinates
1220 * @return The point at the specified coordinates or NULL if not found
1221 */
1222 static struct route_graph_point *
1223 route_graph_get_point_next(struct route_graph *this, struct coord *c,
1224 struct route_graph_point *last)
1225 {
1226 struct route_graph_point *p;
1227 int seen = 0, hashval = HASHCOORD(c);
1228 p = this->hash[hashval];
1229 while (p)
1230 {
1231 if (p->c.x == c->x && p->c.y == c->y)
1232 {
1233 if (!last || seen)
1234 return p;
1235 if (p == last)
1236 seen = 1;
1237 }
1238 p = p->hash_next;
1239 }
1240 return NULL;
1241 }
1242
1243 static struct route_graph_point *
1244 route_graph_get_point(struct route_graph *this, struct coord *c)
1245 {
1246 return route_graph_get_point_next(this, c, NULL);
1247 }
1248
1249 /**
1250 * @brief Gets the last route_graph_point with the specified coordinates
1251 *
1252 * @param this The route in which to search
1253 * @param c Coordinates to search for
1254 * @return The point at the specified coordinates or NULL if not found
1255 */
1256 static struct route_graph_point *
1257 route_graph_get_point_last(struct route_graph *this, struct coord *c)
1258 {
1259 struct route_graph_point *p, *ret = NULL;
1260 int hashval = HASHCOORD(c);
1261 p = this->hash[hashval];
1262 while (p)
1263 {
1264 if (p->c.x == c->x && p->c.y == c->y)
1265 ret = p;
1266 p = p->hash_next;
1267 }
1268 return ret;
1269 }
1270
1271 /**
1272 * @brief Create a new point for the route graph with the specified coordinates
1273 *
1274 * @param this The route to insert the point into
1275 * @param f The coordinates at which the point should be created
1276 * @return The point created
1277 */
1278
1279 static struct route_graph_point *
1280 route_graph_point_new(struct route_graph *this, struct coord *f)
1281 {
1282 int hashval;
1283 struct route_graph_point *p;
1284
1285 hashval = HASHCOORD(f);
1286 if (debug_route)
1287 printf("p (0x%x,0x%x)\n", f->x, f->y);
1288 p=g_slice_new0(struct route_graph_point);
1289 p->hash_next = this->hash[hashval];
1290 this->hash[hashval] = p;
1291 p->value = INT_MAX;
1292 p->c = *f;
1293 return p;
1294 }
1295
1296 /**
1297 * @brief Inserts a point into the route graph at the specified coordinates
1298 *
1299 * This will insert a point into the route graph at the coordinates passed in f.
1300 * Note that the point is not yet linked to any segments.
1301 *
1302 * @param this The route to insert the point into
1303 * @param f The coordinates at which the point should be inserted
1304 * @return The point inserted or NULL on failure
1305 */
1306 static struct route_graph_point *
1307 route_graph_add_point(struct route_graph *this, struct coord *f)
1308 {
1309 struct route_graph_point *p;
1310
1311 p = route_graph_get_point(this, f);
1312 if (!p)
1313 p = route_graph_point_new(this, f);
1314 return p;
1315 }
1316
1317 /**
1318 * @brief Frees all the memory used for points in the route graph passed
1319 *
1320 * @param this The route graph to delete all points from
1321 */
1322 static void route_graph_free_points(struct route_graph *this)
1323 {
1324 struct route_graph_point *curr, *next;
1325 int i;
1326 for (i = 0; i < HASH_SIZE; i++)
1327 {
1328 curr = this->hash[i];
1329 while (curr)
1330 {
1331 next = curr->hash_next;
1332 g_slice_free(struct route_graph_point, curr);
1333 curr = next;
1334 }
1335 this->hash[i] = NULL;
1336 }
1337 }
1338
1339 /**
1340 * @brief Resets all nodes
1341 *
1342 * @param this The route graph to reset
1343 */
1344 static void route_graph_reset(struct route_graph *this)
1345 {
1346 struct route_graph_point *curr;
1347 int i;
1348 for (i = 0; i < HASH_SIZE; i++)
1349 {
1350 curr = this->hash[i];
1351 while (curr)
1352 {
1353 curr->value = INT_MAX;
1354 curr->seg = NULL;
1355 curr->el = NULL;
1356 curr = curr->hash_next;
1357 }
1358 }
1359 }
1360
1361 /**
1362 * @brief Returns the position of a certain field appended to a route graph segment
1363 *
1364 * This function returns a pointer to a field that is appended to a route graph
1365 * segment.
1366 *
1367 * @param seg The route graph segment the field is appended to
1368 * @param type Type of the field that should be returned
1369 * @return A pointer to a field of a certain type, or NULL if no such field is present
1370 */
1371 static void *
1372 route_segment_data_field_pos(struct route_segment_data *seg,
1373 enum attr_type type)
1374 {
1375 unsigned char *ptr;
1376
1377 ptr = ((unsigned char*) seg) + sizeof(struct route_segment_data);
1378
1379 if (seg->flags & AF_SPEED_LIMIT)
1380 {
1381 if (type == attr_maxspeed)
1382 return (void*) ptr;
1383 ptr += sizeof(int);
1384 }
1385 if (seg->flags & AF_SEGMENTED)
1386 {
1387 if (type == attr_offset)
1388 return (void*) ptr;
1389 ptr += sizeof(int);
1390 }
1391 if (seg->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1392 {
1393 if (type == attr_vehicle_width)
1394 return (void*) ptr;
1395 ptr += sizeof(struct size_weight_limit);
1396 }
1397 if (seg->flags & AF_DANGEROUS_GOODS)
1398 {
1399 if (type == attr_vehicle_dangerous_goods)
1400 return (void*) ptr;
1401 ptr += sizeof(int);
1402 }
1403 return NULL;
1404 }
1405
1406 /**
1407 * @brief Calculates the size of a route_segment_data struct with given flags
1408 *
1409 * @param flags The flags of the route_segment_data
1410 */
1411
1412 static int route_segment_data_size(int flags)
1413 {
1414 int ret = sizeof(struct route_segment_data);
1415 if (flags & AF_SPEED_LIMIT)
1416 ret += sizeof(int);
1417 if (flags & AF_SEGMENTED)
1418 ret += sizeof(int);
1419 if (flags & AF_SIZE_OR_WEIGHT_LIMIT)
1420 ret += sizeof(struct size_weight_limit);
1421 if (flags & AF_DANGEROUS_GOODS)
1422 ret += sizeof(int);
1423 return ret;
1424 }
1425
1426 static int route_graph_segment_is_duplicate(struct route_graph_point *start,
1427 struct route_graph_segment_data *data)
1428 {
1429 struct route_graph_segment *s;
1430 s = start->start;
1431 while (s)
1432 {
1433 if (item_is_equal(*data->item, s->data.item))
1434 {
1435 if (data->flags & AF_SEGMENTED)
1436 {
1437 if (RSD_OFFSET(&s->data) == data->offset)
1438 {
1439 return 1;
1440 }
1441 }
1442 else
1443 return 1;
1444 }
1445 s = s->start_next;
1446 }
1447 return 0;
1448 }
1449
1450 /**
1451 * @brief Inserts a new segment into the route graph
1452 *
1453 * This function performs a check if a segment for the item specified already exists, and inserts
1454 * a new segment representing this item if it does not.
1455 *
1456 * @param this The route graph to insert the segment into
1457 * @param start The graph point which should be connected to the start of this segment
1458 * @param end The graph point which should be connected to the end of this segment
1459 * @param len The length of this segment
1460 * @param item The item that is represented by this segment
1461 * @param flags Flags for this segment
1462 * @param offset If the item passed in "item" is segmented (i.e. divided into several segments), this indicates the position of this segment within the item
1463 * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1464 */
1465 static void route_graph_add_segment(struct route_graph *this,
1466 struct route_graph_point *start, struct route_graph_point *end,
1467 struct route_graph_segment_data *data)
1468 {
1469 struct route_graph_segment *s;
1470 int size;
1471
1472 size = sizeof(struct route_graph_segment)
1473 - sizeof(struct route_segment_data) + route_segment_data_size(
1474 data->flags);
1475 s = g_slice_alloc0(size);
1476 if (!s)
1477 {
1478 printf("%s:Out of memory\n", __FUNCTION__);
1479 return;
1480 }
1481 s->start = start;
1482 s->start_next = start->start;
1483 start->start = s;
1484 s->end = end;
1485 s->end_next = end->end;
1486 end->end = s;
1487 dbg_assert(data->len >= 0);
1488 s->data.len = data->len;
1489 s->data.item = *data->item;
1490 s->data.flags = data->flags;
1491
1492 if (data->flags & AF_SPEED_LIMIT)
1493 RSD_MAXSPEED(&s->data) = data->maxspeed;
1494 if (data->flags & AF_SEGMENTED)
1495 RSD_OFFSET(&s->data) = data->offset;
1496 if (data->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1497 RSD_SIZE_WEIGHT(&s->data) = data->size_weight;
1498 if (data->flags & AF_DANGEROUS_GOODS)
1499 RSD_DANGEROUS_GOODS(&s->data) = data->dangerous_goods;
1500
1501 s->next = this->route_segments;
1502 this->route_segments = s;
1503 if (debug_route)
1504 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x,
1505 end->c.y);
1506 }
1507
1508 /**
1509 * @brief Gets all the coordinates of an item
1510 *
1511 * This will get all the coordinates of the item i and return them in c,
1512 * up to max coordinates. Additionally it is possible to limit the coordinates
1513 * returned to all the coordinates of the item between the two coordinates
1514 * start end end.
1515 *
1516 * @important Make sure that whatever c points to has enough memory allocated
1517 * @important to hold max coordinates!
1518 *
1519 * @param i The item to get the coordinates of
1520 * @param c Pointer to memory allocated for holding the coordinates
1521 * @param max Maximum number of coordinates to return
1522 * @param start First coordinate to get
1523 * @param end Last coordinate to get
1524 * @return The number of coordinates returned
1525 */
1526 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1527 struct coord *start, struct coord *end)
1528 {
1529 struct map_rect *mr;
1530 struct item *item;
1531 int rc = 0, p = 0;
1532 struct coord c1;
1533 mr = map_rect_new(i->map, NULL);
1534 if (!mr)
1535 return 0;
1536 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1537 if (item)
1538 {
1539 rc = item_coord_get(item, &c1, 1);
1540 while (rc && (c1.x != start->x || c1.y != start->y))
1541 {
1542 rc = item_coord_get(item, &c1, 1);
1543 }
1544 while (rc && p < max)
1545 {
1546 c[p++] = c1;
1547 if (c1.x == end->x && c1.y == end->y)
1548 break;
1549 rc = item_coord_get(item, &c1, 1);
1550 }
1551 }
1552 map_rect_destroy(mr);
1553 return p;
1554 }
1555
1556 /**
1557 * @brief Returns and removes one segment from a path
1558 *
1559 * @param path The path to take the segment from
1560 * @param item The item whose segment to remove
1561 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1562 * @return The segment removed
1563 */
1564 static struct route_path_segment *
1565 route_extract_segment_from_path(struct route_path *path, struct item *item,
1566 int offset)
1567 {
1568 int soffset;
1569 struct route_path_segment *sp = NULL, *s;
1570 s = path->path;
1571 while (s)
1572 {
1573 if (item_is_equal(s->data->item, *item))
1574 {
1575 if (s->data->flags & AF_SEGMENTED)
1576 soffset = RSD_OFFSET(s->data);
1577 else
1578 soffset = 1;
1579 if (soffset == offset)
1580 {
1581 if (sp)
1582 {
1583 sp->next = s->next;
1584 break;
1585 }
1586 else
1587 {
1588 path->path = s->next;
1589 break;
1590 }
1591 }
1592 }
1593 sp = s;
1594 s = s->next;
1595 }
1596 if (s)
1597 item_hash_remove(path->path_hash, item);
1598 return s;
1599 }
1600
1601 /**
1602 * @brief Adds a segment and the end of a path
1603 *
1604 * @param this The path to add the segment to
1605 * @param segment The segment to add
1606 */
1607 static void route_path_add_segment(struct route_path *this,
1608 struct route_path_segment *segment)
1609 {
1610 if (!this->path)
1611 this->path = segment;
1612 if (this->path_last)
1613 this->path_last->next = segment;
1614 this->path_last = segment;
1615 }
1616
1617 /**
1618 * @brief Adds a two coordinate line to a path
1619 *
1620 * This adds a new line to a path, creating a new segment for it.
1621 *
1622 * @param this The path to add the item to
1623 * @param start coordinate to add to the start of the item. If none should be added, make this NULL.
1624 * @param end coordinate to add to the end of the item. If none should be added, make this NULL.
1625 * @param len The length of the item
1626 */
1627 static void route_path_add_line(struct route_path *this, struct coord *start,
1628 struct coord *end, int len)
1629 {
1630 int ccnt = 2;
1631 struct route_path_segment *segment;
1632 int seg_size, seg_dat_size;
1633
1634 //dbg(1, "line from 0x%x,0x%x-0x%x,0x%x\n", start->x, start->y, end->x,
1635 // end->y);
1636 seg_size = sizeof(*segment) + sizeof(struct coord) * ccnt;
1637 seg_dat_size = sizeof(struct route_segment_data);
1638 segment = g_malloc0(seg_size + seg_dat_size);
1639 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
1640 segment->ncoords = ccnt;
1641 segment->direction = 0;
1642 segment->c[0] = *start;
1643 segment->c[1] = *end;
1644 segment->data->len = len;
1645 route_path_add_segment(this, segment);
1646 }
1647
1648 /**
1649 * @brief Inserts a new item into the path
1650 *
1651 * This function does almost the same as "route_path_add_item()", but identifies
1652 * the item to add by a segment from the route graph. Another difference is that it "copies" the
1653 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1654 * be added to the route path, not all segments of the item.
1655 *
1656 * The function can be sped up by passing an old path already containing this segment in oldpath -
1657 * the segment will then be extracted from this old path. Please note that in this case the direction
1658 * parameter has no effect.
1659 *
1660 * @param this The path to add the item to
1661 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1662 * @param rgs Segment of the route graph that should be "copied" to the route path
1663 * @param dir Order in which to add the coordinates. See route_path_add_item()
1664 * @param pos Information about start point if this is the first segment
1665 * @param dst Information about end point if this is the last segment
1666 */
1667
1668 static int route_path_add_item_from_graph(struct route_path *this,
1669 struct route_path *oldpath, struct route_graph_segment *rgs, int dir,
1670 struct route_info *pos, struct route_info *dst)
1671 {
1672 struct route_path_segment *segment;
1673 int i, ccnt, extra = 0, ret = 0;
1674 struct coord *c, *cd, ca[2048];
1675 int offset = 1;
1676 int seg_size, seg_dat_size;
1677 int len = rgs->data.len;
1678 if (rgs->data.flags & AF_SEGMENTED)
1679 {
1680 offset = RSD_OFFSET(&rgs->data);
1681 }
1682
1683 //dbg(1, "enter (0x%x,0x%x) dir=%d pos=%p dst=%p\n", rgs->data.item.id_hi,
1684 // rgs->data.item.id_lo, dir, pos, dst);
1685 if (oldpath)
1686 {
1687 segment = item_hash_lookup(oldpath->path_hash, &rgs->data.item);
1688 if (segment && segment->direction == dir)
1689 {
1690 segment = route_extract_segment_from_path(oldpath, &rgs->data.item,
1691 offset);
1692 if (segment)
1693 {
1694 ret = 1;
1695 if (!pos)
1696 goto linkold;
1697 }
1698 }
1699 }
1700
1701 if (pos)
1702 {
1703 if (dst)
1704 {
1705 extra = 2;
1706 if (dst->lenneg >= pos->lenneg)
1707 {
1708 dir = 1;
1709 ccnt = dst->pos - pos->pos;
1710 c = pos->street->c + pos->pos + 1;
1711 len = dst->lenneg - pos->lenneg;
1712 }
1713 else
1714 {
1715 dir = -1;
1716 ccnt = pos->pos - dst->pos;
1717 c = pos->street->c + dst->pos + 1;
1718 len = pos->lenneg - dst->lenneg;
1719 }
1720 }
1721 else
1722 {
1723 extra = 1;
1724 //dbg(1, "pos dir=%d\n", dir);
1725 //dbg(1, "pos pos=%d\n", pos->pos);
1726 //dbg(1, "pos count=%d\n", pos->street->count);
1727 if (dir > 0)
1728 {
1729 c = pos->street->c + pos->pos + 1;
1730 ccnt = pos->street->count - pos->pos - 1;
1731 len = pos->lenpos;
1732 }
1733 else
1734 {
1735 c = pos->street->c;
1736 ccnt = pos->pos + 1;
1737 len = pos->lenneg;
1738 }
1739 }
1740 pos->dir = dir;
1741 }
1742 else if (dst)
1743 {
1744 extra = 1;
1745 //dbg(1, "dst dir=%d\n", dir);
1746 //dbg(1, "dst pos=%d\n", dst->pos);
1747 if (dir > 0)
1748 {
1749 c = dst->street->c;
1750 ccnt = dst->pos + 1;
1751 len = dst->lenpos;
1752 }
1753 else
1754 {
1755 c = dst->street->c + dst->pos + 1;
1756 ccnt = dst->street->count - dst->pos - 1;
1757 len = dst->lenneg;
1758 }
1759 }
1760 else
1761 {
1762 ccnt = get_item_seg_coords(&rgs->data.item, ca, 2047, &rgs->start->c,
1763 &rgs->end->c);
1764 c = ca;
1765 }
1766 seg_size = sizeof(*segment) + sizeof(struct coord) * (ccnt + extra);
1767 seg_dat_size = route_segment_data_size(rgs->data.flags);
1768 segment = g_malloc0(seg_size + seg_dat_size);
1769 segment->data = (struct route_segment_data *) ((char *) segment + seg_size);
1770 segment->direction = dir;
1771 cd = segment->c;
1772 if (pos && (c[0].x != pos->lp.x || c[0].y != pos->lp.y))
1773 *cd++ = pos->lp;
1774 if (dir < 0)
1775 c += ccnt - 1;
1776 for (i = 0; i < ccnt; i++)
1777 {
1778 *cd++ = *c;
1779 c += dir;
1780 }
1781 segment->ncoords += ccnt;
1782 if (dst && (cd[-1].x != dst->lp.x || cd[-1].y != dst->lp.y))
1783 *cd++ = dst->lp;
1784 segment->ncoords = cd - segment->c;
1785 if (segment->ncoords <= 1)
1786 {
1787 g_free(segment);
1788 return 1;
1789 }
1790
1791 /* We check if the route graph segment is part of a roundabout here, because this
1792 * only matters for route graph segments which form parts of the route path */
1793 if (!(rgs->data.flags & AF_ROUNDABOUT))
1794 { // We identified this roundabout earlier
1795 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1796 }
1797
1798 memcpy(segment->data, &rgs->data, seg_dat_size);
1799 linkold: segment->data->len = len;
1800 segment->next = NULL;
1801 item_hash_insert(this->path_hash, &rgs->data.item, segment);
1802
1803 route_path_add_segment(this, segment);
1804
1805 return ret;
1806 }
1807
1808 /**
1809 * @brief Destroys all segments of a route graph
1810 *
1811 * @param this The graph to destroy all segments from
1812 */
1813 static void route_graph_free_segments(struct route_graph *this)
1814 {
1815 struct route_graph_segment *curr, *next;
1816 int size;
1817 curr = this->route_segments;
1818 while (curr)
1819 {
1820 next = curr->next;
1821 size = sizeof(struct route_graph_segment)
1822 - sizeof(struct route_segment_data) + route_segment_data_size(
1823 curr->data.flags);
1824 g_slice_free1(size, curr);
1825 curr = next;
1826 }
1827 this->route_segments = NULL;
1828 }
1829
1830 /**
1831 * @brief Destroys a route graph
1832 *
1833 * @param this The route graph to be destroyed
1834 */
1835 void route_graph_destroy(struct route_graph *this)
1836 {
1837 if (this)
1838 {
1839 route_graph_build_done(this, 1);
1840 route_graph_free_points(this);
1841 route_graph_free_segments(this);
1842 g_free(this);
1843 }
1844 }
1845
1846 /**
1847 * @brief Returns the estimated speed on a segment
1848 *
1849 * This function returns the estimated speed to be driven on a segment, 0=not passable
1850 *
1851 * @param profile The routing preferences
1852 * @param over The segment which is passed
1853 * @param dist A traffic distortion if applicable
1854 * @return The estimated speed
1855 */
1856 static int route_seg_speed(struct vehicleprofile *profile,
1857 struct route_segment_data *over, struct route_traffic_distortion *dist)
1858 {
1859 struct roadprofile *roadprofile = vehicleprofile_get_roadprofile(profile,
1860 over->item.type);
1861 int speed, maxspeed;
1862 if (!roadprofile || !roadprofile->route_weight)
1863 return 0;
1864 /* maxspeed_handling: 0=always, 1 only if maxspeed restricts the speed, 2 never */
1865 speed = roadprofile->route_weight;
1866 if (profile->maxspeed_handling != 2)
1867 {
1868 if (over->flags & AF_SPEED_LIMIT)
1869 {
1870 maxspeed = RSD_MAXSPEED(over);
1871 if (!profile->maxspeed_handling)
1872 speed = maxspeed;
1873 }
1874 else
1875 maxspeed = INT_MAX;
1876 if (dist && maxspeed > dist->maxspeed)
1877 maxspeed = dist->maxspeed;
1878 if (maxspeed != INT_MAX && (profile->maxspeed_handling != 1 || maxspeed
1879 < speed))
1880 speed = maxspeed;
1881 }
1882 if (over->flags & AF_DANGEROUS_GOODS)
1883 {
1884 if (profile->dangerous_goods & RSD_DANGEROUS_GOODS(over))
1885 return 0;
1886 }
1887 if (over->flags & AF_SIZE_OR_WEIGHT_LIMIT)
1888 {
1889 struct size_weight_limit *size_weight = &RSD_SIZE_WEIGHT(over);
1890 if (size_weight->width != -1 && profile->width != -1 && profile->width
1891 > size_weight->width)
1892 return 0;
1893 if (size_weight->height != -1 && profile->height != -1
1894 && profile->height > size_weight->height)
1895 return 0;
1896 if (size_weight->length != -1 && profile->length != -1
1897 && profile->length > size_weight->length)
1898 return 0;
1899 if (size_weight->weight != -1 && profile->weight != -1
1900 && profile->weight > size_weight->weight)
1901 return 0;
1902 if (size_weight->axle_weight != -1 && profile->axle_weight != -1
1903 && profile->axle_weight > size_weight->axle_weight)
1904 return 0;
1905 }
1906 return speed;
1907 }
1908
1909 /**
1910 * @brief Returns the time needed to drive len on item
1911 *
1912 * This function returns the time needed to drive len meters on
1913 * the item passed in item in tenth of seconds.
1914 *
1915 * @param profile The routing preferences
1916 * @param over The segment which is passed
1917 * @param dist A traffic distortion if applicable
1918 * @return The time needed to drive len on item in thenth of senconds
1919 */
1920
1921 static int route_time_seg(struct vehicleprofile *profile,
1922 struct route_segment_data *over, struct route_traffic_distortion *dist)
1923 {
1924 int speed = route_seg_speed(profile, over, dist);
1925 if (!speed)
1926 return INT_MAX;
1927 return over->len * 36 / speed + (dist ? dist->delay : 0);
1928 }
1929
1930 static int route_get_traffic_distortion(struct route_graph_segment *seg,
1931 struct route_traffic_distortion *ret)
1932 {
1933 struct route_graph_point *start = seg->start;
1934 struct route_graph_point *end = seg->end;
1935 struct route_graph_segment *tmp, *found = NULL;
1936 tmp = start->start;
1937 while (tmp && !found)
1938 {
1939 if (tmp->data.item.type == type_traffic_distortion && tmp->start
1940 == start && tmp->end == end)
1941 found = tmp;
1942 tmp = tmp->start_next;
1943 }
1944 tmp = start->end;
1945 while (tmp && !found)
1946 {
1947 if (tmp->data.item.type == type_traffic_distortion && tmp->end == start
1948 && tmp->start == end)
1949 found = tmp;
1950 tmp = tmp->end_next;
1951 }
1952 if (found)
1953 {
1954 ret->delay = found->data.len;
1955 if (found->data.flags & AF_SPEED_LIMIT)
1956 ret->maxspeed = RSD_MAXSPEED(&found->data);
1957 else
1958 ret->maxspeed = INT_MAX;
1959 return 1;
1960 }
1961 return 0;
1962 }
1963
1964 static int route_through_traffic_allowed(struct vehicleprofile *profile,
1965 struct route_graph_segment *seg)
1966 {
1967 return (seg->data.flags & AF_THROUGH_TRAFFIC_LIMIT) == 0;
1968 }
1969
1970 /**
1971 * @brief Returns the "costs" of driving from point from over segment over in direction dir
1972 *
1973 * @param profile The routing preferences
1974 * @param from The point where we are starting
1975 * @param over The segment we are using
1976 * @param dir The direction of segment which we are driving
1977 * @return The "costs" needed to drive len on item
1978 */
1979
1980 static int route_value_seg(struct vehicleprofile *profile,
1981 struct route_graph_point *from, struct route_graph_segment *over,
1982 int dir)
1983 {
1984 int ret;
1985 struct route_traffic_distortion dist, *distp = NULL;
1986 #if 0
1987 dbg(0,"flags 0x%x mask 0x%x flags 0x%x\n", over->flags, dir >= 0 ? profile->flags_forward_mask : profile->flags_reverse_mask, profile->flags);
1988 #endif
1989 if ((over->data.flags & (dir >= 0 ? profile->flags_forward_mask
1990 : profile->flags_reverse_mask)) != profile->flags)
1991 return INT_MAX;
1992 if (dir > 0 && (over->start->flags & RP_TURN_RESTRICTION))
1993 return INT_MAX;
1994 if (dir < 0 && (over->end->flags & RP_TURN_RESTRICTION))
1995 return INT_MAX;
1996 if (from && from->seg == over)
1997 return INT_MAX;
1998 if ((over->start->flags & RP_TRAFFIC_DISTORTION) && (over->end->flags
1999 & RP_TRAFFIC_DISTORTION) && route_get_traffic_distortion(over,
2000 &dist))
2001 {
2002 distp = &dist;
2003 }
2004 ret = route_time_seg(profile, &over->data, distp);
2005 if (ret == INT_MAX)
2006 return ret;
2007 if (!route_through_traffic_allowed(profile, over) && from
2008 && route_through_traffic_allowed(profile, from->seg))
2009 ret += profile->through_traffic_penalty;
2010 return ret;
2011 }
2012
2013 /**
2014 * @brief Adds a route distortion item to the route graph
2015 *
2016 * @param this The route graph to add to
2017 * @param item The item to add
2018 */
2019 static void route_process_traffic_distortion(struct route_graph *this,
2020 struct item *item)
2021 {
2022 struct route_graph_point *s_pnt, *e_pnt;
2023 struct coord c, l;
2024 struct attr delay_attr, maxspeed_attr;
2025 struct route_graph_segment_data data;
2026
2027 data.item = item;
2028 data.len = 0;
2029 data.flags = 0;
2030 data.offset = 1;
2031 data.maxspeed = INT_MAX;
2032
2033 if (item_coord_get(item, &l, 1))
2034 {
2035 s_pnt = route_graph_add_point(this, &l);
2036 while (item_coord_get(item, &c, 1))
2037 {
2038 l = c;
2039 }
2040 e_pnt = route_graph_add_point(this, &l);
2041 s_pnt->flags |= RP_TRAFFIC_DISTORTION;
2042 e_pnt->flags |= RP_TRAFFIC_DISTORTION;
2043 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
2044 {
2045 data.flags |= AF_SPEED_LIMIT;
2046 data.maxspeed = maxspeed_attr.u.num;
2047 }
2048 if (item_attr_get(item, attr_delay, &delay_attr))
2049 data.len = delay_attr.u.num;
2050 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2051 }
2052 }
2053
2054 /**
2055 * @brief Adds a route distortion item to the route graph
2056 *
2057 * @param this The route graph to add to
2058 * @param item The item to add
2059 */
2060 static void route_process_turn_restriction(struct route_graph *this,
2061 struct item *item)
2062 {
2063 struct route_graph_point *pnt[4];
2064 struct coord c[5];
2065 int i, count;
2066 struct route_graph_segment_data data;
2067
2068 count = item_coord_get(item, c, 5);
2069 if (count != 3 && count != 4)
2070 {
2071 dbg(0, "wrong count %d\n", count);
2072 return;
2073 }
2074 if (count == 4)
2075 {
2076 return;
2077 }
2078 for (i = 0; i < count; i++)
2079 {
2080 pnt[i] = route_graph_add_point(this, &c[i]);
2081 }
2082 //dbg(1, "%s: (0x%x,0x%x)-(0x%x,0x%x)-(0x%x,0x%x) %p-%p-%p\n",
2083 // item_to_name(item->type), c[0].x, c[0].y, c[1].x, c[1].y, c[2].x,
2084 // c[2].y, pnt[0], pnt[1], pnt[2]);
2085 data.item = item;
2086 data.flags = 0;
2087 data.len = 0;
2088 route_graph_add_segment(this, pnt[0], pnt[1], &data);
2089 route_graph_add_segment(this, pnt[1], pnt[2], &data);
2090 #if 1
2091 if (count == 4)
2092 {
2093 pnt[1]->flags |= RP_TURN_RESTRICTION;
2094 pnt[2]->flags |= RP_TURN_RESTRICTION;
2095 route_graph_add_segment(this, pnt[2], pnt[3], &data);
2096 }
2097 else
2098 {
2099 pnt[1]->flags |= RP_TURN_RESTRICTION;
2100 }
2101 #endif
2102 }
2103
2104 /**
2105 * @brief Adds an item to the route graph
2106 *
2107 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
2108 * segmented item.
2109 *
2110 * @param this The route graph to add to
2111 * @param item The item to add
2112 * @param profile The vehicle profile currently in use
2113 */
2114 static void route_process_street_graph(struct route_graph *this,
2115 struct item *item, struct vehicleprofile *profile)
2116 {
2117 #ifdef AVOID_FLOAT
2118 int len=0;
2119 #else
2120 double len = 0;
2121 #endif
2122 int segmented = 0;
2123 struct roadprofile *roadp;
2124 struct route_graph_point *s_pnt, *e_pnt;
2125 struct coord c, l;
2126 struct attr attr;
2127 struct route_graph_segment_data data;
2128 data.flags = 0;
2129 data.offset = 1;
2130 data.maxspeed = -1;
2131 data.item = item;
2132
2133 roadp = vehicleprofile_get_roadprofile(profile, item->type);
2134 if (!roadp)
2135 {
2136 // Don't include any roads that don't have a road profile in our vehicle profile
2137 return;
2138 }
2139
2140 if (item_coord_get(item, &l, 1))
2141 {
2142 int *default_flags = item_get_default_flags(item->type);
2143 if (!default_flags)
2144 return;
2145 if (item_attr_get(item, attr_flags, &attr))
2146 {
2147 data.flags = attr.u.num;
2148 if (data.flags & AF_SEGMENTED)
2149 segmented = 1;
2150 }
2151 else
2152 data.flags = *default_flags;
2153
2154 if (data.flags & AF_SPEED_LIMIT)
2155 {
2156 if (item_attr_get(item, attr_maxspeed, &attr))
2157 data.maxspeed = attr.u.num;
2158 }
2159 if (data.flags & AF_DANGEROUS_GOODS)
2160 {
2161 if (item_attr_get(item, attr_vehicle_dangerous_goods, &attr))
2162 data.dangerous_goods = attr.u.num;
2163 else
2164 data.flags &= ~AF_DANGEROUS_GOODS;
2165 }
2166 if (data.flags & AF_SIZE_OR_WEIGHT_LIMIT)
2167 {
2168 if (item_attr_get(item, attr_vehicle_width, &attr))
2169 data.size_weight.width = attr.u.num;
2170 else
2171 data.size_weight.width = -1;
2172 if (item_attr_get(item, attr_vehicle_height, &attr))
2173 data.size_weight.height = attr.u.num;
2174 else
2175 data.size_weight.height = -1;
2176 if (item_attr_get(item, attr_vehicle_length, &attr))
2177 data.size_weight.length = attr.u.num;
2178 else
2179 data.size_weight.length = -1;
2180 if (item_attr_get(item, attr_vehicle_weight, &attr))
2181 data.size_weight.weight = attr.u.num;
2182 else
2183 data.size_weight.weight = -1;
2184 if (item_attr_get(item, attr_vehicle_axle_weight, &attr))
2185 data.size_weight.axle_weight = attr.u.num;
2186 else
2187 data.size_weight.axle_weight = -1;
2188 }
2189
2190 s_pnt = route_graph_add_point(this, &l);
2191 if (!segmented)
2192 {
2193 while (item_coord_get(item, &c, 1))
2194 {
2195 len += transform_distance(map_projection(item->map), &l, &c);
2196 l = c;
2197 }
2198 e_pnt = route_graph_add_point(this, &l);
2199 dbg_assert(len >= 0);
2200 data.len = len;
2201 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2202 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2203 }
2204 else
2205 {
2206 int isseg, rc;
2207 int sc = 0;
2208 do
2209 {
2210 isseg = item_coord_is_node(item);
2211 rc = item_coord_get(item, &c, 1);
2212 if (rc)
2213 {
2214 len
2215 += transform_distance(map_projection(item->map),
2216 &l, &c);
2217 l = c;
2218 if (isseg)
2219 {
2220 e_pnt = route_graph_add_point(this, &l);
2221 data.len = len;
2222 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2223 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2224 data.offset++;
2225 s_pnt = route_graph_add_point(this, &l);
2226 len = 0;
2227 }
2228 }
2229 }
2230 while (rc);
2231 e_pnt = route_graph_add_point(this, &l);
2232 dbg_assert(len >= 0);
2233 sc++;
2234 data.len = len;
2235 if (!route_graph_segment_is_duplicate(s_pnt, &data))
2236 route_graph_add_segment(this, s_pnt, e_pnt, &data);
2237 }
2238 }
2239 }
2240
2241 static struct route_graph_segment *
2242 route_graph_get_segment(struct route_graph *graph, struct street_data *sd,
2243 struct route_graph_segment *last)
2244 {
2245 struct route_graph_point *start = NULL;
2246 struct route_graph_segment *s;
2247 int seen = 0;
2248
2249 while ((start = route_graph_get_point_next(graph, &sd->c[0], start)))
2250 {
2251 s = start->start;
2252 while (s)
2253 {
2254 if (item_is_equal(sd->item, s->data.item))
2255 {
2256 if (!last || seen)
2257 return s;
2258 if (last == s)
2259 seen = 1;
2260 }
2261 s = s->start_next;
2262 }
2263 }
2264 return NULL;
2265 }
2266
2267 /**
2268 * @brief Calculates the routing costs for each point
2269 *
2270 * This function is the heart of routing. It assigns each point in the route graph a
2271 * cost at which one can reach the destination from this point on. Additionally it assigns
2272 * each point a segment one should follow from this point on to reach the destination at the
2273 * stated costs.
2274 *
2275 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
2276 * at this algorithm.
2277 */
2278 static void route_graph_flood(struct route_graph *this, struct route_info *dst,
2279 struct vehicleprofile *profile, struct callback *cb)
2280 {
2281 struct route_graph_point *p_min;
2282 struct route_graph_segment *s = NULL;
2283 int min, new, old, val;
2284 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
2285
2286 heap = fh_makekeyheap();
2287
2288 while ((s = route_graph_get_segment(this, dst->street, s)))
2289 {
2290 val = route_value_seg(profile, NULL, s, -1);
2291 if (val != INT_MAX)
2292 {
2293 val = val * (100 - dst->percent) / 100;
2294 s->end->seg = s;
2295 s->end->value = val;
2296 s->end->el = fh_insertkey(heap, s->end->value, s->end);
2297 }
2298 val = route_value_seg(profile, NULL, s, 1);
2299 if (val != INT_MAX)
2300 {
2301 val = val * dst->percent / 100;
2302 s->start->seg = s;
2303 s->start->value = val;
2304 s->start->el = fh_insertkey(heap, s->start->value, s->start);
2305 }
2306 }
2307 for (;;)
2308 {
2309 p_min = fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
2310 if (!p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
2311 break;
2312 min = p_min->value;
2313 if (debug_route)
2314 printf("extract p=%p free el=%p min=%d, 0x%x, 0x%x\n", p_min,
2315 p_min->el, min, p_min->c.x, p_min->c.y);
2316 p_min->el = NULL; /* This point is permanently calculated now, we've taken it out of the heap */
2317 s = p_min->start;
2318 while (s)
2319 { /* Iterating all the segments leading away from our point to update the points at their ends */
2320 val = route_value_seg(profile, p_min, s, -1);
2321 if (val != INT_MAX && !item_is_equal(s->data.item,
2322 p_min->seg->data.item))
2323 {
2324 new = min + val;
2325 if (debug_route)
2326 printf("begin %d len %d vs %d (0x%x,0x%x)\n", new, val,
2327 s->end->value, s->end->c.x, s->end->c.y);
2328 if (new < s->end->value)
2329 { /* We've found a less costly way to reach the end of s, update it */
2330 s->end->value = new;
2331 s->end->seg = s;
2332 if (!s->end->el)
2333 {
2334 if (debug_route)
2335 printf("insert_end p=%p el=%p val=%d ", s->end,
2336 s->end->el, s->end->value);
2337 s->end->el = fh_insertkey(heap, new, s->end);
2338 if (debug_route)
2339 printf("el new=%p\n", s->end->el);
2340 }
2341 else
2342 {
2343 if (debug_route)
2344 printf("replace_end p=%p el=%p val=%d\n", s->end,
2345 s->end->el, s->end->value);
2346 fh_replacekey(heap, s->end->el, new);
2347 }
2348 }
2349 if (debug_route)
2350 printf("\n");
2351 }
2352 s = s->start_next;
2353 }
2354 s = p_min->end;
2355 while (s)
2356 { /* Doing the same as above with the segments leading towards our point */
2357 val = route_value_seg(profile, p_min, s, 1);
2358 if (val != INT_MAX && !item_is_equal(s->data.item,
2359 p_min->seg->data.item))
2360 {
2361 new = min + val;
2362 if (debug_route)
2363 printf("end %d len %d vs %d (0x%x,0x%x)\n", new, val,
2364 s->start->value, s->start->c.x, s->start->c.y);
2365 if (new < s->start->value)
2366 {
2367 old = s->start->value;
2368 s->start->value = new;
2369 s->start->seg = s;
2370 if (!s->start->el)
2371 {
2372 if (debug_route)
2373 printf("insert_start p=%p el=%p val=%d ", s->start,
2374 s->start->el, s->start->value);
2375 s->start->el = fh_insertkey(heap, new, s->start);
2376 if (debug_route)
2377 printf("el new=%p\n", s->start->el);
2378 }
2379 else
2380 {
2381 if (debug_route)
2382 printf("replace_start p=%p el=%p val=%d\n",
2383 s->start, s->start->el, s->start->value);
2384 fh_replacekey(heap, s->start->el, new);
2385 }
2386 }
2387 if (debug_route)
2388 printf("\n");
2389 }
2390 s = s->end_next;
2391 }
2392 }
2393 fh_deleteheap(heap);
2394 callback_call_0(cb);
2395 //dbg(1, "return\n");
2396 }
2397
2398 /**
2399 * @brief Starts an "offroad" path
2400 *
2401 * This starts a path that is not located on a street. It creates a new route path
2402 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
2403 *
2404 * @param this Not used
2405 * @param pos The starting position for the new path
2406 * @param dst The destination of the new path
2407 * @param dir Not used
2408 * @return The new path
2409 */
2410 static struct route_path *
2411 route_path_new_offroad(struct route_graph *this, struct route_info *pos,
2412 struct route_info *dst)
2413 {
2414 struct route_path *ret;
2415
2416 ret=g_new0(struct route_path, 1);
2417 ret->in_use = 1;
2418 ret->path_hash = item_hash_new();
2419 route_path_add_line(ret, &pos->c, &dst->c, pos->lenextra + dst->lenextra);
2420 ret->updated = 1;
2421
2422 return ret;
2423 }
2424
2425 /**
2426 * @brief Returns a coordinate at a given distance
2427 *
2428 * This function returns the coordinate, where the user will be if he
2429 * follows the current route for a certain distance.
2430 *
2431 * @param this_ The route we're driving upon
2432 * @param dist The distance in meters
2433 * @return The coordinate where the user will be in that distance
2434 */
2435 struct coord route_get_coord_dist(struct route *this_, int dist)
2436 {
2437 int d, l, i, len;
2438 int dx, dy;
2439 double frac;
2440 struct route_path_segment *cur;
2441 struct coord ret;
2442 enum projection pro = route_projection(this_);
2443 struct route_info *dst = route_get_dst(this_);
2444
2445 d = dist;
2446
2447 if (!this_->path2 || pro == projection_none)
2448 {
2449 return this_->pos->c;
2450 }
2451
2452 ret = this_->pos->c;
2453 cur = this_->path2->path;
2454 while (cur)
2455 {
2456 if (cur->data->len < d)
2457 {
2458 d -= cur->data->len;
2459 }
2460 else
2461 {
2462 for (i = 0; i < (cur->ncoords - 1); i++)
2463 {
2464 l = d;
2465 len = (int) transform_polyline_length(pro, (cur->c + i), 2);
2466 d -= len;
2467 if (d <= 0)
2468 {
2469 // We interpolate a bit here...
2470 frac = (double) l / len;
2471
2472 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
2473 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
2474
2475 ret.x = (cur->c + i)->x + (frac * dx);
2476 ret.y = (cur->c + i)->y + (frac * dy);
2477 return ret;
2478 }
2479 }
2480 return cur->c[(cur->ncoords - 1)];
2481 }
2482 cur = cur->next;
2483 }
2484
2485 return dst->c;
2486 }
2487
2488 /**
2489 * @brief Creates a new route path
2490 *
2491 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
2492 * make sure to run route_graph_flood() after changing the destination before using this function.
2493 *
2494 * @param this The route graph to create the route from
2495 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
2496 * @param pos The starting position of the route
2497 * @param dst The destination of the route
2498 * @param preferences The routing preferences
2499 * @return The new route path
2500 */
2501 static struct route_path *
2502 route_path_new(struct route_graph *this, struct route_path *oldpath,
2503 struct route_info *pos, struct route_info *dst,
2504 struct vehicleprofile *profile)
2505 {
2506 struct route_graph_segment *first, *s = NULL, *s1 = NULL, *s2 = NULL;
2507 struct route_graph_point *start;
2508 struct route_info *posinfo, *dstinfo;
2509 int segs = 0;
2510 int val1 = INT_MAX, val2 = INT_MAX;
2511 int val, val1_new, val2_new;
2512 struct route_path *ret;
2513
2514 if (!pos->street || !dst->street)
2515 {
2516 dbg(0, "pos or dest not set\n");
2517 return NULL;
2518 }
2519
2520 if (profile->mode == 2 || (profile->mode == 0 && pos->lenextra
2521 + dst->lenextra > transform_distance(
2522 map_projection(pos->street->item.map), &pos->c, &dst->c)))
2523 return route_path_new_offroad(this, pos, dst);
2524 while ((s = route_graph_get_segment(this, pos->street, s)))
2525 {
2526 val = route_value_seg(profile, NULL, s, 1);
2527 if (val != INT_MAX && s->end->value != INT_MAX)
2528 {
2529 val = val * (100 - pos->percent) / 100;
2530 val1_new = s->end->value + val;
2531 if (val1_new < val1)
2532 {
2533 val1 = val1_new;
2534 s1 = s;
2535 }
2536 }
2537 val = route_value_seg(profile, NULL, s, -1);
2538 if (val != INT_MAX && s->start->value != INT_MAX)
2539 {
2540 val = val * pos->percent / 100;
2541 val2_new = s->start->value + val;
2542 if (val2_new < val2)
2543 {
2544 val2 = val2_new;
2545 s2 = s;
2546 }
2547 }
2548 }
2549 if (val1 == INT_MAX && val2 == INT_MAX)
2550 {
2551 dbg(0, "no route found, pos blocked\n");
2552 return NULL;
2553 }
2554 if (val1 == val2)
2555 {
2556 val1 = s1->end->value;
2557 val2 = s2->start->value;
2558 }
2559 if (val1 < val2)
2560 {
2561 start = s1->start;
2562 s = s1;
2563 }
2564 else
2565 {
2566 start = s2->end;
2567 s = s2;
2568 }ret=g_new0(struct route_path, 1);
2569 ret->in_use = 1;
2570 ret->updated = 1;
2571 if (pos->lenextra)
2572 route_path_add_line(ret, &pos->c, &pos->lp, pos->lenextra);
2573 ret->path_hash = item_hash_new();
2574 dstinfo = NULL;
2575 posinfo = pos;
2576 first = s;
2577 while (s && !dstinfo)
2578 { /* following start->seg, which indicates the least costly way to reach our destination */
2579 segs++;
2580 #if 0
2581 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
2582 #endif
2583 if (s->start == start)
2584 {
2585 if (item_is_equal(s->data.item, dst->street->item) && (s->end->seg
2586 == s || !posinfo))
2587 dstinfo = dst;
2588 if (!route_path_add_item_from_graph(ret, oldpath, s, 1, posinfo,
2589 dstinfo))
2590 ret->updated = 0;
2591 start = s->end;
2592 }
2593 else
2594 {
2595 if (item_is_equal(s->data.item, dst->street->item)
2596 && (s->start->seg == s || !posinfo))
2597 dstinfo = dst;
2598 if (!route_path_add_item_from_graph(ret, oldpath, s, -1, posinfo,
2599 dstinfo))
2600 ret->updated = 0;
2601 start = s->start;
2602 }
2603 posinfo = NULL;
2604 s = start->seg;
2605 }
2606 if (dst->lenextra)
2607 route_path_add_line(ret, &dst->lp, &dst->c, dst->lenextra);
2608 //dbg(1, "%d segments\n", segs);
2609 return ret;
2610 }
2611
2612 static int route_graph_build_next_map(struct route_graph *rg)
2613 {
2614 do
2615 {
2616 rg->m = mapset_next(rg->h, 2);
2617 if (!rg->m)
2618 return 0;
2619 map_rect_destroy(rg->mr);
2620 rg->mr = map_rect_new(rg->m, rg->sel);
2621 }
2622 while (!rg->mr);
2623
2624 return 1;
2625 }
2626
2627 static int is_turn_allowed(struct route_graph_point *p,
2628 struct route_graph_segment *from, struct route_graph_segment *to)
2629 {
2630 struct route_graph_point *prev, *next;
2631 struct route_graph_segment *tmp1, *tmp2;
2632 if (item_is_equal(from->data.item, to->data.item))
2633 return 0;
2634 if (from->start == p)
2635 prev = from->end;
2636 else
2637 prev = from->start;
2638 if (to->start == p)
2639 next = to->end;
2640 else
2641 next = to->start;
2642 tmp1 = p->end;
2643 while (tmp1)
2644 {
2645 if (tmp1->start->c.x == prev->c.x && tmp1->start->c.y == prev->c.y
2646 && (tmp1->data.item.type == type_street_turn_restriction_no
2647 || tmp1->data.item.type
2648 == type_street_turn_restriction_only))
2649 {
2650 tmp2 = p->start;
2651 //dbg(1, "found %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
2652 // item_to_name(tmp1->data.item.type), tmp1->data.item.id_hi,
2653 // tmp1->data.item.id_lo, tmp1->start->c.x, tmp1->start->c.y,
2654 // tmp1->end->c.x, tmp1->end->c.y, tmp1->start, tmp1->end);
2655 while (tmp2)
2656 {
2657 //dbg(
2658 // 1,
2659 // "compare %s (0x%x,0x%x) (0x%x,0x%x)-(0x%x,0x%x) %p-%p\n",
2660 // item_to_name(tmp2->data.item.type),
2661 // tmp2->data.item.id_hi, tmp2->data.item.id_lo,
2662 // tmp2->start->c.x, tmp2->start->c.y, tmp2->end->c.x,
2663 // tmp2->end->c.y, tmp2->start, tmp2->end);
2664 if (item_is_equal(tmp1->data.item, tmp2->data.item))
2665 break;
2666 tmp2 = tmp2->start_next;
2667 }
2668 //dbg(1, "tmp2=%p\n", tmp2);
2669 if (tmp2)
2670 {
2671 //dbg(1, "%s tmp2->end=%p next=%p\n",
2672 // item_to_name(tmp1->data.item.type), tmp2->end, next);
2673 }
2674 if (tmp1->data.item.type == type_street_turn_restriction_no && tmp2
2675 && tmp2->end->c.x == next->c.x && tmp2->end->c.y
2676 == next->c.y)
2677 {
2678 //dbg(
2679 // 1,
2680 // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (no)\n",
2681 // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
2682 // next->c.y);
2683 return 0;
2684 }
2685 if (tmp1->data.item.type == type_street_turn_restriction_only
2686 && tmp2 && (tmp2->end->c.x != next->c.x || tmp2->end->c.y
2687 != next->c.y))
2688 {
2689 //dbg(
2690 // 1,
2691 // "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x not allowed (only)\n",
2692 // prev->c.x, prev->c.y, p->c.x, p->c.y, next->c.x,
2693 // next->c.y);
2694 return 0;
2695 }
2696 }
2697 tmp1 = tmp1->end_next;
2698 }
2699 //dbg(1, "from 0x%x,0x%x over 0x%x,0x%x to 0x%x,0x%x allowed\n", prev->c.x,
2700 // prev->c.y, p->c.x, p->c.y, next->c.x, next->c.y);
2701 return 1;
2702 }
2703
2704 static void route_graph_clone_segment(struct route_graph *this,
2705 struct route_graph_segment *s, struct route_graph_point *start,
2706 struct route_graph_point *end, int flags)
2707 {
2708 struct route_graph_segment_data data;
2709 data.flags = s->data.flags | flags;
2710 data.offset = 1;
2711 data.maxspeed = -1;
2712 data.item = &s->data.item;
2713 data.len = s->data.len + 1;
2714 if (s->data.flags & AF_SPEED_LIMIT)
2715 data.maxspeed = RSD_MAXSPEED(&s->data);
2716 if (s->data.flags & AF_SEGMENTED)
2717 data.offset = RSD_OFFSET(&s->data);
2718 //dbg(1, "cloning segment from %p (0x%x,0x%x) to %p (0x%x,0x%x)\n", start,
2719 // start->c.x, start->c.y, end, end->c.x, end->c.y);
2720 route_graph_add_segment(this, start, end, &data);
2721 }
2722
2723 static void route_graph_process_restriction_segment(struct route_graph *this,
2724 struct route_graph_point *p, struct route_graph_segment *s, int dir)
2725 {
2726 struct route_graph_segment *tmp;
2727 struct route_graph_point *pn;
2728 struct coord c = p->c;
2729 int dx = 0;
2730 int dy = 0;
2731 c.x += dx;
2732 c.y += dy;
2733 //dbg(1, "From %s %d,%d\n", item_to_name(s->data.item.type), dx, dy);
2734 pn = route_graph_point_new(this, &c);
2735 if (dir > 0)
2736 { /* going away */
2737 //dbg(1, "other 0x%x,0x%x\n", s->end->c.x, s->end->c.y);
2738 if (s->data.flags & AF_ONEWAY)
2739 {
2740 //dbg(1, "Not possible\n");
2741 return;
2742 }
2743 route_graph_clone_segment(this, s, pn, s->end, AF_ONEWAYREV);
2744 }
2745 else
2746 { /* coming in */
2747 //dbg(1, "other 0x%x,0x%x\n", s->start->c.x, s->start->c.y);
2748 if (s->data.flags & AF_ONEWAYREV)
2749 {
2750 //dbg(1, "Not possible\n");
2751 return;
2752 }
2753 route_graph_clone_segment(this, s, s->start, pn, AF_ONEWAY);
2754 }
2755 tmp = p->start;
2756 while (tmp)
2757 {
2758 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no
2759 && tmp->data.item.type != type_street_turn_restriction_only
2760 && !(tmp->data.flags & AF_ONEWAYREV) && is_turn_allowed(p, s,
2761 tmp))
2762 {
2763 route_graph_clone_segment(this, tmp, pn, tmp->end, AF_ONEWAY);
2764 //dbg(1, "To start %s\n", item_to_name(tmp->data.item.type));
2765 }
2766 tmp = tmp->start_next;
2767 }
2768 tmp = p->end;
2769 while (tmp)
2770 {
2771 if (tmp != s && tmp->data.item.type != type_street_turn_restriction_no
2772 && tmp->data.item.type != type_street_turn_restriction_only
2773 && !(tmp->data.flags & AF_ONEWAY) && is_turn_allowed(p, s, tmp))
2774 {
2775 route_graph_clone_segment(this, tmp, tmp->start, pn, AF_ONEWAYREV);
2776 //dbg(1, "To end %s\n", item_to_name(tmp->data.item.type));
2777 }
2778 tmp = tmp->end_next;
2779 }
2780 }
2781
2782 static void route_graph_process_restriction_point(struct route_graph *this,
2783 struct route_graph_point *p)
2784 {
2785 struct route_graph_segment *tmp;
2786 tmp = p->start;
2787 //dbg(1, "node 0x%x,0x%x\n", p->c.x, p->c.y);
2788 while (tmp)
2789 {
2790 if (tmp->data.item.type != type_street_turn_restriction_no
2791 && tmp->data.item.type != type_street_turn_restriction_only)
2792 route_graph_process_restriction_segment(this, p, tmp, 1);
2793 tmp = tmp->start_next;
2794 }
2795 tmp = p->end;
2796 while (tmp)
2797 {
2798 if (tmp->data.item.type != type_street_turn_restriction_no
2799 && tmp->data.item.type != type_street_turn_restriction_only)
2800 route_graph_process_restriction_segment(this, p, tmp, -1);
2801 tmp = tmp->end_next;
2802 }
2803 p->flags |= RP_TURN_RESTRICTION_RESOLVED;
2804 }
2805
2806 static void route_graph_process_restrictions(struct route_graph *this)
2807 {
2808 struct route_graph_point *curr;
2809 int i;
2810 //dbg(1, "enter\n");
2811 for (i = 0; i < HASH_SIZE; i++)
2812 {
2813 curr = this->hash[i];
2814 while (curr)
2815 {
2816 if (curr->flags & RP_TURN_RESTRICTION)
2817 route_graph_process_restriction_point(this, curr);
2818 curr = curr->hash_next;
2819 }
2820 }
2821 }
2822
2823 static void route_graph_build_done(struct route_graph *rg, int cancel)
2824 {
2825 //dbg(1, "cancel=%d\n", cancel);
2826 if (rg->idle_ev)
2827 event_remove_idle(rg->idle_ev);
2828 if (rg->idle_cb)
2829 callback_destroy(rg->idle_cb);
2830 map_rect_destroy(rg->mr);
2831 mapset_close(rg->h);
2832 route_free_selection(rg->sel);
2833 rg->idle_ev = NULL;
2834 rg->idle_cb = NULL;
2835 rg->mr = NULL;
2836 rg->h = NULL;
2837 rg->sel = NULL;
2838 if (!cancel)
2839 {
2840 route_graph_process_restrictions(rg);
2841 callback_call_0(rg->done_cb);
2842 }
2843 rg->busy = 0;
2844 }
2845
2846 static void route_graph_build_idle(struct route_graph *rg,
2847 struct vehicleprofile *profile)
2848 {
2849 int count = 1000;
2850 struct item *item;
2851
2852 while (count > 0)
2853 {
2854 for (;;)
2855 {
2856 item = map_rect_get_item(rg->mr);
2857 if (item)
2858 break;
2859 if (!route_graph_build_next_map(rg))
2860 {
2861 route_graph_build_done(rg, 0);
2862 return;
2863 }
2864 }
2865 if (item->type == type_traffic_distortion)
2866 route_process_traffic_distortion(rg, item);
2867 else if (item->type == type_street_turn_restriction_no || item->type
2868 == type_street_turn_restriction_only)
2869 route_process_turn_restriction(rg, item);
2870 else
2871 route_process_street_graph(rg, item, profile);
2872 count--;
2873 }
2874 }
2875
2876 /**
2877 * @brief Builds a new route graph from a mapset
2878 *
2879 * This function builds a new route graph from a map. Please note that this function does not
2880 * add any routing information to the route graph - this has to be done via the route_graph_flood()
2881 * function.
2882 *
2883 * The function does not create a graph covering the whole map, but only covering the rectangle
2884 * between c1 and c2.
2885 *
2886 * @param ms The mapset to build the route graph from
2887 * @param c1 Corner 1 of the rectangle to use from the map
2888 * @param c2 Corner 2 of the rectangle to use from the map
2889 * @param done_cb The callback which will be called when graph is complete
2890 * @return The new route graph.
2891 */
2892 static struct route_graph *
2893 route_graph_build(struct mapset *ms, struct coord *c, int count,
2894 struct callback *done_cb, int async, struct vehicleprofile *profile,
2895 int try_harder)
2896 {
2897 struct route_graph *ret=g_new0(struct route_graph, 1);
2898
2899 //dbg(1, "enter\n");
2900
2901 ret->sel = route_calc_selection(c, count, try_harder);
2902 ret->h = mapset_open(ms);
2903 ret->done_cb = done_cb;
2904 ret->busy = 1;
2905 if (route_graph_build_next_map(ret))
2906 {
2907 if (async)
2908 {
2909 ret->idle_cb = callback_new_2(
2910 callback_cast(route_graph_build_idle), ret, profile);
2911 ret->idle_ev = event_add_idle(50, ret->idle_cb);
2912 }
2913 }
2914 else
2915 route_graph_build_done(ret, 0);
2916
2917 return ret;
2918 }
2919
2920 static void route_graph_update_done(struct route *this, struct callback *cb)
2921 {
2922 route_graph_flood(this->graph, this->current_dst, this->vehicleprofile, cb);
2923 }
2924
2925 /**
2926 * @brief Updates the route graph
2927 *
2928 * This updates the route graph after settings in the route have changed. It also
2929 * adds routing information afterwards by calling route_graph_flood().
2930 *
2931 * @param this The route to update the graph for
2932 */
2933 static void route_graph_update(struct route *this, struct callback *cb,
2934 int async)
2935 {
2936 struct attr route_status;
2937 struct coord *c = g_alloca(
2938 sizeof(struct coord) * (1 + g_list_length(this->destinations)));
2939 int i = 0;
2940 GList *tmp;
2941
2942 route_status.type = attr_route_status;
2943 route_graph_destroy(this->graph);
2944 this->graph = NULL;
2945 callback_destroy(this->route_graph_done_cb);
2946 this->route_graph_done_cb = callback_new_2(
2947 callback_cast(route_graph_update_done), this, cb);
2948 route_status.u.num = route_status_building_graph;
2949 route_set_attr(this, &route_status);
2950 c[i++] = this->pos->c;
2951 tmp = this->destinations;
2952 while (tmp)
2953 {
2954 struct route_info *dst = tmp->data;
2955 c[i++] = dst->c;
2956 tmp = g_list_next(tmp);
2957 }
2958 this->graph = route_graph_build(this->ms, c, i, this->route_graph_done_cb,
2959 async, this->vehicleprofile, this->try_harder);
2960 if (!async)
2961 {
2962 while (this->graph->busy)
2963 route_graph_build_idle(this->graph, this->vehicleprofile);
2964 }
2965 }
2966
2967 /**
2968 * @brief Gets street data for an item
2969 *
2970 * @param item The item to get the data for
2971 * @return Street data for the item
2972 */
2973 struct street_data *
2974 street_get_data(struct item *item)
2975 {
2976 int count = 0, *flags;
2977 struct street_data *ret = NULL, *ret1;
2978 struct attr flags_attr, maxspeed_attr;
2979 const int step = 128;
2980 int c;
2981
2982 do
2983 {
2984 ret1 = g_realloc(
2985 ret,
2986 sizeof(struct street_data) + (count + step)
2987 * sizeof(struct coord));
2988 if (!ret1)
2989 {
2990 if (ret)
2991 g_free(ret);
2992 return NULL;
2993 }
2994 ret = ret1;
2995 c = item_coord_get(item, &ret->c[count], step);
2996 count += c;
2997 }
2998 while (c && c == step);
2999
3000 ret1 = g_realloc(ret,
3001 sizeof(struct street_data) + count * sizeof(struct coord));
3002 if (ret1)
3003 ret = ret1;
3004 ret->item = *item;
3005 ret->count = count;
3006 if (item_attr_get(item, attr_flags, &flags_attr))
3007 ret->flags = flags_attr.u.num;
3008 else
3009 {
3010 flags = item_get_default_flags(item->type);
3011 if (flags)
3012 ret->flags = *flags;
3013 else
3014 ret->flags = 0;
3015 }
3016
3017 ret->maxspeed = -1;
3018 if (ret->flags & AF_SPEED_LIMIT)
3019 {
3020 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr))
3021 {
3022 ret->maxspeed = maxspeed_attr.u.num;
3023 }
3024 }
3025
3026 return ret;
3027 }
3028
3029 /**
3030 * @brief Copies street data
3031 *
3032 * @param orig The street data to copy
3033 * @return The copied street data
3034 */
3035 struct street_data *
3036 street_data_dup(struct street_data *orig)
3037 {
3038 struct street_data *ret;
3039 int size = sizeof(struct street_data) + orig->count * sizeof(struct coord);
3040
3041 ret = g_malloc(size);
3042 memcpy(ret, orig, size);
3043
3044 return ret;
3045 }
3046
3047 /**
3048 * @brief Frees street data
3049 *
3050 * @param sd Street data to be freed
3051 */
3052 void street_data_free(struct street_data *sd)
3053 {
3054 g_free(sd);
3055 }
3056
3057 /**
3058 * @brief Finds the nearest street to a given coordinate
3059 *
3060 * @param ms The mapset to search in for the street
3061 * @param pc The coordinate to find a street nearby
3062 * @return The nearest street
3063 */
3064 static struct route_info *
3065 route_find_nearest_street(struct vehicleprofile *vehicleprofile,
3066 struct mapset *ms, struct pcoord *pc)
3067 {
3068 struct route_info *ret = NULL;
3069 int max_dist = 1000;
3070 struct map_selection *sel;
3071 int dist, mindist = 0, pos;
3072 struct mapset_handle *h;
3073 struct map *m;
3074 struct map_rect *mr;
3075 struct item *item;
3076 struct coord lp;
3077 struct street_data *sd;
3078 struct coord c;
3079 struct coord_geo g;
3080
3081 ret=g_new0(struct route_info, 1);
3082 mindist = INT_MAX;
3083
3084 h = mapset_open(ms);
3085 while ((m = mapset_next(h, 2)))
3086 {
3087 c.x = pc->x;
3088 c.y = pc->y;
3089 if (map_projection(m) != pc->pro)
3090 {
3091 transform_to_geo(pc->pro, &c, &g);
3092 transform_from_geo(map_projection(m), &g, &c);
3093 }
3094 sel = route_rect(18, &c, &c, 0, max_dist);
3095 if (!sel)
3096 continue;
3097 mr = map_rect_new(m, sel);
3098 if (!mr)
3099 {
3100 map_selection_destroy(sel);
3101 continue;
3102 }
3103 while ((item = map_rect_get_item(mr)))
3104 {
3105 if (item_get_default_flags(item->type))
3106 {
3107 sd = street_get_data(item);
3108 if (!sd)
3109 continue;
3110 dist = transform_distance_polyline_sq(sd->c, sd->count, &c,
3111 &lp, &pos);
3112 if (dist < mindist && ((sd->flags
3113 & vehicleprofile->flags_forward_mask)
3114 == vehicleprofile->flags || (sd->flags
3115 & vehicleprofile->flags_reverse_mask)
3116 == vehicleprofile->flags))
3117 {
3118 mindist = dist;
3119 if (ret->street)
3120 {
3121 street_data_free(ret->street);
3122 }
3123 ret->c = c;
3124 ret->lp = lp;
3125 ret->pos = pos;
3126 ret->street = sd;
3127 //dbg(1, "dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi,
3128 // item->id_lo, pos);
3129 }
3130 else
3131 {
3132 street_data_free(sd);
3133 }
3134 }
3135 }
3136 map_selection_destroy(sel);
3137 map_rect_destroy(mr);
3138 }
3139 mapset_close(h);
3140
3141 if (!ret->street || mindist > max_dist * max_dist)
3142 {
3143 if (ret->street)
3144 {
3145 street_data_free(ret->street);
3146 //dbg(1, "Much too far %d > %d\n", mindist, max_dist);
3147 }
3148 g_free(ret);
3149 ret = NULL;
3150 }
3151
3152 return ret;
3153 }
3154
3155 /**
3156 * @brief Destroys a route_info
3157 *
3158 * @param info The route info to be destroyed
3159 */
3160 void route_info_free(struct route_info *inf)
3161 {
3162 if (!inf)
3163 return;
3164 if (inf->street)
3165 street_data_free(inf->street);
3166 g_free(inf);
3167 }
3168
3169 #include "point.h"
3170
3171 /**
3172 * @brief Returns street data for a route info
3173 *
3174 * @param rinf The route info to return the street data for
3175 * @return Street data for the route info
3176 */
3177 struct street_data *
3178 route_info_street(struct route_info *rinf)
3179 {
3180 return rinf->street;
3181 }
3182
3183 #if 0
3184 struct route_crossings *
3185 route_crossings_get(struct route *this, struct coord *c)
3186 {
3187 struct route_point *pnt;
3188 struct route_segment *seg;
3189 int crossings=0;
3190 struct route_crossings *ret;
3191
3192 pnt=route_graph_get_point(this, c);
3193 seg=pnt->start;
3194 while (seg)
3195 {
3196 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
3197 crossings++;
3198 seg=seg->start_next;
3199 }
3200 seg=pnt->end;
3201 while (seg)
3202 {
3203 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
3204 crossings++;
3205 seg=seg->end_next;
3206 }
3207 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
3208 ret->count=crossings;
3209 return ret;
3210 }
3211 #endif
3212
3213 struct map_rect_priv
3214 {
3215 struct route_info_handle *ri;
3216 enum attr_type attr_next;
3217 int pos;
3218 struct map_priv *mpriv;
3219 struct item item;
3220 unsigned int last_coord;
3221 struct route_path *path;
3222 struct route_path_segment *seg, *seg_next;
3223 struct route_graph_point *point;
3224 struct route_graph_segment *rseg;
3225 char *str;
3226 int hash_bucket;
3227 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
3228 struct route_graph_point_iterator it;
3229 };
3230
3231 static void rm_coord_rewind(void *priv_data)
3232 {
3233 struct map_rect_priv *mr = priv_data;
3234 mr->last_coord = 0;
3235 }
3236
3237 static void rm_attr_rewind(void *priv_data)
3238 {
3239 struct map_rect_priv *mr = priv_data;
3240 mr->attr_next = attr_street_item;
3241 }
3242
3243 static int rm_attr_get(void *priv_data, enum attr_type attr_type,
3244 struct attr *attr)
3245 {
3246 struct map_rect_priv *mr = priv_data;
3247 struct route_path_segment *seg = mr->seg;
3248 struct route *route = mr->mpriv->route;
3249 if (mr->item.type != type_street_route)
3250 return 0;
3251 attr->type = attr_type;
3252 switch (attr_type)
3253 {
3254 case attr_any:
3255 while (mr->attr_next != attr_none)
3256 {
3257 if (rm_attr_get(priv_data, mr->attr_next, attr))
3258 return 1;
3259 }
3260 return 0;
3261 case attr_maxspeed:
3262 mr->attr_next = attr_street_item;
3263 if (seg && seg->data->flags & AF_SPEED_LIMIT)
3264 {
3265 attr->u.num = RSD_MAXSPEED(seg->data);
3266
3267 }
3268 else
3269 {
3270 return 0;
3271 }
3272 return 1;
3273 case attr_street_item:
3274 mr->attr_next = attr_direction;
3275 if (seg && seg->data->item.map)
3276 attr->u.item = &seg->data->item;
3277 else
3278 return 0;
3279 return 1;
3280 case attr_direction:
3281 mr->attr_next = attr_route;
3282 if (seg)
3283 attr->u.num = seg->direction;
3284 else
3285 return 0;
3286 return 1;
3287 case attr_route:
3288 mr->attr_next = attr_length;
3289 attr->u.route = mr->mpriv->route;
3290 return 1;
3291 case attr_length:
3292 mr->attr_next = attr_time;
3293 if (seg)
3294 attr->u.num = seg->data->len;
3295 else
3296 return 0;
3297 return 1;
3298 case attr_time:
3299 mr->attr_next = attr_speed;
3300 if (seg)
3301 attr->u.num = route_time_seg(route->vehicleprofile, seg->data,
3302 NULL);
3303 else
3304 return 0;
3305 return 1;
3306 case attr_speed:
3307 mr->attr_next = attr_none;
3308 if (seg)
3309 attr->u.num = route_seg_speed(route->vehicleprofile, seg->data,
3310 NULL);
3311 else
3312 return 0;
3313 return 1;
3314 case attr_label:
3315 mr->attr_next = attr_none;
3316 return 0;
3317 default:
3318 mr->attr_next = attr_none;
3319 attr->type = attr_none;
3320 return 0;
3321 }
3322 return 0;
3323 }
3324
3325 static int rm_coord_get(void *priv_data, struct coord *c, int count)
3326 {
3327 struct map_rect_priv *mr = priv_data;
3328 struct route_path_segment *seg = mr->seg;
3329 int i, rc = 0;
3330 struct route *r = mr->mpriv->route;
3331 enum projection pro = route_projection(r);
3332
3333 if (pro == projection_none)
3334 return 0;
3335 if (mr->item.type == type_route_start || mr->item.type
3336 == type_route_start_reverse || mr->item.type == type_route_end)
3337 {
3338 if (!count || mr->last_coord)
3339 return 0;
3340 mr->last_coord = 1;
3341 if (mr->item.type == type_route_start || mr->item.type
3342 == type_route_start_reverse)
3343 c[0] = r->pos->c;
3344 else
3345 {
3346 c[0] = route_get_dst(r)->c;
3347 }
3348 return 1;
3349 }
3350 if (!seg)
3351 return 0;
3352 for (i = 0; i < count; i++)
3353 {
3354 if (mr->last_coord >= seg->ncoords)
3355 break;
3356 if (i >= seg->ncoords)
3357 break;
3358 if (pro != projection_mg)
3359 transform_from_to(&seg->c[mr->last_coord++], pro, &c[i],
3360 projection_mg);
3361 else
3362 c[i] = seg->c[mr->last_coord++];
3363 rc++;
3364 }
3365 //dbg(1, "return %d\n", rc);
3366 return rc;
3367 }
3368
3369 static struct item_methods methods_route_item =
3370 { rm_coord_rewind, rm_coord_get, rm_attr_rewind, rm_attr_get, };
3371
3372 static void rp_attr_rewind(void *priv_data)
3373 {
3374 struct map_rect_priv *mr = priv_data;
3375 mr->attr_next = attr_label;
3376 }
3377
3378 static int rp_attr_get(void *priv_data, enum attr_type attr_type,
3379 struct attr *attr)
3380 {
3381 struct map_rect_priv *mr = priv_data;
3382 struct route_graph_point *p = mr->point;
3383 struct route_graph_segment *seg = mr->rseg;
3384 struct route *route = mr->mpriv->route;
3385
3386 attr->type = attr_type;
3387 switch (attr_type)
3388 {
3389 case attr_any: // works only with rg_points for now
3390 while (mr->attr_next != attr_none)
3391 {
3392 //dbg(0, "querying %s\n", attr_to_name(mr->attr_next));
3393 if (rp_attr_get(priv_data, mr->attr_next, attr))
3394 return 1;
3395 }
3396 return 0;
3397 case attr_maxspeed:
3398 mr->attr_next = attr_label;
3399 if (mr->item.type != type_rg_segment)
3400 return 0;
3401 if (seg && (seg->data.flags & AF_SPEED_LIMIT))
3402 {
3403 attr->type = attr_maxspeed;
3404 attr->u.num = RSD_MAXSPEED(&seg->data);
3405 return 1;
3406 }
3407 else
3408 {
3409 return 0;
3410 }
3411 case attr_label:
3412 mr->attr_next = attr_street_item;
3413 if (mr->item.type != type_rg_point)
3414 return 0;
3415 attr->type = attr_label;
3416 if (mr->str)
3417 g_free(mr->str);
3418 if (p->value != INT_MAX)
3419 mr->str = g_strdup_printf("%d", p->value);
3420 else
3421 mr->str = g_strdup("-");
3422 attr->u.str = mr->str;
3423 return 1;
3424 case attr_street_item:
3425 mr->attr_next = attr_flags;
3426 if (mr->item.type != type_rg_segment)
3427 return 0;
3428 if (seg && seg->data.item.map)
3429 attr->u.item = &seg->data.item;
3430 else
3431 return 0;
3432 return 1;
3433 case attr_flags:
3434 mr->attr_next = attr_direction;
3435 if (mr->item.type != type_rg_segment)
3436 return 0;
3437 if (seg)
3438 {
3439 attr->u.num = seg->data.flags;
3440 }
3441 else
3442 {
3443 return 0;
3444 }
3445 return 1;
3446 case attr_direction:
3447 mr->attr_next = attr_debug;
3448 // This only works if the map has been opened at a single point, and in that case indicates if the
3449 // segment returned last is connected to this point via its start (1) or its end (-1)
3450 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
3451 return 0;
3452 if (seg->start == mr->point)
3453 {
3454 attr->u.num = 1;
3455 }
3456 else if (seg->end == mr->point)
3457 {
3458 attr->u.num = -1;
3459 }
3460 else
3461 {
3462 return 0;
3463 }
3464 return 1;
3465 case attr_debug:
3466 mr->attr_next = attr_none;
3467 if (mr->str)
3468 g_free(mr->str);
3469 switch (mr->item.type)
3470 {
3471 case type_rg_point:
3472 {
3473 struct route_graph_segment *tmp;
3474 int start = 0;
3475 int end = 0;
3476 tmp = p->start;
3477 while (tmp)
3478 {
3479 start++;
3480 tmp = tmp->start_next;
3481 }
3482 tmp = p->end;
3483 while (tmp)
3484 {
3485 end++;
3486 tmp = tmp->end_next;
3487 }
3488 mr->str = g_strdup_printf("%d %d %p (0x%x,0x%x)", start,
3489 end, p, p->c.x, p->c.y);
3490 attr->u.str = mr->str;
3491 }
3492 return 1;
3493 case type_rg_segment:
3494 if (!seg)
3495 return 0;
3496 mr->str = g_strdup_printf(
3497 "len %d time %d start %p end %p",
3498 seg->data.len,
3499 route_time_seg(route->vehicleprofile, &seg->data,
3500 NULL), seg->start, seg->end);
3501 attr->u.str = mr->str;
3502 return 1;
3503 default:
3504 return 0;
3505 }
3506 default:
3507 mr->attr_next = attr_none;
3508 attr->type = attr_none;
3509 return 0;
3510 }
3511 }
3512
3513 /**
3514 * @brief Returns the coordinates of a route graph item
3515 *
3516 * @param priv_data The route graph item's private data
3517 * @param c Pointer where to store the coordinates
3518 * @param count How many coordinates to get at a max?
3519 * @return The number of coordinates retrieved
3520 */
3521 static int rp_coord_get(void *priv_data, struct coord *c, int count)
3522 {
3523 struct map_rect_priv *mr = priv_data;
3524 struct route_graph_point *p = mr->point;
3525 struct route_graph_segment *seg = mr->rseg;
3526 int rc = 0, i, dir;
3527 struct route *r = mr->mpriv->route;
3528 enum projection pro = route_projection(r);
3529
3530 if (pro == projection_none)
3531 return 0;
3532 for (i = 0; i < count; i++)
3533 {
3534 if (mr->item.type == type_rg_point)
3535 {
3536 if (mr->last_coord >= 1)
3537 break;
3538 if (pro != projection_mg)
3539 transform_from_to(&p->c, pro, &c[i], projection_mg);
3540 else
3541 c[i] = p->c;
3542 }
3543 else
3544 {
3545 if (mr->last_coord >= 2)
3546 break;
3547 dir = 0;
3548 if (seg->end->seg == seg)
3549 dir = 1;
3550 if (mr->last_coord)
3551 dir = 1 - dir;
3552 if (dir)
3553 {
3554 if (pro != projection_mg)
3555 transform_from_to(&seg->end->c, pro, &c[i], projection_mg);
3556 else
3557 c[i] = seg->end->c;
3558 }
3559 else
3560 {
3561 if (pro != projection_mg)
3562 transform_from_to(&seg->start->c, pro, &c[i], projection_mg);
3563 else
3564 c[i] = seg->start->c;
3565 }
3566 }
3567 mr->last_coord++;
3568 rc++;
3569 }
3570 return rc;
3571 }
3572
3573 static struct item_methods methods_point_item =
3574 { rm_coord_rewind, rp_coord_get, rp_attr_rewind, rp_attr_get, };
3575
3576 static void rp_destroy(struct map_priv *priv)
3577 {
3578 g_free(priv);
3579 }
3580
3581 static void rm_destroy(struct map_priv *priv)
3582 {
3583 g_free(priv);
3584 }
3585
3586 static struct map_rect_priv *
3587 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
3588 {
3589 struct map_rect_priv * mr;
3590 //dbg(1, "enter\n");
3591
3592 #if 0
3593 if (! route_get_pos(priv->route))
3594 return NULL;
3595 if (! route_get_dst(priv->route))
3596 return NULL;
3597 #endif
3598
3599 #if 0
3600 if (! priv->route->path2)
3601 return NULL;
3602 #endif
3603
3604 mr=g_new0(struct map_rect_priv, 1);
3605 mr->mpriv = priv;
3606 mr->item.priv_data = mr;
3607 mr->item.type = type_none;
3608 mr->item.meth = &methods_route_item;
3609 if (priv->route->path2)
3610 {
3611 mr->path = priv->route->path2;
3612 mr->seg_next = mr->path->path;
3613 mr->path->in_use++;
3614 }
3615 else
3616 mr->seg_next = NULL;
3617 return mr;
3618 }
3619
3620 /**
3621 * @brief Opens a new map rectangle on the route graph's map
3622 *
3623 * This function opens a new map rectangle on the route graph's map.
3624 * The "sel" parameter enables you to only search for a single route graph
3625 * point on this map (or exactly: open a map rectangle that only contains
3626 * this one point). To do this, pass here a single map selection, whose
3627 * c_rect has both coordinates set to the same point. Otherwise this parameter
3628 * has no effect.
3629 *
3630 * @param priv The route graph map's private data
3631 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
3632 * @return A new map rect's private data
3633 */
3634 static struct map_rect_priv *
3635 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
3636 {
3637 struct map_rect_priv * mr;
3638
3639 //dbg(1, "enter\n");
3640 if (!priv->route->graph)
3641 return NULL;mr=g_new0(struct map_rect_priv, 1);
3642 mr->mpriv = priv;
3643 mr->item.priv_data = mr;
3644 mr->item.type = type_rg_point;
3645 mr->item.meth = &methods_point_item;
3646 if (sel)
3647 {
3648 if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y
3649 == sel->u.c_rect.rl.y))
3650 {
3651 mr->coord_sel = g_malloc(sizeof(struct coord));
3652 *(mr->coord_sel) = sel->u.c_rect.lu;
3653 }
3654 }
3655 return mr;
3656 }
3657
3658 static void rm_rect_destroy(struct map_rect_priv *mr)
3659 {
3660 if (mr->str)
3661 g_free(mr->str);
3662 if (mr->coord_sel)
3663 {
3664 g_free(mr->coord_sel);
3665 }
3666 if (mr->path)
3667 {
3668 mr->path->in_use--;
3669 if (mr->path->update_required && (mr->path->in_use == 1))
3670 route_path_update_done(mr->mpriv->route,
3671 mr->path->update_required - 1);
3672 else if (!mr->path->in_use)
3673 g_free(mr->path);
3674 }
3675
3676 g_free(mr);
3677 }
3678
3679 static struct item *
3680 rp_get_item(struct map_rect_priv *mr)
3681 {
3682 struct route *r = mr->mpriv->route;
3683 struct route_graph_point *p = mr->point;
3684 struct route_graph_segment *seg = mr->rseg;
3685
3686 if (mr->item.type == type_rg_point)
3687 {
3688 if (mr->coord_sel)
3689 {
3690 // We are supposed to return only the point at one specified coordinate...
3691 if (!p)
3692 {
3693 p = route_graph_get_point_last(r->graph, mr->coord_sel);
3694 if (!p)
3695 {
3696 mr->point = NULL; // This indicates that no point has been found
3697 }
3698 else
3699 {
3700 mr->it = rp_iterator_new(p);
3701 }
3702 }
3703 else
3704 {
3705 p = NULL;
3706 }
3707 }
3708 else
3709 {
3710 if (!p)
3711 {
3712 mr->hash_bucket = 0;
3713 p = r->graph->hash[0];
3714 }
3715 else
3716 p = p->hash_next;
3717 while (!p)
3718 {
3719 mr->hash_bucket++;
3720 if (mr->hash_bucket >= HASH_SIZE)
3721 break;
3722 p = r->graph->hash[mr->hash_bucket];
3723 }
3724 }
3725 if (p)
3726 {
3727 mr->point = p;
3728 mr->item.id_lo++;
3729 rm_coord_rewind(mr);
3730 rp_attr_rewind(mr);
3731 return &mr->item;
3732 }
3733 else
3734 mr->item.type = type_rg_segment;
3735 }
3736
3737 if (mr->coord_sel)
3738 {
3739 if (!mr->point)
3740 { // This means that no point has been found
3741 return NULL;
3742 }
3743 seg = rp_iterator_next(&(mr->it));
3744 }
3745 else
3746 {
3747 if (!seg)
3748 seg = r->graph->route_segments;
3749 else
3750 seg = seg->next;
3751 }
3752
3753 if (seg)
3754 {
3755 mr->rseg = seg;
3756 mr->item.id_lo++;
3757 rm_coord_rewind(mr);
3758 rp_attr_rewind(mr);
3759 return &mr->item;
3760 }
3761 return NULL;
3762
3763 }
3764
3765 static struct item *
3766 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
3767 {
3768 struct item *ret = NULL;
3769 while (id_lo-- > 0)
3770 ret = rp_get_item(mr);
3771 return ret;
3772 }
3773
3774 static struct item *
3775 rm_get_item(struct map_rect_priv *mr)
3776 {
3777 struct route *route = mr->mpriv->route;
3778 //dbg(1, "enter\n", mr->pos);
3779
3780 switch (mr->item.type)
3781 {
3782 case type_none:
3783 if (route->pos && route->pos->street_direction
3784 && route->pos->street_direction != route->pos->dir)
3785 mr->item.type = type_route_start_reverse;
3786 else
3787 mr->item.type = type_route_start;
3788 if (route->pos)
3789 break;
3790 default:
3791 mr->item.type = type_street_route;
3792 mr->seg = mr->seg_next;
3793 if (!mr->seg && mr->path && mr->path->next)
3794 {
3795 struct route_path *p = NULL;
3796 mr->path->in_use--;
3797 if (!mr->path->in_use)
3798 p = mr->path;
3799 mr->path = mr->path->next;
3800 mr->path->in_use++;
3801 mr->seg = mr->path->path;
3802 if (p)
3803 g_free(p);
3804 }
3805 if (mr->seg)
3806 {
3807 mr->seg_next = mr->seg->next;
3808 break;
3809 }
3810 mr->item.type = type_route_end;
3811 // dbg(0,"* set route_end *\n");
3812 if (mr->mpriv->route->destinations)
3813 break;
3814 case type_route_end:
3815 return NULL;
3816 }
3817 mr->last_coord = 0;
3818 mr->item.id_lo++;
3819 rm_attr_rewind(mr);
3820 return &mr->item;
3821 }
3822
3823 static struct item *
3824 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
3825 {
3826 struct item *ret = NULL;
3827 while (id_lo-- > 0)
3828 ret = rm_get_item(mr);
3829 return ret;
3830 }
3831
3832 static struct map_methods route_meth =
3833 { projection_mg, "utf-8", rm_destroy, rm_rect_new, rm_rect_destroy,
3834 rm_get_item, rm_get_item_byid, NULL, NULL, NULL, };
3835
3836 static struct map_methods route_graph_meth =
3837 { projection_mg, "utf-8", rp_destroy, rp_rect_new, rm_rect_destroy,
3838 rp_get_item, rp_get_item_byid, NULL, NULL, NULL, };
3839
3840 static struct map_priv *
3841 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
3842 {
3843 struct map_priv *ret;
3844 struct attr *route_attr;
3845
3846 route_attr = attr_search(attrs, NULL, attr_route);
3847 if (!route_attr)
3848 return NULL;ret=g_new0(struct map_priv, 1);
3849 if (graph)
3850 *meth = route_graph_meth;
3851 else
3852 *meth = route_meth;
3853 ret->route = route_attr->u.route;
3854
3855 return ret;
3856 }
3857
3858 static struct map_priv *
3859 route_map_new(struct map_methods *meth, struct attr **attrs,
3860 struct callback_list *cbl)
3861 {
3862 return route_map_new_helper(meth, attrs, 0);
3863 }
3864
3865 static struct map_priv *
3866 route_graph_map_new(struct map_methods *meth, struct attr **attrs,
3867 struct callback_list *cbl)
3868 {
3869 return route_map_new_helper(meth, attrs, 1);
3870 }
3871
3872 static struct map *
3873 route_get_map_helper(struct route *this_, struct map **map, char *type,
3874 char *description)
3875 {
3876 struct attr *attrs[5];
3877 struct attr a_type, navigation, data, a_description;
3878 a_type.type = attr_type;
3879 a_type.u.str = type;
3880 navigation.type = attr_route;
3881 navigation.u.route = this_;
3882 data.type = attr_data;
3883 data.u.str = "";
3884 a_description.type = attr_description;
3885 a_description.u.str = description;
3886
3887 attrs[0] = &a_type;
3888 attrs[1] = &navigation;
3889 attrs[2] = &data;
3890 attrs[3] = &a_description;
3891 attrs[4] = NULL;
3892
3893 if (!*map)
3894 {
3895 *map = map_new(NULL, attrs);
3896 map_ref(*map);
3897 }
3898
3899 return *map;
3900 }
3901
3902 /**
3903 * @brief Returns a new map containing the route path
3904 *
3905 * This function returns a new map containing the route path.
3906 *
3907 * @important Do not map_destroy() this!
3908 *
3909 * @param this_ The route to get the map of
3910 * @return A new map containing the route path
3911 */
3912 struct map *
3913 route_get_map(struct route *this_)
3914 {
3915 return route_get_map_helper(this_, &this_->map, "route", "Route");
3916 }
3917
3918 /**
3919 * @brief Returns a new map containing the route graph
3920 *
3921 * This function returns a new map containing the route graph.
3922 *
3923 * @important Do not map_destroy() this!
3924 *
3925 * @param this_ The route to get the map of
3926 * @return A new map containing the route graph
3927 */
3928 struct map *
3929 route_get_graph_map(struct route *this_)
3930 {
3931 return route_get_map_helper(this_, &this_->graph_map, "route_graph",
3932 "Route Graph");
3933 }
3934
3935 void route_set_projection(struct route *this_, enum projection pro)
3936 {
3937 }
3938
3939 int route_set_attr(struct route *this_, struct attr *attr)
3940 {
3941 int attr_updated = 0;
3942 switch (attr->type)
3943 {
3944 case attr_route_status:
3945 attr_updated = (this_->route_status != attr->u.num);
3946 this_->route_status = attr->u.num;
3947 // update global route_status notifier
3948 this_->route_status_was_updated = 1;
3949 break;
3950 case attr_destination:
3951 route_set_destination(this_, attr->u.pcoord, 1);
3952 return 1;
3953 case attr_vehicle:
3954 attr_updated = (this_->v != attr->u.vehicle);
3955 this_->v = attr->u.vehicle;
3956 if (attr_updated)
3957 {
3958 struct attr g;
3959 struct pcoord pc;
3960 struct coord c;
3961 if (vehicle_get_attr(this_->v, attr_position_coord_geo, &g,
3962 NULL))
3963 {
3964 pc.pro = projection_mg;
3965 transform_from_geo(projection_mg, g.u.coord_geo, &c);
3966 pc.x = c.x;
3967 pc.y = c.y;
3968 route_set_position(this_, &pc);
3969 }
3970 }
3971 break;
3972 default:
3973 dbg(0, "unsupported attribute: %s\n", attr_to_name(attr->type));
3974 return 0;
3975 }
3976 if (attr_updated)
3977 callback_list_call_attr_2(this_->cbl2, attr->type, this_, attr);
3978 return 1;
3979 }
3980
3981 int route_add_attr(struct route *this_, struct attr *attr)
3982 {
3983 switch (attr->type)
3984 {
3985 case attr_callback:
3986 callback_list_add(this_->cbl2, attr->u.callback);
3987 return 1;
3988 default:
3989 return 0;
3990 }
3991 }
3992
3993 int route_remove_attr(struct route *this_, struct attr *attr)
3994 {
3995 //dbg(0,"enter\n");
3996 switch (attr->type)
3997 {
3998 case attr_callback:
3999 callback_list_remove(this_->cbl2, attr->u.callback);
4000 return 1;
4001 case attr_vehicle:
4002 this_->v = NULL;
4003 return 1;
4004 default:
4005 return 0;
4006 }
4007 }
4008
4009 int route_get_attr(struct route *this_, enum attr_type type, struct attr *attr,
4010 struct attr_iter *iter)
4011 {
4012 int ret = 1;
4013 switch (type)
4014 {
4015 case attr_map:
4016 attr->u.map = route_get_map(this_);
4017 ret = (attr->u.map != NULL);
4018 break;
4019 case attr_destination:
4020 if (this_->destinations)
4021 {
4022 struct route_info *dst;
4023 if (iter)
4024 {
4025 if (iter->u.list)
4026 {
4027 iter->u.list = g_list_next(iter->u.list);
4028 }
4029 else
4030 {
4031 iter->u.list = this_->destinations;
4032 }
4033 if (!iter->u.list)
4034 {
4035 return 0;
4036 }
4037 dst = (struct route_info*) iter->u.list->data;
4038 }
4039 else
4040 { //No iter handling
4041 dst = route_get_dst(this_);
4042 }
4043 attr->u.pcoord = &this_->pc;
4044 this_->pc.pro = projection_mg; /* fixme */
4045 this_->pc.x = dst->c.x;
4046 this_->pc.y = dst->c.y;
4047 }
4048 else
4049 ret = 0;
4050 break;
4051 case attr_vehicle:
4052 attr->u.vehicle = this_->v;
4053 ret = (this_->v != NULL);
4054 //dbg(0,"get vehicle %p\n",this_->v);
4055 break;
4056 case attr_vehicleprofile:
4057 attr->u.vehicleprofile = this_->vehicleprofile;
4058 ret = (this_->vehicleprofile != NULL);
4059 break;
4060 case attr_route_status:
4061 attr->u.num = this_->route_status;
4062 break;
4063 case attr_destination_time:
4064 if (this_->path2 && (this_->route_status
4065 == route_status_path_done_new || this_->route_status
4066 == route_status_path_done_incremental))
4067 {
4068
4069 attr->u.num = this_->path2->path_time;
4070 //dbg(1, "path_time %d\n", attr->u.num);
4071 }
4072 else
4073 ret = 0;
4074 break;
4075 case attr_destination_length:
4076 if (this_->path2 && (this_->route_status
4077 == route_status_path_done_new || this_->route_status
4078 == route_status_path_done_incremental))
4079 attr->u.num = this_->path2->path_len;
4080 else
4081 ret = 0;
4082 break;
4083 default:
4084 return 0;
4085 }
4086 attr->type = type;
4087 return ret;
4088 }
4089
4090 struct attr_iter *
4091 route_attr_iter_new(void)
4092 {
4093 return g_new0(struct attr_iter, 1);
4094 }
4095
4096 void route_attr_iter_destroy(struct attr_iter *iter)
4097 {
4098 g_free(iter);
4099 }
4100
4101 void route_init(void)
4102 {
4103 plugin_register_map_type("route", route_map_new);
4104 plugin_register_map_type("route_graph", route_graph_map_new);
4105 }
4106
4107 void route_destroy(struct route *this_)
4108 {
4109 route_path_destroy(this_->path2, 1);
4110 route_graph_destroy(this_->graph);
4111 route_clear_destinations(this_);
4112 route_info_free(this_->pos);
4113 map_destroy(this_->map);
4114 map_destroy(this_->graph_map);
4115 g_free(this_);
4116 }

   
Visit the ZANavi Wiki