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

Contents of /navit/navit/route.c

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki