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"
76 * @brief A point in the route graph
78 * This represents a point in the route graph. A point usually connects two or more segments,
79 * but there are also points which don't do that (e.g. at the end of a dead-end).
81 struct route_graph_point {
82 struct route_graph_point *next; /**< Linked-list pointer to a list of all route_graph_points */
83 struct route_graph_point *hash_next; /**< Pointer to a chained hashlist of all route_graph_points with this hash */
84 struct route_graph_segment *start; /**< Pointer to a list of segments of which this point is the start. The links
85 * of this linked-list are in route_graph_segment->start_next.*/
86 struct route_graph_segment *end; /**< Pointer to a list of segments of which this pointer is the end. The links
87 * of this linked-list are in route_graph_segment->end_next. */
88 struct route_graph_segment *seg; /**< Pointer to the segment one should use to reach the destination at
90 struct fibheap_el *el; /**< When this point is put on a Fibonacci heap, this is a pointer
91 * to this point's heap-element */
92 int value; /**< The cost at which one can reach the destination from this point on */
93 struct coord c; /**< Coordinates of this point */
97 * @brief A segment in the route graph
99 * This is a segment in the route graph. A segment represents a driveable way.
101 struct route_graph_segment {
102 struct route_graph_segment *next; /**< Linked-list pointer to a list of all route_graph_segments */
103 struct route_graph_segment *start_next; /**< Pointer to the next element in the list of segments that start at the
104 * same point. Start of this list is in route_graph_point->start. */
105 struct route_graph_segment *end_next; /**< Pointer to the next element in the list of segments that end at the
106 * same point. Start of this list is in route_graph_point->end. */
107 struct route_graph_point *start; /**< Pointer to the point this segment starts at. */
108 struct route_graph_point *end; /**< Pointer to the point this segment ends at. */
109 struct item item; /**< The item (e.g. street) that this segment represents. */
111 int len; /**< Length of this segment */
112 int offset; /**< If the item represented by this segment is "segmented" (i.e.
113 * is represented by several segments instead of just one), this
114 * indicates the position of this segment in the item - for items
115 * that are not segmented this should always be 1 */
119 * @brief A segment in the route path
121 * This is a segment in the route path.
123 struct route_path_segment {
124 struct route_path_segment *next; /**< Pointer to the next segment in the path */
125 struct item item; /**< The item (e.g. street) this segment represents */
126 int length; /**< Length of the segment */
127 int offset; /**< Same as in route_graph_segment->offset */
128 int direction; /**< Order in which the coordinates are ordered. >0 means "First
129 * coordinate of the segment is the first coordinate of the item", <=0
131 unsigned ncoords; /**< How many coordinates does this segment have? */
132 struct attr **attrs; /**< Attributes of this route path segment */
133 struct coord c[0]; /**< Pointer to the ncoords coordinates of this segment */
134 /* WARNING: There will be coordinates following here, so do not create new fields after c! */
138 * @brief Usually represents a destination or position
140 * This struct usually represents a destination or position
143 struct coord c; /**< The actual destination / position */
144 struct coord lp; /**< The nearest point on a street to c */
145 int pos; /**< The position of lp within the coords of the street */
146 int lenpos; /**< Distance between lp and the end of the street */
147 int lenneg; /**< Distance between lp and the start of the street */
148 int lenextra; /**< Distance between lp and c */
150 struct street_data *street; /**< The street lp is on */
154 * @brief A complete route path
156 * This structure describes a whole routing path
159 struct route_path_segment *path; /**< The first segment in the path, i.e. the segment one should
161 struct route_path_segment *path_last; /**< The last segment in the path */
162 /* XXX: path_hash is not necessery now */
163 struct item_hash *path_hash; /**< A hashtable of all the items represented by this route's segements */
166 #define RF_FASTEST (1<<0)
167 #define RF_SHORTEST (1<<1)
168 #define RF_AVOIDHW (1<<2)
169 #define RF_AVOIDPAID (1<<3)
170 #define RF_LOCKONROAD (1<<4)
171 #define RF_SHOWGRAPH (1<<5)
174 * @brief A complete route
176 * This struct holds all information about a route.
179 int version; /**< Counts how many times this route got updated */
180 struct mapset *ms; /**< The mapset this route is built upon */
182 struct route_info *pos; /**< Current position within this route */
183 struct route_info *dst; /**< Destination of the route */
185 struct route_graph *graph; /**< Pointer to the route graph */
186 struct route_path *path2; /**< Pointer to the route path */
188 struct map *graph_map;
189 int speedlist[route_item_last-route_item_first+1]; /**< The speedlist for this route */
193 * @brief A complete route graph
195 * This structure describes a whole routing graph
198 struct route_graph_point *route_points; /**< Pointer to the first route_graph_point in the linked list of all points */
199 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
200 #define HASH_SIZE 8192
201 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
204 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
206 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
207 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
208 static void route_graph_update(struct route *this);
209 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);
210 static void route_process_street_graph(struct route_graph *this, struct item *item);
211 static void route_graph_destroy(struct route_graph *this);
212 static void route_path_update(struct route *this);
215 * @brief Returns the projection used for this route
217 * @param route The route to return the projection for
218 * @return The projection used for this route
220 static enum projection route_projection(struct route *route)
222 struct street_data *street;
223 street = route->pos ? route->pos->street : route->dst->street;
224 return map_projection(street->item.map);
228 * @brief Destroys a route_path
230 * @param this The route_path to be destroyed
233 route_path_destroy(struct route_path *this)
235 struct route_path_segment *c,*n;
238 if (this->path_hash) {
239 item_hash_destroy(this->path_hash);
240 this->path_hash=NULL;
246 attr_list_free(c->attrs);
255 * @brief Creates a completely new route structure
257 * @param attrs Not used
258 * @return The newly created route
261 route_new(struct attr **attrs)
263 struct route *this=g_new0(struct route, 1);
265 printf("%s:Out of memory\n", __FUNCTION__);
272 * @brief Sets the mapset of the route passwd
274 * @param this The route to set the mapset for
275 * @param ms The mapset to set for this route
278 route_set_mapset(struct route *this, struct mapset *ms)
284 * @brief Returns the mapset of the route passed
286 * @param this The route to get the mapset of
287 * @return The mapset of the route passed
290 route_get_mapset(struct route *this)
296 * @brief Returns the current position within the route passed
298 * @param this The route to get the position for
299 * @return The position within the route passed
302 route_get_pos(struct route *this)
308 * @brief Returns the destination of the route passed
310 * @param this The route to get the destination for
311 * @return The destination of the route passed
314 route_get_dst(struct route *this)
320 * @brief Returns the speedlist of the route passed
322 * @param this The route to get the speedlist for
323 * @return The speedlist of the route passed
326 route_get_speedlist(struct route *this)
328 return this->speedlist;
332 * @brief Checks if the path is calculated for the route passed
334 * @param this The route to check
335 * @return True if the path is calculated, false if not
338 route_get_path_set(struct route *this)
340 return this->path2 != NULL;
344 * @brief Sets the driving speed for a certain itemtype
346 * @param this The route to set the speed for
347 * @param type The itemtype to set the speed for
348 * @param value The speed that should be set
349 * @return True on success, false if the itemtype does not exist
352 route_set_speed(struct route *this, enum item_type type, int value)
354 if (type < route_item_first || type > route_item_last) {
355 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
358 this->speedlist[type-route_item_first]=value;
363 * @brief Checks if the route passed contains a certain item within the route path
365 * This function checks if a certain items exists in the path that navit will guide
366 * the user to his destination. It does *not* check if this item exists in the route
369 * @param this The route to check for this item
370 * @param item The item to search for
371 * @return True if the item was found, false if the item was not found or the route was not calculated
374 route_contains(struct route *this, struct item *item)
376 if (! this->path2 || !this->path2->path_hash)
378 return (int)item_hash_lookup(this->path2->path_hash, item);
382 * @brief Checks if the current position in a route is a certain item
384 * @param this The route to check for this item
385 * @param item The item to search for
386 * @return True if the current position is this item, false otherwise
389 route_pos_contains(struct route *this, struct item *item)
393 return item_is_equal(this->pos->street->item, *item);
397 * @brief Updates the route graph and the route path if something changed with the route
399 * This will update the route graph and the route path of the route if some of the
400 * route's settings (destination, position) have changed.
402 * @attention For this to work the route graph has to be destroyed if the route's
403 * @attention destination is changed somewhere!
405 * @param this The route to update
408 route_path_update(struct route *this)
410 struct route_path *oldpath = NULL;
411 if (! this->pos || ! this->dst) {
412 route_path_destroy(this->path2);
416 /* the graph is destroyed when setting the destination */
417 if (this->graph && this->pos && this->dst && this->path2) {
418 // we can try to update
419 oldpath = this->path2;
422 if (! this->graph || !(this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist))) {
424 route_graph_update(this);
425 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
426 profile(1,"route_path_new");
430 /* Destroy what's left */
431 route_path_destroy(oldpath);
436 * @brief This will calculate all the distances stored in a route_info
438 * @param ri The route_info to calculate the distances for
439 * @param pro The projection used for this route
442 route_info_distances(struct route_info *ri, enum projection pro)
445 struct street_data *sd=ri->street;
446 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
447 ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
448 ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
449 ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
453 * @brief This sets the current position of the route passed
455 * This will set the current position of the route passed to the street that is nearest to the
456 * passed coordinates. It also automatically updates the route.
458 * @param this The route to set the position of
459 * @param pos Coordinates to set as position
462 route_set_position(struct route *this, struct pcoord *pos)
465 route_info_free(this->pos);
467 this->pos=route_find_nearest_street(this->ms, pos);
468 dbg(1,"this->pos=%p\n", this->pos);
471 route_info_distances(this->pos, pos->pro);
473 route_path_update(this);
477 * @brief Sets a route's current position based on coordinates from tracking
479 * @param this The route to set the current position of
480 * @param tracking The tracking to get the coordinates from
483 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
486 struct route_info *ret;
489 c=tracking_get_pos(tracking);
490 ret=g_new0(struct route_info, 1);
492 printf("%s:Out of memory\n", __FUNCTION__);
496 route_info_free(this->pos);
500 ret->pos=tracking_get_segment_pos(tracking);
501 ret->street=street_data_dup(tracking_get_street_data(tracking));
502 route_info_distances(ret, projection_mg);
503 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);
504 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);
507 route_path_update(this);
511 /* Used for debuging of route_rect, what routing sees */
512 struct map_selection *route_selection;
515 * @brief Returns a single map selection
517 struct map_selection *
518 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
520 int dx,dy,sx=1,sy=1,d,m;
521 struct map_selection *sel=g_new(struct map_selection, 1);
523 printf("%s:Out of memory\n", __FUNCTION__);
526 sel->order[layer_town]=0;
527 sel->order[layer_poly]=0;
528 sel->order[layer_street]=order;
529 dbg(1,"%p %p\n", c1, c2);
534 sel->u.c_rect.lu.x=c1->x;
535 sel->u.c_rect.rl.x=c2->x;
537 sel->u.c_rect.lu.x=c2->x;
538 sel->u.c_rect.rl.x=c1->x;
542 sel->u.c_rect.lu.y=c2->y;
543 sel->u.c_rect.rl.y=c1->y;
545 sel->u.c_rect.lu.y=c1->y;
546 sel->u.c_rect.rl.y=c2->y;
553 sel->u.c_rect.lu.x-=m;
554 sel->u.c_rect.rl.x+=m;
555 sel->u.c_rect.lu.y+=m;
556 sel->u.c_rect.rl.y-=m;
562 * @brief Returns a list of map selections useable to create a route graph
564 * Returns a list of map selections useable to get a map rect from which items can be
565 * retrieved to build a route graph. The selections are a rectangle with
566 * c1 and c2 as two corners.
568 * @param c1 Corner 1 of the rectangle
569 * @param c2 Corder 2 of the rectangle
571 static struct map_selection *
572 route_calc_selection(struct coord *c1, struct coord *c2)
574 struct map_selection *ret,*sel;
575 sel=route_rect(4, c1, c2, 25, 0);
577 sel->next=route_rect(8, c1, c1, 0, 40000);
579 sel->next=route_rect(18, c1, c1, 0, 10000);
581 sel->next=route_rect(8, c2, c2, 0, 40000);
583 sel->next=route_rect(18, c2, c2, 0, 10000);
584 /* route_selection=ret; */
589 * @brief Destroys a list of map selections
591 * @param sel Start of the list to be destroyed
594 route_free_selection(struct map_selection *sel)
596 struct map_selection *next;
606 * @brief Sets the destination of a route
608 * This sets the destination of a route to the street nearest to the coordinates passed
609 * and updates the route.
611 * @param this The route to set the destination for
612 * @param dst Coordinates to set as destination
615 route_set_destination(struct route *this, struct pcoord *dst)
619 route_info_free(this->dst);
622 this->dst=route_find_nearest_street(this->ms, dst);
623 route_info_distances(this->dst, dst->pro);
625 profile(1,"find_nearest_street");
627 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
628 route_graph_destroy(this->graph);
630 route_path_update(this);
635 * @brief Gets the route_graph_point with the specified coordinates
637 * @param this The route in which to search
638 * @param c Coordinates to search for
639 * @return The point at the specified coordinates or NULL if not found
641 static struct route_graph_point *
642 route_graph_get_point(struct route_graph *this, struct coord *c)
644 struct route_graph_point *p;
645 int hashval=HASHCOORD(c);
646 p=this->hash[hashval];
648 if (p->c.x == c->x && p->c.y == c->y)
656 * @brief Inserts a point into the route graph at the specified coordinates
658 * This will insert a point into the route graph at the coordinates passed in f.
659 * Note that the point is not yet linked to any segments.
661 * @param this The route to insert the point into
662 * @param f The coordinates at which the point should be inserted
663 * @return The point inserted or NULL on failure
665 static struct route_graph_point *
666 route_graph_add_point(struct route_graph *this, struct coord *f)
669 struct route_graph_point *p;
671 p=route_graph_get_point(this,f);
673 hashval=HASHCOORD(f);
675 printf("p (0x%x,0x%x)\n", f->x, f->y);
676 p=g_new(struct route_graph_point,1);
678 printf("%s:Out of memory\n", __FUNCTION__);
681 p->hash_next=this->hash[hashval];
682 this->hash[hashval]=p;
683 p->next=this->route_points;
690 this->route_points=p;
696 * @brief Frees all the memory used for points in the route graph passed
698 * @param this The route graph to delete all points from
701 route_graph_free_points(struct route_graph *this)
703 struct route_graph_point *curr,*next;
704 curr=this->route_points;
710 this->route_points=NULL;
711 memset(this->hash, 0, sizeof(this->hash));
715 * @brief Inserts a new segment into the route graph
717 * This function performs a check if a segment for the item specified already exists, and inserts
718 * a new segment representing this item if it does not.
720 * @param this The route graph to insert the segment into
721 * @param start The graph point which should be connected to the start of this segment
722 * @param end The graph point which should be connected to the end of this segment
723 * @param len The length of this segment
724 * @param item The item that is represented by this segment
725 * @param flags Flags for this segment
726 * @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
729 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
730 struct route_graph_point *end, int len, struct item *item,
731 int flags, int offset)
733 struct route_graph_segment *s;
736 if (item_is_equal(*item, s->item))
740 s = g_new0(struct route_graph_segment, 1);
742 printf("%s:Out of memory\n", __FUNCTION__);
746 s->start_next=start->start;
749 s->end_next=end->end;
756 s->next=this->route_segments;
757 this->route_segments=s;
759 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
763 * @brief Gets all the coordinates of an item
765 * This will get all the coordinates of the item i and return them in c,
766 * up to max coordinates. Additionally it is possible to limit the coordinates
767 * returned to all the coordinates of the item between the two coordinates
770 * @important Make shure that whatever c points to has enough memory allocated
771 * @important to hold max coordinates!
773 * @param i The item to get the coordinates of
774 * @param c Pointer to memory allocated for holding the coordinates
775 * @param max Maximum number of coordinates to return
776 * @param start First coordinate to get
777 * @param end Last coordinate to get
779 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
780 struct coord *start, struct coord *end)
786 mr=map_rect_new(i->map, NULL);
789 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
791 rc = item_coord_get(item, &c1, 1);
792 while (rc && (c1.x != start->x || c1.y != start->y)) {
793 rc = item_coord_get(item, &c1, 1);
795 while (rc && p < max) {
797 if (c1.x == end->x && c1.y == end->y)
799 rc = item_coord_get(item, &c1, 1);
802 map_rect_destroy(mr);
807 * @brief Returns and removes one segment from a path
809 * @param path The path to take the segment from
810 * @param item The item whose segment to remove
811 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
812 * @return The segment removed
814 static struct route_path_segment *
815 route_extract_segment_from_path(struct route_path *path, struct item *item,
818 struct route_path_segment *sp = NULL, *s;
821 if (s->offset == offset && item_is_equal(s->item,*item)) {
826 path->path = s->next;
834 item_hash_remove(path->path_hash, item);
839 * @brief Adds a segment and the end of a path
841 * @param this The path to add the segment to
842 * @param segment The segment to add
845 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
850 this->path_last->next=segment;
851 this->path_last=segment;
855 * @brief Adds a new item to a path
857 * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
858 * if the item passed is segmented - it will create exactly one segment.
860 * @param this The path to add the item to
861 * @param item The item to add
862 * @param len The length of the item
863 * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
864 * @param c Pointer to count coordinates of the item.
865 * @param cound Number of coordinates in c
866 * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
867 * @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"
870 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)
872 int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
873 struct route_path_segment *segment;
875 segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
876 segment->ncoords=ccount;
877 segment->direction=dir;
879 segment->c[idx++]=*first;
881 for (i = 0 ; i < count ; i++)
882 segment->c[idx++]=c[i];
884 for (i = 0 ; i < count ; i++)
885 segment->c[idx++]=c[count-i-1];
888 segment->c[idx++]=*last;
892 route_path_add_segment(this, segment);
896 * @brief Inserts a new item into the path
898 * This function does almost the same as "route_apth_add_item()", but identifies
899 * the item to add by a segment from the route graph. Another difference is that it "copies" the
900 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
901 * be added to the route path, not all segments of the item.
903 * The function can be sped up by passing an old path already containing this segment in oldpath -
904 * the segment will then be extracted from this old path. Please note that in this case the direction
905 * parameter has no effect.
907 * @param this The path to add the item to
908 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
909 * @param rgs Segment of the route graph that should be "copied" to the route path
910 * @param len Length of the item to be added
911 * @param offset Offset of rgs within the item it represents
912 * @param dir Order in which to add the coordinates. See route_path_add_item()
913 * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
916 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
917 struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
919 struct route_path_segment *segment;
921 struct coord ca[2048];
922 struct attr straight_attr;
925 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
927 segment = route_extract_segment_from_path(oldpath,
935 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
936 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
938 printf("%s:Out of memory\n", __FUNCTION__);
941 segment->direction=dir;
943 for (i = 0 ; i < ccnt ; i++)
946 for (i = 0 ; i < ccnt ; i++)
947 segment->c[i]=ca[ccnt-i-1];
949 segment->ncoords = ccnt;
950 segment->item=rgs->item;
951 segment->offset = offset;
955 item_hash_insert(this->path_hash, &rgs->item, (void *)ccnt);
957 straight_attr.type = attr_route_follow_straight;
958 straight_attr.u.num = straight;
960 segment->attrs = attr_generic_set_attr(segment->attrs, &straight_attr);
962 route_path_add_segment(this, segment);
966 * @brief Destroys all segments of a route graph
968 * @param this The graph to destroy all segments from
971 route_graph_free_segments(struct route_graph *this)
973 struct route_graph_segment *curr,*next;
974 curr=this->route_segments;
980 this->route_segments=NULL;
984 * @brief Destroys a route graph
986 * @param this The route graph to be destroyed
989 route_graph_destroy(struct route_graph *this)
992 route_graph_free_points(this);
993 route_graph_free_segments(this);
999 * @brief Returns the time needed to drive len on item
1001 * @param speedlist The speedlist that should be used
1002 * @param item The item to be driven on
1003 * @param len The length to drive
1004 * @return The time needed to drive len on item
1007 route_time(int *speedlist, struct item *item, int len)
1009 if (item->type < route_item_first || item->type > route_item_last) {
1010 dbg(0,"street type %d out of range [%d,%d]", item->type, route_item_first, route_item_last);
1013 return len*36/speedlist[item->type-route_item_first];
1017 * @brief Returns the "costs" of driving len on item
1019 * @param speedlist The speedlist that should be used
1020 * @param item The item to be driven on
1021 * @param len The length to drive
1022 * @return The "costs" needed to drive len on item
1025 route_value(int *speedlist, struct item *item, int len)
1029 printf("len=%d\n", len);
1032 ret=route_time(speedlist, item, len);
1033 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1038 * @brief Adds an item to the route graph
1040 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1043 * @param this The route graph to add to
1044 * @param item The item to add
1047 route_process_street_graph(struct route_graph *this, struct item *item)
1054 struct route_graph_point *s_pnt,*e_pnt;
1061 if (item_coord_get(item, &l, 1)) {
1062 if (item_attr_get(item, attr_flags, &attr)) {
1064 if (flags & AF_SEGMENTED)
1067 s_pnt=route_graph_add_point(this,&l);
1069 while (item_coord_get(item, &c, 1)) {
1070 len+=transform_distance(map_projection(item->map), &l, &c);
1073 e_pnt=route_graph_add_point(this,&l);
1075 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1080 isseg = item_coord_is_segment(item);
1081 rc = item_coord_get(item, &c, 1);
1083 len+=transform_distance(map_projection(item->map), &l, &c);
1086 e_pnt=route_graph_add_point(this,&l);
1087 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1089 s_pnt=route_graph_add_point(this,&l);
1094 e_pnt=route_graph_add_point(this,&l);
1097 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1103 * @brief Compares the costs of reaching the destination from two points on
1105 * @important Do not pass anything other than route_graph_points in v1 and v2!
1109 * @return The additional costs of v1 compared to v2 (may be negative)
1112 compare(void *v1, void *v2)
1114 struct route_graph_point *p1=v1;
1115 struct route_graph_point *p2=v2;
1118 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1120 return p1->value-p2->value;
1124 * @brief Calculates the routing costs for each point
1126 * This function is the heart of routing. It assigns each point in the route graph a
1127 * cost at which one can reach the destination from this point on. Additionally it assigns
1128 * each point a segment one should follow from this point on to reach the destination at the
1131 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1132 * at this algorithm.
1135 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
1137 struct route_graph_point *p_min,*end=NULL;
1138 struct route_graph_segment *s;
1139 int min,new,old,val;
1140 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1141 struct street_data *sd=dst->street;
1143 heap = fh_makeheap();
1144 fh_setcmp(heap, compare);
1146 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 */
1147 end=route_graph_get_point(this, &sd->c[0]);
1149 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1150 end->el=fh_insert(heap, end);
1153 if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1154 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1156 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1157 end->el=fh_insert(heap, end);
1160 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1162 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1163 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1167 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);
1168 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1170 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1171 val=route_value(speedlist, &s->item, s->len);
1173 val+=val*2*street_route_contained(s->str->segid);
1177 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);
1178 if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1183 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1184 s->end->el=fh_insert(heap, s->end);
1186 printf("el new=%p\n", s->end->el);
1190 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1191 fh_replacedata(heap, s->end->el, s->end);
1199 while (s) { /* Doing the same as above with the segments leading towards our point */
1200 val=route_value(speedlist, &s->item, s->len);
1203 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);
1204 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1205 old=s->start->value;
1206 s->start->value=new;
1208 if (! s->start->el) {
1210 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1211 s->start->el=fh_insert(heap, s->start);
1213 printf("el new=%p\n", s->start->el);
1217 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1218 fh_replacedata(heap, s->start->el, s->start);
1226 fh_deleteheap(heap);
1230 * @brief Starts an "offroad" path
1232 * This starts a path that is not located on a street. It creates a new route path
1233 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1235 * @param this Not used
1236 * @param pos The starting position for the new path
1237 * @param dst The destination of the new path
1238 * @param dir Not used
1239 * @return The new path
1241 static struct route_path *
1242 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1244 struct route_path *ret;
1246 ret=g_new0(struct route_path, 1);
1247 ret->path_hash=item_hash_new();
1248 route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1254 * @brief Creates a new "trivial" route
1256 * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1257 * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1259 * @param this The route graph to place the route on
1260 * @param pos The starting position for the new path
1261 * @param dst The destination of the new path
1262 * @param dir Direction of the coordinates to be added
1263 * @return The new path
1265 static struct route_path *
1266 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1268 struct street_data *sd=pos->street;
1269 struct route_path *ret;
1272 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1273 return route_path_new_offroad(this, pos, dst, dir);
1275 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1276 return route_path_new_offroad(this, pos, dst, dir);
1278 ret=g_new0(struct route_path, 1);
1279 ret->path_hash=item_hash_new();
1281 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1283 route_path_add_item(ret, &sd->item, pos->lenneg-dst->lenneg, &pos->lp, sd->c+pos->pos+1, dst->pos+pos->pos, &dst->lp, 1);
1285 route_path_add_item(ret, &sd->item, pos->lenpos-dst->lenpos, &pos->lp, sd->c+dst->pos+1, pos->pos-dst->pos, &dst->lp, -1);
1287 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1292 * @brief Calculates of two coordinates' connection
1294 * This function calculates the angle between coordinates, with north = 0
1297 * %FIXME This is a duplicate of road_angle() in navigation.c - combine them?
1299 * @param c1 Coordinate 1
1300 * @param c2 Coordinate 2
1301 * @param dir Set to true if c1 is the prior, and c2 the later coordinate.
1302 * @return The angle of the coordinate's connection
1305 route_road_angle(struct coord *c1, struct coord *c2, int dir)
1307 int ret=transform_get_angle_delta(c1, c2, dir);
1308 dbg(1, "road_angle(0x%x,0x%x - 0x%x,0x%x)=%d\n", c1->x, c1->y, c2->x, c2->y, ret);
1313 * @brief Checks if entering one segment from another is a "straight" road
1315 * This checks if one can enter seg_to from seg_from by driving "straight" - i.e.
1316 * if seg_to is the segment you can drive to from seg_from by steering less than
1317 * all to all other segments.
1319 * This function returns true on failure, so we don't create maneuvers on every error.
1321 * @param seg_from Segment we are driving from
1322 * @param seg_to Segment we are driving to
1323 * @return True if driving from seg_from to seg_to is "straight", false otherwise
1326 route_check_straight(struct route_graph_segment *seg_from, struct route_graph_segment *seg_to)
1328 struct route_graph_segment *curr;
1329 struct route_graph_point *conn;
1330 int from_angle, to_angle, curr_angle, angle_diff;
1332 struct coord ca[2048];
1334 if ((seg_from->end == seg_to->start) || (seg_from->end == seg_to->end)) {
1335 ccnt = get_item_seg_coords(&seg_from->item, ca, 2047, &seg_from->start->c, &seg_from->end->c);
1336 from_angle = route_road_angle(&ca[ccnt-2], &ca[ccnt-1],1);
1338 conn = seg_from->end;
1339 } else if ((seg_from->start == seg_to->start) || (seg_from->start == seg_to->end)) {
1340 ccnt = get_item_seg_coords(&seg_from->item, ca, 2, &seg_from->start->c, &seg_from->end->c);
1341 from_angle = route_road_angle(&ca[1], &ca[0],1);
1343 conn = seg_from->start;
1350 if (seg_to->end == conn) {
1351 ccnt = get_item_seg_coords(&seg_to->item, ca, 2047, &seg_to->start->c, &seg_to->end->c);
1352 to_angle = route_road_angle(&ca[ccnt-1], &ca[ccnt-2],1);
1354 ccnt = get_item_seg_coords(&seg_to->item, ca, 2, &seg_to->start->c, &seg_to->end->c);
1355 to_angle = route_road_angle(&ca[0], &ca[1],1);
1359 angle_diff = from_angle - to_angle;
1360 if (angle_diff < 0) {
1366 while (curr != NULL) {
1368 curr = curr->start_next;
1372 ccnt = get_item_seg_coords(&curr->item, ca, 2, &curr->start->c, &curr->end->c);
1373 curr_angle = route_road_angle(&ca[0], &ca[1], 1);
1375 curr_angle = from_angle - curr_angle;
1377 if (curr_angle < 0) {
1382 if (curr_angle <= angle_diff) {
1386 curr = curr->start_next;
1390 while (curr != NULL) {
1392 curr = curr->end_next;
1396 ccnt = get_item_seg_coords(&curr->item, ca, 2047, &curr->start->c, &curr->end->c);
1397 curr_angle = route_road_angle(&ca[ccnt-1], &ca[ccnt-2], 1);
1399 curr_angle = from_angle - curr_angle;
1401 if (curr_angle < 0) {
1405 if (curr_angle <= angle_diff) {
1409 curr = curr->end_next;
1416 * @brief Creates a new route path
1418 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1419 * make shure to run route_graph_flood() after changing the destination before using this function.
1421 * @param this The route graph to create the route from
1422 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1423 * @param pos The starting position of the route
1424 * @param dst The destination of the route
1425 * @param speedlist The speedlist to use
1426 * @return The new route path
1428 static struct route_path *
1429 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1431 struct route_graph_point *start1=NULL,*start2=NULL,*start;
1432 struct route_graph_segment *s=NULL;
1433 struct route_graph_segment *lastseg = NULL;
1438 int time=0,hr,min,sec
1440 unsigned int val1=0xffffffff,val2=0xffffffff;
1441 struct street_data *sd=pos->street;
1442 struct route_path *ret;
1444 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 */
1445 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1446 return route_path_new_trivial(this, pos, dst, -1);
1448 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1449 return route_path_new_trivial(this, pos, dst, 1);
1452 if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1453 start1=route_graph_get_point(this, &sd->c[0]);
1456 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1457 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1459 if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1460 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1463 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1464 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1466 dbg(1,"val1=%d val2=%d\n", val1, val2);
1468 val1=start1->start->start->value;
1469 val2=start2->end->end->value;
1471 ret=g_new0(struct route_path, 1);
1473 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1474 if (start1 && (val1 < val2)) {
1476 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1480 route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1482 printf("no route found, pos blocked\n");
1486 ret->path_hash=item_hash_new();
1487 while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1490 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1496 is_straight = route_check_straight(lastseg,s);
1501 if (s->start == start) {
1502 route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight);
1505 route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight);
1512 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1513 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);
1514 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 */
1515 route_path_add_item(ret, &sd->item, dst->lenneg, &dst->lp, sd->c, dst->pos+1, NULL, -1);
1516 } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1517 route_path_add_item(ret, &sd->item, dst->lenpos, &dst->lp, sd->c+dst->pos+1, sd->count-dst->pos-1, NULL, 1);
1519 printf("no route found\n");
1520 route_path_destroy(ret);
1524 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1525 dbg(1, "%d segments\n", segs);
1530 * @brief Builds a new route graph from a mapset
1532 * This function builds a new route graph from a map. Please note that this function does not
1533 * add any routing information to the route graph - this has to be done via the route_graph_flood()
1536 * The function does not create a graph covering the whole map, but only covering the rectangle
1537 * between c1 and c2.
1539 * @param ms The mapset to build the route graph from
1540 * @param c1 Corner 1 of the rectangle to use from the map
1541 * @param c2 Corner 2 of the rectangle to use from the map
1542 * @return The new route graph.
1544 static struct route_graph *
1545 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
1547 struct route_graph *ret=g_new0(struct route_graph, 1);
1548 struct map_selection *sel;
1549 struct mapset_handle *h;
1550 struct map_rect *mr;
1555 printf("%s:Out of memory\n", __FUNCTION__);
1558 sel=route_calc_selection(c1, c2);
1560 while ((m=mapset_next(h,1))) {
1561 mr=map_rect_new(m, sel);
1564 while ((item=map_rect_get_item(mr))) {
1565 if (item->type >= type_street_0 && item->type <= type_ferry) {
1566 route_process_street_graph(ret, item);
1569 map_rect_destroy(mr);
1572 route_free_selection(sel);
1578 * @brief Updates the route graph
1580 * This updates the route graph after settings in the route have changed. It also
1581 * adds routing information afterwards by calling route_graph_flood().
1583 * @param this The route to update the graph for
1586 route_graph_update(struct route *this)
1588 route_graph_destroy(this->graph);
1589 profile(1,"graph_free");
1590 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
1591 profile(1,"route_graph_build");
1592 route_graph_flood(this->graph, this->dst, this->speedlist);
1593 profile(1,"route_graph_flood");
1598 * @brief Gets street data for an item
1600 * @param item The item to get the data for
1601 * @return Street data for the item
1603 struct street_data *
1604 street_get_data (struct item *item)
1607 struct coord c[maxcount];
1609 struct street_data *ret;
1612 while (count < maxcount) {
1613 if (!item_coord_get(item, &c[count], 1))
1617 if (count >= maxcount) {
1618 dbg(0, "count=%d maxcount=%d id_hi=0x%x id_lo=0x%x\n", count, maxcount, item->id_hi, item->id_lo);
1619 if (item_attr_get(item, attr_debug, &attr))
1620 dbg(0,"debug='%s'\n", attr.u.str);
1622 g_assert(count < maxcount);
1623 ret=g_malloc(sizeof(struct street_data)+count*sizeof(struct coord));
1626 if (item_attr_get(item, attr_flags, &attr))
1627 ret->flags=attr.u.num;
1630 memcpy(ret->c, c, count*sizeof(struct coord));
1636 * @brief Copies street data
1638 * @param orig The street data to copy
1639 * @return The copied street data
1641 struct street_data *
1642 street_data_dup(struct street_data *orig)
1644 struct street_data *ret;
1645 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1648 memcpy(ret, orig, size);
1654 * @brief Frees street data
1656 * @param sd Street data to be freed
1659 street_data_free(struct street_data *sd)
1665 * @brief Finds the nearest street to a given coordinate
1667 * @param ms The mapset to search in for the street
1668 * @param pc The coordinate to find a street nearby
1669 * @return The nearest street
1671 static struct route_info *
1672 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1674 struct route_info *ret=NULL;
1676 struct map_selection *sel;
1677 int dist,mindist=0,pos;
1678 struct mapset_handle *h;
1680 struct map_rect *mr;
1683 struct street_data *sd;
1690 * This is not correct for two reasons:
1691 * - You may need to go back first
1692 * - Currently we allow mixing of mapsets
1694 sel = route_rect(18, &c, &c, 0, max_dist);
1696 while ((m=mapset_next(h,1))) {
1699 if (map_projection(m) != pc->pro) {
1700 transform_to_geo(pc->pro, &c, &g);
1701 transform_from_geo(map_projection(m), &g, &c);
1703 mr=map_rect_new(m, sel);
1706 while ((item=map_rect_get_item(mr))) {
1707 if (item->type >= type_street_0 && item->type <= type_ferry) {
1708 sd=street_get_data(item);
1709 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1710 if (!ret || dist < mindist) {
1712 street_data_free(ret->street);
1715 ret=g_new(struct route_info, 1);
1717 printf("%s:Out of memory\n", __FUNCTION__);
1725 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1727 street_data_free(sd);
1730 map_rect_destroy(mr);
1733 map_selection_destroy(sel);
1739 * @brief Destroys a route_info
1741 * @param info The route info to be destroyed
1744 route_info_free(struct route_info *inf)
1747 street_data_free(inf->street);
1755 * @brief Returns street data for a route info
1757 * @param rinf The route info to return the street data for
1758 * @return Street data for the route info
1760 struct street_data *
1761 route_info_street(struct route_info *rinf)
1763 return rinf->street;
1767 struct route_crossings *
1768 route_crossings_get(struct route *this, struct coord *c)
1770 struct route_point *pnt;
1771 struct route_segment *seg;
1773 struct route_crossings *ret;
1775 pnt=route_graph_get_point(this, c);
1778 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1780 seg=seg->start_next;
1784 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1788 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1789 ret->count=crossings;
1795 struct map_rect_priv {
1796 struct route_info_handle *ri;
1797 enum attr_type attr_next;
1799 struct map_priv *mpriv;
1802 unsigned int last_coord;
1803 struct route_path_segment *seg,*seg_next;
1804 struct route_graph_point *point;
1805 struct route_graph_segment *rseg;
1810 rm_coord_rewind(void *priv_data)
1812 struct map_rect_priv *mr = priv_data;
1817 rm_attr_rewind(void *priv_data)
1819 struct map_rect_priv *mr = priv_data;
1820 mr->attr_next = attr_street_item;
1824 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1826 struct map_rect_priv *mr = priv_data;
1827 struct route_path_segment *seg=mr->seg;
1828 struct route *route=mr->mpriv->route;
1829 attr->type=attr_type;
1830 switch (attr_type) {
1832 while (mr->attr_next != attr_none) {
1833 if (rm_attr_get(priv_data, mr->attr_next, attr))
1837 case attr_street_item:
1838 mr->attr_next=attr_route_follow_straight;
1839 if (seg && seg->item.map)
1840 attr->u.item=&seg->item;
1844 case attr_route_follow_straight:
1845 mr->attr_next=attr_direction;
1847 return attr_generic_get_attr(seg->attrs,NULL,attr_route_follow_straight,attr,NULL);
1850 case attr_direction:
1851 mr->attr_next=attr_length;
1853 attr->u.num=seg->direction;
1859 attr->u.num=seg->length;
1861 attr->u.num=mr->length;
1862 mr->attr_next=attr_time;
1865 mr->attr_next=attr_none;
1867 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1872 attr->type=attr_none;
1879 rm_coord_get(void *priv_data, struct coord *c, int count)
1881 struct map_rect_priv *mr = priv_data;
1882 struct route_path_segment *seg = mr->seg;
1886 for (i=0; i < count; i++) {
1887 if (mr->last_coord >= seg->ncoords)
1889 if (i >= seg->ncoords)
1891 c[i] = seg->c[mr->last_coord++];
1894 dbg(1,"return %d\n",rc);
1898 static struct item_methods methods_route_item = {
1906 rp_attr_rewind(void *priv_data)
1908 struct map_rect_priv *mr = priv_data;
1909 mr->attr_next = attr_label;
1913 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1915 struct map_rect_priv *mr = priv_data;
1916 struct route_graph_point *p = mr->point;
1917 if (mr->item.type != type_rg_point)
1919 switch (attr_type) {
1921 while (mr->attr_next != attr_none) {
1922 if (rm_attr_get(priv_data, mr->attr_next, attr))
1926 attr->type = attr_label;
1929 if (p->value != INT_MAX)
1930 mr->str=g_strdup_printf("%d", p->value);
1932 mr->str=g_strdup("-");
1933 attr->u.str = mr->str;
1934 mr->attr_next=attr_none;
1937 attr->type = attr_debug;
1940 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
1941 attr->u.str = mr->str;
1942 mr->attr_next=attr_none;
1950 rp_coord_get(void *priv_data, struct coord *c, int count)
1952 struct map_rect_priv *mr = priv_data;
1953 struct route_graph_point *p = mr->point;
1954 struct route_graph_segment *seg = mr->rseg;
1956 for (i=0; i < count; i++) {
1957 if (mr->item.type == type_rg_point) {
1958 if (mr->last_coord >= 1)
1962 if (mr->last_coord >= 2)
1965 if (seg->end->seg == seg)
1972 c[i] = seg->start->c;
1980 static struct item_methods methods_point_item = {
1988 rm_destroy(struct map_priv *priv)
1993 static struct map_rect_priv *
1994 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
1996 struct map_rect_priv * mr;
1998 if (! route_get_pos(priv->route))
2000 if (! route_get_dst(priv->route))
2002 if (! priv->route->path2)
2004 mr=g_new0(struct map_rect_priv, 1);
2006 mr->item.priv_data = mr;
2007 mr->item.type = type_street_route;
2008 mr->item.meth = &methods_route_item;
2009 mr->seg_next=priv->route->path2->path;
2013 static struct map_rect_priv *
2014 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2016 struct map_rect_priv * mr;
2018 if (! priv->route->graph || ! priv->route->graph->route_points)
2020 mr=g_new0(struct map_rect_priv, 1);
2022 mr->item.priv_data = mr;
2023 mr->item.type = type_rg_point;
2024 mr->item.meth = &methods_point_item;
2029 rm_rect_destroy(struct map_rect_priv *mr)
2036 static struct item *
2037 rp_get_item(struct map_rect_priv *mr)
2039 struct route *r = mr->mpriv->route;
2040 struct route_graph_point *p = mr->point;
2041 struct route_graph_segment *seg = mr->rseg;
2043 if (mr->item.type == type_rg_point) {
2045 p = r->graph->route_points;
2051 rm_coord_rewind(mr);
2055 mr->item.type = type_rg_segment;
2058 seg=r->graph->route_segments;
2064 rm_coord_rewind(mr);
2072 static struct item *
2073 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2075 struct item *ret=NULL;
2077 ret=rp_get_item(mr);
2082 static struct item *
2083 rm_get_item(struct map_rect_priv *mr)
2085 struct route *r = mr->mpriv->route;
2086 struct route_path_segment *seg = mr->seg;
2087 dbg(1,"enter\n", mr->pos);
2089 mr->seg=mr->seg_next;
2092 mr->seg_next=mr->seg->next;
2099 static struct item *
2100 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2102 struct item *ret=NULL;
2104 ret=rm_get_item(mr);
2108 static struct map_methods route_meth = {
2121 static struct map_methods route_graph_meth = {
2135 route_toggle_routegraph_display(struct route *route)
2137 if (route->flags & RF_SHOWGRAPH) {
2138 route->flags &= ~RF_SHOWGRAPH;
2140 route->flags |= RF_SHOWGRAPH;
2144 static struct map_priv *
2145 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2147 struct map_priv *ret;
2148 struct attr *route_attr;
2150 route_attr=attr_search(attrs, NULL, attr_route);
2153 ret=g_new0(struct map_priv, 1);
2155 *meth=route_graph_meth;
2158 ret->route=route_attr->u.route;
2163 static struct map_priv *
2164 route_map_new(struct map_methods *meth, struct attr **attrs)
2166 return route_map_new_helper(meth, attrs, 0);
2169 static struct map_priv *
2170 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2172 return route_map_new_helper(meth, attrs, 1);
2176 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2179 *map=map_new((struct attr*[]){
2180 &(struct attr){attr_type,{type}},
2181 &(struct attr){attr_route,.u.route=this_},
2182 &(struct attr){attr_data,{""}},
2183 &(struct attr){attr_description,{description}},
2189 route_get_map(struct route *this_)
2191 return route_get_map_helper(this_, &this_->map, "route","Route");
2196 route_get_graph_map(struct route *this_)
2198 return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2202 route_set_projection(struct route *this_, enum projection pro)
2209 plugin_register_map_type("route", route_map_new);
2210 plugin_register_map_type("route_graph", route_graph_map_new);