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 street = route->pos ? route->pos->street : route->dst->street;
250 return map_projection(street->item.map);
254 * @brief Creates a new graph point iterator
256 * This function creates a new route graph point iterator, that can be used to
257 * iterate through all segments connected to the point.
259 * @param p The route graph point to create the iterator from
260 * @return A new iterator.
262 static struct route_graph_point_iterator
263 rp_iterator_new(struct route_graph_point *p)
265 struct route_graph_point_iterator it;
280 * @brief Gets the next segment connected to a route graph point from an iterator
282 * @param it The route graph point iterator to get the segment from
283 * @return The next segment or NULL if there are no more segments
285 static struct route_graph_segment
286 *rp_iterator_next(struct route_graph_point_iterator *it)
288 struct route_graph_segment *ret;
296 if (ret->start_next) {
297 it->next = ret->start_next;
299 it->next = it->p->end;
303 it->next = ret->end_next;
310 * @brief Checks if the last segment returned from a route_graph_point_iterator comes from the end
312 * @param it The route graph point iterator to be checked
313 * @return 1 if the last segment returned comes from the end of the route graph point, 0 otherwise
316 rp_iterator_end(struct route_graph_point_iterator *it) {
317 if (it->end && (it->next != it->p->end)) {
325 * @brief Destroys a route_path
327 * @param this The route_path to be destroyed
330 route_path_destroy(struct route_path *this)
332 struct route_path_segment *c,*n;
335 if (this->path_hash) {
336 item_hash_destroy(this->path_hash);
337 this->path_hash=NULL;
349 * @brief Creates a completely new route structure
351 * @param attrs Not used
352 * @return The newly created route
355 route_new(struct attr *parent, struct attr **attrs)
357 struct route *this=g_new0(struct route, 1);
358 struct attr dest_attr;
360 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
361 this->destination_distance = dest_attr.u.num;
363 this->destination_distance = 50; // Default value
365 this->cbl=callback_list_new();
371 * @brief Checks if a segment is part of a roundabout
373 * This function checks if a segment is part of a roundabout.
375 * @param seg The segment to be checked
376 * @param level How deep to scan the route graph
377 * @param direction Set this to 1 if we're entering the segment through its end, to 0 otherwise
378 * @param origin Used internally, set to NULL
379 * @return 1 If a roundabout was detected, 0 otherwise
382 route_check_roundabout(struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
384 struct route_graph_point_iterator it,it2;
385 struct route_graph_segment *cur;
391 if (!direction && !(seg->flags & AF_ONEWAY)) {
394 if (direction && !(seg->flags & AF_ONEWAYREV)) {
403 it = rp_iterator_new(seg->end);
405 it = rp_iterator_new(seg->start);
409 while ((cur = rp_iterator_next(&it2)))
414 cur = rp_iterator_next(&it);
417 cur = rp_iterator_next(&it);
422 seg->flags |= AF_ROUNDABOUT;
426 if (route_check_roundabout(cur, (level-1), rp_iterator_end(&it), origin)) {
427 seg->flags |= AF_ROUNDABOUT;
431 cur = rp_iterator_next(&it);
438 * @brief Sets the mapset of the route passwd
440 * @param this The route to set the mapset for
441 * @param ms The mapset to set for this route
444 route_set_mapset(struct route *this, struct mapset *ms)
450 * @brief Returns the mapset of the route passed
452 * @param this The route to get the mapset of
453 * @return The mapset of the route passed
456 route_get_mapset(struct route *this)
462 * @brief Returns the current position within the route passed
464 * @param this The route to get the position for
465 * @return The position within the route passed
468 route_get_pos(struct route *this)
474 * @brief Returns the destination of the route passed
476 * @param this The route to get the destination for
477 * @return The destination of the route passed
480 route_get_dst(struct route *this)
486 * @brief Returns the speedlist of the route passed
488 * @param this The route to get the speedlist for
489 * @return The speedlist of the route passed
492 route_get_speedlist(struct route *this)
494 return this->speedlist;
498 * @brief Checks if the path is calculated for the route passed
500 * @param this The route to check
501 * @return True if the path is calculated, false if not
504 route_get_path_set(struct route *this)
506 return this->path2 != NULL;
510 * @brief Sets the driving speed for a certain itemtype
512 * @param this The route to set the speed for
513 * @param type The itemtype to set the speed for
514 * @param value The speed that should be set
515 * @return True on success, false if the itemtype does not exist
518 route_set_speed(struct route *this, enum item_type type, int value)
520 if (type < route_item_first || type > route_item_last) {
521 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
524 this->speedlist[type-route_item_first]=value;
529 * @brief Checks if the route passed contains a certain item within the route path
531 * This function checks if a certain items exists in the path that navit will guide
532 * the user to his destination. It does *not* check if this item exists in the route
535 * @param this The route to check for this item
536 * @param item The item to search for
537 * @return True if the item was found, false if the item was not found or the route was not calculated
540 route_contains(struct route *this, struct item *item)
542 if (! this->path2 || !this->path2->path_hash)
544 return (int)item_hash_lookup(this->path2->path_hash, item);
548 * @brief Checks if the current position in a route is a certain item
550 * @param this The route to check for this item
551 * @param item The item to search for
552 * @return True if the current position is this item, false otherwise
555 route_pos_contains(struct route *this, struct item *item)
557 if (! this->pos || !this->pos->street)
559 return item_is_equal(this->pos->street->item, *item);
563 * @brief Checks if a route has reached its destination
565 * @param this The route to be checked
566 * @return True if the destination is "reached", false otherwise.
569 route_destination_reached(struct route *this)
571 struct street_data *sd = NULL;
576 sd = this->pos->street;
582 if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
586 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
589 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
593 if (transform_distance(route_projection(this), &this->pos->c, &this->dst->lp) > this->destination_distance) {
601 route_path_update_done(struct route *this, int new_graph)
603 struct route_path *oldpath=this->path2;
606 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
607 route_path_destroy(oldpath);
612 val=2+!this->path2->updated;
615 callback_list_call_attr_1(this->cbl, attr_route, (void *)val);
619 * @brief Updates the route graph and the route path if something changed with the route
621 * This will update the route graph and the route path of the route if some of the
622 * route's settings (destination, position) have changed.
624 * @attention For this to work the route graph has to be destroyed if the route's
625 * @attention destination is changed somewhere!
627 * @param this The route to update
630 route_path_update(struct route *this, int cancel)
632 dbg(1,"enter %d\n", cancel);
633 if (! this->pos || ! this->dst) {
635 route_path_destroy(this->path2);
640 route_graph_destroy(this->graph);
643 /* the graph is destroyed when setting the destination */
645 if (this->graph->busy) {
646 dbg(1,"busy building graph\n");
649 // we can try to update
650 dbg(1,"try update\n");
651 route_path_update_done(this, 0);
653 route_path_destroy(this->path2);
656 if (!this->graph || !this->path2) {
657 dbg(1,"rebuild graph\n");
658 if (! this->route_graph_flood_done_cb)
659 this->route_graph_flood_done_cb=callback_new_2(callback_cast(route_path_update_done), this, 1);
660 dbg(1,"route_graph_update\n");
661 route_graph_update(this, this->route_graph_flood_done_cb);
666 * @brief This will calculate all the distances stored in a route_info
668 * @param ri The route_info to calculate the distances for
669 * @param pro The projection used for this route
672 route_info_distances(struct route_info *ri, enum projection pro)
675 struct street_data *sd=ri->street;
676 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
677 ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
678 ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
679 ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
683 * @brief This sets the current position of the route passed
685 * This will set the current position of the route passed to the street that is nearest to the
686 * passed coordinates. It also automatically updates the route.
688 * @param this The route to set the position of
689 * @param pos Coordinates to set as position
692 route_set_position(struct route *this, struct pcoord *pos)
695 route_info_free(this->pos);
697 this->pos=route_find_nearest_street(this->ms, pos);
698 dbg(1,"this->pos=%p\n", this->pos);
701 route_info_distances(this->pos, pos->pro);
702 route_path_update(this, 0);
706 * @brief Sets a route's current position based on coordinates from tracking
708 * @param this The route to set the current position of
709 * @param tracking The tracking to get the coordinates from
712 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
715 struct route_info *ret;
716 struct street_data *sd;
719 c=tracking_get_pos(tracking);
720 ret=g_new0(struct route_info, 1);
722 printf("%s:Out of memory\n", __FUNCTION__);
726 route_info_free(this->pos);
732 ret->pos=tracking_get_segment_pos(tracking);
733 sd=tracking_get_street_data(tracking);
735 ret->street=street_data_dup(sd);
736 route_info_distances(ret, c->pro);
738 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);
739 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);
742 route_path_update(this, 0);
746 /* Used for debuging of route_rect, what routing sees */
747 struct map_selection *route_selection;
750 * @brief Returns a single map selection
752 struct map_selection *
753 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
755 int dx,dy,sx=1,sy=1,d,m;
756 struct map_selection *sel=g_new(struct map_selection, 1);
758 printf("%s:Out of memory\n", __FUNCTION__);
762 sel->range.min=route_item_first;
763 sel->range.max=route_item_last;
764 dbg(1,"%p %p\n", c1, c2);
769 sel->u.c_rect.lu.x=c1->x;
770 sel->u.c_rect.rl.x=c2->x;
772 sel->u.c_rect.lu.x=c2->x;
773 sel->u.c_rect.rl.x=c1->x;
777 sel->u.c_rect.lu.y=c2->y;
778 sel->u.c_rect.rl.y=c1->y;
780 sel->u.c_rect.lu.y=c1->y;
781 sel->u.c_rect.rl.y=c2->y;
788 sel->u.c_rect.lu.x-=m;
789 sel->u.c_rect.rl.x+=m;
790 sel->u.c_rect.lu.y+=m;
791 sel->u.c_rect.rl.y-=m;
797 * @brief Returns a list of map selections useable to create a route graph
799 * Returns a list of map selections useable to get a map rect from which items can be
800 * retrieved to build a route graph. The selections are a rectangle with
801 * c1 and c2 as two corners.
803 * @param c1 Corner 1 of the rectangle
804 * @param c2 Corder 2 of the rectangle
806 static struct map_selection *
807 route_calc_selection(struct coord *c1, struct coord *c2)
809 struct map_selection *ret,*sel;
810 sel=route_rect(4, c1, c2, 25, 0);
812 sel->next=route_rect(8, c1, c1, 0, 40000);
814 sel->next=route_rect(18, c1, c1, 0, 10000);
816 sel->next=route_rect(8, c2, c2, 0, 40000);
818 sel->next=route_rect(18, c2, c2, 0, 10000);
819 /* route_selection=ret; */
824 * @brief Destroys a list of map selections
826 * @param sel Start of the list to be destroyed
829 route_free_selection(struct map_selection *sel)
831 struct map_selection *next;
841 * @brief Sets the destination of a route
843 * This sets the destination of a route to the street nearest to the coordinates passed
844 * and updates the route.
846 * @param this The route to set the destination for
847 * @param dst Coordinates to set as destination
850 route_set_destination(struct route *this, struct pcoord *dst)
854 route_info_free(this->dst);
857 this->dst=route_find_nearest_street(this->ms, dst);
859 route_info_distances(this->dst, dst->pro);
861 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
862 profile(1,"find_nearest_street");
864 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
865 route_graph_destroy(this->graph);
867 route_path_update(this, 1);
872 * @brief Gets the route_graph_point with the specified coordinates
874 * @param this The route in which to search
875 * @param c Coordinates to search for
876 * @return The point at the specified coordinates or NULL if not found
878 static struct route_graph_point *
879 route_graph_get_point(struct route_graph *this, struct coord *c)
881 struct route_graph_point *p;
882 int hashval=HASHCOORD(c);
883 p=this->hash[hashval];
885 if (p->c.x == c->x && p->c.y == c->y)
893 * @brief Inserts a point into the route graph at the specified coordinates
895 * This will insert a point into the route graph at the coordinates passed in f.
896 * Note that the point is not yet linked to any segments.
898 * @param this The route to insert the point into
899 * @param f The coordinates at which the point should be inserted
900 * @return The point inserted or NULL on failure
902 static struct route_graph_point *
903 route_graph_add_point(struct route_graph *this, struct coord *f)
906 struct route_graph_point *p;
908 p=route_graph_get_point(this,f);
910 hashval=HASHCOORD(f);
912 printf("p (0x%x,0x%x)\n", f->x, f->y);
913 p=g_new(struct route_graph_point,1);
915 printf("%s:Out of memory\n", __FUNCTION__);
918 p->hash_next=this->hash[hashval];
919 this->hash[hashval]=p;
920 p->next=this->route_points;
927 this->route_points=p;
933 * @brief Frees all the memory used for points in the route graph passed
935 * @param this The route graph to delete all points from
938 route_graph_free_points(struct route_graph *this)
940 struct route_graph_point *curr,*next;
941 curr=this->route_points;
947 this->route_points=NULL;
948 memset(this->hash, 0, sizeof(this->hash));
952 * @brief Inserts a new segment into the route graph
954 * This function performs a check if a segment for the item specified already exists, and inserts
955 * a new segment representing this item if it does not.
957 * @param this The route graph to insert the segment into
958 * @param start The graph point which should be connected to the start of this segment
959 * @param end The graph point which should be connected to the end of this segment
960 * @param len The length of this segment
961 * @param item The item that is represented by this segment
962 * @param flags Flags for this segment
963 * @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
966 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
967 struct route_graph_point *end, int len, struct item *item,
968 int flags, int offset)
970 struct route_graph_segment *s;
974 if (item_is_equal(*item, s->item) && (s->offset == offset))
979 s = g_new0(struct route_graph_segment, 1);
981 printf("%s:Out of memory\n", __FUNCTION__);
985 s->start_next=start->start;
988 s->end_next=end->end;
990 dbg_assert(len >= 0);
995 s->next=this->route_segments;
996 this->route_segments=s;
998 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
1002 * @brief Gets all the coordinates of an item
1004 * This will get all the coordinates of the item i and return them in c,
1005 * up to max coordinates. Additionally it is possible to limit the coordinates
1006 * returned to all the coordinates of the item between the two coordinates
1009 * @important Make shure that whatever c points to has enough memory allocated
1010 * @important to hold max coordinates!
1012 * @param i The item to get the coordinates of
1013 * @param c Pointer to memory allocated for holding the coordinates
1014 * @param max Maximum number of coordinates to return
1015 * @param start First coordinate to get
1016 * @param end Last coordinate to get
1017 * @return The number of coordinates returned
1019 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
1020 struct coord *start, struct coord *end)
1022 struct map_rect *mr;
1026 mr=map_rect_new(i->map, NULL);
1029 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
1031 rc = item_coord_get(item, &c1, 1);
1032 while (rc && (c1.x != start->x || c1.y != start->y)) {
1033 rc = item_coord_get(item, &c1, 1);
1035 while (rc && p < max) {
1037 if (c1.x == end->x && c1.y == end->y)
1039 rc = item_coord_get(item, &c1, 1);
1042 map_rect_destroy(mr);
1047 * @brief Returns and removes one segment from a path
1049 * @param path The path to take the segment from
1050 * @param item The item whose segment to remove
1051 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
1052 * @return The segment removed
1054 static struct route_path_segment *
1055 route_extract_segment_from_path(struct route_path *path, struct item *item,
1058 struct route_path_segment *sp = NULL, *s;
1061 if (s->offset == offset && item_is_equal(s->item,*item)) {
1066 path->path = s->next;
1074 item_hash_remove(path->path_hash, item);
1079 * @brief Adds a segment and the end of a path
1081 * @param this The path to add the segment to
1082 * @param segment The segment to add
1085 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
1089 if (this->path_last)
1090 this->path_last->next=segment;
1091 this->path_last=segment;
1095 * @brief Adds a new item to a path
1097 * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
1098 * if the item passed is segmented - it will create exactly one segment.
1100 * @param this The path to add the item to
1101 * @param item The item to add
1102 * @param len The length of the item
1103 * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
1104 * @param c Pointer to count coordinates of the item.
1105 * @param cound Number of coordinates in c
1106 * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
1107 * @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"
1110 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)
1112 int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
1113 struct route_path_segment *segment;
1115 segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
1116 segment->ncoords=ccount;
1117 segment->direction=dir;
1119 segment->c[idx++]=*first;
1121 for (i = 0 ; i < count ; i++)
1122 segment->c[idx++]=c[i];
1124 for (i = 0 ; i < count ; i++)
1125 segment->c[idx++]=c[count-i-1];
1128 segment->c[idx++]=*last;
1129 segment->length=len;
1131 segment->item=*item;
1132 route_path_add_segment(this, segment);
1136 * @brief Inserts a new item into the path
1138 * This function does almost the same as "route_apth_add_item()", but identifies
1139 * the item to add by a segment from the route graph. Another difference is that it "copies" the
1140 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1141 * be added to the route path, not all segments of the item.
1143 * The function can be sped up by passing an old path already containing this segment in oldpath -
1144 * the segment will then be extracted from this old path. Please note that in this case the direction
1145 * parameter has no effect.
1147 * @param this The path to add the item to
1148 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1149 * @param rgs Segment of the route graph that should be "copied" to the route path
1150 * @param len Length of the item to be added
1151 * @param offset Offset of rgs within the item it represents
1152 * @param dir Order in which to add the coordinates. See route_path_add_item()
1153 * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
1156 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
1157 struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
1159 struct route_path_segment *segment;
1160 int i,ccnt = 0, ret=1;
1161 struct coord ca[2048];
1164 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
1166 segment = route_extract_segment_from_path(oldpath,
1167 &rgs->item, offset);
1174 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1175 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1176 segment->direction=dir;
1178 for (i = 0 ; i < ccnt ; i++)
1179 segment->c[i]=ca[i];
1181 for (i = 0 ; i < ccnt ; i++)
1182 segment->c[i]=ca[ccnt-i-1];
1184 segment->ncoords = ccnt;
1186 /* We check if the route graph segment is part of a roundabout here, because this
1187 * only matters for route graph segments which form parts of the route path */
1188 if (!(rgs->flags & AF_ROUNDABOUT)) { // We identified this roundabout earlier
1189 route_check_roundabout(rgs, 13, (dir < 1), NULL);
1193 segment->item=rgs->item;
1194 segment->offset = offset;
1196 segment->length=len;
1198 item_hash_insert(this->path_hash, &rgs->item, (void *)ccnt);
1200 route_path_add_segment(this, segment);
1206 * @brief Destroys all segments of a route graph
1208 * @param this The graph to destroy all segments from
1211 route_graph_free_segments(struct route_graph *this)
1213 struct route_graph_segment *curr,*next;
1214 curr=this->route_segments;
1220 this->route_segments=NULL;
1224 * @brief Destroys a route graph
1226 * @param this The route graph to be destroyed
1229 route_graph_destroy(struct route_graph *this)
1232 route_graph_build_done(this, 1);
1233 route_graph_free_points(this);
1234 route_graph_free_segments(this);
1240 * @brief Returns the time needed to drive len on item
1242 * This function returns the time needed to drive len meters on
1243 * the item passed in item in tenth of seconds.
1245 * @param speedlist The speedlist that should be used
1246 * @param item The item to be driven on
1247 * @param len The length to drive
1248 * @return The time needed to drive len on item in thenth of senconds
1251 route_time(int *speedlist, struct item *item, int len)
1253 if (item->type < route_item_first || item->type > route_item_last) {
1254 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1257 if (!speedlist[item->type-route_item_first]) {
1258 dbg(0,"street type %d speed is zero\n", item->type);
1262 return len*36/speedlist[item->type-route_item_first];
1266 * @brief Returns the "costs" of driving len on item
1268 * @param speedlist The speedlist that should be used
1269 * @param item The item to be driven on
1270 * @param len The length to drive
1271 * @return The "costs" needed to drive len on item
1274 route_value(int *speedlist, struct item *item, int len)
1278 printf("len=%d\n", len);
1280 dbg_assert(len >= 0);
1281 ret=route_time(speedlist, item, len);
1282 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1287 * @brief Adds an item to the route graph
1289 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1292 * @param this The route graph to add to
1293 * @param item The item to add
1296 route_process_street_graph(struct route_graph *this, struct item *item)
1303 struct route_graph_point *s_pnt,*e_pnt;
1310 if (item_coord_get(item, &l, 1)) {
1311 if (item_attr_get(item, attr_flags, &attr)) {
1313 if (flags & AF_SEGMENTED)
1316 s_pnt=route_graph_add_point(this,&l);
1318 while (item_coord_get(item, &c, 1)) {
1319 len+=transform_distance(map_projection(item->map), &l, &c);
1322 e_pnt=route_graph_add_point(this,&l);
1323 dbg_assert(len >= 0);
1324 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1329 isseg = item_coord_is_node(item);
1330 rc = item_coord_get(item, &c, 1);
1332 len+=transform_distance(map_projection(item->map), &l, &c);
1335 e_pnt=route_graph_add_point(this,&l);
1336 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1338 s_pnt=route_graph_add_point(this,&l);
1343 e_pnt=route_graph_add_point(this,&l);
1344 dbg_assert(len >= 0);
1346 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1352 * @brief Compares the costs of reaching the destination from two points on
1354 * @important Do not pass anything other than route_graph_points in v1 and v2!
1358 * @return The additional costs of v1 compared to v2 (may be negative)
1361 compare(void *v1, void *v2)
1363 struct route_graph_point *p1=v1;
1364 struct route_graph_point *p2=v2;
1367 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1369 return p1->value-p2->value;
1373 * @brief Calculates the routing costs for each point
1375 * This function is the heart of routing. It assigns each point in the route graph a
1376 * cost at which one can reach the destination from this point on. Additionally it assigns
1377 * each point a segment one should follow from this point on to reach the destination at the
1380 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1381 * at this algorithm.
1384 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist, struct callback *cb)
1386 struct route_graph_point *p_min,*end=NULL;
1387 struct route_graph_segment *s;
1388 int min,new,old,val;
1389 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1390 struct street_data *sd=dst->street;
1392 heap = fh_makeheap();
1393 fh_setcmp(heap, compare);
1395 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 */
1396 end=route_graph_get_point(this, &sd->c[0]);
1397 dbg_assert(end != 0);
1398 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1399 end->el=fh_insert(heap, end);
1402 if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1403 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1404 dbg_assert(end != 0);
1405 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1406 end->el=fh_insert(heap, end);
1409 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1411 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1412 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1416 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);
1417 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1419 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1420 val=route_value(speedlist, &s->item, s->len);
1422 val+=val*2*street_route_contained(s->str->segid);
1426 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);
1427 if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1432 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1433 s->end->el=fh_insert(heap, s->end);
1435 printf("el new=%p\n", s->end->el);
1439 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1440 fh_replacedata(heap, s->end->el, s->end);
1448 while (s) { /* Doing the same as above with the segments leading towards our point */
1449 val=route_value(speedlist, &s->item, s->len);
1452 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);
1453 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1454 old=s->start->value;
1455 s->start->value=new;
1457 if (! s->start->el) {
1459 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1460 s->start->el=fh_insert(heap, s->start);
1462 printf("el new=%p\n", s->start->el);
1466 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1467 fh_replacedata(heap, s->start->el, s->start);
1475 fh_deleteheap(heap);
1476 callback_call_0(cb);
1480 * @brief Starts an "offroad" path
1482 * This starts a path that is not located on a street. It creates a new route path
1483 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1485 * @param this Not used
1486 * @param pos The starting position for the new path
1487 * @param dst The destination of the new path
1488 * @param dir Not used
1489 * @return The new path
1491 static struct route_path *
1492 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1494 struct route_path *ret;
1496 ret=g_new0(struct route_path, 1);
1497 ret->path_hash=item_hash_new();
1498 route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1505 * @brief Creates a new "trivial" route
1507 * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1508 * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1510 * @param this The route graph to place the route on
1511 * @param pos The starting position for the new path
1512 * @param dst The destination of the new path
1513 * @param dir Direction of the coordinates to be added
1514 * @return The new path
1516 static struct route_path *
1517 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1519 struct street_data *sd=pos->street;
1520 struct route_path *ret;
1523 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1524 return route_path_new_offroad(this, pos, dst, dir);
1526 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1527 return route_path_new_offroad(this, pos, dst, dir);
1529 ret=g_new0(struct route_path, 1);
1530 ret->path_hash=item_hash_new();
1532 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1534 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);
1536 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);
1538 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1544 * @brief Returns a coordinate at a given distance
1546 * This function returns the coordinate, where the user will be if he
1547 * follows the current route for a certain distance.
1549 * @param this_ The route we're driving upon
1550 * @param dist The distance in meters
1551 * @return The coordinate where the user will be in that distance
1554 route_get_coord_dist(struct route *this_, int dist)
1559 struct route_path_segment *cur;
1564 if (!this_->path2) {
1565 return this_->pos->c;
1568 ret = this_->pos->c;
1569 cur = this_->path2->path;
1571 if (cur->length < d) {
1574 for (i=0; i < (cur->ncoords-1); i++) {
1576 len = (int)transform_polyline_length(route_projection(this_), (cur->c + i), 2);
1579 // We interpolate a bit here...
1580 frac = (double)l / len;
1582 dx = (cur->c + i + 1)->x - (cur->c + i)->x;
1583 dy = (cur->c + i + 1)->y - (cur->c + i)->y;
1585 ret.x = (cur->c + i)->x + (frac * dx);
1586 ret.y = (cur->c + i)->y + (frac * dy);
1590 return cur->c[(cur->ncoords-1)];
1595 return this_->dst->c;
1599 * @brief Creates a new route path
1601 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1602 * make shure to run route_graph_flood() after changing the destination before using this function.
1604 * @param this The route graph to create the route from
1605 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1606 * @param pos The starting position of the route
1607 * @param dst The destination of the route
1608 * @param speedlist The speedlist to use
1609 * @return The new route path
1611 static struct route_path *
1612 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1614 struct route_graph_point *start1=NULL,*start2=NULL,*start;
1615 struct route_graph_segment *s=NULL;
1616 struct route_graph_segment *lastseg = NULL;
1621 int time=0,hr,min,sec
1623 unsigned int val1=0xffffffff,val2=0xffffffff;
1624 struct street_data *sd=pos->street;
1625 struct route_path *ret;
1627 if (! pos->street || ! dst->street)
1629 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 */
1630 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1631 return route_path_new_trivial(this, pos, dst, -1);
1633 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1634 return route_path_new_trivial(this, pos, dst, 1);
1637 if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1638 start1=route_graph_get_point(this, &sd->c[0]);
1641 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1642 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1644 if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1645 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1648 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1649 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1651 dbg(1,"val1=%d val2=%d\n", val1, val2);
1653 val1=start1->start->start->value;
1654 val2=start2->end->end->value;
1656 ret=g_new0(struct route_path, 1);
1659 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1660 if (start1 && (val1 < val2)) {
1662 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1666 route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1668 printf("no route found, pos blocked\n");
1672 ret->path_hash=item_hash_new();
1673 while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1676 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1681 if (s->start == start) {
1682 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight))
1686 if (!route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight))
1694 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1695 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);
1696 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 */
1697 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1);
1698 } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1699 route_path_add_item(ret, &sd->item, dst->lenpos, NULL, sd->c+dst->pos+1, sd->count-dst->pos-1, &dst->lp, -1);
1701 printf("no route found\n");
1702 route_path_destroy(ret);
1706 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1707 dbg(1, "%d segments\n", segs);
1712 route_graph_build_next_map(struct route_graph *rg)
1715 rg->m=mapset_next(rg->h, 1);
1718 map_rect_destroy(rg->mr);
1719 rg->mr=map_rect_new(rg->m, rg->sel);
1726 route_graph_build_done(struct route_graph *rg, int cancel)
1728 dbg(1,"cancel=%d\n",cancel);
1729 event_remove_idle(rg->idle_ev);
1730 callback_destroy(rg->idle_cb);
1731 map_rect_destroy(rg->mr);
1732 mapset_close(rg->h);
1733 route_free_selection(rg->sel);
1740 callback_call_0(rg->done_cb);
1745 route_graph_build_idle(struct route_graph *rg)
1752 item=map_rect_get_item(rg->mr);
1755 if (!route_graph_build_next_map(rg)) {
1756 route_graph_build_done(rg, 0);
1760 if (item->type >= type_street_0 && item->type <= type_ferry)
1761 route_process_street_graph(rg, item);
1767 * @brief Builds a new route graph from a mapset
1769 * This function builds a new route graph from a map. Please note that this function does not
1770 * add any routing information to the route graph - this has to be done via the route_graph_flood()
1773 * The function does not create a graph covering the whole map, but only covering the rectangle
1774 * between c1 and c2.
1776 * @param ms The mapset to build the route graph from
1777 * @param c1 Corner 1 of the rectangle to use from the map
1778 * @param c2 Corner 2 of the rectangle to use from the map
1779 * @param done_cb The callback which will be called when graph is complete
1780 * @return The new route graph.
1782 static struct route_graph *
1783 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb)
1785 struct route_graph *ret=g_new0(struct route_graph, 1);
1789 ret->sel=route_calc_selection(c1, c2);
1790 ret->h=mapset_open(ms);
1791 ret->done_cb=done_cb;
1793 if (route_graph_build_next_map(ret)) {
1794 ret->idle_cb=callback_new_1(callback_cast(route_graph_build_idle), ret);
1795 ret->idle_ev=event_add_idle(50, ret->idle_cb);
1797 route_graph_build_done(ret, 0);
1803 route_graph_update_done(struct route *this, struct callback *cb)
1805 route_graph_flood(this->graph, this->dst, this->speedlist, cb);
1809 * @brief Updates the route graph
1811 * This updates the route graph after settings in the route have changed. It also
1812 * adds routing information afterwards by calling route_graph_flood().
1814 * @param this The route to update the graph for
1817 route_graph_update(struct route *this, struct callback *cb)
1819 route_graph_destroy(this->graph);
1820 callback_destroy(this->route_graph_done_cb);
1821 this->route_graph_done_cb=callback_new_2(callback_cast(route_graph_update_done), this, cb);
1822 callback_list_call_attr_1(this->cbl, attr_route, (void *)0);
1823 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c, this->route_graph_done_cb);
1827 * @brief Gets street data for an item
1829 * @param item The item to get the data for
1830 * @return Street data for the item
1832 struct street_data *
1833 street_get_data (struct item *item)
1836 struct street_data *ret = NULL, *ret1;
1838 const int step = 128;
1842 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
1849 c = item_coord_get(item, &ret->c[count], step);
1851 } while (c && c == step);
1853 ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
1858 if (item_attr_get(item, attr_flags, &attr))
1859 ret->flags=attr.u.num;
1867 * @brief Copies street data
1869 * @param orig The street data to copy
1870 * @return The copied street data
1872 struct street_data *
1873 street_data_dup(struct street_data *orig)
1875 struct street_data *ret;
1876 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1879 memcpy(ret, orig, size);
1885 * @brief Frees street data
1887 * @param sd Street data to be freed
1890 street_data_free(struct street_data *sd)
1896 * @brief Finds the nearest street to a given coordinate
1898 * @param ms The mapset to search in for the street
1899 * @param pc The coordinate to find a street nearby
1900 * @return The nearest street
1902 static struct route_info *
1903 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1905 struct route_info *ret=NULL;
1907 struct map_selection *sel;
1908 int dist,mindist=0,pos;
1909 struct mapset_handle *h;
1911 struct map_rect *mr;
1914 struct street_data *sd;
1918 ret=g_new0(struct route_info, 1);
1920 dbg(0,"Out of memory\n");
1926 while ((m=mapset_next(h,1))) {
1929 if (map_projection(m) != pc->pro) {
1930 transform_to_geo(pc->pro, &c, &g);
1931 transform_from_geo(map_projection(m), &g, &c);
1933 sel = route_rect(18, &c, &c, 0, max_dist);
1936 mr=map_rect_new(m, sel);
1938 map_selection_destroy(sel);
1941 while ((item=map_rect_get_item(mr))) {
1942 if (item->type >= type_street_0 && item->type <= type_ferry) {
1943 sd=street_get_data(item);
1946 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1947 if (dist < mindist) {
1950 street_data_free(ret->street);
1956 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1958 street_data_free(sd);
1962 map_selection_destroy(sel);
1963 map_rect_destroy(mr);
1967 if (!ret->street || mindist > max_dist*max_dist) {
1969 street_data_free(ret->street);
1970 dbg(1,"Much too far %d > %d\n", mindist, max_dist);
1980 * @brief Destroys a route_info
1982 * @param info The route info to be destroyed
1985 route_info_free(struct route_info *inf)
1988 street_data_free(inf->street);
1996 * @brief Returns street data for a route info
1998 * @param rinf The route info to return the street data for
1999 * @return Street data for the route info
2001 struct street_data *
2002 route_info_street(struct route_info *rinf)
2004 return rinf->street;
2008 struct route_crossings *
2009 route_crossings_get(struct route *this, struct coord *c)
2011 struct route_point *pnt;
2012 struct route_segment *seg;
2014 struct route_crossings *ret;
2016 pnt=route_graph_get_point(this, c);
2019 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2021 seg=seg->start_next;
2025 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
2029 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
2030 ret->count=crossings;
2036 struct map_rect_priv {
2037 struct route_info_handle *ri;
2038 enum attr_type attr_next;
2040 struct map_priv *mpriv;
2043 unsigned int last_coord;
2044 struct route_path_segment *seg,*seg_next;
2045 struct route_graph_point *point;
2046 struct route_graph_segment *rseg;
2048 struct coord *coord_sel; /**< Set this to a coordinate if you want to filter for just a single route graph point */
2049 struct route_graph_point_iterator it;
2053 rm_coord_rewind(void *priv_data)
2055 struct map_rect_priv *mr = priv_data;
2060 rm_attr_rewind(void *priv_data)
2062 struct map_rect_priv *mr = priv_data;
2063 mr->attr_next = attr_street_item;
2067 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2069 struct map_rect_priv *mr = priv_data;
2070 struct route_path_segment *seg=mr->seg;
2071 struct route *route=mr->mpriv->route;
2072 attr->type=attr_type;
2073 switch (attr_type) {
2075 while (mr->attr_next != attr_none) {
2076 if (rm_attr_get(priv_data, mr->attr_next, attr))
2080 case attr_street_item:
2081 mr->attr_next=attr_direction;
2082 if (seg && seg->item.map)
2083 attr->u.item=&seg->item;
2087 case attr_direction:
2088 mr->attr_next=attr_route;
2090 attr->u.num=seg->direction;
2095 mr->attr_next=attr_length;
2096 attr->u.route = mr->mpriv->route;
2100 attr->u.num=seg->length;
2102 attr->u.num=mr->length;
2103 mr->attr_next=attr_time;
2106 mr->attr_next=attr_none;
2108 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
2113 mr->attr_next=attr_none;
2116 mr->attr_next=attr_none;
2117 attr->type=attr_none;
2124 rm_coord_get(void *priv_data, struct coord *c, int count)
2126 struct map_rect_priv *mr = priv_data;
2127 struct route_path_segment *seg = mr->seg;
2129 struct route *r = mr->mpriv->route;
2130 enum projection pro = route_projection(r);
2134 for (i=0; i < count; i++) {
2135 if (mr->last_coord >= seg->ncoords)
2137 if (i >= seg->ncoords)
2139 if (pro != projection_mg)
2140 transform_from_to(&seg->c[mr->last_coord++], pro,
2141 &c[i],projection_mg);
2143 c[i] = seg->c[mr->last_coord++];
2146 dbg(1,"return %d\n",rc);
2150 static struct item_methods methods_route_item = {
2158 rp_attr_rewind(void *priv_data)
2160 struct map_rect_priv *mr = priv_data;
2161 mr->attr_next = attr_label;
2165 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
2167 struct map_rect_priv *mr = priv_data;
2168 struct route_graph_point *p = mr->point;
2169 struct route_graph_segment *seg = mr->rseg;
2170 switch (attr_type) {
2171 case attr_any: // works only with rg_points for now
2172 if (mr->item.type != type_rg_point)
2174 while (mr->attr_next != attr_none) {
2175 if (rp_attr_get(priv_data, mr->attr_next, attr))
2180 if (mr->item.type != type_rg_point)
2182 attr->type = attr_label;
2185 if (p->value != INT_MAX)
2186 mr->str=g_strdup_printf("%d", p->value);
2188 mr->str=g_strdup("-");
2189 attr->u.str = mr->str;
2190 mr->attr_next=attr_none;
2192 case attr_street_item:
2193 if (mr->item.type != type_rg_segment)
2195 mr->attr_next=attr_none;
2196 if (seg && seg->item.map)
2197 attr->u.item=&seg->item;
2202 if (mr->item.type != type_rg_segment)
2204 mr->attr_next = attr_none;
2206 attr->u.num = seg->flags;
2211 case attr_direction:
2212 // This only works if the map has been opened at a single point, and in that case indicates if the
2213 // segment returned last is connected to this point via its start (1) or its end (-1)
2214 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
2216 if (seg->start == mr->point) {
2218 } else if (seg->end == mr->point) {
2225 if (mr->item.type != type_rg_point)
2227 attr->type = attr_debug;
2230 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2231 attr->u.str = mr->str;
2232 mr->attr_next=attr_none;
2235 mr->attr_next=attr_none;
2236 attr->type=attr_none;
2242 * @brief Returns the coordinates of a route graph item
2244 * @param priv_data The route graph item's private data
2245 * @param c Pointer where to store the coordinates
2246 * @param count How many coordinates to get at a max?
2247 * @return The number of coordinates retrieved
2250 rp_coord_get(void *priv_data, struct coord *c, int count)
2252 struct map_rect_priv *mr = priv_data;
2253 struct route_graph_point *p = mr->point;
2254 struct route_graph_segment *seg = mr->rseg;
2256 struct route *r = mr->mpriv->route;
2257 enum projection pro = route_projection(r);
2259 for (i=0; i < count; i++) {
2260 if (mr->item.type == type_rg_point) {
2261 if (mr->last_coord >= 1)
2263 if (pro != projection_mg)
2264 transform_from_to(&p->c, pro,
2265 &c[i],projection_mg);
2269 if (mr->last_coord >= 2)
2272 if (seg->end->seg == seg)
2277 if (pro != projection_mg)
2278 transform_from_to(&seg->end->c, pro,
2279 &c[i],projection_mg);
2283 if (pro != projection_mg)
2284 transform_from_to(&seg->start->c, pro,
2285 &c[i],projection_mg);
2287 c[i] = seg->start->c;
2296 static struct item_methods methods_point_item = {
2304 rp_destroy(struct map_priv *priv)
2310 rm_destroy(struct map_priv *priv)
2315 static struct map_rect_priv *
2316 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2318 struct map_rect_priv * mr;
2320 if (! route_get_pos(priv->route))
2322 if (! route_get_dst(priv->route))
2324 if (! priv->route->path2)
2326 mr=g_new0(struct map_rect_priv, 1);
2328 mr->item.priv_data = mr;
2329 mr->item.type = type_street_route;
2330 mr->item.meth = &methods_route_item;
2331 mr->seg_next=priv->route->path2->path;
2336 * @brief Opens a new map rectangle on the route graph's map
2338 * This function opens a new map rectangle on the route graph's map.
2339 * The "sel" parameter enables you to only search for a single route graph
2340 * point on this map (or exactly: open a map rectangle that only contains
2341 * this one point). To do this, pass here a single map selection, whose
2342 * c_rect has both coordinates set to the same point. Otherwise this parameter
2345 * @param priv The route graph map's private data
2346 * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2347 * @return A new map rect's private data
2349 static struct map_rect_priv *
2350 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2352 struct map_rect_priv * mr;
2355 if (! priv->route->graph || ! priv->route->graph->route_points)
2357 mr=g_new0(struct map_rect_priv, 1);
2359 mr->item.priv_data = mr;
2360 mr->item.type = type_rg_point;
2361 mr->item.meth = &methods_point_item;
2363 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)) {
2364 mr->coord_sel = g_malloc(sizeof(struct coord));
2365 *(mr->coord_sel) = sel->u.c_rect.lu;
2372 rm_rect_destroy(struct map_rect_priv *mr)
2376 if (mr->coord_sel) {
2377 g_free(mr->coord_sel);
2383 static struct item *
2384 rp_get_item(struct map_rect_priv *mr)
2386 struct route *r = mr->mpriv->route;
2387 struct route_graph_point *p = mr->point;
2388 struct route_graph_segment *seg = mr->rseg;
2390 if (mr->item.type == type_rg_point) {
2391 if (mr->coord_sel) {
2392 // We are supposed to return only the point at one specified coordinate...
2394 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2395 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2398 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2399 mr->point = NULL; // This indicates that no point has been found
2401 mr->it = rp_iterator_new(p);
2408 p = r->graph->route_points;
2415 rm_coord_rewind(mr);
2419 mr->item.type = type_rg_segment;
2422 if (mr->coord_sel) {
2423 if (!mr->point) { // This means that no point has been found
2426 seg = rp_iterator_next(&(mr->it));
2429 seg=r->graph->route_segments;
2437 rm_coord_rewind(mr);
2445 static struct item *
2446 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2448 struct item *ret=NULL;
2450 ret=rp_get_item(mr);
2455 static struct item *
2456 rm_get_item(struct map_rect_priv *mr)
2458 dbg(1,"enter\n", mr->pos);
2460 mr->seg=mr->seg_next;
2463 mr->seg_next=mr->seg->next;
2470 static struct item *
2471 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2473 struct item *ret=NULL;
2475 ret=rm_get_item(mr);
2479 static struct map_methods route_meth = {
2492 static struct map_methods route_graph_meth = {
2506 route_toggle_routegraph_display(struct route *route)
2508 if (route->flags & RF_SHOWGRAPH) {
2509 route->flags &= ~RF_SHOWGRAPH;
2511 route->flags |= RF_SHOWGRAPH;
2515 static struct map_priv *
2516 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2518 struct map_priv *ret;
2519 struct attr *route_attr;
2521 route_attr=attr_search(attrs, NULL, attr_route);
2524 ret=g_new0(struct map_priv, 1);
2526 *meth=route_graph_meth;
2529 ret->route=route_attr->u.route;
2534 static struct map_priv *
2535 route_map_new(struct map_methods *meth, struct attr **attrs)
2537 return route_map_new_helper(meth, attrs, 0);
2540 static struct map_priv *
2541 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2543 return route_map_new_helper(meth, attrs, 1);
2547 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2550 *map=map_new(NULL, (struct attr*[]){
2551 &(struct attr){attr_type,{type}},
2552 &(struct attr){attr_route,.u.route=this_},
2553 &(struct attr){attr_data,{""}},
2554 &(struct attr){attr_description,{description}},
2561 * @brief Returns a new map containing the route path
2563 * This function returns a new map containing the route path.
2565 * @important Do not map_destroy() this!
2567 * @param this_ The route to get the map of
2568 * @return A new map containing the route path
2571 route_get_map(struct route *this_)
2573 return route_get_map_helper(this_, &this_->map, "route","Route");
2578 * @brief Returns a new map containing the route graph
2580 * This function returns a new map containing the route graph.
2582 * @important Do not map_destroy() this!
2584 * @param this_ The route to get the map of
2585 * @return A new map containing the route graph
2588 route_get_graph_map(struct route *this_)
2590 return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2594 route_set_projection(struct route *this_, enum projection pro)
2599 route_add_callback(struct route *this_, struct callback *cb)
2601 callback_list_add(this_->cbl, cb);
2605 route_remove_callback(struct route *this_, struct callback *cb)
2607 callback_list_remove(this_->cbl, cb);
2614 plugin_register_map_type("route", route_map_new);
2615 plugin_register_map_type("route_graph", route_graph_map_new);