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 int offset; /**< If the item represented by this segment is "segmented" (i.e.
115 * is represented by several segments instead of just one), this
116 * indicates the position of this segment in the item - for items
117 * that are not segmented this should always be 1 */
121 * @brief A segment in the route path
123 * This is a segment in the route path.
125 struct route_path_segment {
126 struct route_path_segment *next; /**< Pointer to the next segment in the path */
127 struct item item; /**< The item (e.g. street) this segment represents */
128 int length; /**< Length of the segment */
129 int offset; /**< Same as in route_graph_segment->offset */
130 int direction; /**< Order in which the coordinates are ordered. >0 means "First
131 * coordinate of the segment is the first coordinate of the item", <=0
133 unsigned ncoords; /**< How many coordinates does this segment have? */
134 struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
135 /* WARNING: There will be coordinates following here, so do not create new fields after c! */
139 * @brief Usually represents a destination or position
141 * This struct usually represents a destination or position
144 struct coord c; /**< The actual destination / position */
145 struct coord lp; /**< The nearest point on a street to c */
146 int pos; /**< The position of lp within the coords of the street */
147 int lenpos; /**< Distance between lp and the end of the street */
148 int lenneg; /**< Distance between lp and the start of the street */
149 int lenextra; /**< Distance between lp and c */
151 struct street_data *street; /**< The street lp is on */
155 * @brief A complete route path
157 * This structure describes a whole routing path
160 int updated; /**< The path has only been updated */
161 struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
163 struct route_path_segment *path_last; /**< The last segment in the path */
164 /* XXX: path_hash is not necessery now */
165 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
168 #define RF_FASTEST (1<<0)
169 #define RF_SHORTEST (1<<1)
170 #define RF_AVOIDHW (1<<2)
171 #define RF_AVOIDPAID (1<<3)
172 #define RF_LOCKONROAD (1<<4)
173 #define RF_SHOWGRAPH (1<<5)
176 * @brief A complete route
178 * This struct holds all information about a route.
181 struct mapset *ms; /**< The mapset this route is built upon */
183 struct route_info *pos; /**< Current position within this route */
184 struct route_info *dst; /**< Destination of the route */
186 struct route_graph *graph; /**< Pointer to the route graph */
187 struct route_path *path2; /**< Pointer to the route path */
189 struct map *graph_map;
190 struct callback * route_graph_done_cb ; /**< Callback when route graph is done */
191 struct callback * route_graph_flood_done_cb ; /**< Callback when route graph flooding is done */
192 struct callback_list *cbl; /**< Callback list to call when route changes */
193 int destination_distance; /**< Distance to the destination at which the destination is considered "reached" */
194 int speedlist[route_item_last-route_item_first+1]; /**< The speedlist for this route */
198 * @brief A complete route graph
200 * This structure describes a whole routing graph
203 int busy; /**< The graph is being built */
204 struct map_selection *sel; /**< The rectangle selection for the graph */
205 struct mapset_handle *h; /**< Handle to the mapset */
206 struct map *m; /**< Pointer to the currently active map */
207 struct map_rect *mr; /**< Pointer to the currently active map rectangle */
208 struct callback *idle_cb; /**< Idle callback to process the graph */
209 struct callback *done_cb; /**< Callback when graph is done */
210 struct event_idle *idle_ev; /**< The pointer to the idle event */
211 struct route_graph_point *route_points; /**< Pointer to the first route_graph_point in the linked list of all points */
212 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
213 #define HASH_SIZE 8192
214 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
217 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
220 * @brief Iterator to iterate through all route graph segments in a route graph point
222 * This structure can be used to iterate through all route graph segments connected to a
223 * route graph point. Use this with the rp_iterator_* functions.
225 struct route_graph_point_iterator {
226 struct route_graph_point *p; /**< The route graph point whose segments should be iterated */
227 int end; /**< Indicates if we have finished iterating through the "start" segments */
228 struct route_graph_segment *next; /**< The next segment to be returned */
231 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
232 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
233 static void route_graph_update(struct route *this, struct callback *cb);
234 static void route_graph_build_done(struct route_graph *rg, int cancel);
235 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);
236 static void route_process_street_graph(struct route_graph *this, struct item *item);
237 static void route_graph_destroy(struct route_graph *this);
238 static void route_path_update(struct route *this, int cancel);
241 * @brief Returns the projection used for this route
243 * @param route The route to return the projection for
244 * @return The projection used for this route
246 static enum projection route_projection(struct route *route)
248 struct street_data *street;
249 if (!route->pos && !route->dst)
250 return projection_none;
251 street = route->pos ? route->pos->street : route->dst->street;
252 return map_projection(street->item.map);
256 * @brief Creates a new graph point iterator
258 * This function creates a new route graph point iterator, that can be used to
259 * iterate through all segments connected to the point.
261 * @param p The route graph point to create the iterator from
262 * @return A new iterator.
264 static struct route_graph_point_iterator
265 rp_iterator_new(struct route_graph_point *p)
267 struct route_graph_point_iterator it;
282 * @brief Gets the next segment connected to a route graph point from an iterator
284 * @param it The route graph point iterator to get the segment from
285 * @return The next segment or NULL if there are no more segments
287 static struct route_graph_segment
288 *rp_iterator_next(struct route_graph_point_iterator *it)
290 struct route_graph_segment *ret;
298 if (ret->start_next) {
299 it->next = ret->start_next;
301 it->next = it->p->end;
305 it->next = ret->end_next;
312 * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
314 * @param it The route graph point iterator to be checked
315 * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
318 rp_iterator_end(struct route_graph_point_iterator *it) {
319 if (it->end && (it->next != it->p->end)) {
327 * @brief Destroys a route_path
329 * @param this The route_path to be destroyed
332 route_path_destroy(struct route_path *this)
334 struct route_path_segment *c,*n;
337 if (this->path_hash) {
338 item_hash_destroy(this->path_hash);
339 this->path_hash=NULL;
351 * @brief Creates a completely new route structure
353 * @param attrs Not used
354 * @return The newly created route
357 route_new(struct attr *parent, struct attr **attrs)
359 struct route *this=g_new0(struct route, 1);
360 struct attr dest_attr;
362 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
363 this->destination_distance = dest_attr.u.num;
365 this->destination_distance = 50; // Default value
367 this->cbl=callback_list_new();
373 * @brief Checks if a segment is part of a roundabout
375 * This function checks if a segment is part of a roundabout.
377 * @param seg The segment to be checked
378 * @param level How deep to scan the route graph
379 * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
380 * @param origin Used internally, set to NULL
381 * @return 1 If a roundabout was detected, 0 otherwise
384 route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
386 struct route_graph_point_iterator it,it2;
387 struct route_graph_segment *cur;
393 if (!direction && !(seg->flags & AF_ONEWAY)) {
396 if (direction && !(seg->flags & AF_ONEWAYREV)) {
405 it = rp_iterator_new(seg->end);
407 it = rp_iterator_new(seg->start);
411 while ((cur = rp_iterator_next(&it2)))
416 cur = rp_iterator_next(&it);
419 cur = rp_iterator_next(&it);
424 seg->flags |= AF_ROUNDABOUT;
428 if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) {
429 seg->flags |= AF_ROUNDABOUT;
433 cur = rp_iterator_next(&it);
440 * @brief Sets the mapset of the route passwd
442 * @param this The route to set the mapset for
443 * @param ms The mapset to set for this route
446 route_set_mapset(struct route *this, struct mapset *ms)
452 * @brief Returns the mapset of the route passed
454 * @param this The route to get the mapset of
455 * @return The mapset of the route passed
458 route_get_mapset(struct route *this)
464 * @brief Returns the current position within the route passed
466 * @param this The route to get the position for
467 * @return The position within the route passed
470 route_get_pos(struct route *this)
476 * @brief Returns the destination of the route passed
478 * @param this The route to get the destination for
479 * @return The destination of the route passed
482 route_get_dst(struct route *this)
488 * @brief Returns the speedlist of the route passed
490 * @param this The route to get the speedlist for
491 * @return The speedlist of the route passed
494 route_get_speedlist(struct route *this)
496 return this->speedlist;
500 * @brief Checks if the path is calculated for the route passed
502 * @param this The route to check
503 * @return True if the path is calculated, false if not
506 route_get_path_set(struct route *this)
508 return this->path2 != NULL;
512 * @brief Sets the driving speed for a certain itemtype
514 * @param this The route to set the speed for
515 * @param type The itemtype to set the speed for
516 * @param value The speed that should be set
517 * @return True on success, false if the itemtype does not exist
520 route_set_speed(struct route *this, enum item_type type, int value)
522 if (type < route_item_first || type > route_item_last) {
523 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
526 this->speedlist[type-route_item_first]=value;
531 * @brief Checks if the route passed contains a certain item within the route path
533 * This function checks if a certain items exists in the path that navit will guide
534 * the user to his destination. It does *not* check if this item exists in the route
537 * @param this The route to check for this item
538 * @param item The item to search for
539 * @return True if the item was found, false if the item was not found or the route was not calculated
542 route_contains(struct route *this, struct item *item)
544 if (! this->path2 || !this->path2->path_hash)
546 return (int)item_hash_lookup(this->path2->path_hash, item);
550 * @brief Checks if the current position in a route is a certain item
552 * @param this The route to check for this item
553 * @param item The item to search for
554 * @return True if the current position is this item, false otherwise
557 route_pos_contains(struct route *this, struct item *item)
559 if (! this->pos || !this->pos->street)
561 return item_is_equal(this->pos->street->item, *item);
565 * @brief Checks if a route has reached its destination
567 * @param this The route to be checked
568 * @return True if the destination is "reached", false otherwise.
571 route_destination_reached(struct route *this)
573 struct street_data *sd = NULL;
579 sd = this->pos->street;
585 if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
589 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
592 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
595 pro=route_projection(this);
596 if (pro == projection_none)
599 if (transform_distance(pro, &this->pos->c, &this->dst->lp) > this->destination_distance) {
607 route_path_update_done(struct route *this, int new_graph)
609 struct route_path *oldpath=this->path2;
612 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
613 route_path_destroy(oldpath);
618 val=2+!this->path2->updated;
621 callback_list_call_attr_1(this->cbl, attr_route, (void *)val);
625 * @brief Updates the route graph and the route path if something changed with the route
627 * This will update the route graph and the route path of the route if some of the
628 * route's settings (destination, position) have changed.
630 * @attention For this to work the route graph has to be destroyed if the route's
631 * @attention destination is changed somewhere!
633 * @param this The route to update
636 route_path_update(struct route *this, int cancel)
638 dbg(1,"enter %d\n", cancel);
639 if (! this->pos || ! this->dst) {
641 route_path_destroy(this->path2);
646 route_graph_destroy(this->graph);
649 /* the graph is destroyed when setting the destination */
651 if (this->graph->busy) {
652 dbg(1,"busy building graph\n");
655 // we can try to update
656 dbg(1,"try update\n");
657 route_path_update_done(this, 0);
659 route_path_destroy(this->path2);
662 if (!this->graph || !this->path2) {
663 dbg(1,"rebuild graph\n");
664 if (! this->route_graph_flood_done_cb)
665 this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, 1);
666 dbg(1,"route_graph_update\n");
667 route_graph_update(this, this->route_graph_flood_done_cb);
672 * @brief This will calculate all the distances stored in a route_info
674 * @param ri The route_info to calculate the distances for
675 * @param pro The projection used for this route
678 route_info_distances(struct route_info *ri, enum projection pro)
681 struct street_data *sd=ri->street;
682 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
683 ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
684 ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
685 ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
689 * @brief This sets the current position of the route passed
691 * This will set the current position of the route passed to the street that is nearest to the
692 * passed coordinates. It also automatically updates the route.
694 * @param this The route to set the position of
695 * @param pos Coordinates to set as position
698 route_set_position(struct route *this, struct pcoord *pos)
701 route_info_free(this->pos);
703 this->pos=route_find_nearest_street(this->ms, pos);
704 dbg(1,"this->pos=%p\n", this->pos);
707 route_info_distances(this->pos, pos->pro);
708 route_path_update(this, 0);
712 * @brief Sets a route's current position based on coordinates from tracking
714 * @param this The route to set the current position of
715 * @param tracking The tracking to get the coordinates from
718 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
721 struct route_info *ret;
722 struct street_data *sd;
725 c=tracking_get_pos(tracking);
726 ret=g_new0(struct route_info, 1);
728 printf("%s:Out of memory\n", __FUNCTION__);
732 route_info_free(this->pos);
738 ret->pos=tracking_get_segment_pos(tracking);
739 sd=tracking_get_street_data(tracking);
741 ret->street=street_data_dup(sd);
742 route_info_distances(ret, c->pro);
744 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);
745 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);
748 route_path_update(this, 0);
752 /* Used for debuging of route_rect, what routing sees */
753 struct map_selection *route_selection;
756 * @brief Returns a single map selection
758 struct map_selection *
759 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
761 int dx,dy,sx=1,sy=1,d,m;
762 struct map_selection *sel=g_new(struct map_selection, 1);
764 printf("%s:Out of memory\n", __FUNCTION__);
768 sel->range.min=route_item_first;
769 sel->range.max=route_item_last;
770 dbg(1,"%p %p\n", c1, c2);
775 sel->u.c_rect.lu.x=c1->x;
776 sel->u.c_rect.rl.x=c2->x;
778 sel->u.c_rect.lu.x=c2->x;
779 sel->u.c_rect.rl.x=c1->x;
783 sel->u.c_rect.lu.y=c2->y;
784 sel->u.c_rect.rl.y=c1->y;
786 sel->u.c_rect.lu.y=c1->y;
787 sel->u.c_rect.rl.y=c2->y;
794 sel->u.c_rect.lu.x-=m;
795 sel->u.c_rect.rl.x+=m;
796 sel->u.c_rect.lu.y+=m;
797 sel->u.c_rect.rl.y-=m;
803 * @brief Returns a list of map selections useable to create a route graph
805 * Returns a list of map selections useable to get a map rect from which items can be
806 * retrieved to build a route graph. The selections are a rectangle with
807 * c1 and c2 as two corners.
809 * @param c1 Corner 1 of the rectangle
810 * @param c2 Corder 2 of the rectangle
812 static struct map_selection *
813 route_calc_selection(struct coord *c1, struct coord *c2)
815 struct map_selection *ret,*sel;
816 sel=route_rect(4, c1, c2, 25, 0);
818 sel->next=route_rect(8, c1, c1, 0, 40000);
820 sel->next=route_rect(18, c1, c1, 0, 10000);
822 sel->next=route_rect(8, c2, c2, 0, 40000);
824 sel->next=route_rect(18, c2, c2, 0, 10000);
825 /* route_selection=ret; */
830 * @brief Destroys a list of map selections
832 * @param sel Start of the list to be destroyed
835 route_free_selection(struct map_selection *sel)
837 struct map_selection *next;
847 * @brief Sets the destination of a route
849 * This sets the destination of a route to the street nearest to the coordinates passed
850 * and updates the route.
852 * @param this The route to set the destination for
853 * @param dst Coordinates to set as destination
856 route_set_destination(struct route *this, struct pcoord *dst)
860 route_info_free(this->dst);
863 this->dst=route_find_nearest_street(this->ms, dst);
865 route_info_distances(this->dst, dst->pro);
867 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
868 profile(1,"find_nearest_street");
870 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
871 route_graph_destroy(this->graph);
873 route_path_update(this, 1);
878 * @brief Gets the route_graph_point with the specified coordinates
880 * @param this The route in which to search
881 * @param c Coordinates to search for
882 * @return The point at the specified coordinates or NULL if not found
884 static struct route_graph_point *
885 route_graph_get_point(struct route_graph *this, struct coord *c)
887 struct route_graph_point *p;
888 int hashval=HASHCOORD(c);
889 p=this->hash[hashval];
891 if (p->c.x == c->x && p->c.y == c->y)
899 * @brief Inserts a point into the route graph at the specified coordinates
901 * This will insert a point into the route graph at the coordinates passed in f.
902 * Note that the point is not yet linked to any segments.
904 * @param this The route to insert the point into
905 * @param f The coordinates at which the point should be inserted
906 * @return The point inserted or NULL on failure
908 static struct route_graph_point *
909 route_graph_add_point(struct route_graph *this, struct coord *f)
912 struct route_graph_point *p;
914 p=route_graph_get_point(this,f);
916 hashval=HASHCOORD(f);
918 printf("p (0x%x,0x%x)\n", f->x, f->y);
919 p=g_new(struct route_graph_point,1);
921 printf("%s:Out of memory\n", __FUNCTION__);
924 p->hash_next=this->hash[hashval];
925 this->hash[hashval]=p;
926 p->next=this->route_points;
933 this->route_points=p;
939 * @brief Frees all the memory used for points in the route graph passed
941 * @param this The route graph to delete all points from
944 route_graph_free_points(struct route_graph *this)
946 struct route_graph_point *curr,*next;
947 curr=this->route_points;
953 this->route_points=NULL;
954 memset(this->hash, 0, sizeof(this->hash));
958 * @brief Inserts a new segment into the route graph
960 * This function performs a check if a segment for the item specified already exists, and inserts
961 * a new segment representing this item if it does not.
963 * @param this The route graph to insert the segment into
964 * @param start The graph point which should be connected to the start of this segment
965 * @param end The graph point which should be connected to the end of this segment
966 * @param len The length of this segment
967 * @param item The item that is represented by this segment
968 * @param flags Flags for this segment
969 * @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
972 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
973 struct route_graph_point *end, int len, struct item *item,
974 int flags, int offset)
976 struct route_graph_segment *s;
980 if (item_is_equal(*item, s->item) && (s->offset == offset))
985 s = g_new0(struct route_graph_segment, 1);
987 printf("%s:Out of memory\n", __FUNCTION__);
991 s->start_next=start->start;
994 s->end_next=end->end;
996 dbg_assert(len >= 0);
1001 s->next=this->route_segments;
1002 this->route_segments=s;
1004 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1008 * @brief Gets all the coordinates of an item
1010 * This will get all the coordinates of the item i and return them in c,
1011 * up to max coordinates. Additionally it is possible to limit the coordinates
1012 * returned to all the coordinates of the item between the two coordinates
1015 * @important Make shure that whatever c points to has enough memory allocated
1016 * @important to hold max coordinates!
1018 * @param i The item to get the coordinates of
1019 * @param c Pointer to memory allocated for holding the coordinates
1020 * @param max Maximum number of coordinates to return
1021 * @param start First coordinate to get
1022 * @param end Last coordinate to get
1023 * @return The number of coordinates returned
1025 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1026 struct coord *start, struct coord *end)
1028 struct map_rect *mr;
1032 mr=map_rect_new(i->map, NULL);
1035 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1037 rc = item_coord_get(item, &c1, 1);
1038 while (rc && (c1.x != start->x || c1.y != start->y)) {
1039 rc = item_coord_get(item, &c1, 1);
1041 while (rc && p < max) {
1043 if (c1.x == end->x && c1.y == end->y)
1045 rc = item_coord_get(item, &c1, 1);
1048 map_rect_destroy(mr);
1053 * @brief Returns and removes one segment from a path
1055 * @param path The path to take the segment from
1056 * @param item The item whose segment to remove
1057 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1058 * @return The segment removed
1060 static struct route_path_segment *
1061 route_extract_segment_from_path(struct route_path *path, struct item *item,
1064 struct route_path_segment *sp = NULL, *s;
1067 if (s->offset == offset && item_is_equal(s->item,*item)) {
1072 path->path = s->next;
1080 item_hash_remove(path->path_hash, item);
1085 * @brief Adds a segment and the end of a path
1087 * @param this The path to add the segment to
1088 * @param segment The segment to add
1091 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1095 if (this->path_last)
1096 this->path_last->next=segment;
1097 this->path_last=segment;
1101 * @brief Adds a new item to a path
1103 * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
1104 * if the item passed is segmented - it will create exactly one segment.
1106 * @param this The path to add the item to
1107 * @param item The item to add
1108 * @param len The length of the item
1109 * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
1110 * @param c Pointer to count coordinates of the item.
1111 * @param cound Number of coordinates in c
1112 * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
1113 * @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"
1116 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)
1118 int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
1119 struct route_path_segment *segment;
1121 segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
1122 segment->ncoords=ccount;
1123 segment->direction=dir;
1125 segment->c[idx++]=*first;
1127 for (i = 0 ; i < count ; i++)
1128 segment->c[idx++]=c[i];
1130 for (i = 0 ; i < count ; i++)
1131 segment->c[idx++]=c[count-i-1];
1134 segment->c[idx++]=*last;
1135 segment->length=len;
1137 segment->item=*item;
1138 route_path_add_segment(this, segment);
1142 * @brief Inserts a new item into the path
1144 * This function does almost the same as "route_apth_add_item()", but identifies
1145 * the item to add by a segment from the route graph. Another difference is that it "copies" the
1146 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1147 * be added to the route path, not all segments of the item.
1149 * The function can be sped up by passing an old path already containing this segment in oldpath -
1150 * the segment will then be extracted from this old path. Please note that in this case the direction
1151 * parameter has no effect.
1153 * @param this The path to add the item to
1154 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1155 * @param rgs Segment of the route graph that should be "copied" to the route path
1156 * @param len Length of the item to be added
1157 * @param offset Offset of rgs within the item it represents
1158 * @param dir Order in which to add the coordinates. See route_path_add_item()
1159 * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
1162 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
1163 struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
1165 struct route_path_segment *segment;
1166 int i,ccnt = 0, ret=1;
1167 struct coord ca[2048];
1170 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
1172 segment = route_extract_segment_from_path(oldpath,
1173 &rgs->item, offset);
1180 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1181 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1182 segment->direction=dir;
1184 for (i = 0 ; i < ccnt ; i++)
1185 segment->c[i]=ca[i];
1187 for (i = 0 ; i < ccnt ; i++)
1188 segment->c[i]=ca[ccnt-i-1];
1190 segment->ncoords = ccnt;
1192 /* We check if the route graph segment is part of a roundabout here, because this
1193 * only matters for route graph segments which form parts of the route path */
1194 if (!(rgs->flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier
1195 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1199 segment->item=rgs->item;
1200 segment->offset = offset;
1202 segment->length=len;
1204 item_hash_insert(this->path_hash, &rgs->item, (void *)ccnt);
1206 route_path_add_segment(this, segment);
1212 * @brief Destroys all segments of a route graph
1214 * @param this The graph to destroy all segments from
1217 route_graph_free_segments(struct route_graph *this)
1219 struct route_graph_segment *curr,*next;
1220 curr=this->route_segments;
1226 this->route_segments=NULL;
1230 * @brief Destroys a route graph
1232 * @param this The route graph to be destroyed
1235 route_graph_destroy(struct route_graph *this)
1238 route_graph_build_done(this, 1);
1239 route_graph_free_points(this);
1240 route_graph_free_segments(this);
1246 * @brief Returns the time needed to drive len on item
1248 * This function returns the time needed to drive len meters on
1249 * the item passed in item in tenth of seconds.
1251 * @param speedlist The speedlist that should be used
1252 * @param item The item to be driven on
1253 * @param len The length to drive
1254 * @return The time needed to drive len on item in thenth of senconds
1257 route_time(int *speedlist, struct item *item, int len)
1259 if (item->type < route_item_first || item->type > route_item_last) {
1260 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1263 if (!speedlist[item->type-route_item_first]) {
1264 dbg(0,"street type %d speed is zero\n", item->type);
1268 return len*36/speedlist[item->type-route_item_first];
1272 * @brief Returns the "costs" of driving len on item
1274 * @param speedlist The speedlist that should be used
1275 * @param item The item to be driven on
1276 * @param len The length to drive
1277 * @return The "costs" needed to drive len on item
1280 route_value(int *speedlist, struct item *item, int len)
1284 printf("len=%d\n", len);
1286 dbg_assert(len >= 0);
1287 ret=route_time(speedlist, item, len);
1288 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1293 * @brief Adds an item to the route graph
1295 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1298 * @param this The route graph to add to
1299 * @param item The item to add
1302 route_process_street_graph(struct route_graph *this, struct item *item)
1309 struct route_graph_point *s_pnt,*e_pnt;
1316 if (item_coord_get(item, &l, 1)) {
1317 if (item_attr_get(item, attr_flags, &attr)) {
1319 if (flags & AF_SEGMENTED)
1322 s_pnt=route_graph_add_point(this,&l);
1324 while (item_coord_get(item, &c, 1)) {
1325 len+=transform_distance(map_projection(item->map), &l, &c);
1328 e_pnt=route_graph_add_point(this,&l);
1329 dbg_assert(len >= 0);
1330 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1335 isseg = item_coord_is_node(item);
1336 rc = item_coord_get(item, &c, 1);
1338 len+=transform_distance(map_projection(item->map), &l, &c);
1341 e_pnt=route_graph_add_point(this,&l);
1342 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1344 s_pnt=route_graph_add_point(this,&l);
1349 e_pnt=route_graph_add_point(this,&l);
1350 dbg_assert(len >= 0);
1352 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1358 * @brief Compares the costs of reaching the destination from two points on
1360 * @important Do not pass anything other than route_graph_points in v1 and v2!
1364 * @return The additional costs of v1 compared to v2 (may be negative)
1367 compare(void *v1, void *v2)
1369 struct route_graph_point *p1=v1;
1370 struct route_graph_point *p2=v2;
1373 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1375 return p1->value-p2->value;
1379 * @brief Calculates the routing costs for each point
1381 * This function is the heart of routing. It assigns each point in the route graph a
1382 * cost at which one can reach the destination from this point on. Additionally it assigns
1383 * each point a segment one should follow from this point on to reach the destination at the
1386 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1387 * at this algorithm.
1390 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist, struct callback *cb)
1392 struct route_graph_point *p_min,*end=NULL;
1393 struct route_graph_segment *s;
1394 int min,new,old,val;
1395 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1396 struct street_data *sd=dst->street;
1398 heap = fh_makeheap();
1399 fh_setcmp(heap, compare);
1401 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 */
1402 end=route_graph_get_point(this, &sd->c[0]);
1403 dbg_assert(end != 0);
1404 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1405 end->el=fh_insert(heap, end);
1408 if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1409 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1410 dbg_assert(end != 0);
1411 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1412 end->el=fh_insert(heap, end);
1415 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1417 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1418 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1422 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);
1423 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1425 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1426 val=route_value(speedlist, &s->item, s->len);
1428 val+=val*2*street_route_contained(s->str->segid);
1432 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);
1433 if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1438 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1439 s->end->el=fh_insert(heap, s->end);
1441 printf("el new=%p\n", s->end->el);
1445 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1446 fh_replacedata(heap, s->end->el, s->end);
1454 while (s) { /* Doing the same as above with the segments leading towards our point */
1455 val=route_value(speedlist, &s->item, s->len);
1458 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);
1459 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1460 old=s->start->value;
1461 s->start->value=new;
1463 if (! s->start->el) {
1465 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1466 s->start->el=fh_insert(heap, s->start);
1468 printf("el new=%p\n", s->start->el);
1472 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1473 fh_replacedata(heap, s->start->el, s->start);
1481 fh_deleteheap(heap);
1482 callback_call_0(cb);
1486 * @brief Starts an "offroad" path
1488 * This starts a path that is not located on a street. It creates a new route path
1489 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1491 * @param this Not used
1492 * @param pos The starting position for the new path
1493 * @param dst The destination of the new path
1494 * @param dir Not used
1495 * @return The new path
1497 static struct route_path *
1498 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1500 struct route_path *ret;
1502 ret=g_new0(struct route_path, 1);
1503 ret->path_hash=item_hash_new();
1504 route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1511 * @brief Creates a new "trivial" route
1513 * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1514 * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1516 * @param this The route graph to place the route on
1517 * @param pos The starting position for the new path
1518 * @param dst The destination of the new path
1519 * @param dir Direction of the coordinates to be added
1520 * @return The new path
1522 static struct route_path *
1523 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1525 struct street_data *sd=pos->street;
1526 struct route_path *ret;
1529 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1530 return route_path_new_offroad(this, pos, dst, dir);
1532 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1533 return route_path_new_offroad(this, pos, dst, dir);
1535 ret=g_new0(struct route_path, 1);
1536 ret->path_hash=item_hash_new();
1538 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1540 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);
1542 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);
1544 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1550 * @brief Returns a coordinate at a given distance
1552 * This function returns the coordinate, where the user will be if he
1553 * follows the current route for a certain distance.
1555 * @param this_ The route we're driving upon
1556 * @param dist The distance in meters
1557 * @return The coordinate where the user will be in that distance
1560 route_get_coord_dist(struct route *this_, int dist)
1565 struct route_path_segment *cur;
1567 enum projection pro=route_projection(this_);
1571 if (!this_->path2 || pro == projection_none) {
1572 return this_->pos->c;
1575 ret = this_->pos->c;
1576 cur = this_->path2->path;
1578 if (cur->length < d) {
1581 for (i=0; i < (cur->ncoords-1); i++) {
1583 len = (int)transform_polyline_length(pro, (cur->c + i), 2);
1586 // We interpolate a bit here...
1587 frac = (double)l / len;
1589 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
1590 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
1592 ret.x = (cur->c + i)->x + (frac * dx);
1593 ret.y = (cur->c + i)->y + (frac * dy);
1597 return cur->c[(cur->ncoords-1)];
1602 return this_->dst->c;
1606 * @brief Creates a new route path
1608 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1609 * make shure to run route_graph_flood() after changing the destination before using this function.
1611 * @param this The route graph to create the route from
1612 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1613 * @param pos The starting position of the route
1614 * @param dst The destination of the route
1615 * @param speedlist The speedlist to use
1616 * @return The new route path
1618 static struct route_path *
1619 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1621 struct route_graph_point *start1=NULL,*start2=NULL,*start;
1622 struct route_graph_segment *s=NULL;
1623 struct route_graph_segment *lastseg = NULL;
1628 int time=0,hr,min,sec
1630 unsigned int val1=0xffffffff,val2=0xffffffff;
1631 struct street_data *sd=pos->street;
1632 struct route_path *ret;
1634 if (! pos->street || ! dst->street)
1636 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 */
1637 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1638 return route_path_new_trivial(this, pos, dst, -1);
1640 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1641 return route_path_new_trivial(this, pos, dst, 1);
1644 if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1645 start1=route_graph_get_point(this, &sd->c[0]);
1648 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1649 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1651 if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1652 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1655 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1656 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1658 dbg(1,"val1=%d val2=%d\n", val1, val2);
1660 val1=start1->start->start->value;
1661 val2=start2->end->end->value;
1663 ret=g_new0(struct route_path, 1);
1666 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1667 if (start1 && (val1 < val2)) {
1669 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1673 route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1675 printf("no route found, pos blocked\n");
1679 ret->path_hash=item_hash_new();
1680 while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1683 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1688 if (s->start == start) {
1689 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight))
1693 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight))
1701 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1702 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);
1703 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 */
1704 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1);
1705 } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1706 route_path_add_item(ret, &sd->item, dst->lenpos, NULL, sd->c+dst->pos+1, sd->count-dst->pos-1, &dst->lp, -1);
1708 printf("no route found\n");
1709 route_path_destroy(ret);
1713 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1714 dbg(1, "%d segments\n", segs);
1719 route_graph_build_next_map(struct route_graph *rg)
1722 rg->m=mapset_next(rg->h, 1);
1725 map_rect_destroy(rg->mr);
1726 rg->mr=map_rect_new(rg->m, rg->sel);
1733 route_graph_build_done(struct route_graph *rg, int cancel)
1735 dbg(1,"cancel=%d\n",cancel);
1736 event_remove_idle(rg->idle_ev);
1737 callback_destroy(rg->idle_cb);
1738 map_rect_destroy(rg->mr);
1739 mapset_close(rg->h);
1740 route_free_selection(rg->sel);
1747 callback_call_0(rg->done_cb);
1752 route_graph_build_idle(struct route_graph *rg)
1759 item=map_rect_get_item(rg->mr);
1762 if (!route_graph_build_next_map(rg)) {
1763 route_graph_build_done(rg, 0);
1767 if (item->type >= type_street_0 && item->type <= type_ferry)
1768 route_process_street_graph(rg, item);
1774 * @brief Builds a new route graph from a mapset
1776 * This function builds a new route graph from a map. Please note that this function does not
1777 * add any routing information to the route graph - this has to be done via the route_graph_flood()
1780 * The function does not create a graph covering the whole map, but only covering the rectangle
1781 * between c1 and c2.
1783 * @param ms The mapset to build the route graph from
1784 * @param c1 Corner 1 of the rectangle to use from the map
1785 * @param c2 Corner 2 of the rectangle to use from the map
1786 * @param done_cb The callback which will be called when graph is complete
1787 * @return The new route graph.
1789 static struct route_graph *
1790 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb)
1792 struct route_graph *ret=g_new0(struct route_graph, 1);
1796 ret->sel=route_calc_selection(c1, c2);
1797 ret->h=mapset_open(ms);
1798 ret->done_cb=done_cb;
1800 if (route_graph_build_next_map(ret)) {
1801 ret->idle_cb=callback_new_1(callback_cast(route_graph_build_idle), ret);
1802 ret->idle_ev=event_add_idle(50, ret->idle_cb);
1804 route_graph_build_done(ret, 0);
1810 route_graph_update_done(struct route *this, struct callback *cb)
1812 route_graph_flood(this->graph, this->dst, this->speedlist, cb);
1816 * @brief Updates the route graph
1818 * This updates the route graph after settings in the route have changed. It also
1819 * adds routing information afterwards by calling route_graph_flood().
1821 * @param this The route to update the graph for
1824 route_graph_update(struct route *this, struct callback *cb)
1826 route_graph_destroy(this->graph);
1827 callback_destroy(this->route_graph_done_cb);
1828 this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
1829 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
1830 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c, this->route_graph_done_cb);
1834 * @brief Gets street data for an item
1836 * @param item The item to get the data for
1837 * @return Street data for the item
1839 struct street_data *
1840 street_get_data (struct item *item)
1843 struct street_data *ret = NULL, *ret1;
1845 const int step = 128;
1849 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
1856 c = item_coord_get(item, &ret->c[count], step);
1858 } while (c && c == step);
1860 ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
1865 if (item_attr_get(item, attr_flags, &attr))
1866 ret->flags=attr.u.num;
1874 * @brief Copies street data
1876 * @param orig The street data to copy
1877 * @return The copied street data
1879 struct street_data *
1880 street_data_dup(struct street_data *orig)
1882 struct street_data *ret;
1883 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1886 memcpy(ret, orig, size);
1892 * @brief Frees street data
1894 * @param sd Street data to be freed
1897 street_data_free(struct street_data *sd)
1903 * @brief Finds the nearest street to a given coordinate
1905 * @param ms The mapset to search in for the street
1906 * @param pc The coordinate to find a street nearby
1907 * @return The nearest street
1909 static struct route_info *
1910 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1912 struct route_info *ret=NULL;
1914 struct map_selection *sel;
1915 int dist,mindist=0,pos;
1916 struct mapset_handle *h;
1918 struct map_rect *mr;
1921 struct street_data *sd;
1925 ret=g_new0(struct route_info, 1);
1927 dbg(0,"Out of memory\n");
1933 while ((m=mapset_next(h,1))) {
1936 if (map_projection(m) != pc->pro) {
1937 transform_to_geo(pc->pro, &c, &g);
1938 transform_from_geo(map_projection(m), &g, &c);
1940 sel = route_rect(18, &c, &c, 0, max_dist);
1943 mr=map_rect_new(m, sel);
1945 map_selection_destroy(sel);
1948 while ((item=map_rect_get_item(mr))) {
1949 if (item->type >= type_street_0 && item->type <= type_ferry) {
1950 sd=street_get_data(item);
1953 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1954 if (dist < mindist) {
1957 street_data_free(ret->street);
1963 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1965 street_data_free(sd);
1969 map_selection_destroy(sel);
1970 map_rect_destroy(mr);
1974 if (!ret->street || mindist > max_dist*max_dist) {
1976 street_data_free(ret->street);
1977 dbg(1,"Much too far %d > %d\n", mindist, max_dist);
1987 * @brief Destroys a route_info
1989 * @param info The route info to be destroyed
1992 route_info_free(struct route_info *inf)
1995 street_data_free(inf->street);
2003 * @brief Returns street data for a route info
2005 * @param rinf The route info to return the street data for
2006 * @return Street data for the route info
2008 struct street_data *
2009 route_info_street(struct route_info *rinf)
2011 return rinf->street;
2015 struct route_crossings *
2016 route_crossings_get(struct route *this, struct coord *c)
2018 struct route_point *pnt;
2019 struct route_segment *seg;
2021 struct route_crossings *ret;
2023 pnt=route_graph_get_point(this, c);
2026 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2028 seg=seg->start_next;
2032 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2036 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
2037 ret->count=crossings;
2043 struct map_rect_priv {
2044 struct route_info_handle *ri;
2045 enum attr_type attr_next;
2047 struct map_priv *mpriv;
2050 unsigned int last_coord;
2051 struct route_path_segment *seg,*seg_next;
2052 struct route_graph_point *point;
2053 struct route_graph_segment *rseg;
2055 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
2056 struct route_graph_point_iterator it;
2060 rm_coord_rewind(void *priv_data)
2062 struct map_rect_priv *mr = priv_data;
2067 rm_attr_rewind(void *priv_data)
2069 struct map_rect_priv *mr = priv_data;
2070 mr->attr_next = attr_street_item;
2074 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2076 struct map_rect_priv *mr = priv_data;
2077 struct route_path_segment *seg=mr->seg;
2078 struct route *route=mr->mpriv->route;
2079 if (mr->item.type != type_street_route)
2081 attr->type=attr_type;
2082 switch (attr_type) {
2084 while (mr->attr_next != attr_none) {
2085 if (rm_attr_get(priv_data, mr->attr_next, attr))
2089 case attr_street_item:
2090 mr->attr_next=attr_direction;
2091 if (seg && seg->item.map)
2092 attr->u.item=&seg->item;
2096 case attr_direction:
2097 mr->attr_next=attr_route;
2099 attr->u.num=seg->direction;
2104 mr->attr_next=attr_length;
2105 attr->u.route = mr->mpriv->route;
2109 attr->u.num=seg->length;
2111 attr->u.num=mr->length;
2112 mr->attr_next=attr_time;
2115 mr->attr_next=attr_none;
2117 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
2122 mr->attr_next=attr_none;
2125 mr->attr_next=attr_none;
2126 attr->type=attr_none;
2133 rm_coord_get(void *priv_data, struct coord *c, int count)
2135 struct map_rect_priv *mr = priv_data;
2136 struct route_path_segment *seg = mr->seg;
2138 struct route *r = mr->mpriv->route;
2139 enum projection pro = route_projection(r);
2141 if (pro == projection_none)
2143 if (mr->item.type == type_route_start || mr->item.type == type_route_end) {
2144 if (! count || mr->last_coord)
2147 if (mr->item.type == type_route_start)
2155 for (i=0; i < count; i++) {
2156 if (mr->last_coord >= seg->ncoords)
2158 if (i >= seg->ncoords)
2160 if (pro != projection_mg)
2161 transform_from_to(&seg->c[mr->last_coord++], pro,
2162 &c[i],projection_mg);
2164 c[i] = seg->c[mr->last_coord++];
2167 dbg(1,"return %d\n",rc);
2171 static struct item_methods methods_route_item = {
2179 rp_attr_rewind(void *priv_data)
2181 struct map_rect_priv *mr = priv_data;
2182 mr->attr_next = attr_label;
2186 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2188 struct map_rect_priv *mr = priv_data;
2189 struct route_graph_point *p = mr->point;
2190 struct route_graph_segment *seg = mr->rseg;
2191 switch (attr_type) {
2192 case attr_any: // works only with rg_points for now
2193 if (mr->item.type != type_rg_point)
2195 while (mr->attr_next != attr_none) {
2196 if (rp_attr_get(priv_data, mr->attr_next, attr))
2201 if (mr->item.type != type_rg_point)
2203 attr->type = attr_label;
2206 if (p->value != INT_MAX)
2207 mr->str=g_strdup_printf("%d", p->value);
2209 mr->str=g_strdup("-");
2210 attr->u.str = mr->str;
2211 mr->attr_next=attr_none;
2213 case attr_street_item:
2214 if (mr->item.type != type_rg_segment)
2216 mr->attr_next=attr_none;
2217 if (seg && seg->item.map)
2218 attr->u.item=&seg->item;
2223 if (mr->item.type != type_rg_segment)
2225 mr->attr_next = attr_none;
2227 attr->u.num = seg->flags;
2232 case attr_direction:
2233 // This only works if the map has been opened at a single point, and in that case indicates if the
2234 // segment returned last is connected to this point via its start (1) or its end (-1)
2235 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
2237 if (seg->start == mr->point) {
2239 } else if (seg->end == mr->point) {
2246 if (mr->item.type != type_rg_point)
2248 attr->type = attr_debug;
2251 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2252 attr->u.str = mr->str;
2253 mr->attr_next=attr_none;
2256 mr->attr_next=attr_none;
2257 attr->type=attr_none;
2263 * @brief Returns the coordinates of a route graph item
2265 * @param priv_data The route graph item's private data
2266 * @param c Pointer where to store the coordinates
2267 * @param count How many coordinates to get at a max?
2268 * @return The number of coordinates retrieved
2271 rp_coord_get(void *priv_data, struct coord *c, int count)
2273 struct map_rect_priv *mr = priv_data;
2274 struct route_graph_point *p = mr->point;
2275 struct route_graph_segment *seg = mr->rseg;
2277 struct route *r = mr->mpriv->route;
2278 enum projection pro = route_projection(r);
2280 if (pro == projection_none)
2282 for (i=0; i < count; i++) {
2283 if (mr->item.type == type_rg_point) {
2284 if (mr->last_coord >= 1)
2286 if (pro != projection_mg)
2287 transform_from_to(&p->c, pro,
2288 &c[i],projection_mg);
2292 if (mr->last_coord >= 2)
2295 if (seg->end->seg == seg)
2300 if (pro != projection_mg)
2301 transform_from_to(&seg->end->c, pro,
2302 &c[i],projection_mg);
2306 if (pro != projection_mg)
2307 transform_from_to(&seg->start->c, pro,
2308 &c[i],projection_mg);
2310 c[i] = seg->start->c;
2319 static struct item_methods methods_point_item = {
2327 rp_destroy(struct map_priv *priv)
2333 rm_destroy(struct map_priv *priv)
2338 static struct map_rect_priv *
2339 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2341 struct map_rect_priv * mr;
2343 if (! route_get_pos(priv->route))
2345 if (! route_get_dst(priv->route))
2348 if (! priv->route->path2)
2351 mr=g_new0(struct map_rect_priv, 1);
2353 mr->item.priv_data = mr;
2354 mr->item.type = type_none;
2355 mr->item.meth = &methods_route_item;
2356 if (priv->route->path2)
2357 mr->seg_next=priv->route->path2->path;
2364 * @brief Opens a new map rectangle on the route graph's map
2366 * This function opens a new map rectangle on the route graph's map.
2367 * The "sel" parameter enables you to only search for a single route graph
2368 * point on this map (or exactly: open a map rectangle that only contains
2369 * this one point). To do this, pass here a single map selection, whose
2370 * c_rect has both coordinates set to the same point. Otherwise this parameter
2373 * @param priv The route graph map's private data
2374 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2375 * @return A new map rect's private data
2377 static struct map_rect_priv *
2378 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2380 struct map_rect_priv * mr;
2383 if (! priv->route->graph || ! priv->route->graph->route_points)
2385 mr=g_new0(struct map_rect_priv, 1);
2387 mr->item.priv_data = mr;
2388 mr->item.type = type_rg_point;
2389 mr->item.meth = &methods_point_item;
2391 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)) {
2392 mr->coord_sel = g_malloc(sizeof(struct coord));
2393 *(mr->coord_sel) = sel->u.c_rect.lu;
2400 rm_rect_destroy(struct map_rect_priv *mr)
2404 if (mr->coord_sel) {
2405 g_free(mr->coord_sel);
2411 static struct item *
2412 rp_get_item(struct map_rect_priv *mr)
2414 struct route *r = mr->mpriv->route;
2415 struct route_graph_point *p = mr->point;
2416 struct route_graph_segment *seg = mr->rseg;
2418 if (mr->item.type == type_rg_point) {
2419 if (mr->coord_sel) {
2420 // We are supposed to return only the point at one specified coordinate...
2422 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2423 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2426 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2427 mr->point = NULL; // This indicates that no point has been found
2429 mr->it = rp_iterator_new(p);
2436 p = r->graph->route_points;
2443 rm_coord_rewind(mr);
2447 mr->item.type = type_rg_segment;
2450 if (mr->coord_sel) {
2451 if (!mr->point) { // This means that no point has been found
2454 seg = rp_iterator_next(&(mr->it));
2457 seg=r->graph->route_segments;
2465 rm_coord_rewind(mr);
2473 static struct item *
2474 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2476 struct item *ret=NULL;
2478 ret=rp_get_item(mr);
2483 static struct item *
2484 rm_get_item(struct map_rect_priv *mr)
2486 dbg(1,"enter\n", mr->pos);
2488 switch (mr->item.type) {
2490 mr->item.type=type_route_start;
2491 if (mr->mpriv->route->pos)
2494 mr->item.type=type_street_route;
2495 mr->seg=mr->seg_next;
2497 mr->seg_next=mr->seg->next;
2500 mr->item.type=type_route_end;
2501 if (mr->mpriv->route->dst)
2503 case type_route_end:
2512 static struct item *
2513 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2515 struct item *ret=NULL;
2517 ret=rm_get_item(mr);
2521 static struct map_methods route_meth = {
2534 static struct map_methods route_graph_meth = {
2548 route_toggle_routegraph_display(struct route *route)
2550 if (route->flags & RF_SHOWGRAPH) {
2551 route->flags &= ~RF_SHOWGRAPH;
2553 route->flags |= RF_SHOWGRAPH;
2557 static struct map_priv *
2558 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2560 struct map_priv *ret;
2561 struct attr *route_attr;
2563 route_attr=attr_search(attrs, NULL, attr_route);
2566 ret=g_new0(struct map_priv, 1);
2568 *meth=route_graph_meth;
2571 ret->route=route_attr->u.route;
2576 static struct map_priv *
2577 route_map_new(struct map_methods *meth, struct attr **attrs)
2579 return route_map_new_helper(meth, attrs, 0);
2582 static struct map_priv *
2583 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2585 return route_map_new_helper(meth, attrs, 1);
2589 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2592 *map=map_new(NULL, (struct attr*[]){
2593 &(struct attr){attr_type,{type}},
2594 &(struct attr){attr_route,.u.route=this_},
2595 &(struct attr){attr_data,{""}},
2596 &(struct attr){attr_description,{description}},
2603 * @brief Returns a new map containing the route path
2605 * This function returns a new map containing the route path.
2607 * @important Do not map_destroy() this!
2609 * @param this_ The route to get the map of
2610 * @return A new map containing the route path
2613 route_get_map(struct route *this_)
2615 return route_get_map_helper(this_, &this_->map, "route","Route");
2620 * @brief Returns a new map containing the route graph
2622 * This function returns a new map containing the route graph.
2624 * @important Do not map_destroy() this!
2626 * @param this_ The route to get the map of
2627 * @return A new map containing the route graph
2630 route_get_graph_map(struct route *this_)
2632 return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2636 route_set_projection(struct route *this_, enum projection pro)
2641 route_add_callback(struct route *this_, struct callback *cb)
2643 callback_list_add(this_->cbl, cb);
2647 route_remove_callback(struct route *this_, struct callback *cb)
2649 callback_list_remove(this_->cbl, cb);
2656 plugin_register_map_type("route", route_map_new);
2657 plugin_register_map_type("route_graph", route_graph_map_new);