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 destination_distance; /**< Distance to the destination at which the destination is considered "reached" */
190 int speedlist[route_item_last-route_item_first+1]; /**< The speedlist for this route */
194 * @brief A complete route graph
196 * This structure describes a whole routing graph
199 struct route_graph_point *route_points; /**< Pointer to the first route_graph_point in the linked list of all points */
200 struct route_graph_segment *route_segments; /**< Pointer to the first route_graph_segment in the linked list of all segments */
201 #define HASH_SIZE 8192
202 struct route_graph_point *hash[HASH_SIZE]; /**< A hashtable containing all route_graph_points in this graph */
205 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
207 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
208 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
209 static void route_graph_update(struct route *this);
210 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);
211 static void route_process_street_graph(struct route_graph *this, struct item *item);
212 static void route_graph_destroy(struct route_graph *this);
213 static void route_path_update(struct route *this);
216 * @brief Returns the projection used for this route
218 * @param route The route to return the projection for
219 * @return The projection used for this route
221 static enum projection route_projection(struct route *route)
223 struct street_data *street;
224 street = route->pos ? route->pos->street : route->dst->street;
225 return map_projection(street->item.map);
229 * @brief Destroys a route_path
231 * @param this The route_path to be destroyed
234 route_path_destroy(struct route_path *this)
236 struct route_path_segment *c,*n;
239 if (this->path_hash) {
240 item_hash_destroy(this->path_hash);
241 this->path_hash=NULL;
247 attr_list_free(c->attrs);
256 * @brief Creates a completely new route structure
258 * @param attrs Not used
259 * @return The newly created route
262 route_new(struct attr **attrs)
264 struct route *this=g_new0(struct route, 1);
265 struct attr dest_attr;
268 printf("%s:Out of memory\n", __FUNCTION__);
272 if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
273 this->destination_distance = dest_attr.u.num;
275 this->destination_distance = 50; // Default value
282 * @brief Sets the mapset of the route passwd
284 * @param this The route to set the mapset for
285 * @param ms The mapset to set for this route
288 route_set_mapset(struct route *this, struct mapset *ms)
294 * @brief Returns the mapset of the route passed
296 * @param this The route to get the mapset of
297 * @return The mapset of the route passed
300 route_get_mapset(struct route *this)
306 * @brief Returns the current position within the route passed
308 * @param this The route to get the position for
309 * @return The position within the route passed
312 route_get_pos(struct route *this)
318 * @brief Returns the destination of the route passed
320 * @param this The route to get the destination for
321 * @return The destination of the route passed
324 route_get_dst(struct route *this)
330 * @brief Returns the speedlist of the route passed
332 * @param this The route to get the speedlist for
333 * @return The speedlist of the route passed
336 route_get_speedlist(struct route *this)
338 return this->speedlist;
342 * @brief Checks if the path is calculated for the route passed
344 * @param this The route to check
345 * @return True if the path is calculated, false if not
348 route_get_path_set(struct route *this)
350 return this->path2 != NULL;
354 * @brief Sets the driving speed for a certain itemtype
356 * @param this The route to set the speed for
357 * @param type The itemtype to set the speed for
358 * @param value The speed that should be set
359 * @return True on success, false if the itemtype does not exist
362 route_set_speed(struct route *this, enum item_type type, int value)
364 if (type < route_item_first || type > route_item_last) {
365 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
368 this->speedlist[type-route_item_first]=value;
373 * @brief Checks if the route passed contains a certain item within the route path
375 * This function checks if a certain items exists in the path that navit will guide
376 * the user to his destination. It does *not* check if this item exists in the route
379 * @param this The route to check for this item
380 * @param item The item to search for
381 * @return True if the item was found, false if the item was not found or the route was not calculated
384 route_contains(struct route *this, struct item *item)
386 if (! this->path2 || !this->path2->path_hash)
388 return (int)item_hash_lookup(this->path2->path_hash, item);
392 * @brief Checks if the current position in a route is a certain item
394 * @param this The route to check for this item
395 * @param item The item to search for
396 * @return True if the current position is this item, false otherwise
399 route_pos_contains(struct route *this, struct item *item)
403 return item_is_equal(this->pos->street->item, *item);
407 * @brief Checks if a route has reached its destination
409 * @param this The route to be checked
410 * @return True if the destination is "reached", false otherwise.
413 route_destination_reached(struct route *this)
415 struct street_data *sd = NULL;
420 sd = this->pos->street;
426 if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
430 if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
433 if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
437 if (transform_distance(route_projection(this), &this->pos->c, &this->dst->lp) > this->destination_distance) {
445 * @brief Updates the route graph and the route path if something changed with the route
447 * This will update the route graph and the route path of the route if some of the
448 * route's settings (destination, position) have changed.
450 * @attention For this to work the route graph has to be destroyed if the route's
451 * @attention destination is changed somewhere!
453 * @param this The route to update
456 route_path_update(struct route *this)
458 struct route_path *oldpath = NULL;
459 if (! this->pos || ! this->dst) {
460 route_path_destroy(this->path2);
464 /* the graph is destroyed when setting the destination */
465 if (this->graph && this->pos && this->dst && this->path2) {
466 // we can try to update
467 oldpath = this->path2;
470 if (! this->graph || !(this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist))) {
472 route_graph_update(this);
473 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
474 profile(1,"route_path_new");
479 /* Destroy what's left */
480 route_path_destroy(oldpath);
485 * @brief This will calculate all the distances stored in a route_info
487 * @param ri The route_info to calculate the distances for
488 * @param pro The projection used for this route
491 route_info_distances(struct route_info *ri, enum projection pro)
494 struct street_data *sd=ri->street;
495 /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
496 ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
497 ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
498 ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
502 * @brief This sets the current position of the route passed
504 * This will set the current position of the route passed to the street that is nearest to the
505 * passed coordinates. It also automatically updates the route.
507 * @param this The route to set the position of
508 * @param pos Coordinates to set as position
511 route_set_position(struct route *this, struct pcoord *pos)
514 route_info_free(this->pos);
516 this->pos=route_find_nearest_street(this->ms, pos);
517 dbg(1,"this->pos=%p\n", this->pos);
520 route_info_distances(this->pos, pos->pro);
522 route_path_update(this);
526 * @brief Sets a route's current position based on coordinates from tracking
528 * @param this The route to set the current position of
529 * @param tracking The tracking to get the coordinates from
532 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
535 struct route_info *ret;
538 c=tracking_get_pos(tracking);
539 ret=g_new0(struct route_info, 1);
541 printf("%s:Out of memory\n", __FUNCTION__);
545 route_info_free(this->pos);
549 ret->pos=tracking_get_segment_pos(tracking);
550 ret->street=street_data_dup(tracking_get_street_data(tracking));
551 route_info_distances(ret, projection_mg);
552 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);
553 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);
556 route_path_update(this);
560 /* Used for debuging of route_rect, what routing sees */
561 struct map_selection *route_selection;
564 * @brief Returns a single map selection
566 struct map_selection *
567 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
569 int dx,dy,sx=1,sy=1,d,m;
570 struct map_selection *sel=g_new(struct map_selection, 1);
572 printf("%s:Out of memory\n", __FUNCTION__);
575 sel->order[layer_town]=0;
576 sel->order[layer_poly]=0;
577 sel->order[layer_street]=order;
578 dbg(1,"%p %p\n", c1, c2);
583 sel->u.c_rect.lu.x=c1->x;
584 sel->u.c_rect.rl.x=c2->x;
586 sel->u.c_rect.lu.x=c2->x;
587 sel->u.c_rect.rl.x=c1->x;
591 sel->u.c_rect.lu.y=c2->y;
592 sel->u.c_rect.rl.y=c1->y;
594 sel->u.c_rect.lu.y=c1->y;
595 sel->u.c_rect.rl.y=c2->y;
602 sel->u.c_rect.lu.x-=m;
603 sel->u.c_rect.rl.x+=m;
604 sel->u.c_rect.lu.y+=m;
605 sel->u.c_rect.rl.y-=m;
611 * @brief Returns a list of map selections useable to create a route graph
613 * Returns a list of map selections useable to get a map rect from which items can be
614 * retrieved to build a route graph. The selections are a rectangle with
615 * c1 and c2 as two corners.
617 * @param c1 Corner 1 of the rectangle
618 * @param c2 Corder 2 of the rectangle
620 static struct map_selection *
621 route_calc_selection(struct coord *c1, struct coord *c2)
623 struct map_selection *ret,*sel;
624 sel=route_rect(4, c1, c2, 25, 0);
626 sel->next=route_rect(8, c1, c1, 0, 40000);
628 sel->next=route_rect(18, c1, c1, 0, 10000);
630 sel->next=route_rect(8, c2, c2, 0, 40000);
632 sel->next=route_rect(18, c2, c2, 0, 10000);
633 /* route_selection=ret; */
638 * @brief Destroys a list of map selections
640 * @param sel Start of the list to be destroyed
643 route_free_selection(struct map_selection *sel)
645 struct map_selection *next;
655 * @brief Sets the destination of a route
657 * This sets the destination of a route to the street nearest to the coordinates passed
658 * and updates the route.
660 * @param this The route to set the destination for
661 * @param dst Coordinates to set as destination
664 route_set_destination(struct route *this, struct pcoord *dst)
668 route_info_free(this->dst);
671 this->dst=route_find_nearest_street(this->ms, dst);
673 route_info_distances(this->dst, dst->pro);
675 profile(1,"find_nearest_street");
677 /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
678 route_graph_destroy(this->graph);
680 route_path_update(this);
685 * @brief Gets the route_graph_point with the specified coordinates
687 * @param this The route in which to search
688 * @param c Coordinates to search for
689 * @return The point at the specified coordinates or NULL if not found
691 static struct route_graph_point *
692 route_graph_get_point(struct route_graph *this, struct coord *c)
694 struct route_graph_point *p;
695 int hashval=HASHCOORD(c);
696 p=this->hash[hashval];
698 if (p->c.x == c->x && p->c.y == c->y)
706 * @brief Inserts a point into the route graph at the specified coordinates
708 * This will insert a point into the route graph at the coordinates passed in f.
709 * Note that the point is not yet linked to any segments.
711 * @param this The route to insert the point into
712 * @param f The coordinates at which the point should be inserted
713 * @return The point inserted or NULL on failure
715 static struct route_graph_point *
716 route_graph_add_point(struct route_graph *this, struct coord *f)
719 struct route_graph_point *p;
721 p=route_graph_get_point(this,f);
723 hashval=HASHCOORD(f);
725 printf("p (0x%x,0x%x)\n", f->x, f->y);
726 p=g_new(struct route_graph_point,1);
728 printf("%s:Out of memory\n", __FUNCTION__);
731 p->hash_next=this->hash[hashval];
732 this->hash[hashval]=p;
733 p->next=this->route_points;
740 this->route_points=p;
746 * @brief Frees all the memory used for points in the route graph passed
748 * @param this The route graph to delete all points from
751 route_graph_free_points(struct route_graph *this)
753 struct route_graph_point *curr,*next;
754 curr=this->route_points;
760 this->route_points=NULL;
761 memset(this->hash, 0, sizeof(this->hash));
765 * @brief Inserts a new segment into the route graph
767 * This function performs a check if a segment for the item specified already exists, and inserts
768 * a new segment representing this item if it does not.
770 * @param this The route graph to insert the segment into
771 * @param start The graph point which should be connected to the start of this segment
772 * @param end The graph point which should be connected to the end of this segment
773 * @param len The length of this segment
774 * @param item The item that is represented by this segment
775 * @param flags Flags for this segment
776 * @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
779 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
780 struct route_graph_point *end, int len, struct item *item,
781 int flags, int offset)
783 struct route_graph_segment *s;
785 FIXME: commented out becouse
786 it is possible to have one item with two different
790 if (item_is_equal(*item, s->item))
795 s = g_new0(struct route_graph_segment, 1);
797 printf("%s:Out of memory\n", __FUNCTION__);
801 s->start_next=start->start;
804 s->end_next=end->end;
806 dbg_assert(len >= 0);
811 s->next=this->route_segments;
812 this->route_segments=s;
814 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
818 * @brief Gets all the coordinates of an item
820 * This will get all the coordinates of the item i and return them in c,
821 * up to max coordinates. Additionally it is possible to limit the coordinates
822 * returned to all the coordinates of the item between the two coordinates
825 * @important Make shure that whatever c points to has enough memory allocated
826 * @important to hold max coordinates!
828 * @param i The item to get the coordinates of
829 * @param c Pointer to memory allocated for holding the coordinates
830 * @param max Maximum number of coordinates to return
831 * @param start First coordinate to get
832 * @param end Last coordinate to get
834 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
835 struct coord *start, struct coord *end)
841 mr=map_rect_new(i->map, NULL);
844 item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
846 rc = item_coord_get(item, &c1, 1);
847 while (rc && (c1.x != start->x || c1.y != start->y)) {
848 rc = item_coord_get(item, &c1, 1);
850 while (rc && p < max) {
852 if (c1.x == end->x && c1.y == end->y)
854 rc = item_coord_get(item, &c1, 1);
857 map_rect_destroy(mr);
862 * @brief Returns and removes one segment from a path
864 * @param path The path to take the segment from
865 * @param item The item whose segment to remove
866 * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
867 * @return The segment removed
869 static struct route_path_segment *
870 route_extract_segment_from_path(struct route_path *path, struct item *item,
873 struct route_path_segment *sp = NULL, *s;
876 if (s->offset == offset && item_is_equal(s->item,*item)) {
881 path->path = s->next;
889 item_hash_remove(path->path_hash, item);
894 * @brief Adds a segment and the end of a path
896 * @param this The path to add the segment to
897 * @param segment The segment to add
900 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
905 this->path_last->next=segment;
906 this->path_last=segment;
910 * @brief Adds a new item to a path
912 * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
913 * if the item passed is segmented - it will create exactly one segment.
915 * @param this The path to add the item to
916 * @param item The item to add
917 * @param len The length of the item
918 * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
919 * @param c Pointer to count coordinates of the item.
920 * @param cound Number of coordinates in c
921 * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
922 * @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"
925 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)
927 int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
928 struct route_path_segment *segment;
930 segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
931 segment->ncoords=ccount;
932 segment->direction=dir;
934 segment->c[idx++]=*first;
936 for (i = 0 ; i < count ; i++)
937 segment->c[idx++]=c[i];
939 for (i = 0 ; i < count ; i++)
940 segment->c[idx++]=c[count-i-1];
943 segment->c[idx++]=*last;
947 route_path_add_segment(this, segment);
951 * @brief Inserts a new item into the path
953 * This function does almost the same as "route_apth_add_item()", but identifies
954 * the item to add by a segment from the route graph. Another difference is that it "copies" the
955 * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
956 * be added to the route path, not all segments of the item.
958 * The function can be sped up by passing an old path already containing this segment in oldpath -
959 * the segment will then be extracted from this old path. Please note that in this case the direction
960 * parameter has no effect.
962 * @param this The path to add the item to
963 * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
964 * @param rgs Segment of the route graph that should be "copied" to the route path
965 * @param len Length of the item to be added
966 * @param offset Offset of rgs within the item it represents
967 * @param dir Order in which to add the coordinates. See route_path_add_item()
968 * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
971 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
972 struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
974 struct route_path_segment *segment;
976 struct coord ca[2048];
977 struct attr straight_attr;
980 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
982 segment = route_extract_segment_from_path(oldpath,
990 ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
991 segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
993 printf("%s:Out of memory\n", __FUNCTION__);
996 segment->direction=dir;
998 for (i = 0 ; i < ccnt ; i++)
1001 for (i = 0 ; i < ccnt ; i++)
1002 segment->c[i]=ca[ccnt-i-1];
1004 segment->ncoords = ccnt;
1005 segment->item=rgs->item;
1006 segment->offset = offset;
1008 segment->length=len;
1010 item_hash_insert(this->path_hash, &rgs->item, (void *)ccnt);
1012 straight_attr.type = attr_route_follow_straight;
1013 straight_attr.u.num = straight;
1015 segment->attrs = attr_generic_set_attr(segment->attrs, &straight_attr);
1017 route_path_add_segment(this, segment);
1021 * @brief Destroys all segments of a route graph
1023 * @param this The graph to destroy all segments from
1026 route_graph_free_segments(struct route_graph *this)
1028 struct route_graph_segment *curr,*next;
1029 curr=this->route_segments;
1035 this->route_segments=NULL;
1039 * @brief Destroys a route graph
1041 * @param this The route graph to be destroyed
1044 route_graph_destroy(struct route_graph *this)
1047 route_graph_free_points(this);
1048 route_graph_free_segments(this);
1054 * @brief Returns the time needed to drive len on item
1056 * @param speedlist The speedlist that should be used
1057 * @param item The item to be driven on
1058 * @param len The length to drive
1059 * @return The time needed to drive len on item
1062 route_time(int *speedlist, struct item *item, int len)
1064 if (item->type < route_item_first || item->type > route_item_last) {
1065 dbg(0,"street type %d out of range [%d,%d]", item->type, route_item_first, route_item_last);
1068 return len*36/speedlist[item->type-route_item_first];
1072 * @brief Returns the "costs" of driving len on item
1074 * @param speedlist The speedlist that should be used
1075 * @param item The item to be driven on
1076 * @param len The length to drive
1077 * @return The "costs" needed to drive len on item
1080 route_value(int *speedlist, struct item *item, int len)
1084 printf("len=%d\n", len);
1086 dbg_assert(len >= 0);
1087 ret=route_time(speedlist, item, len);
1088 dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1093 * @brief Adds an item to the route graph
1095 * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1098 * @param this The route graph to add to
1099 * @param item The item to add
1102 route_process_street_graph(struct route_graph *this, struct item *item)
1109 struct route_graph_point *s_pnt,*e_pnt;
1116 if (item_coord_get(item, &l, 1)) {
1117 if (item_attr_get(item, attr_flags, &attr)) {
1119 if (flags & AF_SEGMENTED)
1122 s_pnt=route_graph_add_point(this,&l);
1124 while (item_coord_get(item, &c, 1)) {
1125 len+=transform_distance(map_projection(item->map), &l, &c);
1128 e_pnt=route_graph_add_point(this,&l);
1129 dbg_assert(len >= 0);
1130 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1135 isseg = item_coord_is_node(item);
1136 rc = item_coord_get(item, &c, 1);
1138 len+=transform_distance(map_projection(item->map), &l, &c);
1141 e_pnt=route_graph_add_point(this,&l);
1142 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1144 s_pnt=route_graph_add_point(this,&l);
1149 e_pnt=route_graph_add_point(this,&l);
1150 dbg_assert(len >= 0);
1152 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1158 * @brief Compares the costs of reaching the destination from two points on
1160 * @important Do not pass anything other than route_graph_points in v1 and v2!
1164 * @return The additional costs of v1 compared to v2 (may be negative)
1167 compare(void *v1, void *v2)
1169 struct route_graph_point *p1=v1;
1170 struct route_graph_point *p2=v2;
1173 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1175 return p1->value-p2->value;
1179 * @brief Calculates the routing costs for each point
1181 * This function is the heart of routing. It assigns each point in the route graph a
1182 * cost at which one can reach the destination from this point on. Additionally it assigns
1183 * each point a segment one should follow from this point on to reach the destination at the
1186 * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1187 * at this algorithm.
1190 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
1192 struct route_graph_point *p_min,*end=NULL;
1193 struct route_graph_segment *s;
1194 int min,new,old,val;
1195 struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1196 struct street_data *sd=dst->street;
1198 heap = fh_makeheap();
1199 fh_setcmp(heap, compare);
1201 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 */
1202 end=route_graph_get_point(this, &sd->c[0]);
1203 dbg_assert(end != 0);
1204 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1205 end->el=fh_insert(heap, end);
1208 if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1209 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1210 dbg_assert(end != 0);
1211 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1212 end->el=fh_insert(heap, end);
1215 dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1217 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1218 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1222 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);
1223 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1225 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1226 val=route_value(speedlist, &s->item, s->len);
1228 val+=val*2*street_route_contained(s->str->segid);
1232 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);
1233 if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1238 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1239 s->end->el=fh_insert(heap, s->end);
1241 printf("el new=%p\n", s->end->el);
1245 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1246 fh_replacedata(heap, s->end->el, s->end);
1254 while (s) { /* Doing the same as above with the segments leading towards our point */
1255 val=route_value(speedlist, &s->item, s->len);
1258 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);
1259 if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1260 old=s->start->value;
1261 s->start->value=new;
1263 if (! s->start->el) {
1265 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1266 s->start->el=fh_insert(heap, s->start);
1268 printf("el new=%p\n", s->start->el);
1272 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1273 fh_replacedata(heap, s->start->el, s->start);
1281 fh_deleteheap(heap);
1285 * @brief Starts an "offroad" path
1287 * This starts a path that is not located on a street. It creates a new route path
1288 * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1290 * @param this Not used
1291 * @param pos The starting position for the new path
1292 * @param dst The destination of the new path
1293 * @param dir Not used
1294 * @return The new path
1296 static struct route_path *
1297 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1299 struct route_path *ret;
1301 ret=g_new0(struct route_path, 1);
1302 ret->path_hash=item_hash_new();
1303 route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1309 * @brief Creates a new "trivial" route
1311 * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1312 * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1314 * @param this The route graph to place the route on
1315 * @param pos The starting position for the new path
1316 * @param dst The destination of the new path
1317 * @param dir Direction of the coordinates to be added
1318 * @return The new path
1320 static struct route_path *
1321 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1323 struct street_data *sd=pos->street;
1324 struct route_path *ret;
1327 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1328 return route_path_new_offroad(this, pos, dst, dir);
1330 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1331 return route_path_new_offroad(this, pos, dst, dir);
1333 ret=g_new0(struct route_path, 1);
1334 ret->path_hash=item_hash_new();
1336 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1338 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);
1340 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);
1342 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1347 * @brief Calculates of two coordinates' connection
1349 * This function calculates the angle between coordinates, with north = 0
1352 * %FIXME This is a duplicate of road_angle() in navigation.c - combine them?
1354 * @param c1 Coordinate 1
1355 * @param c2 Coordinate 2
1356 * @param dir Set to true if c1 is the prior, and c2 the later coordinate.
1357 * @return The angle of the coordinate's connection
1360 route_road_angle(struct coord *c1, struct coord *c2, int dir)
1362 int ret=transform_get_angle_delta(c1, c2, dir);
1363 dbg(1, "road_angle(0x%x,0x%x - 0x%x,0x%x)=%d\n", c1->x, c1->y, c2->x, c2->y, ret);
1368 * @brief Checks if entering one segment from another is a "straight" road
1370 * This checks if one can enter seg_to from seg_from by driving "straight" - i.e.
1371 * if seg_to is the segment you can drive to from seg_from by steering less than
1372 * all to all other segments.
1374 * This function returns true on failure, so we don't create maneuvers on every error.
1376 * @param seg_from Segment we are driving from
1377 * @param seg_to Segment we are driving to
1378 * @return True if driving from seg_from to seg_to is "straight", false otherwise
1381 route_check_straight(struct route_graph_segment *seg_from, struct route_graph_segment *seg_to)
1383 struct route_graph_segment *curr;
1384 struct route_graph_point *conn;
1385 int from_angle, to_angle, curr_angle, angle_diff;
1387 struct coord ca[2048];
1389 if ((seg_from->end == seg_to->start) || (seg_from->end == seg_to->end)) {
1390 ccnt = get_item_seg_coords(&seg_from->item, ca, 2047, &seg_from->start->c, &seg_from->end->c);
1391 from_angle = route_road_angle(&ca[ccnt-2], &ca[ccnt-1],1);
1393 conn = seg_from->end;
1394 } else if ((seg_from->start == seg_to->start) || (seg_from->start == seg_to->end)) {
1395 ccnt = get_item_seg_coords(&seg_from->item, ca, 2, &seg_from->start->c, &seg_from->end->c);
1396 from_angle = route_road_angle(&ca[1], &ca[0],1);
1398 conn = seg_from->start;
1405 if (seg_to->end == conn) {
1406 ccnt = get_item_seg_coords(&seg_to->item, ca, 2047, &seg_to->start->c, &seg_to->end->c);
1407 to_angle = route_road_angle(&ca[ccnt-1], &ca[ccnt-2],1);
1409 ccnt = get_item_seg_coords(&seg_to->item, ca, 2, &seg_to->start->c, &seg_to->end->c);
1410 to_angle = route_road_angle(&ca[0], &ca[1],1);
1414 angle_diff = from_angle - to_angle;
1415 if (angle_diff < 0) {
1421 while (curr != NULL) {
1423 curr = curr->start_next;
1427 ccnt = get_item_seg_coords(&curr->item, ca, 2, &curr->start->c, &curr->end->c);
1428 curr_angle = route_road_angle(&ca[0], &ca[1], 1);
1430 curr_angle = from_angle - curr_angle;
1432 if (curr_angle < 0) {
1437 if (curr_angle < angle_diff) {
1441 curr = curr->start_next;
1445 while (curr != NULL) {
1447 curr = curr->end_next;
1451 ccnt = get_item_seg_coords(&curr->item, ca, 2047, &curr->start->c, &curr->end->c);
1452 curr_angle = route_road_angle(&ca[ccnt-1], &ca[ccnt-2], 1);
1454 curr_angle = from_angle - curr_angle;
1456 if (curr_angle < 0) {
1460 if (curr_angle < angle_diff) {
1464 curr = curr->end_next;
1471 * @brief Creates a new route path
1473 * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1474 * make shure to run route_graph_flood() after changing the destination before using this function.
1476 * @param this The route graph to create the route from
1477 * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1478 * @param pos The starting position of the route
1479 * @param dst The destination of the route
1480 * @param speedlist The speedlist to use
1481 * @return The new route path
1483 static struct route_path *
1484 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1486 struct route_graph_point *start1=NULL,*start2=NULL,*start;
1487 struct route_graph_segment *s=NULL;
1488 struct route_graph_segment *lastseg = NULL;
1493 int time=0,hr,min,sec
1495 unsigned int val1=0xffffffff,val2=0xffffffff;
1496 struct street_data *sd=pos->street;
1497 struct route_path *ret;
1499 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 */
1500 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1501 return route_path_new_trivial(this, pos, dst, -1);
1503 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1504 return route_path_new_trivial(this, pos, dst, 1);
1507 if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1508 start1=route_graph_get_point(this, &sd->c[0]);
1511 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1512 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1514 if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1515 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1518 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1519 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1521 dbg(1,"val1=%d val2=%d\n", val1, val2);
1523 val1=start1->start->start->value;
1524 val2=start2->end->end->value;
1526 ret=g_new0(struct route_path, 1);
1528 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1529 if (start1 && (val1 < val2)) {
1531 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1535 route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1537 printf("no route found, pos blocked\n");
1541 ret->path_hash=item_hash_new();
1542 while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1545 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1551 is_straight = route_check_straight(lastseg,s);
1556 if (s->start == start) {
1557 route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight);
1560 route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight);
1567 dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1568 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);
1569 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 */
1570 route_path_add_item(ret, &sd->item, dst->lenneg, &dst->lp, sd->c, dst->pos+1, NULL, -1);
1571 } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1572 route_path_add_item(ret, &sd->item, dst->lenpos, &dst->lp, sd->c+dst->pos+1, sd->count-dst->pos-1, NULL, 1);
1574 printf("no route found\n");
1575 route_path_destroy(ret);
1579 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1580 dbg(1, "%d segments\n", segs);
1585 * @brief Builds a new route graph from a mapset
1587 * This function builds a new route graph from a map. Please note that this function does not
1588 * add any routing information to the route graph - this has to be done via the route_graph_flood()
1591 * The function does not create a graph covering the whole map, but only covering the rectangle
1592 * between c1 and c2.
1594 * @param ms The mapset to build the route graph from
1595 * @param c1 Corner 1 of the rectangle to use from the map
1596 * @param c2 Corner 2 of the rectangle to use from the map
1597 * @return The new route graph.
1599 static struct route_graph *
1600 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
1602 struct route_graph *ret=g_new0(struct route_graph, 1);
1603 struct map_selection *sel;
1604 struct mapset_handle *h;
1605 struct map_rect *mr;
1610 printf("%s:Out of memory\n", __FUNCTION__);
1613 sel=route_calc_selection(c1, c2);
1615 while ((m=mapset_next(h,1))) {
1616 mr=map_rect_new(m, sel);
1619 while ((item=map_rect_get_item(mr))) {
1620 if (item->type >= type_street_0 && item->type <= type_ferry) {
1621 route_process_street_graph(ret, item);
1624 map_rect_destroy(mr);
1627 route_free_selection(sel);
1633 * @brief Updates the route graph
1635 * This updates the route graph after settings in the route have changed. It also
1636 * adds routing information afterwards by calling route_graph_flood().
1638 * @param this The route to update the graph for
1641 route_graph_update(struct route *this)
1643 route_graph_destroy(this->graph);
1644 profile(1,"graph_free");
1645 this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
1646 profile(1,"route_graph_build");
1647 route_graph_flood(this->graph, this->dst, this->speedlist);
1648 profile(1,"route_graph_flood");
1653 * @brief Gets street data for an item
1655 * @param item The item to get the data for
1656 * @return Street data for the item
1658 struct street_data *
1659 street_get_data (struct item *item)
1662 struct coord c[maxcount];
1664 struct street_data *ret;
1667 while (count < maxcount) {
1668 if (!item_coord_get(item, &c[count], 1))
1672 if (count >= maxcount) {
1673 dbg(0, "count=%d maxcount=%d id_hi=0x%x id_lo=0x%x\n", count, maxcount, item->id_hi, item->id_lo);
1674 if (item_attr_get(item, attr_debug, &attr))
1675 dbg(0,"debug='%s'\n", attr.u.str);
1677 dbg_assert(count < maxcount);
1678 ret=g_malloc(sizeof(struct street_data)+count*sizeof(struct coord));
1681 if (item_attr_get(item, attr_flags, &attr))
1682 ret->flags=attr.u.num;
1685 memcpy(ret->c, c, count*sizeof(struct coord));
1691 * @brief Copies street data
1693 * @param orig The street data to copy
1694 * @return The copied street data
1696 struct street_data *
1697 street_data_dup(struct street_data *orig)
1699 struct street_data *ret;
1700 int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1703 memcpy(ret, orig, size);
1709 * @brief Frees street data
1711 * @param sd Street data to be freed
1714 street_data_free(struct street_data *sd)
1720 * @brief Finds the nearest street to a given coordinate
1722 * @param ms The mapset to search in for the street
1723 * @param pc The coordinate to find a street nearby
1724 * @return The nearest street
1726 static struct route_info *
1727 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1729 struct route_info *ret=NULL;
1731 struct map_selection *sel;
1732 int dist,mindist=0,pos;
1733 struct mapset_handle *h;
1735 struct map_rect *mr;
1738 struct street_data *sd;
1745 * This is not correct for two reasons:
1746 * - You may need to go back first
1747 * - Currently we allow mixing of mapsets
1749 sel = route_rect(18, &c, &c, 0, max_dist);
1751 while ((m=mapset_next(h,1))) {
1754 if (map_projection(m) != pc->pro) {
1755 transform_to_geo(pc->pro, &c, &g);
1756 transform_from_geo(map_projection(m), &g, &c);
1758 mr=map_rect_new(m, sel);
1761 while ((item=map_rect_get_item(mr))) {
1762 if (item->type >= type_street_0 && item->type <= type_ferry) {
1763 sd=street_get_data(item);
1764 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1765 if (!ret || dist < mindist) {
1767 street_data_free(ret->street);
1770 ret=g_new(struct route_info, 1);
1772 printf("%s:Out of memory\n", __FUNCTION__);
1780 dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1782 street_data_free(sd);
1785 map_rect_destroy(mr);
1788 map_selection_destroy(sel);
1794 * @brief Destroys a route_info
1796 * @param info The route info to be destroyed
1799 route_info_free(struct route_info *inf)
1802 street_data_free(inf->street);
1810 * @brief Returns street data for a route info
1812 * @param rinf The route info to return the street data for
1813 * @return Street data for the route info
1815 struct street_data *
1816 route_info_street(struct route_info *rinf)
1818 return rinf->street;
1822 struct route_crossings *
1823 route_crossings_get(struct route *this, struct coord *c)
1825 struct route_point *pnt;
1826 struct route_segment *seg;
1828 struct route_crossings *ret;
1830 pnt=route_graph_get_point(this, c);
1833 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1835 seg=seg->start_next;
1839 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1843 ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1844 ret->count=crossings;
1850 struct map_rect_priv {
1851 struct route_info_handle *ri;
1852 enum attr_type attr_next;
1854 struct map_priv *mpriv;
1857 unsigned int last_coord;
1858 struct route_path_segment *seg,*seg_next;
1859 struct route_graph_point *point;
1860 struct route_graph_segment *rseg;
1865 rm_coord_rewind(void *priv_data)
1867 struct map_rect_priv *mr = priv_data;
1872 rm_attr_rewind(void *priv_data)
1874 struct map_rect_priv *mr = priv_data;
1875 mr->attr_next = attr_street_item;
1879 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1881 struct map_rect_priv *mr = priv_data;
1882 struct route_path_segment *seg=mr->seg;
1883 struct route *route=mr->mpriv->route;
1884 attr->type=attr_type;
1885 switch (attr_type) {
1887 while (mr->attr_next != attr_none) {
1888 if (rm_attr_get(priv_data, mr->attr_next, attr))
1892 case attr_street_item:
1893 mr->attr_next=attr_route_follow_straight;
1894 if (seg && seg->item.map)
1895 attr->u.item=&seg->item;
1899 case attr_route_follow_straight:
1900 mr->attr_next=attr_direction;
1902 return attr_generic_get_attr(seg->attrs,NULL,attr_route_follow_straight,attr,NULL);
1905 case attr_direction:
1906 mr->attr_next=attr_length;
1908 attr->u.num=seg->direction;
1914 attr->u.num=seg->length;
1916 attr->u.num=mr->length;
1917 mr->attr_next=attr_time;
1920 mr->attr_next=attr_none;
1922 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1927 mr->attr_next=attr_none;
1930 mr->attr_next=attr_none;
1931 attr->type=attr_none;
1938 rm_coord_get(void *priv_data, struct coord *c, int count)
1940 struct map_rect_priv *mr = priv_data;
1941 struct route_path_segment *seg = mr->seg;
1943 struct route *r = mr->mpriv->route;
1944 enum projection pro = route_projection(r);
1948 for (i=0; i < count; i++) {
1949 if (mr->last_coord >= seg->ncoords)
1951 if (i >= seg->ncoords)
1953 if (pro != projection_mg)
1954 transform_from_to(&seg->c[mr->last_coord++], pro,
1955 &c[i],projection_mg);
1957 c[i] = seg->c[mr->last_coord++];
1960 dbg(1,"return %d\n",rc);
1964 static struct item_methods methods_route_item = {
1972 rp_attr_rewind(void *priv_data)
1974 struct map_rect_priv *mr = priv_data;
1975 mr->attr_next = attr_label;
1979 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1981 struct map_rect_priv *mr = priv_data;
1982 struct route_graph_point *p = mr->point;
1983 if (mr->item.type != type_rg_point)
1985 switch (attr_type) {
1987 while (mr->attr_next != attr_none) {
1988 if (rp_attr_get(priv_data, mr->attr_next, attr))
1993 attr->type = attr_label;
1996 if (p->value != INT_MAX)
1997 mr->str=g_strdup_printf("%d", p->value);
1999 mr->str=g_strdup("-");
2000 attr->u.str = mr->str;
2001 mr->attr_next=attr_none;
2004 attr->type = attr_debug;
2007 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
2008 attr->u.str = mr->str;
2009 mr->attr_next=attr_none;
2012 mr->attr_next=attr_none;
2013 attr->type=attr_none;
2019 rp_coord_get(void *priv_data, struct coord *c, int count)
2021 struct map_rect_priv *mr = priv_data;
2022 struct route_graph_point *p = mr->point;
2023 struct route_graph_segment *seg = mr->rseg;
2025 struct route *r = mr->mpriv->route;
2026 enum projection pro = route_projection(r);
2028 for (i=0; i < count; i++) {
2029 if (mr->item.type == type_rg_point) {
2030 if (mr->last_coord >= 1)
2032 if (pro != projection_mg)
2033 transform_from_to(&p->c, pro,
2034 &c[i],projection_mg);
2038 if (mr->last_coord >= 2)
2041 if (seg->end->seg == seg)
2046 if (pro != projection_mg)
2047 transform_from_to(&seg->end->c, pro,
2048 &c[i],projection_mg);
2052 if (pro != projection_mg)
2053 transform_from_to(&seg->start->c, pro,
2054 &c[i],projection_mg);
2056 c[i] = seg->start->c;
2065 static struct item_methods methods_point_item = {
2073 rm_destroy(struct map_priv *priv)
2078 static struct map_rect_priv *
2079 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2081 struct map_rect_priv * mr;
2083 if (! route_get_pos(priv->route))
2085 if (! route_get_dst(priv->route))
2087 if (! priv->route->path2)
2089 mr=g_new0(struct map_rect_priv, 1);
2091 mr->item.priv_data = mr;
2092 mr->item.type = type_street_route;
2093 mr->item.meth = &methods_route_item;
2094 mr->seg_next=priv->route->path2->path;
2098 static struct map_rect_priv *
2099 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2101 struct map_rect_priv * mr;
2103 if (! priv->route->graph || ! priv->route->graph->route_points)
2105 mr=g_new0(struct map_rect_priv, 1);
2107 mr->item.priv_data = mr;
2108 mr->item.type = type_rg_point;
2109 mr->item.meth = &methods_point_item;
2114 rm_rect_destroy(struct map_rect_priv *mr)
2121 static struct item *
2122 rp_get_item(struct map_rect_priv *mr)
2124 struct route *r = mr->mpriv->route;
2125 struct route_graph_point *p = mr->point;
2126 struct route_graph_segment *seg = mr->rseg;
2128 if (mr->item.type == type_rg_point) {
2130 p = r->graph->route_points;
2136 rm_coord_rewind(mr);
2140 mr->item.type = type_rg_segment;
2143 seg=r->graph->route_segments;
2149 rm_coord_rewind(mr);
2157 static struct item *
2158 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2160 struct item *ret=NULL;
2162 ret=rp_get_item(mr);
2167 static struct item *
2168 rm_get_item(struct map_rect_priv *mr)
2170 struct route *r = mr->mpriv->route;
2171 struct route_path_segment *seg = mr->seg;
2172 dbg(1,"enter\n", mr->pos);
2174 mr->seg=mr->seg_next;
2177 mr->seg_next=mr->seg->next;
2184 static struct item *
2185 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2187 struct item *ret=NULL;
2189 ret=rm_get_item(mr);
2193 static struct map_methods route_meth = {
2206 static struct map_methods route_graph_meth = {
2220 route_toggle_routegraph_display(struct route *route)
2222 if (route->flags & RF_SHOWGRAPH) {
2223 route->flags &= ~RF_SHOWGRAPH;
2225 route->flags |= RF_SHOWGRAPH;
2229 static struct map_priv *
2230 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2232 struct map_priv *ret;
2233 struct attr *route_attr;
2235 route_attr=attr_search(attrs, NULL, attr_route);
2238 ret=g_new0(struct map_priv, 1);
2240 *meth=route_graph_meth;
2243 ret->route=route_attr->u.route;
2248 static struct map_priv *
2249 route_map_new(struct map_methods *meth, struct attr **attrs)
2251 return route_map_new_helper(meth, attrs, 0);
2254 static struct map_priv *
2255 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2257 return route_map_new_helper(meth, attrs, 1);
2261 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2264 *map=map_new((struct attr*[]){
2265 &(struct attr){attr_type,{type}},
2266 &(struct attr){attr_route,.u.route=this_},
2267 &(struct attr){attr_data,{""}},
2268 &(struct attr){attr_description,{description}},
2274 route_get_map(struct route *this_)
2276 return route_get_map_helper(this_, &this_->map, "route","Route");
2281 route_get_graph_map(struct route *this_)
2283 return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2287 route_set_projection(struct route *this_, enum projection pro)
2294 plugin_register_map_type("route", route_map_new);
2295 plugin_register_map_type("route_graph", route_graph_map_new);