navit/navit/route.c

   1 /**
   2  * Navit, a modular navigation system.
   3  * Copyright (C) 2005-2008 Navit Team
   4  *
   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.
   8  *
   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.
  13  *
  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.
  18  */
  19
  20 /** @file
  21  * @brief Contains code related to finding a route from a position to a destination
  22  *
  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.
  29  *
  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
  32  * points.
  33  *
  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.
  37  *
  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.
  40  */
  41
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #if 0
  46 #include <math.h>
  47 #include <assert.h>
  48 #include <unistd.h>
  49 #include <sys/time.h>
  50 #endif
  51 #include <glib.h>
  52 #include "config.h"
  53 #include "debug.h"
  54 #include "profile.h"
  55 #include "coord.h"
  56 #include "projection.h"
  57 #include "item.h"
  58 #include "map.h"
  59 #include "mapset.h"
  60 #include "route.h"
  61 #include "track.h"
  62 #include "point.h"
  63 #include "graphics.h"
  64 #include "transform.h"
  65 #include "plugin.h"
  66 #include "fib.h"
  67
  68
  69 struct map_priv {
  70         struct route *route;
  71 };
  72
  73 int debug_route=0;
  74
  75 /**
  76  * @brief A point in the route graph
  77  *
  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).
  80  */
  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
  89                                                                                   *  least costs */
  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 */
  94 };
  95
  96 /**
  97  * @brief A segment in the route graph
  98  *
  99  * This is a segment in the route graph. A segment represents a driveable way.
 100  */
 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. */
 110         int flags;
 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 */
 116 };
 117
 118 /**
 119  * @brief A segment in the route path
 120  *
 121  * This is a segment in the route path.
 122  */
 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
 130                                                                                  *  means reverse. */
 131         unsigned ncoords;                                       /**< How many coordinates does this segment have? */
 132         struct coord c[0];                                      /**< Pointer to the ncoords coordinates of this segment */
 133         /* WARNING: There will be coordinates following here, so do not create new fields after c! */
 134 };
 135
 136 /**
 137  * @brief Usually represents a destination or position
 138  *
 139  * This struct usually represents a destination or position
 140  */
 141 struct route_info {
 142         struct coord c;                  /**< The actual destination / position */
 143         struct coord lp;                 /**< The nearest point on a street to c */
 144         int pos;                                 /**< The position of lp within the coords of the street */
 145         int lenpos;                      /**< Distance between lp and the end of the street */
 146         int lenneg;                      /**< Distance between lp and the start of the street */
 147         int lenextra;                    /**< Distance between lp and c */
 148
 149         struct street_data *street; /**< The street lp is on */
 150 };
 151
 152 /**
 153  * @brief A complete route path
 154  *
 155  * This structure describes a whole routing path
 156  */
 157 struct route_path {
 158         struct route_path_segment *path;                        /**< The first segment in the path, i.e. the segment one should
 159                                                                                                  *  drive in next */
 160         struct route_path_segment *path_last;           /**< The last segment in the path */
 161         /* XXX: path_hash is not necessery now */
 162         struct item_hash *path_hash;                            /**< A hashtable of all the items represented by this route's segements */
 163 };
 164
 165 #define RF_FASTEST      (1<<0)
 166 #define RF_SHORTEST     (1<<1)
 167 #define RF_AVOIDHW      (1<<2)
 168 #define RF_AVOIDPAID    (1<<3)
 169 #define RF_LOCKONROAD   (1<<4)
 170 #define RF_SHOWGRAPH    (1<<5)
 171
 172 /**
 173  * @brief A complete route
 174  *
 175  * This struct holds all information about a route.
 176  */
 177 struct route {
 178         int version;                            /**< Counts how many times this route got updated */
 179         struct mapset *ms;                      /**< The mapset this route is built upon */
 180         unsigned flags;
 181         struct route_info *pos;         /**< Current position within this route */
 182         struct route_info *dst;         /**< Destination of the route */
 183
 184         struct route_graph *graph;      /**< Pointer to the route graph */
 185         struct route_path *path2;       /**< Pointer to the route path */
 186         struct map *map;
 187         struct map *graph_map;
 188         int destination_distance;       /**< Distance to the destination at which the destination is considered "reached" */
 189         int speedlist[route_item_last-route_item_first+1];      /**< The speedlist for this route */
 190 };
 191
 192 /**
 193  * @brief A complete route graph
 194  *
 195  * This structure describes a whole routing graph
 196  */
 197 struct route_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 */
 202 };
 203
 204 #define HASHCOORD(c) ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
 205
 206 /**
 207  * @brief Iterator to iterate through all route graph segments in a route graph point
 208  *
 209  * This structure can be used to iterate through all route graph segments connected to a
 210  * route graph point. Use this with the rp_iterator_* functions.
 211  */
 212 struct route_graph_point_iterator {
 213         struct route_graph_point *p;            /**< The route graph point whose segments should be iterated */
 214         int end;                                                        /**< Indicates if we have finished iterating through the "start" segments */
 215         struct route_graph_segment *next;       /**< The next segment to be returned */
 216 };
 217
 218 static struct route_info * route_find_nearest_street(struct mapset *ms, struct pcoord *c);
 219 static struct route_graph_point *route_graph_get_point(struct route_graph *this, struct coord *c);
 220 static void route_graph_update(struct route *this);
 221 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);
 222 static void route_process_street_graph(struct route_graph *this, struct item *item);
 223 static void route_graph_destroy(struct route_graph *this);
 224 static void route_path_update(struct route *this);
 225
 226 /**
 227  * @brief Returns the projection used for this route
 228  *
 229  * @param route The route to return the projection for
 230  * @return The projection used for this route
 231  */
 232 static enum projection route_projection(struct route *route)
 233 {
 234         struct street_data *street;
 235         street = route->pos ? route->pos->street : route->dst->street;
 236         return map_projection(street->item.map);
 237 }
 238
 239 /**
 240  * @brief Creates a new graph point iterator
 241  *
 242  * This function creates a new route graph point iterator, that can be used to
 243  * iterate through all segments connected to the point.
 244  *
 245  * @param p The route graph point to create the iterator from
 246  * @return A new iterator.
 247  */
 248 static struct route_graph_point_iterator
 249 rp_iterator_new(struct route_graph_point *p)
 250 {
 251         struct route_graph_point_iterator it;
 252
 253         it.p = p;
 254         if (p->start) {
 255                 it.next = p->start;
 256                 it.end = 0;
 257         } else {
 258                 it.next = p->end;
 259                 it.end = 1;
 260         }
 261
 262         return it;
 263 }
 264
 265 /**
 266  * @brief Gets the next segment connected to a route graph point from an iterator
 267  *
 268  * @param it The route graph point iterator to get the segment from
 269  * @return The next segment or NULL if there are no more segments
 270  */
 271 static struct route_graph_segment
 272 *rp_iterator_next(struct route_graph_point_iterator *it)
 273 {
 274         struct route_graph_segment *ret;
 275
 276         ret = it->next;
 277         if (!ret) {
 278                 return NULL;
 279         }
 280
 281         if (!it->end) {
 282                 if (ret->start_next) {
 283                         it->next = ret->start_next;
 284                 } else {
 285                         it->next = it->p->end;
 286                         it->end = 1;
 287                 }
 288         } else {
 289                 it->next = ret->end_next;
 290         }
 291
 292         return ret;
 293 }
 294
 295 /**
 296  * @brief Destroys a route_path
 297  *
 298  * @param this The route_path to be destroyed
 299  */
 300 static void
 301 route_path_destroy(struct route_path *this)
 302 {
 303         struct route_path_segment *c,*n;
 304         if (! this)
 305                 return;
 306         if (this->path_hash) {
 307                 item_hash_destroy(this->path_hash);
 308                 this->path_hash=NULL;
 309         }
 310         c=this->path;
 311         while (c) {
 312                 n=c->next;
 313                 g_free(c);
 314                 c=n;
 315         }
 316         g_free(this);
 317 }
 318
 319 /**
 320  * @brief Creates a completely new route structure
 321  *
 322  * @param attrs Not used
 323  * @return The newly created route
 324  */
 325 struct route *
 326 route_new(struct attr *parent, struct attr **attrs)
 327 {
 328         struct route *this=g_new0(struct route, 1);
 329         struct attr dest_attr;
 330
 331         if (!this) {
 332                 printf("%s:Out of memory\n", __FUNCTION__);
 333                 return NULL;
 334         }
 335
 336         if (attr_generic_get_attr(attrs, NULL, attr_destination_distance, &dest_attr, NULL)) {
 337                 this->destination_distance = dest_attr.u.num;
 338         } else {
 339                 this->destination_distance = 50; // Default value
 340         }
 341
 342         return this;
 343 }
 344
 345 /**
 346  * @brief Sets the mapset of the route passwd
 347  *
 348  * @param this The route to set the mapset for
 349  * @param ms The mapset to set for this route
 350  */
 351 void
 352 route_set_mapset(struct route *this, struct mapset *ms)
 353 {
 354         this->ms=ms;
 355 }
 356
 357 /**
 358  * @brief Returns the mapset of the route passed
 359  *
 360  * @param this The route to get the mapset of
 361  * @return The mapset of the route passed
 362  */
 363 struct mapset *
 364 route_get_mapset(struct route *this)
 365 {
 366         return this->ms;
 367 }
 368
 369 /**
 370  * @brief Returns the current position within the route passed
 371  *
 372  * @param this The route to get the position for
 373  * @return The position within the route passed
 374  */
 375 struct route_info *
 376 route_get_pos(struct route *this)
 377 {
 378         return this->pos;
 379 }
 380
 381 /**
 382  * @brief Returns the destination of the route passed
 383  *
 384  * @param this The route to get the destination for
 385  * @return The destination of the route passed
 386  */
 387 struct route_info *
 388 route_get_dst(struct route *this)
 389 {
 390         return this->dst;
 391 }
 392
 393 /**
 394  * @brief Returns the speedlist of the route passed
 395  *
 396  * @param this The route to get the speedlist for
 397  * @return The speedlist of the route passed
 398  */
 399 int *
 400 route_get_speedlist(struct route *this)
 401 {
 402         return this->speedlist;
 403 }
 404
 405 /**
 406  * @brief Checks if the path is calculated for the route passed
 407  *
 408  * @param this The route to check
 409  * @return True if the path is calculated, false if not
 410  */
 411 int
 412 route_get_path_set(struct route *this)
 413 {
 414         return this->path2 != NULL;
 415 }
 416
 417 /**
 418  * @brief Sets the driving speed for a certain itemtype
 419  *
 420  * @param this The route to set the speed for
 421  * @param type The itemtype to set the speed for
 422  * @param value The speed that should be set
 423  * @return True on success, false if the itemtype does not exist
 424  */
 425 int
 426 route_set_speed(struct route *this, enum item_type type, int value)
 427 {
 428         if (type < route_item_first || type > route_item_last) {
 429                 dbg(0,"street type %d out of range [%d,%d]", type, route_item_first, route_item_last);
 430                 return 0;
 431         }
 432         this->speedlist[type-route_item_first]=value;
 433         return 1;
 434 }
 435
 436 /**
 437  * @brief Checks if the route passed contains a certain item within the route path
 438  *
 439  * This function checks if a certain items exists in the path that navit will guide
 440  * the user to his destination. It does *not* check if this item exists in the route
 441  * graph!
 442  *
 443  * @param this The route to check for this item
 444  * @param item The item to search for
 445  * @return True if the item was found, false if the item was not found or the route was not calculated
 446  */
 447 int
 448 route_contains(struct route *this, struct item *item)
 449 {
 450         if (! this->path2 || !this->path2->path_hash)
 451                 return 0;
 452         return  (int)item_hash_lookup(this->path2->path_hash, item);
 453 }
 454
 455 /**
 456  * @brief Checks if the current position in a route is a certain item
 457  *
 458  * @param this The route to check for this item
 459  * @param item The item to search for
 460  * @return True if the current position is this item, false otherwise
 461  */
 462 int
 463 route_pos_contains(struct route *this, struct item *item)
 464 {
 465         if (! this->pos)
 466                 return 0;
 467         return item_is_equal(this->pos->street->item, *item);
 468 }
 469
 470 /**
 471  * @brief Checks if a route has reached its destination
 472  *
 473  * @param this The route to be checked
 474  * @return True if the destination is "reached", false otherwise.
 475  */
 476 int
 477 route_destination_reached(struct route *this)
 478 {
 479         struct street_data *sd = NULL;
 480
 481         if (!this->pos)
 482                 return 0;
 483
 484         sd = this->pos->street;
 485
 486         if (!this->path2) {
 487                 return 0;
 488         }
 489
 490         if (!item_is_equal(this->pos->street->item, this->dst->street->item)) {
 491                 return 0;
 492         }
 493
 494         if ((sd->flags & AF_ONEWAY) && (this->pos->lenneg >= this->dst->lenneg)) { // We would have to drive against the one-way road
 495                 return 0;
 496         }
 497         if ((sd->flags & AF_ONEWAYREV) && (this->pos->lenpos >= this->dst->lenpos)) {
 498                 return 0;
 499         }
 500
 501         if (transform_distance(route_projection(this), &this->pos->c, &this->dst->lp) > this->destination_distance) {
 502                 return 0;
 503         }
 504
 505         return 1;
 506 }
 507
 508 /**
 509  * @brief Updates the route graph and the route path if something changed with the route
 510  *
 511  * This will update the route graph and the route path of the route if some of the
 512  * route's settings (destination, position) have changed.
 513  *
 514  * @attention For this to work the route graph has to be destroyed if the route's
 515  * @attention destination is changed somewhere!
 516  *
 517  * @param this The route to update
 518  */
 519 static void
 520 route_path_update(struct route *this)
 521 {
 522         struct route_path *oldpath = NULL;
 523         if (! this->pos || ! this->dst) {
 524                 route_path_destroy(this->path2);
 525                 this->path2 = NULL;
 526                 return;
 527         }
 528         /* the graph is destroyed when setting the destination */
 529         if (this->graph && this->pos && this->dst && this->path2) {
 530                 // we can try to update
 531                 oldpath = this->path2;
 532                 this->path2 = NULL;
 533         }
 534         if (! this->graph || !(this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist))) {
 535                 profile(0,NULL);
 536                 route_graph_update(this);
 537                 this->path2=route_path_new(this->graph, oldpath, this->pos, this->dst, this->speedlist);
 538                 profile(1,"route_path_new");
 539                 profile(0,"end");
 540         }
 541
 542         if (oldpath) {
 543                 /* Destroy what's left */
 544                 route_path_destroy(oldpath);
 545         }
 546 }
 547
 548 /**
 549  * @brief This will calculate all the distances stored in a route_info
 550  *
 551  * @param ri The route_info to calculate the distances for
 552  * @param pro The projection used for this route
 553  */
 554 static void
 555 route_info_distances(struct route_info *ri, enum projection pro)
 556 {
 557         int npos=ri->pos+1;
 558         struct street_data *sd=ri->street;
 559         /* 0 1 2 X 3 4 5 6 pos=2 npos=3 count=7 0,1,2 3,4,5,6*/
 560         ri->lenextra=transform_distance(pro, &ri->lp, &ri->c);
 561         ri->lenneg=transform_polyline_length(pro, sd->c, npos)+transform_distance(pro, &sd->c[ri->pos], &ri->lp);
 562         ri->lenpos=transform_polyline_length(pro, sd->c+npos, sd->count-npos)+transform_distance(pro, &sd->c[npos], &ri->lp);
 563 }
 564
 565 /**
 566  * @brief This sets the current position of the route passed
 567  *
 568  * This will set the current position of the route passed to the street that is nearest to the
 569  * passed coordinates. It also automatically updates the route.
 570  *
 571  * @param this The route to set the position of
 572  * @param pos Coordinates to set as position
 573  */
 574 void
 575 route_set_position(struct route *this, struct pcoord *pos)
 576 {
 577         if (this->pos)
 578                 route_info_free(this->pos);
 579         this->pos=NULL;
 580         this->pos=route_find_nearest_street(this->ms, pos);
 581         dbg(1,"this->pos=%p\n", this->pos);
 582         if (! this->pos)
 583                 return;
 584         route_info_distances(this->pos, pos->pro);
 585         if (this->dst)
 586                 route_path_update(this);
 587 }
 588
 589 /**
 590  * @brief Sets a route's current position based on coordinates from tracking
 591  *
 592  * @param this The route to set the current position of
 593  * @param tracking The tracking to get the coordinates from
 594  */
 595 void
 596 route_set_position_from_tracking(struct route *this, struct tracking *tracking)
 597 {
 598         struct pcoord *c;
 599         struct route_info *ret;
 600
 601         dbg(2,"enter\n");
 602         c=tracking_get_pos(tracking);
 603         ret=g_new0(struct route_info, 1);
 604         if (!ret) {
 605                 printf("%s:Out of memory\n", __FUNCTION__);
 606                 return;
 607         }
 608         if (this->pos)
 609                 route_info_free(this->pos);
 610         this->pos=NULL;
 611         ret->c.x = c->x;
 612         ret->c.y = c->y;
 613         ret->lp.x=c->x;
 614         ret->lp.y=c->y;
 615         ret->pos=tracking_get_segment_pos(tracking);
 616         ret->street=street_data_dup(tracking_get_street_data(tracking));
 617         route_info_distances(ret, c->pro);
 618         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);
 619         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);
 620         this->pos=ret;
 621         if (this->dst)
 622                 route_path_update(this);
 623         dbg(2,"ret\n");
 624 }
 625
 626 /* Used for debuging of route_rect, what routing sees */
 627 struct map_selection *route_selection;
 628
 629 /**
 630  * @brief Returns a single map selection
 631  */
 632 struct map_selection *
 633 route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs)
 634 {
 635         int dx,dy,sx=1,sy=1,d,m;
 636         struct map_selection *sel=g_new(struct map_selection, 1);
 637         if (!sel) {
 638                 printf("%s:Out of memory\n", __FUNCTION__);
 639                 return sel;
 640         }
 641         sel->order=order;
 642         sel->range.min=route_item_first;
 643         sel->range.max=route_item_last;
 644         dbg(1,"%p %p\n", c1, c2);
 645         dx=c1->x-c2->x;
 646         dy=c1->y-c2->y;
 647         if (dx < 0) {
 648                 sx=-1;
 649                 sel->u.c_rect.lu.x=c1->x;
 650                 sel->u.c_rect.rl.x=c2->x;
 651         } else {
 652                 sel->u.c_rect.lu.x=c2->x;
 653                 sel->u.c_rect.rl.x=c1->x;
 654         }
 655         if (dy < 0) {
 656                 sy=-1;
 657                 sel->u.c_rect.lu.y=c2->y;
 658                 sel->u.c_rect.rl.y=c1->y;
 659         } else {
 660                 sel->u.c_rect.lu.y=c1->y;
 661                 sel->u.c_rect.rl.y=c2->y;
 662         }
 663         if (dx*sx > dy*sy)
 664                 d=dx*sx;
 665         else
 666                 d=dy*sy;
 667         m=d*rel/100+abs;
 668         sel->u.c_rect.lu.x-=m;
 669         sel->u.c_rect.rl.x+=m;
 670         sel->u.c_rect.lu.y+=m;
 671         sel->u.c_rect.rl.y-=m;
 672         sel->next=NULL;
 673         return sel;
 674 }
 675
 676 /**
 677  * @brief Returns a list of map selections useable to create a route graph
 678  *
 679  * Returns a list of  map selections useable to get a  map rect from which items can be
 680  * retrieved to build a route graph. The selections are a rectangle with
 681  * c1 and c2 as two corners.
 682  *
 683  * @param c1 Corner 1 of the rectangle
 684  * @param c2 Corder 2 of the rectangle
 685  */
 686 static struct map_selection *
 687 route_calc_selection(struct coord *c1, struct coord *c2)
 688 {
 689         struct map_selection *ret,*sel;
 690         sel=route_rect(4, c1, c2, 25, 0);
 691         ret=sel;
 692         sel->next=route_rect(8, c1, c1, 0, 40000);
 693         sel=sel->next;
 694         sel->next=route_rect(18, c1, c1, 0, 10000);
 695         sel=sel->next;
 696         sel->next=route_rect(8, c2, c2, 0, 40000);
 697         sel=sel->next;
 698         sel->next=route_rect(18, c2, c2, 0, 10000);
 699         /* route_selection=ret; */
 700         return ret;
 701 }
 702
 703 /**
 704  * @brief Destroys a list of map selections
 705  *
 706  * @param sel Start of the list to be destroyed
 707  */
 708 static void
 709 route_free_selection(struct map_selection *sel)
 710 {
 711         struct map_selection *next;
 712         while (sel) {
 713                 next=sel->next;
 714                 g_free(sel);
 715                 sel=next;
 716         }
 717 }
 718
 719
 720 /**
 721  * @brief Sets the destination of a route
 722  *
 723  * This sets the destination of a route to the street nearest to the coordinates passed
 724  * and updates the route.
 725  *
 726  * @param this The route to set the destination for
 727  * @param dst Coordinates to set as destination
 728  */
 729 void
 730 route_set_destination(struct route *this, struct pcoord *dst)
 731 {
 732         profile(0,NULL);
 733         if (this->dst)
 734                 route_info_free(this->dst);
 735         this->dst=NULL;
 736         if (dst) {
 737                 this->dst=route_find_nearest_street(this->ms, dst);
 738                 if(this->dst)
 739                 route_info_distances(this->dst, dst->pro);
 740         }
 741         profile(1,"find_nearest_street");
 742
 743         /* The graph has to be destroyed and set to NULL, otherwise route_path_update() doesn't work */
 744         route_graph_destroy(this->graph);
 745         this->graph=NULL;
 746         route_path_update(this);
 747         profile(0,"end");
 748 }
 749
 750 /**
 751  * @brief Gets the route_graph_point with the specified coordinates
 752  *
 753  * @param this The route in which to search
 754  * @param c Coordinates to search for
 755  * @return The point at the specified coordinates or NULL if not found
 756  */
 757 static struct route_graph_point *
 758 route_graph_get_point(struct route_graph *this, struct coord *c)
 759 {
 760         struct route_graph_point *p;
 761         int hashval=HASHCOORD(c);
 762         p=this->hash[hashval];
 763         while (p) {
 764                 if (p->c.x == c->x && p->c.y == c->y)
 765                         return p;
 766                 p=p->hash_next;
 767         }
 768         return NULL;
 769 }
 770
 771 /**
 772  * @brief Inserts a point into the route graph at the specified coordinates
 773  *
 774  * This will insert a point into the route graph at the coordinates passed in f.
 775  * Note that the point is not yet linked to any segments.
 776  *
 777  * @param this The route to insert the point into
 778  * @param f The coordinates at which the point should be inserted
 779  * @return The point inserted or NULL on failure
 780  */
 781 static struct route_graph_point *
 782 route_graph_add_point(struct route_graph *this, struct coord *f)
 783 {
 784         int hashval;
 785         struct route_graph_point *p;
 786
 787         p=route_graph_get_point(this,f);
 788         if (!p) {
 789                 hashval=HASHCOORD(f);
 790                 if (debug_route)
 791                         printf("p (0x%x,0x%x)\n", f->x, f->y);
 792                 p=g_new(struct route_graph_point,1);
 793                 if (!p) {
 794                         printf("%s:Out of memory\n", __FUNCTION__);
 795                         return p;
 796                 }
 797                 p->hash_next=this->hash[hashval];
 798                 this->hash[hashval]=p;
 799                 p->next=this->route_points;
 800                 p->el=NULL;
 801                 p->start=NULL;
 802                 p->end=NULL;
 803                 p->seg=NULL;
 804                 p->value=INT_MAX;
 805                 p->c=*f;
 806                 this->route_points=p;
 807         }
 808         return p;
 809 }
 810
 811 /**
 812  * @brief Frees all the memory used for points in the route graph passed
 813  *
 814  * @param this The route graph to delete all points from
 815  */
 816 static void
 817 route_graph_free_points(struct route_graph *this)
 818 {
 819         struct route_graph_point *curr,*next;
 820         curr=this->route_points;
 821         while (curr) {
 822                 next=curr->next;
 823                 g_free(curr);
 824                 curr=next;
 825         }
 826         this->route_points=NULL;
 827         memset(this->hash, 0, sizeof(this->hash));
 828 }
 829
 830 /**
 831  * @brief Inserts a new segment into the route graph
 832  *
 833  * This function performs a check if a segment for the item specified already exists, and inserts
 834  * a new segment representing this item if it does not.
 835  *
 836  * @param this The route graph to insert the segment into
 837  * @param start The graph point which should be connected to the start of this segment
 838  * @param end The graph point which should be connected to the end of this segment
 839  * @param len The length of this segment
 840  * @param item The item that is represented by this segment
 841  * @param flags Flags for this segment
 842  * @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
 843  */
 844 static void
 845 route_graph_add_segment(struct route_graph *this, struct route_graph_point *start,
 846                         struct route_graph_point *end, int len, struct item *item,
 847                         int flags, int offset)
 848 {
 849         struct route_graph_segment *s;
 850 /*
 851         FIXME: commented out becouse
 852         it is possible to have one item with two different
 853         offsets as segments
 854         s=start->start;
 855         while (s) {
 856                 if (item_is_equal(*item, s->item))
 857                         return;
 858                 s=s->start_next;
 859         }
 860 */
 861         s = g_new0(struct route_graph_segment, 1);
 862         if (!s) {
 863                 printf("%s:Out of memory\n", __FUNCTION__);
 864                 return;
 865         }
 866         s->start=start;
 867         s->start_next=start->start;
 868         start->start=s;
 869         s->end=end;
 870         s->end_next=end->end;
 871         end->end=s;
 872         dbg_assert(len >= 0);
 873         s->len=len;
 874         s->item=*item;
 875         s->flags=flags;
 876         s->offset = offset;
 877         s->next=this->route_segments;
 878         this->route_segments=s;
 879         if (debug_route)
 880                 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
 881 }
 882
 883 /**
 884  * @brief Gets all the coordinates of an item
 885  *
 886  * This will get all the coordinates of the item i and return them in c,
 887  * up to max coordinates. Additionally it is possible to limit the coordinates
 888  * returned to all the coordinates of the item between the two coordinates
 889  * start end end.
 890  *
 891  * @important Make shure that whatever c points to has enough memory allocated
 892  * @important to hold max coordinates!
 893  *
 894  * @param i The item to get the coordinates of
 895  * @param c Pointer to memory allocated for holding the coordinates
 896  * @param max Maximum number of coordinates to return
 897  * @param start First coordinate to get
 898  * @param end Last coordinate to get
 899  * @return The number of coordinates returned
 900  */
 901 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
 902                 struct coord *start, struct coord *end)
 903 {
 904         struct map_rect *mr;
 905         struct item *item;
 906         int rc = 0, p = 0;
 907         struct coord c1;
 908         mr=map_rect_new(i->map, NULL);
 909         if (!mr)
 910                 return 0;
 911         item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
 912         if (item) {
 913                 rc = item_coord_get(item, &c1, 1);
 914                 while (rc && (c1.x != start->x || c1.y != start->y)) {
 915                         rc = item_coord_get(item, &c1, 1);
 916                 }
 917                 while (rc && p < max) {
 918                         c[p++] = c1;
 919                         if (c1.x == end->x && c1.y == end->y)
 920                                 break;
 921                         rc = item_coord_get(item, &c1, 1);
 922                 }
 923         }
 924         map_rect_destroy(mr);
 925         return p;
 926 }
 927
 928 /**
 929  * @brief Returns and removes one segment from a path
 930  *
 931  * @param path The path to take the segment from
 932  * @param item The item whose segment to remove
 933  * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
 934  * @return The segment removed
 935  */
 936 static struct route_path_segment *
 937 route_extract_segment_from_path(struct route_path *path, struct item *item,
 938                                                  int offset)
 939 {
 940         struct route_path_segment *sp = NULL, *s;
 941         s = path->path;
 942         while (s) {
 943                 if (s->offset == offset && item_is_equal(s->item,*item)) {
 944                         if (sp) {
 945                                 sp->next = s->next;
 946                                 break;
 947                         } else {
 948                                 path->path = s->next;
 949                                 break;
 950                         }
 951                 }
 952                 sp = s;
 953                 s = s->next;
 954         }
 955         if (s)
 956                 item_hash_remove(path->path_hash, item);
 957         return s;
 958 }
 959
 960 /**
 961  * @brief Adds a segment and the end of a path
 962  *
 963  * @param this The path to add the segment to
 964  * @param segment The segment to add
 965  */
 966 static void
 967 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
 968 {
 969         if (!this->path)
 970                 this->path=segment;
 971         if (this->path_last)
 972                 this->path_last->next=segment;
 973         this->path_last=segment;
 974 }
 975
 976 /**
 977  * @brief Adds a new item to a path
 978  *
 979  * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
 980  * if the item passed is segmented - it will create exactly one segment.
 981  *
 982  * @param this The path to add the item to
 983  * @param item The item to add
 984  * @param len The length of the item
 985  * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
 986  * @param c Pointer to count coordinates of the item.
 987  * @param cound Number of coordinates in c
 988  * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
 989  * @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"
 990  */
 991 static void
 992 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)
 993 {
 994         int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
 995         struct route_path_segment *segment;
 996
 997         segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
 998         segment->ncoords=ccount;
 999         segment->direction=dir;
1000         if (first)
1001                 segment->c[idx++]=*first;
1002         if (dir > 0) {
1003                 for (i = 0 ; i < count ; i++)
1004                         segment->c[idx++]=c[i];
1005         } else {
1006                 for (i = 0 ; i < count ; i++)
1007                         segment->c[idx++]=c[count-i-1];
1008         }
1009         if (last)
1010                 segment->c[idx++]=*last;
1011         segment->length=len;
1012         if (item)
1013                 segment->item=*item;
1014         route_path_add_segment(this, segment);
1015 }
1016
1017 /**
1018  * @brief Inserts a new item into the path
1019  *
1020  * This function does almost the same as "route_apth_add_item()", but identifies
1021  * the item to add by a segment from the route graph. Another difference is that it "copies" the
1022  * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1023  * be added to the route path, not all segments of the item.
1024  *
1025  * The function can be sped up by passing an old path already containing this segment in oldpath -
1026  * the segment will then be extracted from this old path. Please note that in this case the direction
1027  * parameter has no effect.
1028  *
1029  * @param this The path to add the item to
1030  * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1031  * @param rgs Segment of the route graph that should be "copied" to the route path
1032  * @param len Length of the item to be added
1033  * @param offset Offset of rgs within the item it represents
1034  * @param dir Order in which to add the coordinates. See route_path_add_item()
1035  * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
1036  */
1037 static void
1038 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
1039                                    struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
1040 {
1041         struct route_path_segment *segment;
1042         int i,ccnt = 0;
1043         struct coord ca[2048];
1044
1045         if (oldpath) {
1046                 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
1047                 if (ccnt) {
1048                         segment = route_extract_segment_from_path(oldpath,
1049                                                          &rgs->item, offset);
1050
1051                         if (segment)
1052                                 goto linkold;
1053                 }
1054         }
1055
1056         ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1057         segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1058         if (!segment) {
1059                 printf("%s:Out of memory\n", __FUNCTION__);
1060                 return;
1061         }
1062         segment->direction=dir;
1063         if (dir > 0) {
1064                 for (i = 0 ; i < ccnt ; i++)
1065                         segment->c[i]=ca[i];
1066         } else {
1067                 for (i = 0 ; i < ccnt ; i++)
1068                         segment->c[i]=ca[ccnt-i-1];
1069         }
1070         segment->ncoords = ccnt;
1071         segment->item=rgs->item;
1072         segment->offset = offset;
1073 linkold:
1074         segment->length=len;
1075         segment->next=NULL;
1076         item_hash_insert(this->path_hash,  &rgs->item, (void *)ccnt);
1077
1078         route_path_add_segment(this, segment);
1079 }
1080
1081 /**
1082  * @brief Destroys all segments of a route graph
1083  *
1084  * @param this The graph to destroy all segments from
1085  */
1086 static void
1087 route_graph_free_segments(struct route_graph *this)
1088 {
1089         struct route_graph_segment *curr,*next;
1090         curr=this->route_segments;
1091         while (curr) {
1092                 next=curr->next;
1093                 g_free(curr);
1094                 curr=next;
1095         }
1096         this->route_segments=NULL;
1097 }
1098
1099 /**
1100  * @brief Destroys a route graph
1101  *
1102  * @param this The route graph to be destroyed
1103  */
1104 static void
1105 route_graph_destroy(struct route_graph *this)
1106 {
1107         if (this) {
1108                 route_graph_free_points(this);
1109                 route_graph_free_segments(this);
1110                 g_free(this);
1111         }
1112 }
1113
1114 /**
1115  * @brief Returns the time needed to drive len on item
1116  *
1117  * @param speedlist The speedlist that should be used
1118  * @param item The item to be driven on
1119  * @param len The length to drive
1120  * @return The time needed to drive len on item
1121  */
1122 int
1123 route_time(int *speedlist, struct item *item, int len)
1124 {
1125         if (item->type < route_item_first || item->type > route_item_last) {
1126                 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1127                 return len*36;
1128         }
1129         if (!speedlist[item->type-route_item_first]) {
1130                 dbg(0,"street type %d speed is zero\n", item->type);
1131                 return len*36;
1132         }
1133         return len*36/speedlist[item->type-route_item_first];
1134 }
1135
1136 /**
1137  * @brief Returns the "costs" of driving len on item
1138  *
1139  * @param speedlist The speedlist that should be used
1140  * @param item The item to be driven on
1141  * @param len The length to drive
1142  * @return The "costs" needed to drive len on item
1143  */
1144 static int
1145 route_value(int *speedlist, struct item *item, int len)
1146 {
1147         int ret;
1148         if (len < 0) {
1149                 printf("len=%d\n", len);
1150         }
1151         dbg_assert(len >= 0);
1152         ret=route_time(speedlist, item, len);
1153         dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1154         return ret;
1155 }
1156
1157 /**
1158  * @brief Adds an item to the route graph
1159  *
1160  * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1161  * segmented item.
1162  *
1163  * @param this The route graph to add to
1164  * @param item The item to add
1165  */
1166 static void
1167 route_process_street_graph(struct route_graph *this, struct item *item)
1168 {
1169 #ifdef AVOID_FLOAT
1170         int len=0;
1171 #else
1172         double len=0;
1173 #endif
1174         struct route_graph_point *s_pnt,*e_pnt;
1175         struct coord c,l;
1176         struct attr attr;
1177         int flags = 0;
1178         int segmented = 0;
1179         int offset = 1;
1180
1181         if (item_coord_get(item, &l, 1)) {
1182                 if (item_attr_get(item, attr_flags, &attr)) {
1183                         flags = attr.u.num;
1184                         if (flags & AF_SEGMENTED)
1185                                 segmented = 1;
1186                 }
1187                 s_pnt=route_graph_add_point(this,&l);
1188                 if (!segmented) {
1189                         while (item_coord_get(item, &c, 1)) {
1190                                 len+=transform_distance(map_projection(item->map), &l, &c);
1191                                 l=c;
1192                         }
1193                         e_pnt=route_graph_add_point(this,&l);
1194                         dbg_assert(len >= 0);
1195                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1196                 } else {
1197                         int isseg,rc;
1198                         int sc = 0;
1199                         do {
1200                                 isseg = item_coord_is_node(item);
1201                                 rc = item_coord_get(item, &c, 1);
1202                                 if (rc) {
1203                                         len+=transform_distance(map_projection(item->map), &l, &c);
1204                                         l=c;
1205                                         if (isseg) {
1206                                                 e_pnt=route_graph_add_point(this,&l);
1207                                                 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1208                                                 offset++;
1209                                                 s_pnt=route_graph_add_point(this,&l);
1210                                                 len = 0;
1211                                         }
1212                                 }
1213                         } while(rc);
1214                         e_pnt=route_graph_add_point(this,&l);
1215                         dbg_assert(len >= 0);
1216                         sc++;
1217                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1218                 }
1219         }
1220 }
1221
1222 /**
1223  * @brief Compares the costs of reaching the destination from two points on
1224  *
1225  * @important Do not pass anything other than route_graph_points in v1 and v2!
1226  *
1227  * @param v1 Point1
1228  * @param v2 Point2
1229  * @return The additional costs of v1 compared to v2 (may be negative)
1230  */
1231 static int
1232 compare(void *v1, void *v2)
1233 {
1234         struct route_graph_point *p1=v1;
1235         struct route_graph_point *p2=v2;
1236 #if 0
1237         if (debug_route)
1238                 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1239 #endif
1240         return p1->value-p2->value;
1241 }
1242
1243 /**
1244  * @brief Calculates the routing costs for each point
1245  *
1246  * This function is the heart of routing. It assigns each point in the route graph a
1247  * cost at which one can reach the destination from this point on. Additionally it assigns
1248  * each point a segment one should follow from this point on to reach the destination at the
1249  * stated costs.
1250  *
1251  * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1252  * at this algorithm.
1253  */
1254 static void
1255 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
1256 {
1257         struct route_graph_point *p_min,*end=NULL;
1258         struct route_graph_segment *s;
1259         int min,new,old,val;
1260         struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1261         struct street_data *sd=dst->street;
1262
1263         heap = fh_makeheap();
1264         fh_setcmp(heap, compare);
1265
1266         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 */
1267                 end=route_graph_get_point(this, &sd->c[0]);
1268                 dbg_assert(end != 0);
1269                 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1270                 end->el=fh_insert(heap, end);
1271         }
1272
1273         if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1274                 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1275                 dbg_assert(end != 0);
1276                 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1277                 end->el=fh_insert(heap, end);
1278         }
1279
1280         dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1281         for (;;) {
1282                 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1283                 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1284                         break;
1285                 min=p_min->value;
1286                 if (debug_route)
1287                         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);
1288                 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1289                 s=p_min->start;
1290                 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1291                         val=route_value(speedlist, &s->item, s->len);
1292 #if 0
1293                         val+=val*2*street_route_contained(s->str->segid);
1294 #endif
1295                         new=min+val;
1296                         if (debug_route)
1297                                 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);
1298                         if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1299                                 s->end->value=new;
1300                                 s->end->seg=s;
1301                                 if (! s->end->el) {
1302                                         if (debug_route)
1303                                                 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1304                                         s->end->el=fh_insert(heap, s->end);
1305                                         if (debug_route)
1306                                                 printf("el new=%p\n", s->end->el);
1307                                 }
1308                                 else {
1309                                         if (debug_route)
1310                                                 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1311                                         fh_replacedata(heap, s->end->el, s->end);
1312                                 }
1313                         }
1314                         if (debug_route)
1315                                 printf("\n");
1316                         s=s->start_next;
1317                 }
1318                 s=p_min->end;
1319                 while (s) { /* Doing the same as above with the segments leading towards our point */
1320                         val=route_value(speedlist, &s->item, s->len);
1321                         new=min+val;
1322                         if (debug_route)
1323                                 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);
1324                         if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1325                                 old=s->start->value;
1326                                 s->start->value=new;
1327                                 s->start->seg=s;
1328                                 if (! s->start->el) {
1329                                         if (debug_route)
1330                                                 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1331                                         s->start->el=fh_insert(heap, s->start);
1332                                         if (debug_route)
1333                                                 printf("el new=%p\n", s->start->el);
1334                                 }
1335                                 else {
1336                                         if (debug_route)
1337                                                 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1338                                         fh_replacedata(heap, s->start->el, s->start);
1339                                 }
1340                         }
1341                         if (debug_route)
1342                                 printf("\n");
1343                         s=s->end_next;
1344                 }
1345         }
1346         fh_deleteheap(heap);
1347 }
1348
1349 /**
1350  * @brief Starts an "offroad" path
1351  *
1352  * This starts a path that is not located on a street. It creates a new route path
1353  * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1354  *
1355  * @param this Not used
1356  * @param pos The starting position for the new path
1357  * @param dst The destination of the new path
1358  * @param dir Not used
1359  * @return The new path
1360  */
1361 static struct route_path *
1362 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1363 {
1364         struct route_path *ret;
1365
1366         ret=g_new0(struct route_path, 1);
1367         ret->path_hash=item_hash_new();
1368         route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1369
1370         return ret;
1371 }
1372
1373 /**
1374  * @brief Creates a new "trivial" route
1375  *
1376  * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1377  * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1378  *
1379  * @param this The route graph to place the route on
1380  * @param pos The starting position for the new path
1381  * @param dst The destination of the new path
1382  * @param dir Direction of the coordinates to be added
1383  * @return The new path
1384  */
1385 static struct route_path *
1386 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1387 {
1388         struct street_data *sd=pos->street;
1389         struct route_path *ret;
1390
1391         if (dir > 0) {
1392                 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1393                         return route_path_new_offroad(this, pos, dst, dir);
1394         } else {
1395                 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1396                         return route_path_new_offroad(this, pos, dst, dir);
1397         }
1398         ret=g_new0(struct route_path, 1);
1399         ret->path_hash=item_hash_new();
1400         if (pos->lenextra)
1401                 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1402         if (dir > 0)
1403                 route_path_add_item(ret, &sd->item, pos->lenpos-dst->lenpos, &pos->lp, sd->c+pos->pos+1, dst->pos+pos->pos, &dst->lp, 1);
1404         else
1405                 route_path_add_item(ret, &sd->item, pos->lenneg-dst->lenneg, &pos->lp, sd->c+dst->pos+1, pos->pos-dst->pos, &dst->lp, -1);
1406         if (dst->lenextra)
1407                 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1408         return ret;
1409 }
1410
1411 /**
1412  * @brief Creates a new route path
1413  *
1414  * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1415  * make shure to run route_graph_flood() after changing the destination before using this function.
1416  *
1417  * @param this The route graph to create the route from
1418  * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1419  * @param pos The starting position of the route
1420  * @param dst The destination of the route
1421  * @param speedlist The speedlist to use
1422  * @return The new route path
1423  */
1424 static struct route_path *
1425 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1426 {
1427         struct route_graph_point *start1=NULL,*start2=NULL,*start;
1428         struct route_graph_segment *s=NULL;
1429         struct route_graph_segment *lastseg = NULL;
1430         int is_straight=0;
1431         int len=0,segs=0;
1432         int seg_len;
1433 #if 0
1434         int time=0,hr,min,sec
1435 #endif
1436         unsigned int val1=0xffffffff,val2=0xffffffff;
1437         struct street_data *sd=pos->street;
1438         struct route_path *ret;
1439
1440         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 */
1441                 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1442                         return route_path_new_trivial(this, pos, dst, -1);
1443                 }
1444                 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1445                         return route_path_new_trivial(this, pos, dst, 1);
1446                 }
1447         }
1448         if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1449                 start1=route_graph_get_point(this, &sd->c[0]);
1450                 if (! start1)
1451                         return NULL;
1452                 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1453                 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1454         }
1455         if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1456                 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1457                 if (! start2)
1458                         return NULL;
1459                 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1460                 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1461         }
1462         dbg(1,"val1=%d val2=%d\n", val1, val2);
1463         if (val1 == val2) {
1464                 val1=start1->start->start->value;
1465                 val2=start2->end->end->value;
1466         }
1467         ret=g_new0(struct route_path, 1);
1468         if (pos->lenextra)
1469                 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1470         if (start1 && (val1 < val2)) {
1471                 start=start1;
1472                 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1473         } else {
1474                 if (start2) {
1475                         start=start2;
1476                         route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1477                 } else {
1478                         printf("no route found, pos blocked\n");
1479                         return NULL;
1480                 }
1481         }
1482         ret->path_hash=item_hash_new();
1483         while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1484                 segs++;
1485 #if 0
1486                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1487 #endif
1488                 seg_len=s->len;
1489                 len+=seg_len;
1490
1491                 if (s->start == start) {
1492                         route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight);
1493                         start=s->end;
1494                 } else {
1495                         route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight);
1496                         start=s->start;
1497                 }
1498
1499                 lastseg = s;
1500         }
1501         sd=dst->street;
1502         dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1503         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);
1504         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 */
1505                 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1);
1506         } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1507                 route_path_add_item(ret, &sd->item, dst->lenpos, NULL, sd->c+dst->pos+1, sd->count-dst->pos-1, &dst->lp, -1);
1508         } else {
1509                 printf("no route found\n");
1510                 route_path_destroy(ret);
1511                 return NULL;
1512         }
1513         if (dst->lenextra)
1514                 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1515         dbg(1, "%d segments\n", segs);
1516         return ret;
1517 }
1518
1519 /**
1520  * @brief Builds a new route graph from a mapset
1521  *
1522  * This function builds a new route graph from a map. Please note that this function does not
1523  * add any routing information to the route graph - this has to be done via the route_graph_flood()
1524  * function.
1525  *
1526  * The function does not create a graph covering the whole map, but only covering the rectangle
1527  * between c1 and c2.
1528  *
1529  * @param ms The mapset to build the route graph from
1530  * @param c1 Corner 1 of the rectangle to use from the map
1531  * @param c2 Corner 2 of the rectangle to use from the map
1532  * @return The new route graph.
1533  */
1534 static struct route_graph *
1535 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
1536 {
1537         struct route_graph *ret=g_new0(struct route_graph, 1);
1538         struct map_selection *sel;
1539         struct mapset_handle *h;
1540         struct map_rect *mr;
1541         struct map *m;
1542         struct item *item;
1543
1544         if (!ret) {
1545                 printf("%s:Out of memory\n", __FUNCTION__);
1546                 return ret;
1547         }
1548         sel=route_calc_selection(c1, c2);
1549         h=mapset_open(ms);
1550         while ((m=mapset_next(h,1))) {
1551                 mr=map_rect_new(m, sel);
1552                 if (! mr)
1553                         continue;
1554                 while ((item=map_rect_get_item(mr))) {
1555                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1556                                 route_process_street_graph(ret, item);
1557                         }
1558                 }
1559                 map_rect_destroy(mr);
1560         }
1561         mapset_close(h);
1562         route_free_selection(sel);
1563
1564         return ret;
1565 }
1566
1567 /**
1568  * @brief Updates the route graph
1569  *
1570  * This updates the route graph after settings in the route have changed. It also
1571  * adds routing information afterwards by calling route_graph_flood().
1572  *
1573  * @param this The route to update the graph for
1574  */
1575 static void
1576 route_graph_update(struct route *this)
1577 {
1578         route_graph_destroy(this->graph);
1579         profile(1,"graph_free");
1580         this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
1581         profile(1,"route_graph_build");
1582         route_graph_flood(this->graph, this->dst, this->speedlist);
1583         profile(1,"route_graph_flood");
1584         this->version++;
1585 }
1586
1587 /**
1588  * @brief Gets street data for an item
1589  *
1590  * @param item The item to get the data for
1591  * @return Street data for the item
1592  */
1593 struct street_data *
1594 street_get_data (struct item *item)
1595 {
1596         int count=0;
1597         struct street_data *ret = NULL, *ret1;
1598         struct attr attr;
1599         const int step = 128;
1600         int c;
1601
1602         do {
1603                 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
1604                 if (!ret1) {
1605                         if (ret)
1606                                 g_free(ret);
1607                         return NULL;
1608                 }
1609                 ret = ret1;
1610                 c = item_coord_get(item, &ret->c[count], step);
1611                 count += c;
1612         } while (c && c == step);
1613
1614         ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
1615         if (ret1)
1616                 ret = ret1;
1617         ret->item=*item;
1618         ret->count=count;
1619         if (item_attr_get(item, attr_flags, &attr))
1620                 ret->flags=attr.u.num;
1621         else
1622                 ret->flags=0;
1623
1624         return ret;
1625 }
1626
1627 /**
1628  * @brief Copies street data
1629  *
1630  * @param orig The street data to copy
1631  * @return The copied street data
1632  */
1633 struct street_data *
1634 street_data_dup(struct street_data *orig)
1635 {
1636         struct street_data *ret;
1637         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1638
1639         ret=g_malloc(size);
1640         memcpy(ret, orig, size);
1641
1642         return ret;
1643 }
1644
1645 /**
1646  * @brief Frees street data
1647  *
1648  * @param sd Street data to be freed
1649  */
1650 void
1651 street_data_free(struct street_data *sd)
1652 {
1653         g_free(sd);
1654 }
1655
1656 /**
1657  * @brief Finds the nearest street to a given coordinate
1658  *
1659  * @param ms The mapset to search in for the street
1660  * @param pc The coordinate to find a street nearby
1661  * @return The nearest street
1662  */
1663 static struct route_info *
1664 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1665 {
1666         struct route_info *ret=NULL;
1667         int max_dist=1000;
1668         struct map_selection *sel;
1669         int dist,mindist=0,pos;
1670         struct mapset_handle *h;
1671         struct map *m;
1672         struct map_rect *mr;
1673         struct item *item;
1674         struct coord lp;
1675         struct street_data *sd;
1676         struct coord c;
1677         struct coord_geo g;
1678
1679         ret=g_new0(struct route_info, 1);
1680         if (!ret) {
1681                 dbg(0,"Out of memory\n");
1682                 return ret;
1683         }
1684         mindist = INT_MAX;
1685
1686         h=mapset_open(ms);
1687         while ((m=mapset_next(h,1))) {
1688                 c.x = pc->x;
1689                 c.y = pc->y;
1690                 if (map_projection(m) != pc->pro) {
1691                         transform_to_geo(pc->pro, &c, &g);
1692                         transform_from_geo(map_projection(m), &g, &c);
1693                 }
1694                 sel = route_rect(18, &c, &c, 0, max_dist);
1695                 if (!sel)
1696                         continue;
1697                 mr=map_rect_new(m, sel);
1698                 if (!mr) {
1699                         map_selection_destroy(sel);
1700                         continue;
1701                 }
1702                 while ((item=map_rect_get_item(mr))) {
1703                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1704                                 sd=street_get_data(item);
1705                                 if (!sd)
1706                                         continue;
1707                                 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1708                                 if (dist < mindist) {
1709                                         mindist = dist;
1710                                         if (ret->street) {
1711                                                 street_data_free(ret->street);
1712                                         }
1713                                         ret->c=c;
1714                                         ret->lp=lp;
1715                                         ret->pos=pos;
1716                                         ret->street=sd;
1717                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1718                                 } else {
1719                                         street_data_free(sd);
1720                                 }
1721                         }
1722                 }
1723                 map_selection_destroy(sel);
1724                 map_rect_destroy(mr);
1725         }
1726         mapset_close(h);
1727
1728         if (!ret->street || mindist > max_dist*max_dist) {
1729                 if (ret->street) {
1730                         street_data_free(ret->street);
1731                         dbg(1,"Much too far %d > %d\n", mindist, max_dist);
1732                 }
1733                 g_free(ret);
1734                 ret = NULL;
1735         }
1736
1737         return ret;
1738 }
1739
1740 /**
1741  * @brief Destroys a route_info
1742  *
1743  * @param info The route info to be destroyed
1744  */
1745 void
1746 route_info_free(struct route_info *inf)
1747 {
1748         if (inf->street)
1749                 street_data_free(inf->street);
1750         g_free(inf);
1751 }
1752
1753
1754 #include "point.h"
1755
1756 /**
1757  * @brief Returns street data for a route info
1758  *
1759  * @param rinf The route info to return the street data for
1760  * @return Street data for the route info
1761  */
1762 struct street_data *
1763 route_info_street(struct route_info *rinf)
1764 {
1765         return rinf->street;
1766 }
1767
1768 #if 0
1769 struct route_crossings *
1770 route_crossings_get(struct route *this, struct coord *c)
1771 {
1772       struct route_point *pnt;
1773       struct route_segment *seg;
1774       int crossings=0;
1775       struct route_crossings *ret;
1776
1777        pnt=route_graph_get_point(this, c);
1778        seg=pnt->start;
1779        while (seg) {
1780                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1781                crossings++;
1782                seg=seg->start_next;
1783        }
1784        seg=pnt->end;
1785        while (seg) {
1786                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1787                crossings++;
1788                seg=seg->end_next;
1789        }
1790        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1791        ret->count=crossings;
1792        return ret;
1793 }
1794 #endif
1795
1796
1797 struct map_rect_priv {
1798         struct route_info_handle *ri;
1799         enum attr_type attr_next;
1800         int pos;
1801         struct map_priv *mpriv;
1802         struct item item;
1803         int length;
1804         unsigned int last_coord;
1805         struct route_path_segment *seg,*seg_next;
1806         struct route_graph_point *point;
1807         struct route_graph_segment *rseg;
1808         char *str;
1809         struct coord *coord_sel;        /**< Set this to a coordinate if you want to filter for just a single route graph point */
1810         struct route_graph_point_iterator it;
1811 };
1812
1813 static void
1814 rm_coord_rewind(void *priv_data)
1815 {
1816         struct map_rect_priv *mr = priv_data;
1817         mr->last_coord = 0;
1818 }
1819
1820 static void
1821 rm_attr_rewind(void *priv_data)
1822 {
1823         struct map_rect_priv *mr = priv_data;
1824         mr->attr_next = attr_street_item;
1825 }
1826
1827 static int
1828 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1829 {
1830         struct map_rect_priv *mr = priv_data;
1831         struct route_path_segment *seg=mr->seg;
1832         struct route *route=mr->mpriv->route;
1833         attr->type=attr_type;
1834         switch (attr_type) {
1835                 case attr_any:
1836                         while (mr->attr_next != attr_none) {
1837                                 if (rm_attr_get(priv_data, mr->attr_next, attr))
1838                                         return 1;
1839                         }
1840                         return 0;
1841                 case attr_street_item:
1842                         mr->attr_next=attr_direction;
1843                         if (seg && seg->item.map)
1844                                 attr->u.item=&seg->item;
1845                         else
1846                                 return 0;
1847                         return 1;
1848                 case attr_direction:
1849                         mr->attr_next=attr_route;
1850                         if (seg)
1851                                 attr->u.num=seg->direction;
1852                         else
1853                                 return 0;
1854                         return 1;
1855                 case attr_route:
1856                         mr->attr_next=attr_length;
1857                         attr->u.route = mr->mpriv->route;
1858                         return 1;
1859                 case attr_length:
1860                         if (seg)
1861                                 attr->u.num=seg->length;
1862                         else
1863                                 attr->u.num=mr->length;
1864                         mr->attr_next=attr_time;
1865                         return 1;
1866                 case attr_time:
1867                         mr->attr_next=attr_none;
1868                         if (seg)
1869                                 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1870                         else
1871                                 return 0;
1872                         return 1;
1873                 case attr_label:
1874                         mr->attr_next=attr_none;
1875                         return 0;
1876                 default:
1877                         mr->attr_next=attr_none;
1878                         attr->type=attr_none;
1879                         return 0;
1880         }
1881         return 0;
1882 }
1883
1884 static int
1885 rm_coord_get(void *priv_data, struct coord *c, int count)
1886 {
1887         struct map_rect_priv *mr = priv_data;
1888         struct route_path_segment *seg = mr->seg;
1889         int i,rc=0;
1890         struct route *r = mr->mpriv->route;
1891         enum projection pro = route_projection(r);
1892
1893         if (! seg)
1894                 return 0;
1895         for (i=0; i < count; i++) {
1896                 if (mr->last_coord >= seg->ncoords)
1897                         break;
1898                 if (i >= seg->ncoords)
1899                         break;
1900                 if (pro != projection_mg)
1901                         transform_from_to(&seg->c[mr->last_coord++], pro,
1902                                 &c[i],projection_mg);
1903                 else
1904                         c[i] = seg->c[mr->last_coord++];
1905                 rc++;
1906         }
1907         dbg(1,"return %d\n",rc);
1908         return rc;
1909 }
1910
1911 static struct item_methods methods_route_item = {
1912         rm_coord_rewind,
1913         rm_coord_get,
1914         rm_attr_rewind,
1915         rm_attr_get,
1916 };
1917
1918 static void
1919 rp_attr_rewind(void *priv_data)
1920 {
1921         struct map_rect_priv *mr = priv_data;
1922         mr->attr_next = attr_label;
1923 }
1924
1925 static int
1926 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1927 {
1928         struct map_rect_priv *mr = priv_data;
1929         struct route_graph_point *p = mr->point;
1930         struct route_graph_segment *seg = mr->rseg;
1931         switch (attr_type) {
1932         case attr_any: // works only with rg_points for now
1933                 if (mr->item.type != type_rg_point)
1934                         return 0;
1935                 while (mr->attr_next != attr_none) {
1936                         if (rp_attr_get(priv_data, mr->attr_next, attr))
1937                                 return 1;
1938                 }
1939                 return 0;
1940         case attr_label:
1941                 if (mr->item.type != type_rg_point)
1942                         return 0;
1943                 attr->type = attr_label;
1944                 if (mr->str)
1945                         g_free(mr->str);
1946                 if (p->value != INT_MAX)
1947                         mr->str=g_strdup_printf("%d", p->value);
1948                 else
1949                         mr->str=g_strdup("-");
1950                 attr->u.str = mr->str;
1951                 mr->attr_next=attr_none;
1952                 return 1;
1953         case attr_street_item:
1954                 if (mr->item.type != type_rg_segment)
1955                         return 0;
1956                 mr->attr_next=attr_none;
1957                 if (seg && seg->item.map)
1958                         attr->u.item=&seg->item;
1959                 else
1960                         return 0;
1961                 return 1;
1962         case attr_direction:
1963                 // This only works if the map has been opened at a single point, and in that case indicates if the
1964                 // segment returned last is connected to this point via its start (1) or its end (-1)
1965                 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
1966                         return 0;
1967                 if (seg->start == mr->point) {
1968                         attr->u.num=1;
1969                 } else if (seg->end == mr->point) {
1970                         attr->u.num=-1;
1971                 } else {
1972                         return 0;
1973                 }
1974                 return 1;
1975         case attr_debug:
1976                 if (mr->item.type != type_rg_point)
1977                         return 0;
1978                 attr->type = attr_debug;
1979                 if (mr->str)
1980                         g_free(mr->str);
1981                 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
1982                 attr->u.str = mr->str;
1983                 mr->attr_next=attr_none;
1984                 return 1;
1985         default:
1986                 mr->attr_next=attr_none;
1987                 attr->type=attr_none;
1988                 return 0;
1989         }
1990 }
1991
1992 /**
1993  * @brief Returns the coordinates of a route graph item
1994  *
1995  * @param priv_data The route graph item's private data
1996  * @param c Pointer where to store the coordinates
1997  * @param count How many coordinates to get at a max?
1998  * @return The number of coordinates retrieved
1999  */
2000 static int
2001 rp_coord_get(void *priv_data, struct coord *c, int count)
2002 {
2003         struct map_rect_priv *mr = priv_data;
2004         struct route_graph_point *p = mr->point;
2005         struct route_graph_segment *seg = mr->rseg;
2006         int rc = 0,i,dir;
2007         struct route *r = mr->mpriv->route;
2008         enum projection pro = route_projection(r);
2009
2010         for (i=0; i < count; i++) {
2011                 if (mr->item.type == type_rg_point) {
2012                         if (mr->last_coord >= 1)
2013                                 break;
2014                         if (pro != projection_mg)
2015                                 transform_from_to(&p->c, pro,
2016                                         &c[i],projection_mg);
2017                         else
2018                                 c[i] = p->c;
2019                 } else {
2020                         if (mr->last_coord >= 2)
2021                                 break;
2022                         dir=0;
2023                         if (seg->end->seg == seg)
2024                                 dir=1;
2025                         if (mr->last_coord)
2026                                 dir=1-dir;
2027                         if (dir) {
2028                                 if (pro != projection_mg)
2029                                         transform_from_to(&seg->end->c, pro,
2030                                                 &c[i],projection_mg);
2031                                 else
2032                                         c[i] = seg->end->c;
2033                         } else {
2034                                 if (pro != projection_mg)
2035                                         transform_from_to(&seg->start->c, pro,
2036                                                 &c[i],projection_mg);
2037                                 else
2038                                         c[i] = seg->start->c;
2039                         }
2040                 }
2041                 mr->last_coord++;
2042                 rc++;
2043         }
2044         return rc;
2045 }
2046
2047 static struct item_methods methods_point_item = {
2048         rm_coord_rewind,
2049         rp_coord_get,
2050         rp_attr_rewind,
2051         rp_attr_get,
2052 };
2053
2054 static void
2055 rp_destroy(struct map_priv *priv)
2056 {
2057         g_free(priv);
2058 }
2059
2060 static void
2061 rm_destroy(struct map_priv *priv)
2062 {
2063         g_free(priv);
2064 }
2065
2066 static struct map_rect_priv *
2067 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2068 {
2069         struct map_rect_priv * mr;
2070         dbg(1,"enter\n");
2071         if (! route_get_pos(priv->route))
2072                 return NULL;
2073         if (! route_get_dst(priv->route))
2074                 return NULL;
2075         if (! priv->route->path2)
2076                 return NULL;
2077         mr=g_new0(struct map_rect_priv, 1);
2078         mr->mpriv = priv;
2079         mr->item.priv_data = mr;
2080         mr->item.type = type_street_route;
2081         mr->item.meth = &methods_route_item;
2082         mr->seg_next=priv->route->path2->path;
2083         return mr;
2084 }
2085
2086 /**
2087  * @brief Opens a new map rectangle on the route graph's map
2088  *
2089  * This function opens a new map rectangle on the route graph's map.
2090  * The "sel" parameter enables you to only search for a single route graph
2091  * point on this map (or exactly: open a map rectangle that only contains
2092  * this one point). To do this, pass here a single map selection, whose
2093  * c_rect has both coordinates set to the same point. Otherwise this parameter
2094  * has no effect.
2095  *
2096  * @param priv The route graph map's private data
2097  * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2098  * @return A new map rect's private data
2099  */
2100 static struct map_rect_priv *
2101 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2102 {
2103         struct map_rect_priv * mr;
2104
2105         dbg(1,"enter\n");
2106         if (! priv->route->graph || ! priv->route->graph->route_points)
2107                 return NULL;
2108         mr=g_new0(struct map_rect_priv, 1);
2109         mr->mpriv = priv;
2110         mr->item.priv_data = mr;
2111         mr->item.type = type_rg_point;
2112         mr->item.meth = &methods_point_item;
2113         if (sel) {
2114                 if ((sel->u.c_rect.lu.x == sel->u.c_rect.rl.x) && (sel->u.c_rect.lu.y == sel->u.c_rect.rl.y)) {
2115                         mr->coord_sel = g_malloc(sizeof(struct coord));
2116                         *(mr->coord_sel) = sel->u.c_rect.lu;
2117                 }
2118         }
2119         return mr;
2120 }
2121
2122 static void
2123 rm_rect_destroy(struct map_rect_priv *mr)
2124 {
2125         if (mr->str)
2126                 g_free(mr->str);
2127         if (mr->coord_sel) {
2128                 g_free(mr->coord_sel);
2129         }
2130
2131         g_free(mr);
2132 }
2133
2134 static struct item *
2135 rp_get_item(struct map_rect_priv *mr)
2136 {
2137         struct route *r = mr->mpriv->route;
2138         struct route_graph_point *p = mr->point;
2139         struct route_graph_segment *seg = mr->rseg;
2140
2141         if (mr->item.type == type_rg_point) {
2142                 if (mr->coord_sel) {
2143                         // We are supposed to return only the point at one specified coordinate...
2144                         if (!p) {
2145                                 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2146                                 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2147                                         p = p->hash_next;
2148                                 }
2149                                 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2150                                         mr->point = NULL; // This indicates that no point has been found
2151                                 } else {
2152                                         mr->it = rp_iterator_new(p);
2153                                 }
2154                         } else {
2155                                 p = NULL;
2156                         }
2157                 } else {
2158                         if (!p)
2159                                 p = r->graph->route_points;
2160                         else
2161                                 p = p->next;
2162                 }
2163                 if (p) {
2164                         mr->point = p;
2165                         mr->item.id_lo++;
2166                         rm_coord_rewind(mr);
2167                         rp_attr_rewind(mr);
2168                         return &mr->item;
2169                 } else
2170                         mr->item.type = type_rg_segment;
2171         }
2172
2173         if (mr->coord_sel) {
2174                 if (!mr->point) { // This means that no point has been found
2175                         return NULL;
2176                 }
2177                 seg = rp_iterator_next(&(mr->it));
2178         } else {
2179                 if (!seg)
2180                         seg=r->graph->route_segments;
2181                 else
2182                         seg=seg->next;
2183         }
2184
2185         if (seg) {
2186                 mr->rseg = seg;
2187                 mr->item.id_lo++;
2188                 rm_coord_rewind(mr);
2189                 rp_attr_rewind(mr);
2190                 return &mr->item;
2191         }
2192         return NULL;
2193
2194 }
2195
2196 static struct item *
2197 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2198 {
2199         struct item *ret=NULL;
2200         while (id_lo-- > 0)
2201                 ret=rp_get_item(mr);
2202         return ret;
2203 }
2204
2205
2206 static struct item *
2207 rm_get_item(struct map_rect_priv *mr)
2208 {
2209         dbg(1,"enter\n", mr->pos);
2210
2211         mr->seg=mr->seg_next;
2212         if (! mr->seg)
2213                 return NULL;
2214         mr->seg_next=mr->seg->next;
2215         mr->last_coord = 0;
2216         mr->item.id_lo++;
2217         rm_attr_rewind(mr);
2218         return &mr->item;
2219 }
2220
2221 static struct item *
2222 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2223 {
2224         struct item *ret=NULL;
2225         while (id_lo-- > 0)
2226                 ret=rm_get_item(mr);
2227         return ret;
2228 }
2229
2230 static struct map_methods route_meth = {
2231         projection_mg,
2232         "utf-8",
2233         rm_destroy,
2234         rm_rect_new,
2235         rm_rect_destroy,
2236         rm_get_item,
2237         rm_get_item_byid,
2238         NULL,
2239         NULL,
2240         NULL,
2241 };
2242
2243 static struct map_methods route_graph_meth = {
2244         projection_mg,
2245         "utf-8",
2246         rp_destroy,
2247         rp_rect_new,
2248         rm_rect_destroy,
2249         rp_get_item,
2250         rp_get_item_byid,
2251         NULL,
2252         NULL,
2253         NULL,
2254 };
2255
2256 void
2257 route_toggle_routegraph_display(struct route *route)
2258 {
2259         if (route->flags & RF_SHOWGRAPH) {
2260                 route->flags &= ~RF_SHOWGRAPH;
2261         } else {
2262                 route->flags |= RF_SHOWGRAPH;
2263         }
2264 }
2265
2266 static struct map_priv *
2267 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2268 {
2269         struct map_priv *ret;
2270         struct attr *route_attr;
2271
2272         route_attr=attr_search(attrs, NULL, attr_route);
2273         if (! route_attr)
2274                 return NULL;
2275         ret=g_new0(struct map_priv, 1);
2276         if (graph)
2277                 *meth=route_graph_meth;
2278         else
2279                 *meth=route_meth;
2280         ret->route=route_attr->u.route;
2281
2282         return ret;
2283 }
2284
2285 static struct map_priv *
2286 route_map_new(struct map_methods *meth, struct attr **attrs)
2287 {
2288         return route_map_new_helper(meth, attrs, 0);
2289 }
2290
2291 static struct map_priv *
2292 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2293 {
2294         return route_map_new_helper(meth, attrs, 1);
2295 }
2296
2297 static struct map *
2298 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2299 {
2300         if (! *map)
2301                 *map=map_new(NULL, (struct attr*[]){
2302                                 &(struct attr){attr_type,{type}},
2303                                 &(struct attr){attr_route,.u.route=this_},
2304                                 &(struct attr){attr_data,{""}},
2305                                 &(struct attr){attr_description,{description}},
2306                                 NULL});
2307
2308         return *map;
2309 }
2310
2311 /**
2312  * @brief Returns a new map containing the route path
2313  *
2314  * This function returns a new map containing the route path.
2315  *
2316  * @important Do not map_destroy() this!
2317  *
2318  * @param this_ The route to get the map of
2319  * @return A new map containing the route path
2320  */
2321 struct map *
2322 route_get_map(struct route *this_)
2323 {
2324         return route_get_map_helper(this_, &this_->map, "route","Route");
2325 }
2326
2327
2328 /**
2329  * @brief Returns a new map containing the route graph
2330  *
2331  * This function returns a new map containing the route graph.
2332  *
2333  * @important Do not map_destroy()  this!
2334  *
2335  * @param this_ The route to get the map of
2336  * @return A new map containing the route graph
2337  */
2338 struct map *
2339 route_get_graph_map(struct route *this_)
2340 {
2341         return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2342 }
2343
2344 void
2345 route_set_projection(struct route *this_, enum projection pro)
2346 {
2347 }
2348
2349 void
2350 route_init(void)
2351 {
2352         plugin_register_map_type("route", route_map_new);
2353         plugin_register_map_type("route_graph", route_graph_map_new);
2354 }