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);
429 if (cur->item.type != origin->item.type) {
430 // This street is of another type, can't be part of the roundabout
431 cur = rp_iterator_next(&it);
436 seg->flags |= AF_ROUNDABOUT;
440 if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) {
441 seg->flags |= AF_ROUNDABOUT;
445 cur = rp_iterator_next(&it);
452 * @brief Sets the mapset of the route passwd
454 * @param this The route to set the mapset for
455 * @param ms The mapset to set for this route
458 route_set_mapset(struct route *this, struct mapset *ms)
464 * @brief Returns the mapset of the route passed
466 * @param this The route to get the mapset of
467 * @return The mapset of the route passed
470 route_get_mapset(struct route *this)
476 * @brief Returns the current position within the route passed
478 * @param this The route to get the position for
479 * @return The position within the route passed
482 route_get_pos(struct route *this)
488 * @brief Returns the destination of the route passed
490 * @param this The route to get the destination for
491 * @return The destination of the route passed
494 route_get_dst(struct route *this)
500 * @brief Returns the speedlist of the route passed
502 * @param this The route to get the speedlist for
503 * @return The speedlist of the route passed
506 route_get_speedlist(struct route *this)
508 return this->speedlist;
512 * @brief Checks if the path is calculated for the route passed
514 * @param this The route to check
515 * @return True if the path is calculated, false if not
518 route_get_path_set(struct route *this)
520 return this->path2 != NULL;
524 * @brief Sets the driving speed for a certain itemtype
526 * @param this The route to set the speed for
527 * @param type The itemtype to set the speed for
528 * @param value The speed that should be set
529 * @return True on success, false if the itemtype does not exist
532 route_set_speed(struct route *this, enum item_type type, int value)
534 if (type < route_item_first || type > route_item_last) {
535 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
538 this->speedlist[type-route_item_first]=value;
543 * @brief Checks if the route passed contains a certain item within the route path
545 * This function checks if a certain items exists in the path that navit will guide
546 * the user to his destination. It does *not* check if this item exists in the route
549 * @param this The route to check for this item
550 * @param item The item to search for
551 * @return True if the item was found, false if the item was not found or the route was not calculated
554 route_contains(struct route *this, struct item *item)
556 if (! this->path2 || !this->path2->path_hash)
558 return (int)item_hash_lookup(this->path2->path_hash, item);
562 * @brief Checks if the current position in a route is a certain item
564 * @param this The route to check for this item
565 * @param item The item to search for
566 * @return True if the current position is this item, false otherwise
569 route_pos_contains(struct route *this, struct item *item)
571 if (! this->pos || !this->pos->street)
573 return item_is_equal(this->pos->street->item, *item);
577 * @brief Checks if a route has reached its destination
579 * @param this The route to be checked
580 * @return True if the destination is "reached", false otherwise.
583 route_destination_reached(struct route *this)
585 struct street_data *sd = NULL;
591 sd = this->pos->street;
597 if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
601 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
604 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
607 pro=route_projection(this);
608 if (pro == projection_none)
611 if (transform_distance(pro, &this->pos->c, &this->dst->lp) > this->destination_distance) {
619 route_path_update_done(struct route *this, int new_graph)
621 struct route_path *oldpath=this->path2;
623 if (this->path2 && this->path2->in_use) {
624 this->path2->update_required=1+new_graph;
628 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
629 route_path_destroy(oldpath);
634 val=2+!this->path2->updated;
637 callback_list_call_attr_1(this->cbl, attr_route, (void *)val);
641 * @brief Updates the route graph and the route path if something changed with the route
643 * This will update the route graph and the route path of the route if some of the
644 * route's settings (destination, position) have changed.
646 * @attention For this to work the route graph has to be destroyed if the route's
647 * @attention destination is changed somewhere!
649 * @param this The route to update
652 route_path_update(struct route *this, int cancel)
654 dbg(1,"enter %d\n", cancel);
655 if (! this->pos || ! this->dst) {
657 route_path_destroy(this->path2);
662 route_graph_destroy(this->graph);
665 /* the graph is destroyed when setting the destination */
667 if (this->graph->busy) {
668 dbg(1,"busy building graph\n");
671 // we can try to update
672 dbg(1,"try update\n");
673 route_path_update_done(this, 0);
675 route_path_destroy(this->path2);
678 if (!this->graph || !this->path2) {
679 dbg(1,"rebuild graph\n");
680 if (! this->route_graph_flood_done_cb)
681 this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, 1);
682 dbg(1,"route_graph_update\n");
683 route_graph_update(this, this->route_graph_flood_done_cb);
688 * @brief This will calculate all the distances stored in a route_info
690 * @param ri The route_info to calculate the distances for
691 * @param pro The projection used for this route
694 route_info_distances(struct route_info *ri, enum projection pro)
697 struct street_data *sd=ri->street;
698 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
699 ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
700 ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
701 ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
705 * @brief This sets the current position of the route passed
707 * This will set the current position of the route passed to the street that is nearest to the
708 * passed coordinates. It also automatically updates the route.
710 * @param this The route to set the position of
711 * @param pos Coordinates to set as position
714 route_set_position(struct route *this, struct pcoord *pos)
717 route_info_free(this->pos);
719 this->pos=route_find_nearest_street(this->ms, pos);
720 dbg(1,"this->pos=%p\n", this->pos);
723 route_info_distances(this->pos, pos->pro);
724 route_path_update(this, 0);
728 * @brief Sets a route's current position based on coordinates from tracking
730 * @param this The route to set the current position of
731 * @param tracking The tracking to get the coordinates from
734 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
737 struct route_info *ret;
738 struct street_data *sd;
741 c=tracking_get_pos(tracking);
742 ret=g_new0(struct route_info, 1);
744 printf("%s:Out of memory\n", __FUNCTION__);
748 route_info_free(this->pos);
754 ret->pos=tracking_get_segment_pos(tracking);
755 sd=tracking_get_street_data(tracking);
757 ret->street=street_data_dup(sd);
758 route_info_distances(ret, c->pro);
760 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);
761 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);
764 route_path_update(this, 0);
768 /* Used for debuging of route_rect, what routing sees */
769 struct map_selection *route_selection;
772 * @brief Returns a single map selection
774 struct map_selection *
775 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
777 int dx,dy,sx=1,sy=1,d,m;
778 struct map_selection *sel=g_new(struct map_selection, 1);
780 printf("%s:Out of memory\n", __FUNCTION__);
784 sel->range.min=route_item_first;
785 sel->range.max=route_item_last;
786 dbg(1,"%p %p\n", c1, c2);
791 sel->u.c_rect.lu.x=c1->x;
792 sel->u.c_rect.rl.x=c2->x;
794 sel->u.c_rect.lu.x=c2->x;
795 sel->u.c_rect.rl.x=c1->x;
799 sel->u.c_rect.lu.y=c2->y;
800 sel->u.c_rect.rl.y=c1->y;
802 sel->u.c_rect.lu.y=c1->y;
803 sel->u.c_rect.rl.y=c2->y;
810 sel->u.c_rect.lu.x-=m;
811 sel->u.c_rect.rl.x+=m;
812 sel->u.c_rect.lu.y+=m;
813 sel->u.c_rect.rl.y-=m;
819 * @brief Returns a list of map selections useable to create a route graph
821 * Returns a list of map selections useable to get a map rect from which items can be
822 * retrieved to build a route graph. The selections are a rectangle with
823 * c1 and c2 as two corners.
825 * @param c1 Corner 1 of the rectangle
826 * @param c2 Corder 2 of the rectangle
828 static struct map_selection *
829 route_calc_selection(struct coord *c1, struct coord *c2)
831 struct map_selection *ret,*sel;
832 sel=route_rect(4, c1, c2, 25, 0);
834 sel->next=route_rect(8, c1, c1, 0, 40000);
836 sel->next=route_rect(18, c1, c1, 0, 10000);
838 sel->next=route_rect(8, c2, c2, 0, 40000);
840 sel->next=route_rect(18, c2, c2, 0, 10000);
841 /* route_selection=ret; */
846 * @brief Destroys a list of map selections
848 * @param sel Start of the list to be destroyed
851 route_free_selection(struct map_selection *sel)
853 struct map_selection *next;
863 * @brief Sets the destination of a route
865 * This sets the destination of a route to the street nearest to the coordinates passed
866 * and updates the route.
868 * @param this The route to set the destination for
869 * @param dst Coordinates to set as destination
872 route_set_destination(struct route *this, struct pcoord *dst)
876 route_info_free(this->dst);
879 this->dst=route_find_nearest_street(this->ms, dst);
881 route_info_distances(this->dst, dst->pro);
883 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
884 profile(1,"find_nearest_street");
886 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
887 route_graph_destroy(this->graph);
889 route_path_update(this, 1);
894 * @brief Gets the route_graph_point with the specified coordinates
896 * @param this The route in which to search
897 * @param c Coordinates to search for
898 * @return The point at the specified coordinates or NULL if not found
900 static struct route_graph_point *
901 route_graph_get_point(struct route_graph *this, struct coord *c)
903 struct route_graph_point *p;
904 int hashval=HASHCOORD(c);
905 p=this->hash[hashval];
907 if (p->c.x == c->x && p->c.y == c->y)
915 * @brief Inserts a point into the route graph at the specified coordinates
917 * This will insert a point into the route graph at the coordinates passed in f.
918 * Note that the point is not yet linked to any segments.
920 * @param this The route to insert the point into
921 * @param f The coordinates at which the point should be inserted
922 * @return The point inserted or NULL on failure
924 static struct route_graph_point *
925 route_graph_add_point(struct route_graph *this, struct coord *f)
928 struct route_graph_point *p;
930 p=route_graph_get_point(this,f);
932 hashval=HASHCOORD(f);
934 printf("p (0x%x,0x%x)\n", f->x, f->y);
935 p=g_new(struct route_graph_point,1);
937 printf("%s:Out of memory\n", __FUNCTION__);
940 p->hash_next=this->hash[hashval];
941 this->hash[hashval]=p;
942 p->next=this->route_points;
949 this->route_points=p;
955 * @brief Frees all the memory used for points in the route graph passed
957 * @param this The route graph to delete all points from
960 route_graph_free_points(struct route_graph *this)
962 struct route_graph_point *curr,*next;
963 curr=this->route_points;
969 this->route_points=NULL;
970 memset(this->hash, 0, sizeof(this->hash));
974 * @brief Returns the position of a certain field appended to a route graph segment
976 * This function returns a pointer to a field that is appended to a route graph
979 * @param seg The route graph segment the field is appended to
980 * @param type Type of the field that should be returned
981 * @return A pointer to a field of a certain type, or NULL if no such field is present
984 *route_graph_segment_field_pos(struct route_graph_segment *seg, enum attr_type type)
988 ptr = ((unsigned char*)seg) + sizeof(struct route_graph_segment);
990 if (type == attr_maxspeed) {
994 if (seg->flags & AF_SPEED_LIMIT) {
998 if (type == attr_offset) {
1006 * @brief Retrieves the value of a certain field appended to a route graph segment
1008 * This function tries to retrieve the value of a certain field, that is appended
1009 * to a route graph segment. The type of the field to be retrieved is determined
1010 * via the type attribute of the attr passed. Returns 0 if the value could not be
1011 * retrieved (e.g. because there is no such field with this route graph segment).
1013 * @param seg The segment to retrieve the field from
1014 * @param field Specifies the type of the field to be retrieved. The value is returned within this attribute.
1015 * @return 1 if the value could be retrieved, 0 if not
1018 route_graph_segment_get_field(struct route_graph_segment *seg, struct attr *field)
1022 switch (field->type) {
1024 if (!(seg->flags & AF_SPEED_LIMIT)) {
1028 num = (int *)route_graph_segment_field_pos(seg, field->type);
1029 field->u.num = *num;
1033 if (!(seg->flags & AF_SEGMENTED)) {
1037 num = (int *)route_graph_segment_field_pos(seg, field->type);
1038 field->u.num = *num;
1048 * @brief Sets the value of a certain field appended to a route graph segment
1050 * This function sets the value of a field, whose type is specified via the type attribute
1051 * of the passed attr. Returns 1 if the value could be set, 0 if not (e.g. if this
1052 * field is not present in this segment).
1054 * @param seg The segment the field is appended to
1055 * @param field Contains the type of the field to set and the value to set.
1056 * @return 1 if value could be set, 0 if not.
1059 route_graph_segment_set_field(struct route_graph_segment *seg, struct attr *field)
1063 switch (field->type) {
1065 if (!(seg->flags & AF_SPEED_LIMIT)) {
1069 num = (int *)route_graph_segment_field_pos(seg, field->type);
1070 *num = field->u.num;
1073 if (!(seg->flags & AF_SEGMENTED)) {
1077 num = (int *)route_graph_segment_field_pos(seg, field->type);
1078 *num = field->u.num;
1088 * @brief Inserts a new segment into the route graph
1090 * This function performs a check if a segment for the item specified already exists, and inserts
1091 * a new segment representing this item if it does not.
1093 * @param this The route graph to insert the segment into
1094 * @param start The graph point which should be connected to the start of this segment
1095 * @param end The graph point which should be connected to the end of this segment
1096 * @param len The length of this segment
1097 * @param item The item that is represented by this segment
1098 * @param flags Flags for this segment
1099 * @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
1100 * @param maxspeed The maximum speed allowed on this segment in km/h. -1 if not known.
1103 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
1104 struct route_graph_point *end, int len, struct item *item,
1105 int flags, int offset, int maxspeed)
1107 struct route_graph_segment *s;
1109 struct attr maxspeed_attr, offset_attr;
1112 offset_attr.type = attr_offset;
1114 if (item_is_equal(*item, s->item)) {
1115 if (flags & AF_SEGMENTED) {
1116 if (route_graph_segment_get_field(s,&offset_attr) && offset_attr.u.num == offset) {
1126 size = sizeof(struct route_graph_segment);
1128 if (flags & AF_SPEED_LIMIT) {
1129 size += sizeof(int);
1132 if (flags & AF_SEGMENTED) {
1133 size += sizeof(int);
1136 s = g_malloc0(size);
1138 printf("%s:Out of memory\n", __FUNCTION__);
1142 s->start_next=start->start;
1145 s->end_next=end->end;
1147 dbg_assert(len >= 0);
1152 if (flags & AF_SPEED_LIMIT) {
1153 maxspeed_attr.type = attr_maxspeed;
1154 maxspeed_attr.u.num = maxspeed;
1156 route_graph_segment_set_field(s, &maxspeed_attr);
1159 if (flags & AF_SEGMENTED) {
1160 offset_attr.type = attr_offset;
1161 offset_attr.u.num = offset;
1163 route_graph_segment_set_field(s, &offset_attr);
1166 s->next=this->route_segments;
1167 this->route_segments=s;
1169 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1173 * @brief Gets all the coordinates of an item
1175 * This will get all the coordinates of the item i and return them in c,
1176 * up to max coordinates. Additionally it is possible to limit the coordinates
1177 * returned to all the coordinates of the item between the two coordinates
1180 * @important Make shure that whatever c points to has enough memory allocated
1181 * @important to hold max coordinates!
1183 * @param i The item to get the coordinates of
1184 * @param c Pointer to memory allocated for holding the coordinates
1185 * @param max Maximum number of coordinates to return
1186 * @param start First coordinate to get
1187 * @param end Last coordinate to get
1188 * @return The number of coordinates returned
1190 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1191 struct coord *start, struct coord *end)
1193 struct map_rect *mr;
1197 mr=map_rect_new(i->map, NULL);
1200 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1202 rc = item_coord_get(item, &c1, 1);
1203 while (rc && (c1.x != start->x || c1.y != start->y)) {
1204 rc = item_coord_get(item, &c1, 1);
1206 while (rc && p < max) {
1208 if (c1.x == end->x && c1.y == end->y)
1210 rc = item_coord_get(item, &c1, 1);
1213 map_rect_destroy(mr);
1218 * @brief Returns and removes one segment from a path
1220 * @param path The path to take the segment from
1221 * @param item The item whose segment to remove
1222 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1223 * @return The segment removed
1225 static struct route_path_segment *
1226 route_extract_segment_from_path(struct route_path *path, struct item *item,
1229 struct route_path_segment *sp = NULL, *s;
1232 if (s->offset == offset && item_is_equal(s->item,*item)) {
1237 path->path = s->next;
1245 item_hash_remove(path->path_hash, item);
1250 * @brief Adds a segment and the end of a path
1252 * @param this The path to add the segment to
1253 * @param segment The segment to add
1256 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1260 if (this->path_last)
1261 this->path_last->next=segment;
1262 this->path_last=segment;
1266 * @brief Adds a new item to a path
1268 * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
1269 * if the item passed is segmented - it will create exactly one segment.
1271 * @param this The path to add the item to
1272 * @param item The item to add
1273 * @param len The length of the item
1274 * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
1275 * @param c Pointer to count coordinates of the item.
1276 * @param cound Number of coordinates in c
1277 * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
1278 * @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"
1279 * @param maxspeed The maximum allowed speed on this item in km/h. -1 if not known.
1282 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)
1284 int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
1285 struct route_path_segment *segment;
1287 segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
1288 segment->ncoords=ccount;
1289 segment->direction=dir;
1291 segment->c[idx++]=*first;
1293 for (i = 0 ; i < count ; i++)
1294 segment->c[idx++]=c[i];
1296 for (i = 0 ; i < count ; i++)
1297 segment->c[idx++]=c[count-i-1];
1300 segment->maxspeed=maxspeed;
1303 segment->c[idx++]=*last;
1304 segment->length=len;
1306 segment->item=*item;
1307 route_path_add_segment(this, segment);
1311 * @brief Inserts a new item into the path
1313 * This function does almost the same as "route_apth_add_item()", but identifies
1314 * the item to add by a segment from the route graph. Another difference is that it "copies" the
1315 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1316 * be added to the route path, not all segments of the item.
1318 * The function can be sped up by passing an old path already containing this segment in oldpath -
1319 * the segment will then be extracted from this old path. Please note that in this case the direction
1320 * parameter has no effect.
1322 * @param this The path to add the item to
1323 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1324 * @param rgs Segment of the route graph that should be "copied" to the route path
1325 * @param len Length of the item to be added
1326 * @param offset Offset of rgs within the item it represents
1327 * @param dir Order in which to add the coordinates. See route_path_add_item()
1328 * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
1331 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
1332 struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
1334 struct route_path_segment *segment;
1335 int i,ccnt = 0, ret=1;
1336 struct coord ca[2048];
1337 struct attr maxspeed_attr, offset_attr;
1340 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
1342 segment = route_extract_segment_from_path(oldpath,
1343 &rgs->item, offset);
1350 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1351 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1352 segment->direction=dir;
1354 for (i = 0 ; i < ccnt ; i++)
1355 segment->c[i]=ca[i];
1357 for (i = 0 ; i < ccnt ; i++)
1358 segment->c[i]=ca[ccnt-i-1];
1360 segment->ncoords = ccnt;
1362 /* We check if the route graph segment is part of a roundabout here, because this
1363 * only matters for route graph segments which form parts of the route path */
1364 if (!(rgs->flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier
1365 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1369 segment->item=rgs->item;
1371 if (rgs->flags & AF_SPEED_LIMIT) {
1372 maxspeed_attr.type = attr_maxspeed;
1373 if (route_graph_segment_get_field(rgs, &maxspeed_attr)) {
1374 segment->maxspeed = maxspeed_attr.u.num;
1376 segment->maxspeed = -1;
1379 segment->maxspeed = -1;
1382 if (rgs->flags & AF_SPEED_LIMIT) {
1383 offset_attr.type = attr_offset;
1384 if (route_graph_segment_get_field(rgs, &offset_attr)) {
1385 segment->offset = offset_attr.u.num;
1387 segment->offset = 1;
1390 segment->offset = 1;
1394 segment->length=len;
1396 item_hash_insert(this->path_hash, &rgs->item, (void *)ccnt);
1398 route_path_add_segment(this, segment);
1404 * @brief Destroys all segments of a route graph
1406 * @param this The graph to destroy all segments from
1409 route_graph_free_segments(struct route_graph *this)
1411 struct route_graph_segment *curr,*next;
1412 curr=this->route_segments;
1418 this->route_segments=NULL;
1422 * @brief Destroys a route graph
1424 * @param this The route graph to be destroyed
1427 route_graph_destroy(struct route_graph *this)
1430 route_graph_build_done(this, 1);
1431 route_graph_free_points(this);
1432 route_graph_free_segments(this);
1438 * @brief Returns the time needed to drive len on item
1440 * This function returns the time needed to drive len meters on
1441 * the item passed in item in tenth of seconds.
1443 * @param speedlist The speedlist that should be used
1444 * @param item The item to be driven on
1445 * @param len The length to drive
1446 * @param maxspeed The maximum allowed speed on this item, -1 if not known
1447 * @return The time needed to drive len on item in thenth of senconds
1450 route_time(int *speedlist, struct item *item, int len, int maxspeed)
1452 if (item->type < route_item_first || item->type > route_item_last) {
1453 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1456 if (!speedlist[item->type-route_item_first] && maxspeed <= 0) {
1457 dbg(0,"street type %d speed is zero\n", item->type);
1461 if (maxspeed <= 0) {
1462 return len*36/speedlist[item->type-route_item_first];
1464 return len*36/maxspeed;
1469 * @brief Returns the "costs" of driving len on item
1471 * @param speedlist The speedlist that should be used
1472 * @param item The item to be driven on
1473 * @param len The length to drive
1474 * @param maxspeed The maximum allowed speed on this item, -1 if not known
1475 * @return The "costs" needed to drive len on item
1478 route_value(int *speedlist, struct item *item, int len, int maxspeed)
1482 printf("len=%d\n", len);
1484 dbg_assert(len >= 0);
1485 ret=route_time(speedlist, item, len, maxspeed);
1486 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1491 * @brief Adds an item to the route graph
1493 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1496 * @param this The route graph to add to
1497 * @param item The item to add
1500 route_process_street_graph(struct route_graph *this, struct item *item)
1507 struct route_graph_point *s_pnt,*e_pnt;
1509 struct attr flags_attr, maxspeed_attr;
1515 if (item_coord_get(item, &l, 1)) {
1516 if (item_attr_get(item, attr_flags, &flags_attr)) {
1517 flags = flags_attr.u.num;
1518 if (flags & AF_SEGMENTED)
1522 if (flags & AF_SPEED_LIMIT) {
1523 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
1524 maxspeed = maxspeed_attr.u.num;
1528 s_pnt=route_graph_add_point(this,&l);
1530 while (item_coord_get(item, &c, 1)) {
1531 len+=transform_distance(map_projection(item->map), &l, &c);
1534 e_pnt=route_graph_add_point(this,&l);
1535 dbg_assert(len >= 0);
1536 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1541 isseg = item_coord_is_node(item);
1542 rc = item_coord_get(item, &c, 1);
1544 len+=transform_distance(map_projection(item->map), &l, &c);
1547 e_pnt=route_graph_add_point(this,&l);
1548 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1550 s_pnt=route_graph_add_point(this,&l);
1555 e_pnt=route_graph_add_point(this,&l);
1556 dbg_assert(len >= 0);
1558 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset, maxspeed);
1564 * @brief Compares the costs of reaching the destination from two points on
1566 * @important Do not pass anything other than route_graph_points in v1 and v2!
1570 * @return The additional costs of v1 compared to v2 (may be negative)
1573 compare(void *v1, void *v2)
1575 struct route_graph_point *p1=v1;
1576 struct route_graph_point *p2=v2;
1579 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1581 return p1->value-p2->value;
1585 * @brief Calculates the routing costs for each point
1587 * This function is the heart of routing. It assigns each point in the route graph a
1588 * cost at which one can reach the destination from this point on. Additionally it assigns
1589 * each point a segment one should follow from this point on to reach the destination at the
1592 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1593 * at this algorithm.
1596 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist, struct callback *cb)
1598 struct route_graph_point *p_min,*end=NULL;
1599 struct route_graph_segment *s;
1600 int min,new,old,val;
1601 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1602 struct street_data *sd=dst->street;
1603 struct attr maxspeed_attr;
1605 heap = fh_makeheap();
1606 fh_setcmp(heap, compare);
1608 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 */
1609 end=route_graph_get_point(this, &sd->c[0]);
1610 dbg_assert(end != 0);
1611 end->value=route_value(speedlist, &sd->item, dst->lenneg, sd->maxspeed);
1612 end->el=fh_insert(heap, end);
1615 if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1616 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1617 dbg_assert(end != 0);
1618 end->value=route_value(speedlist, &sd->item, dst->lenpos, sd->maxspeed);
1619 end->el=fh_insert(heap, end);
1622 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1624 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1625 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1629 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);
1630 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1632 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1633 if (s->flags & AF_SPEED_LIMIT) {
1634 maxspeed_attr.type = attr_maxspeed;
1635 if (!route_graph_segment_get_field(s, &maxspeed_attr)) {
1636 maxspeed_attr.u.num = -1;
1639 maxspeed_attr.u.num = -1;
1641 val=route_value(speedlist, &s->item, s->len, maxspeed_attr.u.num);
1643 val+=val*2*street_route_contained(s->str->segid);
1647 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);
1648 if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1653 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1654 s->end->el=fh_insert(heap, s->end);
1656 printf("el new=%p\n", s->end->el);
1660 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1661 fh_replacedata(heap, s->end->el, s->end);
1669 while (s) { /* Doing the same as above with the segments leading towards our point */
1670 if (s->flags & AF_SPEED_LIMIT) {
1671 maxspeed_attr.type = attr_maxspeed;
1672 if (!route_graph_segment_get_field(s, &maxspeed_attr)) {
1673 maxspeed_attr.u.num = -1;
1676 maxspeed_attr.u.num = -1;
1678 val=route_value(speedlist, &s->item, s->len, maxspeed_attr.u.num);
1681 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);
1682 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1683 old=s->start->value;
1684 s->start->value=new;
1686 if (! s->start->el) {
1688 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1689 s->start->el=fh_insert(heap, s->start);
1691 printf("el new=%p\n", s->start->el);
1695 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1696 fh_replacedata(heap, s->start->el, s->start);
1704 fh_deleteheap(heap);
1705 callback_call_0(cb);
1709 * @brief Starts an "offroad" path
1711 * This starts a path that is not located on a street. It creates a new route path
1712 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1714 * @param this Not used
1715 * @param pos The starting position for the new path
1716 * @param dst The destination of the new path
1717 * @param dir Not used
1718 * @return The new path
1720 static struct route_path *
1721 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1723 struct route_path *ret;
1725 ret=g_new0(struct route_path, 1);
1726 ret->path_hash=item_hash_new();
1727 route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1, -1);
1734 * @brief Creates a new "trivial" route
1736 * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1737 * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1739 * @param this The route graph to place the route on
1740 * @param pos The starting position for the new path
1741 * @param dst The destination of the new path
1742 * @param dir Direction of the coordinates to be added
1743 * @return The new path
1745 static struct route_path *
1746 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1748 struct street_data *sd=pos->street;
1749 struct route_path *ret;
1752 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1753 return route_path_new_offroad(this, pos, dst, dir);
1755 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1756 return route_path_new_offroad(this, pos, dst, dir);
1758 ret=g_new0(struct route_path, 1);
1759 ret->path_hash=item_hash_new();
1761 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1, -1);
1763 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);
1765 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);
1767 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1, -1);
1773 * @brief Returns a coordinate at a given distance
1775 * This function returns the coordinate, where the user will be if he
1776 * follows the current route for a certain distance.
1778 * @param this_ The route we're driving upon
1779 * @param dist The distance in meters
1780 * @return The coordinate where the user will be in that distance
1783 route_get_coord_dist(struct route *this_, int dist)
1788 struct route_path_segment *cur;
1790 enum projection pro=route_projection(this_);
1794 if (!this_->path2 || pro == projection_none) {
1795 return this_->pos->c;
1798 ret = this_->pos->c;
1799 cur = this_->path2->path;
1801 if (cur->length < d) {
1804 for (i=0; i < (cur->ncoords-1); i++) {
1806 len = (int)transform_polyline_length(pro, (cur->c + i), 2);
1809 // We interpolate a bit here...
1810 frac = (double)l / len;
1812 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
1813 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
1815 ret.x = (cur->c + i)->x + (frac * dx);
1816 ret.y = (cur->c + i)->y + (frac * dy);
1820 return cur->c[(cur->ncoords-1)];
1825 return this_->dst->c;
1829 * @brief Creates a new route path
1831 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1832 * make shure to run route_graph_flood() after changing the destination before using this function.
1834 * @param this The route graph to create the route from
1835 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1836 * @param pos The starting position of the route
1837 * @param dst The destination of the route
1838 * @param speedlist The speedlist to use
1839 * @return The new route path
1841 static struct route_path *
1842 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1844 struct route_graph_point *start1=NULL,*start2=NULL,*start;
1845 struct route_graph_segment *s=NULL;
1846 struct route_graph_segment *lastseg = NULL;
1851 int time=0,hr,min,sec
1853 unsigned int val1=0xffffffff,val2=0xffffffff;
1854 struct street_data *sd=pos->street;
1855 struct route_path *ret;
1856 struct attr offset_attr;
1858 offset_attr.type = attr_offset;
1860 if (! pos->street || ! dst->street)
1862 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 */
1863 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1864 return route_path_new_trivial(this, pos, dst, -1);
1866 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1867 return route_path_new_trivial(this, pos, dst, 1);
1870 if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1871 start1=route_graph_get_point(this, &sd->c[0]);
1874 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg, sd->maxspeed);
1875 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1877 if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1878 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1881 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos, sd->maxspeed);
1882 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1884 dbg(1,"val1=%d val2=%d\n", val1, val2);
1886 val1=start1->start->start->value;
1887 val2=start2->end->end->value;
1889 ret=g_new0(struct route_path, 1);
1892 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1, -1);
1893 if (start1 && (val1 < val2)) {
1895 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1, sd->maxspeed);
1899 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);
1901 printf("no route found, pos blocked\n");
1905 ret->path_hash=item_hash_new();
1906 while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1909 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1914 if (!route_graph_segment_get_field(s, &offset_attr)) {
1915 offset_attr.u.num = 1;
1918 if (s->start == start) {
1919 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, offset_attr.u.num, 1, is_straight))
1923 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, offset_attr.u.num, -1, is_straight))
1931 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1932 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);
1933 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 */
1934 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1, sd->maxspeed);
1935 } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1936 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);
1938 printf("no route found\n");
1939 route_path_destroy(ret);
1943 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1, -1);
1944 dbg(1, "%d segments\n", segs);
1949 route_graph_build_next_map(struct route_graph *rg)
1952 rg->m=mapset_next(rg->h, 1);
1955 map_rect_destroy(rg->mr);
1956 rg->mr=map_rect_new(rg->m, rg->sel);
1963 route_graph_build_done(struct route_graph *rg, int cancel)
1965 dbg(1,"cancel=%d\n",cancel);
1966 event_remove_idle(rg->idle_ev);
1967 callback_destroy(rg->idle_cb);
1968 map_rect_destroy(rg->mr);
1969 mapset_close(rg->h);
1970 route_free_selection(rg->sel);
1977 callback_call_0(rg->done_cb);
1982 route_graph_build_idle(struct route_graph *rg)
1989 item=map_rect_get_item(rg->mr);
1992 if (!route_graph_build_next_map(rg)) {
1993 route_graph_build_done(rg, 0);
1997 if (item->type >= type_street_0 && item->type <= type_ferry)
1998 route_process_street_graph(rg, item);
2004 * @brief Builds a new route graph from a mapset
2006 * This function builds a new route graph from a map. Please note that this function does not
2007 * add any routing information to the route graph - this has to be done via the route_graph_flood()
2010 * The function does not create a graph covering the whole map, but only covering the rectangle
2011 * between c1 and c2.
2013 * @param ms The mapset to build the route graph from
2014 * @param c1 Corner 1 of the rectangle to use from the map
2015 * @param c2 Corner 2 of the rectangle to use from the map
2016 * @param done_cb The callback which will be called when graph is complete
2017 * @return The new route graph.
2019 static struct route_graph *
2020 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb)
2022 struct route_graph *ret=g_new0(struct route_graph, 1);
2026 ret->sel=route_calc_selection(c1, c2);
2027 ret->h=mapset_open(ms);
2028 ret->done_cb=done_cb;
2030 if (route_graph_build_next_map(ret)) {
2031 ret->idle_cb=callback_new_1(callback_cast(route_graph_build_idle), ret);
2032 ret->idle_ev=event_add_idle(50, ret->idle_cb);
2034 route_graph_build_done(ret, 0);
2040 route_graph_update_done(struct route *this, struct callback *cb)
2042 route_graph_flood(this->graph, this->dst, this->speedlist, cb);
2046 * @brief Updates the route graph
2048 * This updates the route graph after settings in the route have changed. It also
2049 * adds routing information afterwards by calling route_graph_flood().
2051 * @param this The route to update the graph for
2054 route_graph_update(struct route *this, struct callback *cb)
2056 route_graph_destroy(this->graph);
2057 callback_destroy(this->route_graph_done_cb);
2058 this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
2059 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
2060 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c, this->route_graph_done_cb);
2064 * @brief Gets street data for an item
2066 * @param item The item to get the data for
2067 * @return Street data for the item
2069 struct street_data *
2070 street_get_data (struct item *item)
2073 struct street_data *ret = NULL, *ret1;
2074 struct attr flags_attr, maxspeed_attr;
2075 const int step = 128;
2079 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
2086 c = item_coord_get(item, &ret->c[count], step);
2088 } while (c && c == step);
2090 ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
2095 if (item_attr_get(item, attr_flags, &flags_attr))
2096 ret->flags=flags_attr.u.num;
2101 if (ret->flags & AF_SPEED_LIMIT) {
2102 if (item_attr_get(item, attr_maxspeed, &maxspeed_attr)) {
2103 ret->maxspeed = maxspeed_attr.u.num;
2111 * @brief Copies street data
2113 * @param orig The street data to copy
2114 * @return The copied street data
2116 struct street_data *
2117 street_data_dup(struct street_data *orig)
2119 struct street_data *ret;
2120 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
2123 memcpy(ret, orig, size);
2129 * @brief Frees street data
2131 * @param sd Street data to be freed
2134 street_data_free(struct street_data *sd)
2140 * @brief Finds the nearest street to a given coordinate
2142 * @param ms The mapset to search in for the street
2143 * @param pc The coordinate to find a street nearby
2144 * @return The nearest street
2146 static struct route_info *
2147 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
2149 struct route_info *ret=NULL;
2151 struct map_selection *sel;
2152 int dist,mindist=0,pos;
2153 struct mapset_handle *h;
2155 struct map_rect *mr;
2158 struct street_data *sd;
2162 ret=g_new0(struct route_info, 1);
2164 dbg(0,"Out of memory\n");
2170 while ((m=mapset_next(h,1))) {
2173 if (map_projection(m) != pc->pro) {
2174 transform_to_geo(pc->pro, &c, &g);
2175 transform_from_geo(map_projection(m), &g, &c);
2177 sel = route_rect(18, &c, &c, 0, max_dist);
2180 mr=map_rect_new(m, sel);
2182 map_selection_destroy(sel);
2185 while ((item=map_rect_get_item(mr))) {
2186 if (item->type >= type_street_0 && item->type <= type_ferry) {
2187 sd=street_get_data(item);
2190 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
2191 if (dist < mindist) {
2194 street_data_free(ret->street);
2200 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
2202 street_data_free(sd);
2206 map_selection_destroy(sel);
2207 map_rect_destroy(mr);
2211 if (!ret->street || mindist > max_dist*max_dist) {
2213 street_data_free(ret->street);
2214 dbg(1,"Much too far %d > %d\n", mindist, max_dist);
2224 * @brief Destroys a route_info
2226 * @param info The route info to be destroyed
2229 route_info_free(struct route_info *inf)
2232 street_data_free(inf->street);
2240 * @brief Returns street data for a route info
2242 * @param rinf The route info to return the street data for
2243 * @return Street data for the route info
2245 struct street_data *
2246 route_info_street(struct route_info *rinf)
2248 return rinf->street;
2252 struct route_crossings *
2253 route_crossings_get(struct route *this, struct coord *c)
2255 struct route_point *pnt;
2256 struct route_segment *seg;
2258 struct route_crossings *ret;
2260 pnt=route_graph_get_point(this, c);
2263 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2265 seg=seg->start_next;
2269 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2273 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
2274 ret->count=crossings;
2280 struct map_rect_priv {
2281 struct route_info_handle *ri;
2282 enum attr_type attr_next;
2284 struct map_priv *mpriv;
2287 unsigned int last_coord;
2288 struct route_path *path;
2289 struct route_path_segment *seg,*seg_next;
2290 struct route_graph_point *point;
2291 struct route_graph_segment *rseg;
2293 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
2294 struct route_graph_point_iterator it;
2298 rm_coord_rewind(void *priv_data)
2300 struct map_rect_priv *mr = priv_data;
2305 rm_attr_rewind(void *priv_data)
2307 struct map_rect_priv *mr = priv_data;
2308 mr->attr_next = attr_street_item;
2312 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2314 struct map_rect_priv *mr = priv_data;
2315 struct route_path_segment *seg=mr->seg;
2316 struct route *route=mr->mpriv->route;
2317 if (mr->item.type != type_street_route)
2319 attr->type=attr_type;
2320 switch (attr_type) {
2322 while (mr->attr_next != attr_none) {
2323 if (rm_attr_get(priv_data, mr->attr_next, attr))
2328 mr->attr_next = attr_street_item;
2330 attr->u.num = seg->maxspeed;
2335 case attr_street_item:
2336 mr->attr_next=attr_direction;
2337 if (seg && seg->item.map)
2338 attr->u.item=&seg->item;
2342 case attr_direction:
2343 mr->attr_next=attr_route;
2345 attr->u.num=seg->direction;
2350 mr->attr_next=attr_length;
2351 attr->u.route = mr->mpriv->route;
2355 attr->u.num=seg->length;
2357 attr->u.num=mr->length;
2358 mr->attr_next=attr_time;
2361 mr->attr_next=attr_none;
2363 attr->u.num=route_time(route->speedlist, &seg->item, seg->length, seg->maxspeed);
2368 mr->attr_next=attr_none;
2371 mr->attr_next=attr_none;
2372 attr->type=attr_none;
2379 rm_coord_get(void *priv_data, struct coord *c, int count)
2381 struct map_rect_priv *mr = priv_data;
2382 struct route_path_segment *seg = mr->seg;
2384 struct route *r = mr->mpriv->route;
2385 enum projection pro = route_projection(r);
2387 if (pro == projection_none)
2389 if (mr->item.type == type_route_start || mr->item.type == type_route_end) {
2390 if (! count || mr->last_coord)
2393 if (mr->item.type == type_route_start)
2401 for (i=0; i < count; i++) {
2402 if (mr->last_coord >= seg->ncoords)
2404 if (i >= seg->ncoords)
2406 if (pro != projection_mg)
2407 transform_from_to(&seg->c[mr->last_coord++], pro,
2408 &c[i],projection_mg);
2410 c[i] = seg->c[mr->last_coord++];
2413 dbg(1,"return %d\n",rc);
2417 static struct item_methods methods_route_item = {
2425 rp_attr_rewind(void *priv_data)
2427 struct map_rect_priv *mr = priv_data;
2428 mr->attr_next = attr_label;
2432 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2434 struct map_rect_priv *mr = priv_data;
2435 struct route_graph_point *p = mr->point;
2436 struct route_graph_segment *seg = mr->rseg;
2437 switch (attr_type) {
2438 case attr_any: // works only with rg_points for now
2439 if (mr->item.type != type_rg_point)
2441 while (mr->attr_next != attr_none) {
2442 if (rp_attr_get(priv_data, mr->attr_next, attr))
2447 mr->attr_next = attr_label;
2448 if (mr->item.type != type_rg_segment)
2451 attr->type = attr_maxspeed;
2452 if (!route_graph_segment_get_field(seg,attr)) {
2461 if (mr->item.type != type_rg_point)
2463 attr->type = attr_label;
2466 if (p->value != INT_MAX)
2467 mr->str=g_strdup_printf("%d", p->value);
2469 mr->str=g_strdup("-");
2470 attr->u.str = mr->str;
2471 mr->attr_next=attr_none;
2473 case attr_street_item:
2474 if (mr->item.type != type_rg_segment)
2476 mr->attr_next=attr_none;
2477 if (seg && seg->item.map)
2478 attr->u.item=&seg->item;
2483 if (mr->item.type != type_rg_segment)
2485 mr->attr_next = attr_none;
2487 attr->u.num = seg->flags;
2492 case attr_direction:
2493 // This only works if the map has been opened at a single point, and in that case indicates if the
2494 // segment returned last is connected to this point via its start (1) or its end (-1)
2495 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
2497 if (seg->start == mr->point) {
2499 } else if (seg->end == mr->point) {
2506 if (mr->item.type != type_rg_point)
2508 attr->type = attr_debug;
2511 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2512 attr->u.str = mr->str;
2513 mr->attr_next=attr_none;
2516 mr->attr_next=attr_none;
2517 attr->type=attr_none;
2523 * @brief Returns the coordinates of a route graph item
2525 * @param priv_data The route graph item's private data
2526 * @param c Pointer where to store the coordinates
2527 * @param count How many coordinates to get at a max?
2528 * @return The number of coordinates retrieved
2531 rp_coord_get(void *priv_data, struct coord *c, int count)
2533 struct map_rect_priv *mr = priv_data;
2534 struct route_graph_point *p = mr->point;
2535 struct route_graph_segment *seg = mr->rseg;
2537 struct route *r = mr->mpriv->route;
2538 enum projection pro = route_projection(r);
2540 if (pro == projection_none)
2542 for (i=0; i < count; i++) {
2543 if (mr->item.type == type_rg_point) {
2544 if (mr->last_coord >= 1)
2546 if (pro != projection_mg)
2547 transform_from_to(&p->c, pro,
2548 &c[i],projection_mg);
2552 if (mr->last_coord >= 2)
2555 if (seg->end->seg == seg)
2560 if (pro != projection_mg)
2561 transform_from_to(&seg->end->c, pro,
2562 &c[i],projection_mg);
2566 if (pro != projection_mg)
2567 transform_from_to(&seg->start->c, pro,
2568 &c[i],projection_mg);
2570 c[i] = seg->start->c;
2579 static struct item_methods methods_point_item = {
2587 rp_destroy(struct map_priv *priv)
2593 rm_destroy(struct map_priv *priv)
2598 static struct map_rect_priv *
2599 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2601 struct map_rect_priv * mr;
2603 if (! route_get_pos(priv->route))
2605 if (! route_get_dst(priv->route))
2608 if (! priv->route->path2)
2611 mr=g_new0(struct map_rect_priv, 1);
2613 mr->item.priv_data = mr;
2614 mr->item.type = type_none;
2615 mr->item.meth = &methods_route_item;
2616 if (priv->route->path2) {
2617 mr->path=priv->route->path2;
2618 mr->seg_next=mr->path->path;
2626 * @brief Opens a new map rectangle on the route graph's map
2628 * This function opens a new map rectangle on the route graph's map.
2629 * The "sel" parameter enables you to only search for a single route graph
2630 * point on this map (or exactly: open a map rectangle that only contains
2631 * this one point). To do this, pass here a single map selection, whose
2632 * c_rect has both coordinates set to the same point. Otherwise this parameter
2635 * @param priv The route graph map's private data
2636 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2637 * @return A new map rect's private data
2639 static struct map_rect_priv *
2640 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2642 struct map_rect_priv * mr;
2645 if (! priv->route->graph || ! priv->route->graph->route_points)
2647 mr=g_new0(struct map_rect_priv, 1);
2649 mr->item.priv_data = mr;
2650 mr->item.type = type_rg_point;
2651 mr->item.meth = &methods_point_item;
2653 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)) {
2654 mr->coord_sel = g_malloc(sizeof(struct coord));
2655 *(mr->coord_sel) = sel->u.c_rect.lu;
2662 rm_rect_destroy(struct map_rect_priv *mr)
2666 if (mr->coord_sel) {
2667 g_free(mr->coord_sel);
2671 if (mr->path->update_required && !mr->path->in_use)
2672 route_path_update_done(mr->mpriv->route, mr->path->update_required-1);
2678 static struct item *
2679 rp_get_item(struct map_rect_priv *mr)
2681 struct route *r = mr->mpriv->route;
2682 struct route_graph_point *p = mr->point;
2683 struct route_graph_segment *seg = mr->rseg;
2685 if (mr->item.type == type_rg_point) {
2686 if (mr->coord_sel) {
2687 // We are supposed to return only the point at one specified coordinate...
2689 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2690 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2693 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2694 mr->point = NULL; // This indicates that no point has been found
2696 mr->it = rp_iterator_new(p);
2703 p = r->graph->route_points;
2710 rm_coord_rewind(mr);
2714 mr->item.type = type_rg_segment;
2717 if (mr->coord_sel) {
2718 if (!mr->point) { // This means that no point has been found
2721 seg = rp_iterator_next(&(mr->it));
2724 seg=r->graph->route_segments;
2732 rm_coord_rewind(mr);
2740 static struct item *
2741 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2743 struct item *ret=NULL;
2745 ret=rp_get_item(mr);
2750 static struct item *
2751 rm_get_item(struct map_rect_priv *mr)
2753 dbg(1,"enter\n", mr->pos);
2755 switch (mr->item.type) {
2757 mr->item.type=type_route_start;
2758 if (mr->mpriv->route->pos)
2761 mr->item.type=type_street_route;
2762 mr->seg=mr->seg_next;
2764 mr->seg_next=mr->seg->next;
2767 mr->item.type=type_route_end;
2768 if (mr->mpriv->route->dst)
2770 case type_route_end:
2779 static struct item *
2780 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2782 struct item *ret=NULL;
2784 ret=rm_get_item(mr);
2788 static struct map_methods route_meth = {
2801 static struct map_methods route_graph_meth = {
2815 route_toggle_routegraph_display(struct route *route)
2817 if (route->flags & RF_SHOWGRAPH) {
2818 route->flags &= ~RF_SHOWGRAPH;
2820 route->flags |= RF_SHOWGRAPH;
2824 static struct map_priv *
2825 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2827 struct map_priv *ret;
2828 struct attr *route_attr;
2830 route_attr=attr_search(attrs, NULL, attr_route);
2833 ret=g_new0(struct map_priv, 1);
2835 *meth=route_graph_meth;
2838 ret->route=route_attr->u.route;
2843 static struct map_priv *
2844 route_map_new(struct map_methods *meth, struct attr **attrs)
2846 return route_map_new_helper(meth, attrs, 0);
2849 static struct map_priv *
2850 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2852 return route_map_new_helper(meth, attrs, 1);
2856 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2859 *map=map_new(NULL, (struct attr*[]){
2860 &(struct attr){attr_type,{type}},
2861 &(struct attr){attr_route,.u.route=this_},
2862 &(struct attr){attr_data,{""}},
2863 &(struct attr){attr_description,{description}},
2870 * @brief Returns a new map containing the route path
2872 * This function returns a new map containing the route path.
2874 * @important Do not map_destroy() this!
2876 * @param this_ The route to get the map of
2877 * @return A new map containing the route path
2880 route_get_map(struct route *this_)
2882 return route_get_map_helper(this_, &this_->map, "route","Route");
2887 * @brief Returns a new map containing the route graph
2889 * This function returns a new map containing the route graph.
2891 * @important Do not map_destroy() this!
2893 * @param this_ The route to get the map of
2894 * @return A new map containing the route graph
2897 route_get_graph_map(struct route *this_)
2899 return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2903 route_set_projection(struct route *this_, enum projection pro)
2908 route_add_callback(struct route *this_, struct callback *cb)
2910 callback_list_add(this_->cbl, cb);
2914 route_remove_callback(struct route *this_, struct callback *cb)
2916 callback_list_remove(this_->cbl, cb);
2923 plugin_register_map_type("route", route_map_new);
2924 plugin_register_map_type("route_graph", route_graph_map_new);