2 * Navit, a modular navigation system.
3 * Copyright (C) 2005-2008 Navit Team
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.
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.
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.
21 * @brief Contains code related to finding a route from a position to a destination
23 * Routing uses segments, points and items. Items are items from the map: Streets, highways, etc.
24 * Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item
25 * can be represented by more than one segment - in that case it is "segmented". Each segment has an
26 * "offset" associated, that indicates at which position in a segmented item this segment is - a
27 * segment representing a not-segmented item always has the offset 1.
28 * A point is located at the end of segments, often connecting several segments.
30 * The code in this file will make navit find a route between a position and a destination.
31 * It accomplishes this by first building a "route graph". This graph contains segments and
34 * After building this graph in route_graph_build(), the function route_graph_flood() assigns every
35 * point and segment a "value" which represents the "costs" of traveling from this point to the
36 * destination. This is done by Dijkstra's algorithm.
38 * When the graph is built a "route path" is created, which is a path in this graph from a given
39 * position to the destination determined at time of building the graph.
56 #include "projection.h"
64 #include "transform.h"
78 * @brief A point in the route graph
80 * This represents a point in the route graph. A point usually connects two or more segments,
81 * but there are also points which don't do that (e.g. at the end of a dead-end).
83 struct route_graph_point {
84 struct route_graph_point *next; /**< Linked-list pointer to a list of all route_graph_points */
85 struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
86 struct route_graph_segment *start; /**< Pointer to a list of segments of which this point is the start. The links
87 * of this linked-list are in route_graph_segment->start_next.*/
88 struct route_graph_segment *end; /**< Pointer to a list of segments of which this pointer is the end. The links
89 * of this linked-list are in route_graph_segment->end_next. */
90 struct route_graph_segment *seg; /**< Pointer to the segment one should use to reach the destination at
92 struct fibheap_el *el; /**< When this point is put on a Fibonacci heap, this is a pointer
93 * to this point's heap-element */
94 int value; /**< The cost at which one can reach the destination from this point on */
95 struct coord c; /**< Coordinates of this point */
99 * @brief A segment in the route graph
101 * This is a segment in the route graph. A segment represents a driveable way.
103 struct route_graph_segment {
104 struct route_graph_segment *next; /**< Linked-list pointer to a list of all route_graph_segments */
105 struct route_graph_segment *start_next; /**< Pointer to the next element in the list of segments that start at the
106 * same point. Start of this list is in route_graph_point->start. */
107 struct route_graph_segment *end_next; /**< Pointer to the next element in the list of segments that end at the
108 * same point. Start of this list is in route_graph_point->end. */
109 struct route_graph_point *start; /**< Pointer to the point this segment starts at. */
110 struct route_graph_point *end; /**< Pointer to the point this segment ends at. */
111 struct item item; /**< The item (e.g. street) that this segment represents. */
113 int len; /**< Length of this segment */
114 /*NOTE: After a segment, various fields may follow, depending on what flags are set. Order of fields:
115 1.) maxspeed Maximum allowed speed on this segment. Present if AF_SPEED_LIMIT is set.
116 2.) offset If the item is segmented (i.e. represented by more than one segment), this
117 indicates the position of this segment in the item. Present if AF_SEGMENTED is set.
122 * @brief A segment in the route path
124 * This is a segment in the route path.
126 struct route_path_segment {
127 struct route_path_segment *next; /**< Pointer to the next segment in the path */
128 struct item item; /**< The item (e.g. street) this segment represents */
129 int length; /**< Length of the segment */
130 int offset; /**< Same as in route_graph_segment->offset */
131 int direction; /**< Order in which the coordinates are ordered. >0 means "First
132 * coordinate of the segment is the first coordinate of the item", <=0
134 int maxspeed; /**< Maximum allowed speed on this segment in km/h. 0 if none, -1 if unkown. */
135 unsigned ncoords; /**< How many coordinates does this segment have? */
136 struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
137 /* WARNING: There will be coordinates following here, so do not create new fields after c! */
141 * @brief Usually represents a destination or position
143 * This struct usually represents a destination or position
146 struct coord c; /**< The actual destination / position */
147 struct coord lp; /**< The nearest point on a street to c */
148 int pos; /**< The position of lp within the coords of the street */
149 int lenpos; /**< Distance between lp and the end of the street */
150 int lenneg; /**< Distance between lp and the start of the street */
151 int lenextra; /**< Distance between lp and c */
153 struct street_data *street; /**< The street lp is on */
157 * @brief A complete route path
159 * This structure describes a whole routing path
162 int in_use; /**< The path is in use and can not be updated */
163 int update_required; /**< The path needs to be updated after it is no longer in use */
164 int updated; /**< The path has only been updated */
165 struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
167 struct route_path_segment *path_last; /**< The last segment in the path */
168 /* XXX: path_hash is not necessery now */
169 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
172 #define RF_FASTEST (1<<0)
173 #define RF_SHORTEST (1<<1)
174 #define RF_AVOIDHW (1<<2)
175 #define RF_AVOIDPAID (1<<3)
176 #define RF_LOCKONROAD (1<<4)
177 #define RF_SHOWGRAPH (1<<5)
180 * @brief A complete route
182 * This struct holds all information about a route.
185 struct mapset *ms; /**< The mapset this route is built upon */
187 struct route_info *pos; /**< Current position within this route */
188 struct route_info *dst; /**< Destination of the route */
190 struct route_graph *graph; /**< Pointer to the route graph */
191 struct route_path *path2; /**< Pointer to the route path */
193 struct map *graph_map;
194 struct callback * route_graph_done_cb ; /**< Callback when route graph is done */
195 struct callback * route_graph_flood_done_cb ; /**< Callback when route graph flooding is done */
196 struct callback_list *cbl; /**< Callback list to call when route changes */
197 int destination_distance; /**< Distance to the destination at which the destination is considered "reached" */
198 int speedlist[route_item_last-route_item_first+1]; /**< The speedlist for this route */
202 * @brief A complete route graph
204 * This structure describes a whole routing graph
207 int busy; /**< The graph is being built */
208 struct map_selection *sel; /**< The rectangle selection for the graph */
209 struct mapset_handle *h; /**< Handle to the mapset */
210 struct map *m; /**< Pointer to the currently active map */
211 struct map_rect *mr; /**< Pointer to the currently active map rectangle */
212 struct callback *idle_cb; /**< Idle callback to process the graph */
213 struct callback *done_cb; /**< Callback when graph is done */
214 struct event_idle *idle_ev; /**< The pointer to the idle event */
215 struct route_graph_point *route_points; /**< Pointer to the first route_graph_point in the linked list of all points */
216 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
217 #define HASH_SIZE 8192
218 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
221 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
224 * @brief Iterator to iterate through all route graph segments in a route graph point
226 * This structure can be used to iterate through all route graph segments connected to a
227 * route graph point. Use this with the rp_iterator_* functions.
229 struct route_graph_point_iterator {
230 struct route_graph_point *p; /**< The route graph point whose segments should be iterated */
231 int end; /**< Indicates if we have finished iterating through the "start" segments */
232 struct route_graph_segment *next; /**< The next segment to be returned */
235 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
236 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
237 static void route_graph_update(struct route *this, struct callback *cb);
238 static void route_graph_build_done(struct route_graph *rg, int cancel);
239 static struct route_path *route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist);
240 static void route_process_street_graph(struct route_graph *this, struct item *item);
241 static void route_graph_destroy(struct route_graph *this);
242 static void route_path_update(struct route *this, int cancel);
245 * @brief Returns the projection used for this route
247 * @param route The route to return the projection for
248 * @return The projection used for this route
250 static enum projection route_projection(struct route *route)
252 struct street_data *street;
253 if (!route->pos && !route->dst)
254 return projection_none;
255 street = route->pos ? route->pos->street : route->dst->street;
256 if (!street || !street->item.map)
257 return projection_none;
258 return map_projection(street->item.map);
262 * @brief Creates a new graph point iterator
264 * This function creates a new route graph point iterator, that can be used to
265 * iterate through all segments connected to the point.
267 * @param p The route graph point to create the iterator from
268 * @return A new iterator.
270 static struct route_graph_point_iterator
271 rp_iterator_new(struct route_graph_point *p)
273 struct route_graph_point_iterator it;
288 * @brief Gets the next segment connected to a route graph point from an iterator
290 * @param it The route graph point iterator to get the segment from
291 * @return The next segment or NULL if there are no more segments
293 static struct route_graph_segment
294 *rp_iterator_next(struct route_graph_point_iterator *it)
296 struct route_graph_segment *ret;
304 if (ret->start_next) {
305 it->next = ret->start_next;
307 it->next = it->p->end;
311 it->next = ret->end_next;
318 * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
320 * @param it The route graph point iterator to be checked
321 * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
324 rp_iterator_end(struct route_graph_point_iterator *it) {
325 if (it->end && (it->next != it->p->end)) {
333 * @brief Destroys a route_path
335 * @param this The route_path to be destroyed
338 route_path_destroy(struct route_path *this)
340 struct route_path_segment *c,*n;
343 if (this->path_hash) {
344 item_hash_destroy(this->path_hash);
345 this->path_hash=NULL;
357 * @brief Creates a completely new route structure
359 * @param attrs Not used
360 * @return The newly created route
363 route_new(struct attr *parent, struct attr **attrs)
365 struct route *this=g_new0(struct route, 1);
366 struct attr dest_attr;
368 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
369 this->destination_distance = dest_attr.u.num;
371 this->destination_distance = 50; // Default value
373 this->cbl=callback_list_new();
379 * @brief Checks if a segment is part of a roundabout
381 * This function checks if a segment is part of a roundabout.
383 * @param seg The segment to be checked
384 * @param level How deep to scan the route graph
385 * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
386 * @param origin Used internally, set to NULL
387 * @return 1 If a roundabout was detected, 0 otherwise
390 route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
392 struct route_graph_point_iterator it,it2;
393 struct route_graph_segment *cur;
399 if (!direction && !(seg->flags & AF_ONEWAY)) {
402 if (direction && !(seg->flags & AF_ONEWAYREV)) {
411 it = rp_iterator_new(seg->end);
413 it = rp_iterator_new(seg->start);
417 while ((cur = rp_iterator_next(&it2)))
422 cur = rp_iterator_next(&it);
425 cur = rp_iterator_next(&it);
430 seg->flags |= AF_ROUNDABOUT;
434 if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) {
435 seg->flags |= AF_ROUNDABOUT;
439 cur = rp_iterator_next(&it);
446 * @brief Sets the mapset of the route passwd
448 * @param this The route to set the mapset for
449 * @param ms The mapset to set for this route
452 route_set_mapset(struct route *this, struct mapset *ms)
458 * @brief Returns the mapset of the route passed
460 * @param this The route to get the mapset of
461 * @return The mapset of the route passed
464 route_get_mapset(struct route *this)
470 * @brief Returns the current position within the route passed
472 * @param this The route to get the position for
473 * @return The position within the route passed
476 route_get_pos(struct route *this)
482 * @brief Returns the destination of the route passed
484 * @param this The route to get the destination for
485 * @return The destination of the route passed
488 route_get_dst(struct route *this)
494 * @brief Returns the speedlist of the route passed
496 * @param this The route to get the speedlist for
497 * @return The speedlist of the route passed
500 route_get_speedlist(struct route *this)
502 return this->speedlist;
506 * @brief Checks if the path is calculated for the route passed
508 * @param this The route to check
509 * @return True if the path is calculated, false if not
512 route_get_path_set(struct route *this)
514 return this->path2 != NULL;
518 * @brief Sets the driving speed for a certain itemtype
520 * @param this The route to set the speed for
521 * @param type The itemtype to set the speed for
522 * @param value The speed that should be set
523 * @return True on success, false if the itemtype does not exist
526 route_set_speed(struct route *this, enum item_type type, int value)
528 if (type < route_item_first || type > route_item_last) {
529 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
532 this->speedlist[type-route_item_first]=value;
537 * @brief Checks if the route passed contains a certain item within the route path
539 * This function checks if a certain items exists in the path that navit will guide
540 * the user to his destination. It does *not* check if this item exists in the route
543 * @param this The route to check for this item
544 * @param item The item to search for
545 * @return True if the item was found, false if the item was not found or the route was not calculated
548 route_contains(struct route *this, struct item *item)
550 if (! this->path2 || !this->path2->path_hash)
552 return (int)item_hash_lookup(this->path2->path_hash, item);
556 * @brief Checks if the current position in a route is a certain item
558 * @param this The route to check for this item
559 * @param item The item to search for
560 * @return True if the current position is this item, false otherwise
563 route_pos_contains(struct route *this, struct item *item)
565 if (! this->pos || !this->pos->street)
567 return item_is_equal(this->pos->street->item, *item);
571 * @brief Checks if a route has reached its destination
573 * @param this The route to be checked
574 * @return True if the destination is "reached", false otherwise.
577 route_destination_reached(struct route *this)
579 struct street_data *sd = NULL;
585 sd = this->pos->street;
591 if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
595 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
598 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
601 pro=route_projection(this);
602 if (pro == projection_none)
605 if (transform_distance(pro, &this->pos->c, &this->dst->lp) > this->destination_distance) {
613 route_path_update_done(struct route *this, int new_graph)
615 struct route_path *oldpath=this->path2;
617 if (this->path2 && this->path2->in_use) {
618 this->path2->update_required=1+new_graph;
622 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
623 route_path_destroy(oldpath);
628 val=2+!this->path2->updated;
631 callback_list_call_attr_1(this->cbl, attr_route, (void *)val);
635 * @brief Updates the route graph and the route path if something changed with the route
637 * This will update the route graph and the route path of the route if some of the
638 * route's settings (destination, position) have changed.
640 * @attention For this to work the route graph has to be destroyed if the route's
641 * @attention destination is changed somewhere!
643 * @param this The route to update
646 route_path_update(struct route *this, int cancel)
648 dbg(1,"enter %d\n", cancel);
649 if (! this->pos || ! this->dst) {
651 route_path_destroy(this->path2);
656 route_graph_destroy(this->graph);
659 /* the graph is destroyed when setting the destination */
661 if (this->graph->busy) {
662 dbg(1,"busy building graph\n");
665 // we can try to update
666 dbg(1,"try update\n");
667 route_path_update_done(this, 0);
669 route_path_destroy(this->path2);
672 if (!this->graph || !this->path2) {
673 dbg(1,"rebuild graph\n");
674 if (! this->route_graph_flood_done_cb)
675 this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, 1);
676 dbg(1,"route_graph_update\n");
677 route_graph_update(this, this->route_graph_flood_done_cb);
682 * @brief This will calculate all the distances stored in a route_info
684 * @param ri The route_info to calculate the distances for
685 * @param pro The projection used for this route
688 route_info_distances(struct route_info *ri, enum projection pro)
691 struct street_data *sd=ri->street;
692 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
693 ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
694 ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
695 ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
699 * @brief This sets the current position of the route passed
701 * This will set the current position of the route passed to the street that is nearest to the
702 * passed coordinates. It also automatically updates the route.
704 * @param this The route to set the position of
705 * @param pos Coordinates to set as position
708 route_set_position(struct route *this, struct pcoord *pos)
711 route_info_free(this->pos);
713 this->pos=route_find_nearest_street(this->ms, pos);
714 dbg(1,"this->pos=%p\n", this->pos);
717 route_info_distances(this->pos, pos->pro);
718 route_path_update(this, 0);
722 * @brief Sets a route's current position based on coordinates from tracking
724 * @param this The route to set the current position of
725 * @param tracking The tracking to get the coordinates from
728 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
731 struct route_info *ret;
732 struct street_data *sd;
735 c=tracking_get_pos(tracking);
736 ret=g_new0(struct route_info, 1);
738 printf("%s:Out of memory\n", __FUNCTION__);
742 route_info_free(this->pos);
748 ret->pos=tracking_get_segment_pos(tracking);
749 sd=tracking_get_street_data(tracking);
751 ret->street=street_data_dup(sd);
752 route_info_distances(ret, c->pro);
754 dbg(3,"c->x=0x%x, c->y=0x%x pos=%d item=(0x%x,0x%x)\n", c->x, c->y, ret->pos, ret->street->item.id_hi, ret->street->item.id_lo);
755 dbg(3,"street 0=(0x%x,0x%x) %d=(0x%x,0x%x)\n", ret->street->c[0].x, ret->street->c[0].y, ret->street->count-1, ret->street->c[ret->street->count-1].x, ret->street->c[ret->street->count-1].y);
758 route_path_update(this, 0);
762 /* Used for debuging of route_rect, what routing sees */
763 struct map_selection *route_selection;
766 * @brief Returns a single map selection
768 struct map_selection *
769 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
771 int dx,dy,sx=1,sy=1,d,m;
772 struct map_selection *sel=g_new(struct map_selection, 1);
774 printf("%s:Out of memory\n", __FUNCTION__);
778 sel->range.min=route_item_first;
779 sel->range.max=route_item_last;
780 dbg(1,"%p %p\n", c1, c2);
785 sel->u.c_rect.lu.x=c1->x;
786 sel->u.c_rect.rl.x=c2->x;
788 sel->u.c_rect.lu.x=c2->x;
789 sel->u.c_rect.rl.x=c1->x;
793 sel->u.c_rect.lu.y=c2->y;
794 sel->u.c_rect.rl.y=c1->y;
796 sel->u.c_rect.lu.y=c1->y;
797 sel->u.c_rect.rl.y=c2->y;
804 sel->u.c_rect.lu.x-=m;
805 sel->u.c_rect.rl.x+=m;
806 sel->u.c_rect.lu.y+=m;
807 sel->u.c_rect.rl.y-=m;
813 * @brief Returns a list of map selections useable to create a route graph
815 * Returns a list of map selections useable to get a map rect from which items can be
816 * retrieved to build a route graph. The selections are a rectangle with
817 * c1 and c2 as two corners.
819 * @param c1 Corner 1 of the rectangle
820 * @param c2 Corder 2 of the rectangle
822 static struct map_selection *
823 route_calc_selection(struct coord *c1, struct coord *c2)
825 struct map_selection *ret,*sel;
826 sel=route_rect(4, c1, c2, 25, 0);
828 sel->next=route_rect(8, c1, c1, 0, 40000);
830 sel->next=route_rect(18, c1, c1, 0, 10000);
832 sel->next=route_rect(8, c2, c2, 0, 40000);
834 sel->next=route_rect(18, c2, c2, 0, 10000);
835 /* route_selection=ret; */
840 * @brief Destroys a list of map selections
842 * @param sel Start of the list to be destroyed
845 route_free_selection(struct map_selection *sel)
847 struct map_selection *next;
857 * @brief Sets the destination of a route
859 * This sets the destination of a route to the street nearest to the coordinates passed
860 * and updates the route.
862 * @param this The route to set the destination for
863 * @param dst Coordinates to set as destination
866 route_set_destination(struct route *this, struct pcoord *dst)
870 route_info_free(this->dst);
873 this->dst=route_find_nearest_street(this->ms, dst);
875 route_info_distances(this->dst, dst->pro);
877 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
878 profile(1,"find_nearest_street");
880 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
881 route_graph_destroy(this->graph);
883 route_path_update(this, 1);
888 * @brief Gets the route_graph_point with the specified coordinates
890 * @param this The route in which to search
891 * @param c Coordinates to search for
892 * @return The point at the specified coordinates or NULL if not found
894 static struct route_graph_point *
895 route_graph_get_point(struct route_graph *this, struct coord *c)
897 struct route_graph_point *p;
898 int hashval=HASHCOORD(c);
899 p=this->hash[hashval];
901 if (p->c.x == c->x && p->c.y == c->y)
909 * @brief Inserts a point into the route graph at the specified coordinates
911 * This will insert a point into the route graph at the coordinates passed in f.
912 * Note that the point is not yet linked to any segments.
914 * @param this The route to insert the point into
915 * @param f The coordinates at which the point should be inserted
916 * @return The point inserted or NULL on failure
918 static struct route_graph_point *
919 route_graph_add_point(struct route_graph *this, struct coord *f)
922 struct route_graph_point *p;
924 p=route_graph_get_point(this,f);
926 hashval=HASHCOORD(f);
928 printf("p (0x%x,0x%x)\n", f->x, f->y);
929 p=g_new(struct route_graph_point,1);
931 printf("%s:Out of memory\n", __FUNCTION__);
934 p->hash_next=this->hash[hashval];
935 this->hash[hashval]=p;
936 p->next=this->route_points;
943 this->route_points=p;
949 * @brief Frees all the memory used for points in the route graph passed
951 * @param this The route graph to delete all points from
954 route_graph_free_points(struct route_graph *this)
956 struct route_graph_point *curr,*next;
957 curr=this->route_points;
963 this->route_points=NULL;
964 memset(this->hash, 0, sizeof(this->hash));
968 * @brief Returns the position of a certain field appended to a route graph segment
970 * This function returns a pointer to a field that is appended to a route graph
973 * @param seg The route graph segment the field is appended to
974 * @param type Type of the field that should be returned
975 * @return A pointer to a field of a certain type, or NULL if no such field is present
978 *route_graph_segment_field_pos(struct route_graph_segment *seg, enum attr_type type)
982 ptr = ((unsigned char*)seg) + sizeof(struct route_graph_segment);
984 if (type == attr_maxspeed) {
988 if (seg->flags & AF_SPEED_LIMIT) {
992 if (type == attr_offset) {
1000 * @brief Retrieves the value of a certain field appended to a route graph segment
1002 * This function tries to retrieve the value of a certain field, that is appended
1003 * to a route graph segment. The type of the field to be retrieved is determined
1004 * via the type attribute of the attr passed. Returns 0 if the value could not be
1005 * retrieved (e.g. because there is no such field with this route graph segment).
1007 * @param seg The segment to retrieve the field from
1008 * @param field Specifies the type of the field to be retrieved. The value is returned within this attribute.
1009 * @return 1 if the value could be retrieved, 0 if not
1012 route_graph_segment_get_field(struct route_graph_segment *seg, struct attr *field)
1016 switch (field->type) {
1018 if (!(seg->flags & AF_SPEED_LIMIT)) {
1022 num = (int *)route_graph_segment_field_pos(seg, field->type);
1023 field->u.num = *num;
1027 if (!(seg->flags & AF_SEGMENTED)) {
1031 num = (int *)route_graph_segment_field_pos(seg, field->type);
1032 field->u.num = *num;
1042 * @brief Sets the value of a certain field appended to a route graph segment
1044 * This function sets the value of a field, whose type is specified via the type attribute
1045 * of the passed attr. Returns 1 if the value could be set, 0 if not (e.g. if this
1046 * field is not present in this segment).
1048 * @param seg The segment the field is appended to
1049 * @param field Contains the type of the field to set and the value to set.
1050 * @return 1 if value could be set, 0 if not.
1053 route_graph_segment_set_field(struct route_graph_segment *seg, struct attr *field)
1057 switch (field->type) {
1059 if (!(seg->flags & AF_SPEED_LIMIT)) {
1063 num = (int *)route_graph_segment_field_pos(seg, field->type);
1064 *num = field->u.num;
1067 if (!(seg->flags & AF_SEGMENTED)) {
1071 num = (int *)route_graph_segment_field_pos(seg, field->type);
1072 *num = field->u.num;
1082 * @brief Inserts a new segment into the route graph
1084 * This function performs a check if a segment for the item specified already exists, and inserts
1085 * a new segment representing this item if it does not.
1087 * @param this The route graph to insert the segment into
1088 * @param start The graph point which should be connected to the start of this segment
1089 * @param end The graph point which should be connected to the end of this segment
1090 * @param len The length of this segment
1091 * @param item The item that is represented by this segment
1092 * @param flags Flags for this segment
1093 * @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
1094 * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1097 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
1098 struct route_graph_point *end, int len, struct item *item,
1099 int flags, int offset, int maxspeed)
1101 struct route_graph_segment *s;
1103 struct attr maxspeed_attr, offset_attr;
1106 offset_attr.type = attr_offset;
1108 if (item_is_equal(*item, s->item)) {
1109 if (flags & AF_SEGMENTED) {
1110 if (route_graph_segment_get_field(s,&offset_attr) && offset_attr.u.num == offset) {
1120 size = sizeof(struct route_graph_segment);
1122 if (flags & AF_SPEED_LIMIT) {
1123 size += sizeof(int);
1126 if (flags & AF_SEGMENTED) {
1127 size += sizeof(int);
1130 s = g_malloc0(size);
1132 printf("%s:Out of memory\n", __FUNCTION__);
1136 s->start_next=start->start;
1139 s->end_next=end->end;
1141 dbg_assert(len >= 0);
1146 if (flags & AF_SPEED_LIMIT) {
1147 maxspeed_attr.type = attr_maxspeed;
1148 maxspeed_attr.u.num = maxspeed;
1150 route_graph_segment_set_field(s, &maxspeed_attr);
1153 if (flags & AF_SEGMENTED) {
1154 offset_attr.type = attr_offset;
1155 offset_attr.u.num = offset;
1157 route_graph_segment_set_field(s, &offset_attr);
1160 s->next=this->route_segments;
1161 this->route_segments=s;
1163 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1167 * @brief Gets all the coordinates of an item
1169 * This will get all the coordinates of the item i and return them in c,
1170 * up to max coordinates. Additionally it is possible to limit the coordinates
1171 * returned to all the coordinates of the item between the two coordinates
1174 * @important Make shure that whatever c points to has enough memory allocated
1175 * @important to hold max coordinates!
1177 * @param i The item to get the coordinates of
1178 * @param c Pointer to memory allocated for holding the coordinates
1179 * @param max Maximum number of coordinates to return
1180 * @param start First coordinate to get
1181 * @param end Last coordinate to get
1182 * @return The number of coordinates returned
1184 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1185 struct coord *start, struct coord *end)
1187 struct map_rect *mr;
1191 mr=map_rect_new(i->map, NULL);
1194 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1196 rc = item_coord_get(item, &c1, 1);
1197 while (rc && (c1.x != start->x || c1.y != start->y)) {
1198 rc = item_coord_get(item, &c1, 1);
1200 while (rc && p < max) {
1202 if (c1.x == end->x && c1.y == end->y)
1204 rc = item_coord_get(item, &c1, 1);
1207 map_rect_destroy(mr);
1212 * @brief Returns and removes one segment from a path
1214 * @param path The path to take the segment from
1215 * @param item The item whose segment to remove
1216 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1217 * @return The segment removed
1219 static struct route_path_segment *
1220 route_extract_segment_from_path(struct route_path *path, struct item *item,
1223 struct route_path_segment *sp = NULL, *s;
1226 if (s->offset == offset && item_is_equal(s->item,*item)) {
1231 path->path = s->next;
1239 item_hash_remove(path->path_hash, item);
1244 * @brief Adds a segment and the end of a path
1246 * @param this The path to add the segment to
1247 * @param segment The segment to add
1250 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1254 if (this->path_last)
1255 this->path_last->next=segment;
1256 this->path_last=segment;
1260 * @brief Adds a new item to a path
1262 * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
1263 * if the item passed is segmented - it will create exactly one segment.
1265 * @param this The path to add the item to
1266 * @param item The item to add
1267 * @param len The length of the item
1268 * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
1269 * @param c Pointer to count coordinates of the item.
1270 * @param cound Number of coordinates in c
1271 * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
1272 * @param dir Direction to add the coordinates in. Greater than zero means "start with the first coordinate in c", all other values mean "start with the last coordinate in c"
1273 * @param maxspeed The maximum allowed speed on this item in km/h. -1 if not known.
1276 route_path_add_item(struct route_path *this, struct item *item, int len, struct coord *first, struct coord *c, int count, struct coord *last, int dir, int maxspeed)
1278 int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
1279 struct route_path_segment *segment;
1281 segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
1282 segment->ncoords=ccount;
1283 segment->direction=dir;
1285 segment->c[idx++]=*first;
1287 for (i = 0 ; i < count ; i++)
1288 segment->c[idx++]=c[i];
1290 for (i = 0 ; i < count ; i++)
1291 segment->c[idx++]=c[count-i-1];
1294 segment->maxspeed=maxspeed;
1297 segment->c[idx++]=*last;
1298 segment->length=len;
1300 segment->item=*item;
1301 route_path_add_segment(this, segment);
1305 * @brief Inserts a new item into the path
1307 * This function does almost the same as "route_apth_add_item()", but identifies
1308 * the item to add by a segment from the route graph. Another difference is that it "copies" the
1309 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1310 * be added to the route path, not all segments of the item.
1312 * The function can be sped up by passing an old path already containing this segment in oldpath -
1313 * the segment will then be extracted from this old path. Please note that in this case the direction
1314 * parameter has no effect.
1316 * @param this The path to add the item to
1317 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1318 * @param rgs Segment of the route graph that should be "copied" to the route path
1319 * @param len Length of the item to be added
1320 * @param offset Offset of rgs within the item it represents
1321 * @param dir Order in which to add the coordinates. See route_path_add_item()
1322 * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
1325 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
1326 struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
1328 struct route_path_segment *segment;
1329 int i,ccnt = 0, ret=1;
1330 struct coord ca[2048];
1331 struct attr maxspeed_attr, offset_attr;
1334 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
1336 segment = route_extract_segment_from_path(oldpath,
1337 &rgs->item, offset);
1344 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1345 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1346 segment->direction=dir;
1348 for (i = 0 ; i < ccnt ; i++)
1349 segment->c[i]=ca[i];
1351 for (i = 0 ; i < ccnt ; i++)
1352 segment->c[i]=ca[ccnt-i-1];
1354 segment->ncoords = ccnt;
1356 /* We check if the route graph segment is part of a roundabout here, because this
1357 * only matters for route graph segments which form parts of the route path */
1358 if (!(rgs->flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier
1359 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1363 segment->item=rgs->item;
1365 if (rgs->flags & AF_SPEED_LIMIT) {
1366 maxspeed_attr.type = attr_maxspeed;
1367 if (route_graph_segment_get_field(rgs, &maxspeed_attr)) {
1368 segment->maxspeed = maxspeed_attr.u.num;
1370 segment->maxspeed = -1;
1373 segment->maxspeed = -1;
1376 if (rgs->flags & AF_SPEED_LIMIT) {
1377 offset_attr.type = attr_offset;
1378 if (route_graph_segment_get_field(rgs, &offset_attr)) {
1379 segment->offset = offset_attr.u.num;
1381 segment->offset = 1;
1384 segment->offset = 1;
1388 segment->length=len;
1390 item_hash_insert(this->path_hash, &rgs->item, (void *)ccnt);
1392 route_path_add_segment(this, segment);
1398 * @brief Destroys all segments of a route graph
1400 * @param this The graph to destroy all segments from
1403 route_graph_free_segments(struct route_graph *this)
1405 struct route_graph_segment *curr,*next;
1406 curr=this->route_segments;
1412 this->route_segments=NULL;
1416 * @brief Destroys a route graph
1418 * @param this The route graph to be destroyed
1421 route_graph_destroy(struct route_graph *this)
1424 route_graph_build_done(this, 1);
1425 route_graph_free_points(this);
1426 route_graph_free_segments(this);
1432 * @brief Returns the time needed to drive len on item
1434 * This function returns the time needed to drive len meters on
1435 * the item passed in item in tenth of seconds.
1437 * @param speedlist The speedlist that should be used
1438 * @param item The item to be driven on
1439 * @param len The length to drive
1440 * @param maxspeed The maximum allowed speed on this item, -1 if not known
1441 * @return The time needed to drive len on item in thenth of senconds
1444 route_time(int *speedlist, struct item *item, int len, int maxspeed)
1446 if (item->type < route_item_first || item->type > route_item_last) {
1447 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1450 if (!speedlist[item->type-route_item_first] && maxspeed <= 0) {
1451 dbg(0,"street type %d speed is zero\n", item->type);
1455 if (maxspeed <= 0) {
1456 return len*36/speedlist[item->type-route_item_first];
1458 return len*36/maxspeed;
1463 * @brief Returns the "costs" of driving len on item
1465 * @param speedlist The speedlist that should be used
1466 * @param item The item to be driven on
1467 * @param len The length to drive
1468 * @param maxspeed The maximum allowed speed on this item, -1 if not known
1469 * @return The "costs" needed to drive len on item
1472 route_value(int *speedlist, struct item *item, int len, int maxspeed)
1476 printf("len=%d\n", len);
1478 dbg_assert(len >= 0);
1479 ret=route_time(speedlist, item, len, maxspeed);
1480 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1485 * @brief Adds an item to the route graph
1487 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1490 * @param this The route graph to add to
1491 * @param item The item to add
1494 route_process_street_graph(struct route_graph *this, struct item *item)
1501 struct route_graph_point *s_pnt,*e_pnt;
1503 struct attr flags_attr, maxspeed_attr;
1509 if (item_coord_get(item, &l, 1)) {
1510 if (item_attr_get(item, attr_flags, &flags_attr)) {
1511 flags = flags_attr.u.num;
1512 if (flags & AF_SEGMENTED)
1516 if (flags & AF_SPEED_LIMIT) {
1517 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
1518 maxspeed = maxspeed_attr.u.num;
1522 s_pnt=route_graph_add_point(this,&l);
1524 while (item_coord_get(item, &c, 1)) {
1525 len+=transform_distance(map_projection(item->map), &l, &c);
1528 e_pnt=route_graph_add_point(this,&l);
1529 dbg_assert(len >= 0);
1530 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1535 isseg = item_coord_is_node(item);
1536 rc = item_coord_get(item, &c, 1);
1538 len+=transform_distance(map_projection(item->map), &l, &c);
1541 e_pnt=route_graph_add_point(this,&l);
1542 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1544 s_pnt=route_graph_add_point(this,&l);
1549 e_pnt=route_graph_add_point(this,&l);
1550 dbg_assert(len >= 0);
1552 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1558 * @brief Compares the costs of reaching the destination from two points on
1560 * @important Do not pass anything other than route_graph_points in v1 and v2!
1564 * @return The additional costs of v1 compared to v2 (may be negative)
1567 compare(void *v1, void *v2)
1569 struct route_graph_point *p1=v1;
1570 struct route_graph_point *p2=v2;
1573 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1575 return p1->value-p2->value;
1579 * @brief Calculates the routing costs for each point
1581 * This function is the heart of routing. It assigns each point in the route graph a
1582 * cost at which one can reach the destination from this point on. Additionally it assigns
1583 * each point a segment one should follow from this point on to reach the destination at the
1586 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1587 * at this algorithm.
1590 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist, struct callback *cb)
1592 struct route_graph_point *p_min,*end=NULL;
1593 struct route_graph_segment *s;
1594 int min,new,old,val;
1595 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1596 struct street_data *sd=dst->street;
1597 struct attr maxspeed_attr;
1599 heap = fh_makeheap();
1600 fh_setcmp(heap, compare);
1602 if (! (sd->flags & AF_ONEWAYREV)) { /* If we may drive in the direction of the coordinates of the item, the first coordinate is one starting point */
1603 end=route_graph_get_point(this, &sd->c[0]);
1604 dbg_assert(end != 0);
1605 end->value=route_value(speedlist, &sd->item, dst->lenneg, sd->maxspeed);
1606 end->el=fh_insert(heap, end);
1609 if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1610 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1611 dbg_assert(end != 0);
1612 end->value=route_value(speedlist, &sd->item, dst->lenpos, sd->maxspeed);
1613 end->el=fh_insert(heap, end);
1616 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1618 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1619 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1623 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);
1624 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1626 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1627 if (s->flags & AF_SPEED_LIMIT) {
1628 maxspeed_attr.type = attr_maxspeed;
1629 if (!route_graph_segment_get_field(s, &maxspeed_attr)) {
1630 maxspeed_attr.u.num = -1;
1633 maxspeed_attr.u.num = -1;
1635 val=route_value(speedlist, &s->item, s->len, maxspeed_attr.u.num);
1637 val+=val*2*street_route_contained(s->str->segid);
1641 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);
1642 if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1647 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1648 s->end->el=fh_insert(heap, s->end);
1650 printf("el new=%p\n", s->end->el);
1654 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1655 fh_replacedata(heap, s->end->el, s->end);
1663 while (s) { /* Doing the same as above with the segments leading towards our point */
1664 if (s->flags & AF_SPEED_LIMIT) {
1665 maxspeed_attr.type = attr_maxspeed;
1666 if (!route_graph_segment_get_field(s, &maxspeed_attr)) {
1667 maxspeed_attr.u.num = -1;
1670 maxspeed_attr.u.num = -1;
1672 val=route_value(speedlist, &s->item, s->len, maxspeed_attr.u.num);
1675 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);
1676 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1677 old=s->start->value;
1678 s->start->value=new;
1680 if (! s->start->el) {
1682 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1683 s->start->el=fh_insert(heap, s->start);
1685 printf("el new=%p\n", s->start->el);
1689 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1690 fh_replacedata(heap, s->start->el, s->start);
1698 fh_deleteheap(heap);
1699 callback_call_0(cb);
1703 * @brief Starts an "offroad" path
1705 * This starts a path that is not located on a street. It creates a new route path
1706 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1708 * @param this Not used
1709 * @param pos The starting position for the new path
1710 * @param dst The destination of the new path
1711 * @param dir Not used
1712 * @return The new path
1714 static struct route_path *
1715 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1717 struct route_path *ret;
1719 ret=g_new0(struct route_path, 1);
1720 ret->path_hash=item_hash_new();
1721 route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1, -1);
1728 * @brief Creates a new "trivial" route
1730 * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1731 * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1733 * @param this The route graph to place the route on
1734 * @param pos The starting position for the new path
1735 * @param dst The destination of the new path
1736 * @param dir Direction of the coordinates to be added
1737 * @return The new path
1739 static struct route_path *
1740 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1742 struct street_data *sd=pos->street;
1743 struct route_path *ret;
1746 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1747 return route_path_new_offroad(this, pos, dst, dir);
1749 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1750 return route_path_new_offroad(this, pos, dst, dir);
1752 ret=g_new0(struct route_path, 1);
1753 ret->path_hash=item_hash_new();
1755 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1, -1);
1757 route_path_add_item(ret, &sd->item, pos->lenpos-dst->lenpos, &pos->lp, sd->c+pos->pos+1, dst->pos+pos->pos, &dst->lp, 1, sd->maxspeed);
1759 route_path_add_item(ret, &sd->item, pos->lenneg-dst->lenneg, &pos->lp, sd->c+dst->pos+1, pos->pos-dst->pos, &dst->lp, -1, sd->maxspeed);
1761 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1, -1);
1767 * @brief Returns a coordinate at a given distance
1769 * This function returns the coordinate, where the user will be if he
1770 * follows the current route for a certain distance.
1772 * @param this_ The route we're driving upon
1773 * @param dist The distance in meters
1774 * @return The coordinate where the user will be in that distance
1777 route_get_coord_dist(struct route *this_, int dist)
1782 struct route_path_segment *cur;
1784 enum projection pro=route_projection(this_);
1788 if (!this_->path2 || pro == projection_none) {
1789 return this_->pos->c;
1792 ret = this_->pos->c;
1793 cur = this_->path2->path;
1795 if (cur->length < d) {
1798 for (i=0; i < (cur->ncoords-1); i++) {
1800 len = (int)transform_polyline_length(pro, (cur->c + i), 2);
1803 // We interpolate a bit here...
1804 frac = (double)l / len;
1806 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
1807 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
1809 ret.x = (cur->c + i)->x + (frac * dx);
1810 ret.y = (cur->c + i)->y + (frac * dy);
1814 return cur->c[(cur->ncoords-1)];
1819 return this_->dst->c;
1823 * @brief Creates a new route path
1825 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1826 * make shure to run route_graph_flood() after changing the destination before using this function.
1828 * @param this The route graph to create the route from
1829 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1830 * @param pos The starting position of the route
1831 * @param dst The destination of the route
1832 * @param speedlist The speedlist to use
1833 * @return The new route path
1835 static struct route_path *
1836 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1838 struct route_graph_point *start1=NULL,*start2=NULL,*start;
1839 struct route_graph_segment *s=NULL;
1840 struct route_graph_segment *lastseg = NULL;
1845 int time=0,hr,min,sec
1847 unsigned int val1=0xffffffff,val2=0xffffffff;
1848 struct street_data *sd=pos->street;
1849 struct route_path *ret;
1850 struct attr offset_attr;
1852 offset_attr.type = attr_offset;
1854 if (! pos->street || ! dst->street)
1856 if (item_is_equal(pos->street->item, dst->street->item)) { /* We probably don't have to leave this street and can use a trivial route */
1857 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1858 return route_path_new_trivial(this, pos, dst, -1);
1860 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1861 return route_path_new_trivial(this, pos, dst, 1);
1864 if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1865 start1=route_graph_get_point(this, &sd->c[0]);
1868 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg, sd->maxspeed);
1869 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1871 if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1872 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1875 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos, sd->maxspeed);
1876 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1878 dbg(1,"val1=%d val2=%d\n", val1, val2);
1880 val1=start1->start->start->value;
1881 val2=start2->end->end->value;
1883 ret=g_new0(struct route_path, 1);
1886 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1, -1);
1887 if (start1 && (val1 < val2)) {
1889 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1, sd->maxspeed);
1893 route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1, sd->maxspeed);
1895 printf("no route found, pos blocked\n");
1899 ret->path_hash=item_hash_new();
1900 while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1903 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1908 if (!route_graph_segment_get_field(s, &offset_attr)) {
1909 offset_attr.u.num = 1;
1912 if (s->start == start) {
1913 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, offset_attr.u.num, 1, is_straight))
1917 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, offset_attr.u.num, -1, is_straight))
1925 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1926 dbg(1,"dst sd->flags=%d sd->c[0]=0x%x,0x%x sd->c[sd->count-1]=0x%x,0x%x\n", sd->flags, sd->c[0].x,sd->c[0].y, sd->c[sd->count-1].x, sd->c[sd->count-1].y);
1927 if (start->c.x == sd->c[0].x && start->c.y == sd->c[0].y) { /* Adding a final segment to reach the destination within the destination street */
1928 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1, sd->maxspeed);
1929 } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1930 route_path_add_item(ret, &sd->item, dst->lenpos, NULL, sd->c+dst->pos+1, sd->count-dst->pos-1, &dst->lp, -1, sd->maxspeed);
1932 printf("no route found\n");
1933 route_path_destroy(ret);
1937 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1, -1);
1938 dbg(1, "%d segments\n", segs);
1943 route_graph_build_next_map(struct route_graph *rg)
1946 rg->m=mapset_next(rg->h, 1);
1949 map_rect_destroy(rg->mr);
1950 rg->mr=map_rect_new(rg->m, rg->sel);
1957 route_graph_build_done(struct route_graph *rg, int cancel)
1959 dbg(1,"cancel=%d\n",cancel);
1960 event_remove_idle(rg->idle_ev);
1961 callback_destroy(rg->idle_cb);
1962 map_rect_destroy(rg->mr);
1963 mapset_close(rg->h);
1964 route_free_selection(rg->sel);
1971 callback_call_0(rg->done_cb);
1976 route_graph_build_idle(struct route_graph *rg)
1983 item=map_rect_get_item(rg->mr);
1986 if (!route_graph_build_next_map(rg)) {
1987 route_graph_build_done(rg, 0);
1991 if (item->type >= type_street_0 && item->type <= type_ferry)
1992 route_process_street_graph(rg, item);
1998 * @brief Builds a new route graph from a mapset
2000 * This function builds a new route graph from a map. Please note that this function does not
2001 * add any routing information to the route graph - this has to be done via the route_graph_flood()
2004 * The function does not create a graph covering the whole map, but only covering the rectangle
2005 * between c1 and c2.
2007 * @param ms The mapset to build the route graph from
2008 * @param c1 Corner 1 of the rectangle to use from the map
2009 * @param c2 Corner 2 of the rectangle to use from the map
2010 * @param done_cb The callback which will be called when graph is complete
2011 * @return The new route graph.
2013 static struct route_graph *
2014 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb)
2016 struct route_graph *ret=g_new0(struct route_graph, 1);
2020 ret->sel=route_calc_selection(c1, c2);
2021 ret->h=mapset_open(ms);
2022 ret->done_cb=done_cb;
2024 if (route_graph_build_next_map(ret)) {
2025 ret->idle_cb=callback_new_1(callback_cast(route_graph_build_idle), ret);
2026 ret->idle_ev=event_add_idle(50, ret->idle_cb);
2028 route_graph_build_done(ret, 0);
2034 route_graph_update_done(struct route *this, struct callback *cb)
2036 route_graph_flood(this->graph, this->dst, this->speedlist, cb);
2040 * @brief Updates the route graph
2042 * This updates the route graph after settings in the route have changed. It also
2043 * adds routing information afterwards by calling route_graph_flood().
2045 * @param this The route to update the graph for
2048 route_graph_update(struct route *this, struct callback *cb)
2050 route_graph_destroy(this->graph);
2051 callback_destroy(this->route_graph_done_cb);
2052 this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
2053 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
2054 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c, this->route_graph_done_cb);
2058 * @brief Gets street data for an item
2060 * @param item The item to get the data for
2061 * @return Street data for the item
2063 struct street_data *
2064 street_get_data (struct item *item)
2067 struct street_data *ret = NULL, *ret1;
2068 struct attr flags_attr, maxspeed_attr;
2069 const int step = 128;
2073 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
2080 c = item_coord_get(item, &ret->c[count], step);
2082 } while (c && c == step);
2084 ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
2089 if (item_attr_get(item, attr_flags, &flags_attr))
2090 ret->flags=flags_attr.u.num;
2095 if (ret->flags & AF_SPEED_LIMIT) {
2096 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
2097 ret->maxspeed = maxspeed_attr.u.num;
2105 * @brief Copies street data
2107 * @param orig The street data to copy
2108 * @return The copied street data
2110 struct street_data *
2111 street_data_dup(struct street_data *orig)
2113 struct street_data *ret;
2114 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
2117 memcpy(ret, orig, size);
2123 * @brief Frees street data
2125 * @param sd Street data to be freed
2128 street_data_free(struct street_data *sd)
2134 * @brief Finds the nearest street to a given coordinate
2136 * @param ms The mapset to search in for the street
2137 * @param pc The coordinate to find a street nearby
2138 * @return The nearest street
2140 static struct route_info *
2141 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
2143 struct route_info *ret=NULL;
2145 struct map_selection *sel;
2146 int dist,mindist=0,pos;
2147 struct mapset_handle *h;
2149 struct map_rect *mr;
2152 struct street_data *sd;
2156 ret=g_new0(struct route_info, 1);
2158 dbg(0,"Out of memory\n");
2164 while ((m=mapset_next(h,1))) {
2167 if (map_projection(m) != pc->pro) {
2168 transform_to_geo(pc->pro, &c, &g);
2169 transform_from_geo(map_projection(m), &g, &c);
2171 sel = route_rect(18, &c, &c, 0, max_dist);
2174 mr=map_rect_new(m, sel);
2176 map_selection_destroy(sel);
2179 while ((item=map_rect_get_item(mr))) {
2180 if (item->type >= type_street_0 && item->type <= type_ferry) {
2181 sd=street_get_data(item);
2184 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
2185 if (dist < mindist) {
2188 street_data_free(ret->street);
2194 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
2196 street_data_free(sd);
2200 map_selection_destroy(sel);
2201 map_rect_destroy(mr);
2205 if (!ret->street || mindist > max_dist*max_dist) {
2207 street_data_free(ret->street);
2208 dbg(1,"Much too far %d > %d\n", mindist, max_dist);
2218 * @brief Destroys a route_info
2220 * @param info The route info to be destroyed
2223 route_info_free(struct route_info *inf)
2226 street_data_free(inf->street);
2234 * @brief Returns street data for a route info
2236 * @param rinf The route info to return the street data for
2237 * @return Street data for the route info
2239 struct street_data *
2240 route_info_street(struct route_info *rinf)
2242 return rinf->street;
2246 struct route_crossings *
2247 route_crossings_get(struct route *this, struct coord *c)
2249 struct route_point *pnt;
2250 struct route_segment *seg;
2252 struct route_crossings *ret;
2254 pnt=route_graph_get_point(this, c);
2257 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2259 seg=seg->start_next;
2263 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2267 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
2268 ret->count=crossings;
2274 struct map_rect_priv {
2275 struct route_info_handle *ri;
2276 enum attr_type attr_next;
2278 struct map_priv *mpriv;
2281 unsigned int last_coord;
2282 struct route_path *path;
2283 struct route_path_segment *seg,*seg_next;
2284 struct route_graph_point *point;
2285 struct route_graph_segment *rseg;
2287 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
2288 struct route_graph_point_iterator it;
2292 rm_coord_rewind(void *priv_data)
2294 struct map_rect_priv *mr = priv_data;
2299 rm_attr_rewind(void *priv_data)
2301 struct map_rect_priv *mr = priv_data;
2302 mr->attr_next = attr_street_item;
2306 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2308 struct map_rect_priv *mr = priv_data;
2309 struct route_path_segment *seg=mr->seg;
2310 struct route *route=mr->mpriv->route;
2311 if (mr->item.type != type_street_route)
2313 attr->type=attr_type;
2314 switch (attr_type) {
2316 while (mr->attr_next != attr_none) {
2317 if (rm_attr_get(priv_data, mr->attr_next, attr))
2322 mr->attr_next = attr_street_item;
2324 attr->u.num = seg->maxspeed;
2329 case attr_street_item:
2330 mr->attr_next=attr_direction;
2331 if (seg && seg->item.map)
2332 attr->u.item=&seg->item;
2336 case attr_direction:
2337 mr->attr_next=attr_route;
2339 attr->u.num=seg->direction;
2344 mr->attr_next=attr_length;
2345 attr->u.route = mr->mpriv->route;
2349 attr->u.num=seg->length;
2351 attr->u.num=mr->length;
2352 mr->attr_next=attr_time;
2355 mr->attr_next=attr_none;
2357 attr->u.num=route_time(route->speedlist, &seg->item, seg->length, seg->maxspeed);
2362 mr->attr_next=attr_none;
2365 mr->attr_next=attr_none;
2366 attr->type=attr_none;
2373 rm_coord_get(void *priv_data, struct coord *c, int count)
2375 struct map_rect_priv *mr = priv_data;
2376 struct route_path_segment *seg = mr->seg;
2378 struct route *r = mr->mpriv->route;
2379 enum projection pro = route_projection(r);
2381 if (pro == projection_none)
2383 if (mr->item.type == type_route_start || mr->item.type == type_route_end) {
2384 if (! count || mr->last_coord)
2387 if (mr->item.type == type_route_start)
2395 for (i=0; i < count; i++) {
2396 if (mr->last_coord >= seg->ncoords)
2398 if (i >= seg->ncoords)
2400 if (pro != projection_mg)
2401 transform_from_to(&seg->c[mr->last_coord++], pro,
2402 &c[i],projection_mg);
2404 c[i] = seg->c[mr->last_coord++];
2407 dbg(1,"return %d\n",rc);
2411 static struct item_methods methods_route_item = {
2419 rp_attr_rewind(void *priv_data)
2421 struct map_rect_priv *mr = priv_data;
2422 mr->attr_next = attr_label;
2426 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2428 struct map_rect_priv *mr = priv_data;
2429 struct route_graph_point *p = mr->point;
2430 struct route_graph_segment *seg = mr->rseg;
2431 switch (attr_type) {
2432 case attr_any: // works only with rg_points for now
2433 if (mr->item.type != type_rg_point)
2435 while (mr->attr_next != attr_none) {
2436 if (rp_attr_get(priv_data, mr->attr_next, attr))
2441 mr->attr_next = attr_label;
2442 if (mr->item.type != type_rg_segment)
2445 attr->type = attr_maxspeed;
2446 if (!route_graph_segment_get_field(seg,attr)) {
2455 if (mr->item.type != type_rg_point)
2457 attr->type = attr_label;
2460 if (p->value != INT_MAX)
2461 mr->str=g_strdup_printf("%d", p->value);
2463 mr->str=g_strdup("-");
2464 attr->u.str = mr->str;
2465 mr->attr_next=attr_none;
2467 case attr_street_item:
2468 if (mr->item.type != type_rg_segment)
2470 mr->attr_next=attr_none;
2471 if (seg && seg->item.map)
2472 attr->u.item=&seg->item;
2477 if (mr->item.type != type_rg_segment)
2479 mr->attr_next = attr_none;
2481 attr->u.num = seg->flags;
2486 case attr_direction:
2487 // This only works if the map has been opened at a single point, and in that case indicates if the
2488 // segment returned last is connected to this point via its start (1) or its end (-1)
2489 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
2491 if (seg->start == mr->point) {
2493 } else if (seg->end == mr->point) {
2500 if (mr->item.type != type_rg_point)
2502 attr->type = attr_debug;
2505 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2506 attr->u.str = mr->str;
2507 mr->attr_next=attr_none;
2510 mr->attr_next=attr_none;
2511 attr->type=attr_none;
2517 * @brief Returns the coordinates of a route graph item
2519 * @param priv_data The route graph item's private data
2520 * @param c Pointer where to store the coordinates
2521 * @param count How many coordinates to get at a max?
2522 * @return The number of coordinates retrieved
2525 rp_coord_get(void *priv_data, struct coord *c, int count)
2527 struct map_rect_priv *mr = priv_data;
2528 struct route_graph_point *p = mr->point;
2529 struct route_graph_segment *seg = mr->rseg;
2531 struct route *r = mr->mpriv->route;
2532 enum projection pro = route_projection(r);
2534 if (pro == projection_none)
2536 for (i=0; i < count; i++) {
2537 if (mr->item.type == type_rg_point) {
2538 if (mr->last_coord >= 1)
2540 if (pro != projection_mg)
2541 transform_from_to(&p->c, pro,
2542 &c[i],projection_mg);
2546 if (mr->last_coord >= 2)
2549 if (seg->end->seg == seg)
2554 if (pro != projection_mg)
2555 transform_from_to(&seg->end->c, pro,
2556 &c[i],projection_mg);
2560 if (pro != projection_mg)
2561 transform_from_to(&seg->start->c, pro,
2562 &c[i],projection_mg);
2564 c[i] = seg->start->c;
2573 static struct item_methods methods_point_item = {
2581 rp_destroy(struct map_priv *priv)
2587 rm_destroy(struct map_priv *priv)
2592 static struct map_rect_priv *
2593 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2595 struct map_rect_priv * mr;
2597 if (! route_get_pos(priv->route))
2599 if (! route_get_dst(priv->route))
2602 if (! priv->route->path2)
2605 mr=g_new0(struct map_rect_priv, 1);
2607 mr->item.priv_data = mr;
2608 mr->item.type = type_none;
2609 mr->item.meth = &methods_route_item;
2610 if (priv->route->path2) {
2611 mr->path=priv->route->path2;
2612 mr->seg_next=mr->path->path;
2620 * @brief Opens a new map rectangle on the route graph's map
2622 * This function opens a new map rectangle on the route graph's map.
2623 * The "sel" parameter enables you to only search for a single route graph
2624 * point on this map (or exactly: open a map rectangle that only contains
2625 * this one point). To do this, pass here a single map selection, whose
2626 * c_rect has both coordinates set to the same point. Otherwise this parameter
2629 * @param priv The route graph map's private data
2630 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2631 * @return A new map rect's private data
2633 static struct map_rect_priv *
2634 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2636 struct map_rect_priv * mr;
2639 if (! priv->route->graph || ! priv->route->graph->route_points)
2641 mr=g_new0(struct map_rect_priv, 1);
2643 mr->item.priv_data = mr;
2644 mr->item.type = type_rg_point;
2645 mr->item.meth = &methods_point_item;
2647 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)) {
2648 mr->coord_sel = g_malloc(sizeof(struct coord));
2649 *(mr->coord_sel) = sel->u.c_rect.lu;
2656 rm_rect_destroy(struct map_rect_priv *mr)
2660 if (mr->coord_sel) {
2661 g_free(mr->coord_sel);
2665 if (mr->path->update_required && !mr->path->in_use)
2666 route_path_update_done(mr->mpriv->route, mr->path->update_required-1);
2672 static struct item *
2673 rp_get_item(struct map_rect_priv *mr)
2675 struct route *r = mr->mpriv->route;
2676 struct route_graph_point *p = mr->point;
2677 struct route_graph_segment *seg = mr->rseg;
2679 if (mr->item.type == type_rg_point) {
2680 if (mr->coord_sel) {
2681 // We are supposed to return only the point at one specified coordinate...
2683 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2684 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2687 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2688 mr->point = NULL; // This indicates that no point has been found
2690 mr->it = rp_iterator_new(p);
2697 p = r->graph->route_points;
2704 rm_coord_rewind(mr);
2708 mr->item.type = type_rg_segment;
2711 if (mr->coord_sel) {
2712 if (!mr->point) { // This means that no point has been found
2715 seg = rp_iterator_next(&(mr->it));
2718 seg=r->graph->route_segments;
2726 rm_coord_rewind(mr);
2734 static struct item *
2735 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2737 struct item *ret=NULL;
2739 ret=rp_get_item(mr);
2744 static struct item *
2745 rm_get_item(struct map_rect_priv *mr)
2747 dbg(1,"enter\n", mr->pos);
2749 switch (mr->item.type) {
2751 mr->item.type=type_route_start;
2752 if (mr->mpriv->route->pos)
2755 mr->item.type=type_street_route;
2756 mr->seg=mr->seg_next;
2758 mr->seg_next=mr->seg->next;
2761 mr->item.type=type_route_end;
2762 if (mr->mpriv->route->dst)
2764 case type_route_end:
2773 static struct item *
2774 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2776 struct item *ret=NULL;
2778 ret=rm_get_item(mr);
2782 static struct map_methods route_meth = {
2795 static struct map_methods route_graph_meth = {
2809 route_toggle_routegraph_display(struct route *route)
2811 if (route->flags & RF_SHOWGRAPH) {
2812 route->flags &= ~RF_SHOWGRAPH;
2814 route->flags |= RF_SHOWGRAPH;
2818 static struct map_priv *
2819 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2821 struct map_priv *ret;
2822 struct attr *route_attr;
2824 route_attr=attr_search(attrs, NULL, attr_route);
2827 ret=g_new0(struct map_priv, 1);
2829 *meth=route_graph_meth;
2832 ret->route=route_attr->u.route;
2837 static struct map_priv *
2838 route_map_new(struct map_methods *meth, struct attr **attrs)
2840 return route_map_new_helper(meth, attrs, 0);
2843 static struct map_priv *
2844 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2846 return route_map_new_helper(meth, attrs, 1);
2850 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2853 *map=map_new(NULL, (struct attr*[]){
2854 &(struct attr){attr_type,{type}},
2855 &(struct attr){attr_route,.u.route=this_},
2856 &(struct attr){attr_data,{""}},
2857 &(struct attr){attr_description,{description}},
2864 * @brief Returns a new map containing the route path
2866 * This function returns a new map containing the route path.
2868 * @important Do not map_destroy() this!
2870 * @param this_ The route to get the map of
2871 * @return A new map containing the route path
2874 route_get_map(struct route *this_)
2876 return route_get_map_helper(this_, &this_->map, "route","Route");
2881 * @brief Returns a new map containing the route graph
2883 * This function returns a new map containing the route graph.
2885 * @important Do not map_destroy() this!
2887 * @param this_ The route to get the map of
2888 * @return A new map containing the route graph
2891 route_get_graph_map(struct route *this_)
2893 return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2897 route_set_projection(struct route *this_, enum projection pro)
2902 route_add_callback(struct route *this_, struct callback *cb)
2904 callback_list_add(this_->cbl, cb);
2908 route_remove_callback(struct route *this_, struct callback *cb)
2910 callback_list_remove(this_->cbl, cb);
2917 plugin_register_map_type("route", route_map_new);
2918 plugin_register_map_type("route_graph", route_graph_map_new);