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         s=start->start;
 852         while (s) {
 853                 if (item_is_equal(*item, s->item) && (s->offset == offset))
 854                         return;
 855                 s=s->start_next;
 856         }
 857
 858         s = g_new0(struct route_graph_segment, 1);
 859         if (!s) {
 860                 printf("%s:Out of memory\n", __FUNCTION__);
 861                 return;
 862         }
 863         s->start=start;
 864         s->start_next=start->start;
 865         start->start=s;
 866         s->end=end;
 867         s->end_next=end->end;
 868         end->end=s;
 869         dbg_assert(len >= 0);
 870         s->len=len;
 871         s->item=*item;
 872         s->flags=flags;
 873         s->offset = offset;
 874         s->next=this->route_segments;
 875         this->route_segments=s;
 876         if (debug_route)
 877                 printf("l (0x%x,0x%x)-(0x%x,0x%x)\n", start->c.x, start->c.y, end->c.x, end->c.y);
 878 }
 879
 880 /**
 881  * @brief Gets all the coordinates of an item
 882  *
 883  * This will get all the coordinates of the item i and return them in c,
 884  * up to max coordinates. Additionally it is possible to limit the coordinates
 885  * returned to all the coordinates of the item between the two coordinates
 886  * start end end.
 887  *
 888  * @important Make shure that whatever c points to has enough memory allocated
 889  * @important to hold max coordinates!
 890  *
 891  * @param i The item to get the coordinates of
 892  * @param c Pointer to memory allocated for holding the coordinates
 893  * @param max Maximum number of coordinates to return
 894  * @param start First coordinate to get
 895  * @param end Last coordinate to get
 896  * @return The number of coordinates returned
 897  */
 898 static int get_item_seg_coords(struct item *i, struct coord *c, int max,
 899                 struct coord *start, struct coord *end)
 900 {
 901         struct map_rect *mr;
 902         struct item *item;
 903         int rc = 0, p = 0;
 904         struct coord c1;
 905         mr=map_rect_new(i->map, NULL);
 906         if (!mr)
 907                 return 0;
 908         item = map_rect_get_item_byid(mr, i->id_hi, i->id_lo);
 909         if (item) {
 910                 rc = item_coord_get(item, &c1, 1);
 911                 while (rc && (c1.x != start->x || c1.y != start->y)) {
 912                         rc = item_coord_get(item, &c1, 1);
 913                 }
 914                 while (rc && p < max) {
 915                         c[p++] = c1;
 916                         if (c1.x == end->x && c1.y == end->y)
 917                                 break;
 918                         rc = item_coord_get(item, &c1, 1);
 919                 }
 920         }
 921         map_rect_destroy(mr);
 922         return p;
 923 }
 924
 925 /**
 926  * @brief Returns and removes one segment from a path
 927  *
 928  * @param path The path to take the segment from
 929  * @param item The item whose segment to remove
 930  * @param offset Offset of the segment within the item to remove. If the item is not segmented this should be 1.
 931  * @return The segment removed
 932  */
 933 static struct route_path_segment *
 934 route_extract_segment_from_path(struct route_path *path, struct item *item,
 935                                                  int offset)
 936 {
 937         struct route_path_segment *sp = NULL, *s;
 938         s = path->path;
 939         while (s) {
 940                 if (s->offset == offset && item_is_equal(s->item,*item)) {
 941                         if (sp) {
 942                                 sp->next = s->next;
 943                                 break;
 944                         } else {
 945                                 path->path = s->next;
 946                                 break;
 947                         }
 948                 }
 949                 sp = s;
 950                 s = s->next;
 951         }
 952         if (s)
 953                 item_hash_remove(path->path_hash, item);
 954         return s;
 955 }
 956
 957 /**
 958  * @brief Adds a segment and the end of a path
 959  *
 960  * @param this The path to add the segment to
 961  * @param segment The segment to add
 962  */
 963 static void
 964 route_path_add_segment(struct route_path *this, struct route_path_segment *segment)
 965 {
 966         if (!this->path)
 967                 this->path=segment;
 968         if (this->path_last)
 969                 this->path_last->next=segment;
 970         this->path_last=segment;
 971 }
 972
 973 /**
 974  * @brief Adds a new item to a path
 975  *
 976  * This adds a new item to a path, creating a new segment for it. Please note that this function does not check
 977  * if the item passed is segmented - it will create exactly one segment.
 978  *
 979  * @param this The path to add the item to
 980  * @param item The item to add
 981  * @param len The length of the item
 982  * @param first (Optional) coordinate to add to the start of the item. If none should be added, make this NULL.
 983  * @param c Pointer to count coordinates of the item.
 984  * @param cound Number of coordinates in c
 985  * @param last (Optional) coordinate to add to the end of the item. If none should be added, make this NULL.
 986  * @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"
 987  */
 988 static void
 989 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)
 990 {
 991         int i,idx=0,ccount=count + (first ? 1:0) + (last ? 1:0);
 992         struct route_path_segment *segment;
 993
 994         segment=g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccount);
 995         segment->ncoords=ccount;
 996         segment->direction=dir;
 997         if (first)
 998                 segment->c[idx++]=*first;
 999         if (dir > 0) {
1000                 for (i = 0 ; i < count ; i++)
1001                         segment->c[idx++]=c[i];
1002         } else {
1003                 for (i = 0 ; i < count ; i++)
1004                         segment->c[idx++]=c[count-i-1];
1005         }
1006         if (last)
1007                 segment->c[idx++]=*last;
1008         segment->length=len;
1009         if (item)
1010                 segment->item=*item;
1011         route_path_add_segment(this, segment);
1012 }
1013
1014 /**
1015  * @brief Inserts a new item into the path
1016  *
1017  * This function does almost the same as "route_apth_add_item()", but identifies
1018  * the item to add by a segment from the route graph. Another difference is that it "copies" the
1019  * segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will
1020  * be added to the route path, not all segments of the item.
1021  *
1022  * The function can be sped up by passing an old path already containing this segment in oldpath -
1023  * the segment will then be extracted from this old path. Please note that in this case the direction
1024  * parameter has no effect.
1025  *
1026  * @param this The path to add the item to
1027  * @param oldpath Old path containing the segment to be added. Speeds up the function, but can be NULL.
1028  * @param rgs Segment of the route graph that should be "copied" to the route path
1029  * @param len Length of the item to be added
1030  * @param offset Offset of rgs within the item it represents
1031  * @param dir Order in which to add the coordinates. See route_path_add_item()
1032  * @param straight Indicates if this segment is being entered "straight". See route_check_straight().
1033  */
1034 static void
1035 route_path_add_item_from_graph(struct route_path *this, struct route_path *oldpath,
1036                                    struct route_graph_segment *rgs, int len, int offset, int dir, int straight)
1037 {
1038         struct route_path_segment *segment;
1039         int i,ccnt = 0;
1040         struct coord ca[2048];
1041
1042         if (oldpath) {
1043                 ccnt = (int)item_hash_lookup(oldpath->path_hash, &rgs->item);
1044                 if (ccnt) {
1045                         segment = route_extract_segment_from_path(oldpath,
1046                                                          &rgs->item, offset);
1047
1048                         if (segment)
1049                                 goto linkold;
1050                 }
1051         }
1052
1053         ccnt = get_item_seg_coords(&rgs->item, ca, 2047, &rgs->start->c, &rgs->end->c);
1054         segment= g_malloc0(sizeof(*segment) + sizeof(struct coord) * ccnt);
1055         if (!segment) {
1056                 printf("%s:Out of memory\n", __FUNCTION__);
1057                 return;
1058         }
1059         segment->direction=dir;
1060         if (dir > 0) {
1061                 for (i = 0 ; i < ccnt ; i++)
1062                         segment->c[i]=ca[i];
1063         } else {
1064                 for (i = 0 ; i < ccnt ; i++)
1065                         segment->c[i]=ca[ccnt-i-1];
1066         }
1067         segment->ncoords = ccnt;
1068         segment->item=rgs->item;
1069         segment->offset = offset;
1070 linkold:
1071         segment->length=len;
1072         segment->next=NULL;
1073         item_hash_insert(this->path_hash,  &rgs->item, (void *)ccnt);
1074
1075         route_path_add_segment(this, segment);
1076 }
1077
1078 /**
1079  * @brief Destroys all segments of a route graph
1080  *
1081  * @param this The graph to destroy all segments from
1082  */
1083 static void
1084 route_graph_free_segments(struct route_graph *this)
1085 {
1086         struct route_graph_segment *curr,*next;
1087         curr=this->route_segments;
1088         while (curr) {
1089                 next=curr->next;
1090                 g_free(curr);
1091                 curr=next;
1092         }
1093         this->route_segments=NULL;
1094 }
1095
1096 /**
1097  * @brief Destroys a route graph
1098  *
1099  * @param this The route graph to be destroyed
1100  */
1101 static void
1102 route_graph_destroy(struct route_graph *this)
1103 {
1104         if (this) {
1105                 route_graph_free_points(this);
1106                 route_graph_free_segments(this);
1107                 g_free(this);
1108         }
1109 }
1110
1111 /**
1112  * @brief Returns the time needed to drive len on item
1113  *
1114  * @param speedlist The speedlist that should be used
1115  * @param item The item to be driven on
1116  * @param len The length to drive
1117  * @return The time needed to drive len on item
1118  */
1119 int
1120 route_time(int *speedlist, struct item *item, int len)
1121 {
1122         if (item->type < route_item_first || item->type > route_item_last) {
1123                 dbg(0,"street type %d out of range [%d,%d]\n", item->type, route_item_first, route_item_last);
1124                 return len*36;
1125         }
1126         if (!speedlist[item->type-route_item_first]) {
1127                 dbg(0,"street type %d speed is zero\n", item->type);
1128                 return len*36;
1129         }
1130         return len*36/speedlist[item->type-route_item_first];
1131 }
1132
1133 /**
1134  * @brief Returns the "costs" of driving len on item
1135  *
1136  * @param speedlist The speedlist that should be used
1137  * @param item The item to be driven on
1138  * @param len The length to drive
1139  * @return The "costs" needed to drive len on item
1140  */
1141 static int
1142 route_value(int *speedlist, struct item *item, int len)
1143 {
1144         int ret;
1145         if (len < 0) {
1146                 printf("len=%d\n", len);
1147         }
1148         dbg_assert(len >= 0);
1149         ret=route_time(speedlist, item, len);
1150         dbg(1, "route_value(0x%x, %d)=%d\n", item->type, len, ret);
1151         return ret;
1152 }
1153
1154 /**
1155  * @brief Adds an item to the route graph
1156  *
1157  * This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a
1158  * segmented item.
1159  *
1160  * @param this The route graph to add to
1161  * @param item The item to add
1162  */
1163 static void
1164 route_process_street_graph(struct route_graph *this, struct item *item)
1165 {
1166 #ifdef AVOID_FLOAT
1167         int len=0;
1168 #else
1169         double len=0;
1170 #endif
1171         struct route_graph_point *s_pnt,*e_pnt;
1172         struct coord c,l;
1173         struct attr attr;
1174         int flags = 0;
1175         int segmented = 0;
1176         int offset = 1;
1177
1178         if (item_coord_get(item, &l, 1)) {
1179                 if (item_attr_get(item, attr_flags, &attr)) {
1180                         flags = attr.u.num;
1181                         if (flags & AF_SEGMENTED)
1182                                 segmented = 1;
1183                 }
1184                 s_pnt=route_graph_add_point(this,&l);
1185                 if (!segmented) {
1186                         while (item_coord_get(item, &c, 1)) {
1187                                 len+=transform_distance(map_projection(item->map), &l, &c);
1188                                 l=c;
1189                         }
1190                         e_pnt=route_graph_add_point(this,&l);
1191                         dbg_assert(len >= 0);
1192                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1193                 } else {
1194                         int isseg,rc;
1195                         int sc = 0;
1196                         do {
1197                                 isseg = item_coord_is_node(item);
1198                                 rc = item_coord_get(item, &c, 1);
1199                                 if (rc) {
1200                                         len+=transform_distance(map_projection(item->map), &l, &c);
1201                                         l=c;
1202                                         if (isseg) {
1203                                                 e_pnt=route_graph_add_point(this,&l);
1204                                                 route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1205                                                 offset++;
1206                                                 s_pnt=route_graph_add_point(this,&l);
1207                                                 len = 0;
1208                                         }
1209                                 }
1210                         } while(rc);
1211                         e_pnt=route_graph_add_point(this,&l);
1212                         dbg_assert(len >= 0);
1213                         sc++;
1214                         route_graph_add_segment(this, s_pnt, e_pnt, len, item, flags, offset);
1215                 }
1216         }
1217 }
1218
1219 /**
1220  * @brief Compares the costs of reaching the destination from two points on
1221  *
1222  * @important Do not pass anything other than route_graph_points in v1 and v2!
1223  *
1224  * @param v1 Point1
1225  * @param v2 Point2
1226  * @return The additional costs of v1 compared to v2 (may be negative)
1227  */
1228 static int
1229 compare(void *v1, void *v2)
1230 {
1231         struct route_graph_point *p1=v1;
1232         struct route_graph_point *p2=v2;
1233 #if 0
1234         if (debug_route)
1235                 printf("compare %d (%p) vs %d (%p)\n", p1->value,p1,p2->value,p2);
1236 #endif
1237         return p1->value-p2->value;
1238 }
1239
1240 /**
1241  * @brief Calculates the routing costs for each point
1242  *
1243  * This function is the heart of routing. It assigns each point in the route graph a
1244  * cost at which one can reach the destination from this point on. Additionally it assigns
1245  * each point a segment one should follow from this point on to reach the destination at the
1246  * stated costs.
1247  *
1248  * This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look
1249  * at this algorithm.
1250  */
1251 static void
1252 route_graph_flood(struct route_graph *this, struct route_info *dst, int *speedlist)
1253 {
1254         struct route_graph_point *p_min,*end=NULL;
1255         struct route_graph_segment *s;
1256         int min,new,old,val;
1257         struct fibheap *heap; /* This heap will hold all points with "temporarily" calculated costs */
1258         struct street_data *sd=dst->street;
1259
1260         heap = fh_makeheap();
1261         fh_setcmp(heap, compare);
1262
1263         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 */
1264                 end=route_graph_get_point(this, &sd->c[0]);
1265                 dbg_assert(end != 0);
1266                 end->value=route_value(speedlist, &sd->item, dst->lenneg);
1267                 end->el=fh_insert(heap, end);
1268         }
1269
1270         if (! (sd->flags & AF_ONEWAY)) { /* If we may drive against the direction of the coordinates, the last coordinate is another starting point */
1271                 end=route_graph_get_point(this, &sd->c[sd->count-1]);
1272                 dbg_assert(end != 0);
1273                 end->value=route_value(speedlist, &sd->item, dst->lenpos);
1274                 end->el=fh_insert(heap, end);
1275         }
1276
1277         dbg(1,"0x%x,0x%x\n", end->c.x, end->c.y);
1278         for (;;) {
1279                 p_min=fh_extractmin(heap); /* Starting Dijkstra by selecting the point with the minimum costs on the heap */
1280                 if (! p_min) /* There are no more points with temporarily calculated costs, Dijkstra has finished */
1281                         break;
1282                 min=p_min->value;
1283                 if (debug_route)
1284                         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);
1285                 p_min->el=NULL; /* This point is permanently calculated now, we've taken it out of the heap */
1286                 s=p_min->start;
1287                 while (s) { /* Iterating all the segments leading away from our point to update the points at their ends */
1288                         val=route_value(speedlist, &s->item, s->len);
1289 #if 0
1290                         val+=val*2*street_route_contained(s->str->segid);
1291 #endif
1292                         new=min+val;
1293                         if (debug_route)
1294                                 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);
1295                         if (new < s->end->value && !(s->flags & AF_ONEWAY)) { /* We've found a less costly way to reach the end of s, update it */
1296                                 s->end->value=new;
1297                                 s->end->seg=s;
1298                                 if (! s->end->el) {
1299                                         if (debug_route)
1300                                                 printf("insert_end p=%p el=%p val=%d ", s->end, s->end->el, s->end->value);
1301                                         s->end->el=fh_insert(heap, s->end);
1302                                         if (debug_route)
1303                                                 printf("el new=%p\n", s->end->el);
1304                                 }
1305                                 else {
1306                                         if (debug_route)
1307                                                 printf("replace_end p=%p el=%p val=%d\n", s->end, s->end->el, s->end->value);
1308                                         fh_replacedata(heap, s->end->el, s->end);
1309                                 }
1310                         }
1311                         if (debug_route)
1312                                 printf("\n");
1313                         s=s->start_next;
1314                 }
1315                 s=p_min->end;
1316                 while (s) { /* Doing the same as above with the segments leading towards our point */
1317                         val=route_value(speedlist, &s->item, s->len);
1318                         new=min+val;
1319                         if (debug_route)
1320                                 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);
1321                         if (new < s->start->value && !(s->flags & AF_ONEWAYREV)) {
1322                                 old=s->start->value;
1323                                 s->start->value=new;
1324                                 s->start->seg=s;
1325                                 if (! s->start->el) {
1326                                         if (debug_route)
1327                                                 printf("insert_start p=%p el=%p val=%d ", s->start, s->start->el, s->start->value);
1328                                         s->start->el=fh_insert(heap, s->start);
1329                                         if (debug_route)
1330                                                 printf("el new=%p\n", s->start->el);
1331                                 }
1332                                 else {
1333                                         if (debug_route)
1334                                                 printf("replace_start p=%p el=%p val=%d\n", s->start, s->start->el, s->start->value);
1335                                         fh_replacedata(heap, s->start->el, s->start);
1336                                 }
1337                         }
1338                         if (debug_route)
1339                                 printf("\n");
1340                         s=s->end_next;
1341                 }
1342         }
1343         fh_deleteheap(heap);
1344 }
1345
1346 /**
1347  * @brief Starts an "offroad" path
1348  *
1349  * This starts a path that is not located on a street. It creates a new route path
1350  * adding only one segment, that leads from pos to dest, and which is not associated with an item.
1351  *
1352  * @param this Not used
1353  * @param pos The starting position for the new path
1354  * @param dst The destination of the new path
1355  * @param dir Not used
1356  * @return The new path
1357  */
1358 static struct route_path *
1359 route_path_new_offroad(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1360 {
1361         struct route_path *ret;
1362
1363         ret=g_new0(struct route_path, 1);
1364         ret->path_hash=item_hash_new();
1365         route_path_add_item(ret, NULL, pos->lenextra+dst->lenextra, &pos->c, NULL, 0, &dst->c, 1);
1366
1367         return ret;
1368 }
1369
1370 /**
1371  * @brief Creates a new "trivial" route
1372  *
1373  * This function creates a new "trivial" route. A trivial route is a route that starts and ends on the same street,
1374  * so there is no routing needed. Depending on pos and dst it can optionally add some "offroad" part to the route.
1375  *
1376  * @param this The route graph to place the route on
1377  * @param pos The starting position for the new path
1378  * @param dst The destination of the new path
1379  * @param dir Direction of the coordinates to be added
1380  * @return The new path
1381  */
1382 static struct route_path *
1383 route_path_new_trivial(struct route_graph *this, struct route_info *pos, struct route_info *dst, int dir)
1384 {
1385         struct street_data *sd=pos->street;
1386         struct route_path *ret;
1387
1388         if (dir > 0) {
1389                 if (pos->lenextra + dst->lenextra + pos->lenneg-dst->lenneg > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1390                         return route_path_new_offroad(this, pos, dst, dir);
1391         } else {
1392                 if (pos->lenextra + dst->lenextra + pos->lenpos-dst->lenpos > transform_distance(map_projection(sd->item.map), &pos->c, &dst->c))
1393                         return route_path_new_offroad(this, pos, dst, dir);
1394         }
1395         ret=g_new0(struct route_path, 1);
1396         ret->path_hash=item_hash_new();
1397         if (pos->lenextra)
1398                 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1399         if (dir > 0)
1400                 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);
1401         else
1402                 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);
1403         if (dst->lenextra)
1404                 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1405         return ret;
1406 }
1407
1408 /**
1409  * @brief Creates a new route path
1410  *
1411  * This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so
1412  * make shure to run route_graph_flood() after changing the destination before using this function.
1413  *
1414  * @param this The route graph to create the route from
1415  * @param oldpath (Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
1416  * @param pos The starting position of the route
1417  * @param dst The destination of the route
1418  * @param speedlist The speedlist to use
1419  * @return The new route path
1420  */
1421 static struct route_path *
1422 route_path_new(struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, int *speedlist)
1423 {
1424         struct route_graph_point *start1=NULL,*start2=NULL,*start;
1425         struct route_graph_segment *s=NULL;
1426         struct route_graph_segment *lastseg = NULL;
1427         int is_straight=0;
1428         int len=0,segs=0;
1429         int seg_len;
1430 #if 0
1431         int time=0,hr,min,sec
1432 #endif
1433         unsigned int val1=0xffffffff,val2=0xffffffff;
1434         struct street_data *sd=pos->street;
1435         struct route_path *ret;
1436
1437         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 */
1438                 if (!(sd->flags & AF_ONEWAY) && pos->lenneg >= dst->lenneg) {
1439                         return route_path_new_trivial(this, pos, dst, -1);
1440                 }
1441                 if (!(sd->flags & AF_ONEWAYREV) && pos->lenpos >= dst->lenpos) {
1442                         return route_path_new_trivial(this, pos, dst, 1);
1443                 }
1444         }
1445         if (! (sd->flags & AF_ONEWAY)) { /* Using the start of the current segment as one starting point */
1446                 start1=route_graph_get_point(this, &sd->c[0]);
1447                 if (! start1)
1448                         return NULL;
1449                 val1=start1->value+route_value(speedlist, &sd->item, pos->lenneg);
1450                 dbg(1,"start1: %d(route)+%d=%d\n", start1->value, val1-start1->value, val1);
1451         }
1452         if (! (sd->flags & AF_ONEWAYREV)) { /* Using the start of the current segment as an alternative starting point */
1453                 start2=route_graph_get_point(this, &sd->c[sd->count-1]);
1454                 if (! start2)
1455                         return NULL;
1456                 val2=start2->value+route_value(speedlist, &sd->item, pos->lenpos);
1457                 dbg(1,"start2: %d(route)+%d=%d\n", start2->value, val2-start2->value, val2);
1458         }
1459         dbg(1,"val1=%d val2=%d\n", val1, val2);
1460         if (val1 == val2) {
1461                 val1=start1->start->start->value;
1462                 val2=start2->end->end->value;
1463         }
1464         ret=g_new0(struct route_path, 1);
1465         if (pos->lenextra)
1466                 route_path_add_item(ret, NULL, pos->lenextra, &pos->c, NULL, 0, &pos->lp, 1);
1467         if (start1 && (val1 < val2)) {
1468                 start=start1;
1469                 route_path_add_item(ret, &sd->item, pos->lenneg, &pos->lp, sd->c, pos->pos+1, NULL, -1);
1470         } else {
1471                 if (start2) {
1472                         start=start2;
1473                         route_path_add_item(ret, &sd->item, pos->lenpos, &pos->lp, sd->c+pos->pos+1, sd->count-pos->pos-1, NULL, 1);
1474                 } else {
1475                         printf("no route found, pos blocked\n");
1476                         return NULL;
1477                 }
1478         }
1479         ret->path_hash=item_hash_new();
1480         while ((s=start->seg)) { /* following start->seg, which indicates the least costly way to reach our destination */
1481                 segs++;
1482 #if 0
1483                 printf("start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1484 #endif
1485                 seg_len=s->len;
1486                 len+=seg_len;
1487
1488                 if (s->start == start) {
1489                         route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, 1, is_straight);
1490                         start=s->end;
1491                 } else {
1492                         route_path_add_item_from_graph(ret, oldpath, s, seg_len, s->offset, -1, is_straight);
1493                         start=s->start;
1494                 }
1495
1496                 lastseg = s;
1497         }
1498         sd=dst->street;
1499         dbg(1,"start->value=%d 0x%x,0x%x\n", start->value, start->c.x, start->c.y);
1500         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);
1501         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 */
1502                 route_path_add_item(ret, &sd->item, dst->lenneg, NULL, sd->c, dst->pos+1, &dst->lp, 1);
1503         } else if (start->c.x == sd->c[sd->count-1].x && start->c.y == sd->c[sd->count-1].y) {
1504                 route_path_add_item(ret, &sd->item, dst->lenpos, NULL, sd->c+dst->pos+1, sd->count-dst->pos-1, &dst->lp, -1);
1505         } else {
1506                 printf("no route found\n");
1507                 route_path_destroy(ret);
1508                 return NULL;
1509         }
1510         if (dst->lenextra)
1511                 route_path_add_item(ret, NULL, dst->lenextra, &dst->lp, NULL, 0, &dst->c, 1);
1512         dbg(1, "%d segments\n", segs);
1513         return ret;
1514 }
1515
1516 /**
1517  * @brief Builds a new route graph from a mapset
1518  *
1519  * This function builds a new route graph from a map. Please note that this function does not
1520  * add any routing information to the route graph - this has to be done via the route_graph_flood()
1521  * function.
1522  *
1523  * The function does not create a graph covering the whole map, but only covering the rectangle
1524  * between c1 and c2.
1525  *
1526  * @param ms The mapset to build the route graph from
1527  * @param c1 Corner 1 of the rectangle to use from the map
1528  * @param c2 Corner 2 of the rectangle to use from the map
1529  * @return The new route graph.
1530  */
1531 static struct route_graph *
1532 route_graph_build(struct mapset *ms, struct coord *c1, struct coord *c2)
1533 {
1534         struct route_graph *ret=g_new0(struct route_graph, 1);
1535         struct map_selection *sel;
1536         struct mapset_handle *h;
1537         struct map_rect *mr;
1538         struct map *m;
1539         struct item *item;
1540
1541         if (!ret) {
1542                 printf("%s:Out of memory\n", __FUNCTION__);
1543                 return ret;
1544         }
1545         sel=route_calc_selection(c1, c2);
1546         h=mapset_open(ms);
1547         while ((m=mapset_next(h,1))) {
1548                 mr=map_rect_new(m, sel);
1549                 if (! mr)
1550                         continue;
1551                 while ((item=map_rect_get_item(mr))) {
1552                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1553                                 route_process_street_graph(ret, item);
1554                         }
1555                 }
1556                 map_rect_destroy(mr);
1557         }
1558         mapset_close(h);
1559         route_free_selection(sel);
1560
1561         return ret;
1562 }
1563
1564 /**
1565  * @brief Updates the route graph
1566  *
1567  * This updates the route graph after settings in the route have changed. It also
1568  * adds routing information afterwards by calling route_graph_flood().
1569  *
1570  * @param this The route to update the graph for
1571  */
1572 static void
1573 route_graph_update(struct route *this)
1574 {
1575         route_graph_destroy(this->graph);
1576         profile(1,"graph_free");
1577         this->graph=route_graph_build(this->ms, &this->pos->c, &this->dst->c);
1578         profile(1,"route_graph_build");
1579         route_graph_flood(this->graph, this->dst, this->speedlist);
1580         profile(1,"route_graph_flood");
1581         this->version++;
1582 }
1583
1584 /**
1585  * @brief Gets street data for an item
1586  *
1587  * @param item The item to get the data for
1588  * @return Street data for the item
1589  */
1590 struct street_data *
1591 street_get_data (struct item *item)
1592 {
1593         int count=0;
1594         struct street_data *ret = NULL, *ret1;
1595         struct attr attr;
1596         const int step = 128;
1597         int c;
1598
1599         do {
1600                 ret1=g_realloc(ret, sizeof(struct street_data)+(count+step)*sizeof(struct coord));
1601                 if (!ret1) {
1602                         if (ret)
1603                                 g_free(ret);
1604                         return NULL;
1605                 }
1606                 ret = ret1;
1607                 c = item_coord_get(item, &ret->c[count], step);
1608                 count += c;
1609         } while (c && c == step);
1610
1611         ret1=g_realloc(ret, sizeof(struct street_data)+count*sizeof(struct coord));
1612         if (ret1)
1613                 ret = ret1;
1614         ret->item=*item;
1615         ret->count=count;
1616         if (item_attr_get(item, attr_flags, &attr))
1617                 ret->flags=attr.u.num;
1618         else
1619                 ret->flags=0;
1620
1621         return ret;
1622 }
1623
1624 /**
1625  * @brief Copies street data
1626  *
1627  * @param orig The street data to copy
1628  * @return The copied street data
1629  */
1630 struct street_data *
1631 street_data_dup(struct street_data *orig)
1632 {
1633         struct street_data *ret;
1634         int size=sizeof(struct street_data)+orig->count*sizeof(struct coord);
1635
1636         ret=g_malloc(size);
1637         memcpy(ret, orig, size);
1638
1639         return ret;
1640 }
1641
1642 /**
1643  * @brief Frees street data
1644  *
1645  * @param sd Street data to be freed
1646  */
1647 void
1648 street_data_free(struct street_data *sd)
1649 {
1650         g_free(sd);
1651 }
1652
1653 /**
1654  * @brief Finds the nearest street to a given coordinate
1655  *
1656  * @param ms The mapset to search in for the street
1657  * @param pc The coordinate to find a street nearby
1658  * @return The nearest street
1659  */
1660 static struct route_info *
1661 route_find_nearest_street(struct mapset *ms, struct pcoord *pc)
1662 {
1663         struct route_info *ret=NULL;
1664         int max_dist=1000;
1665         struct map_selection *sel;
1666         int dist,mindist=0,pos;
1667         struct mapset_handle *h;
1668         struct map *m;
1669         struct map_rect *mr;
1670         struct item *item;
1671         struct coord lp;
1672         struct street_data *sd;
1673         struct coord c;
1674         struct coord_geo g;
1675
1676         ret=g_new0(struct route_info, 1);
1677         if (!ret) {
1678                 dbg(0,"Out of memory\n");
1679                 return ret;
1680         }
1681         mindist = INT_MAX;
1682
1683         h=mapset_open(ms);
1684         while ((m=mapset_next(h,1))) {
1685                 c.x = pc->x;
1686                 c.y = pc->y;
1687                 if (map_projection(m) != pc->pro) {
1688                         transform_to_geo(pc->pro, &c, &g);
1689                         transform_from_geo(map_projection(m), &g, &c);
1690                 }
1691                 sel = route_rect(18, &c, &c, 0, max_dist);
1692                 if (!sel)
1693                         continue;
1694                 mr=map_rect_new(m, sel);
1695                 if (!mr) {
1696                         map_selection_destroy(sel);
1697                         continue;
1698                 }
1699                 while ((item=map_rect_get_item(mr))) {
1700                         if (item->type >= type_street_0 && item->type <= type_ferry) {
1701                                 sd=street_get_data(item);
1702                                 if (!sd)
1703                                         continue;
1704                                 dist=transform_distance_polyline_sq(sd->c, sd->count, &c, &lp, &pos);
1705                                 if (dist < mindist) {
1706                                         mindist = dist;
1707                                         if (ret->street) {
1708                                                 street_data_free(ret->street);
1709                                         }
1710                                         ret->c=c;
1711                                         ret->lp=lp;
1712                                         ret->pos=pos;
1713                                         ret->street=sd;
1714                                         dbg(1,"dist=%d id 0x%x 0x%x pos=%d\n", dist, item->id_hi, item->id_lo, pos);
1715                                 } else {
1716                                         street_data_free(sd);
1717                                 }
1718                         }
1719                 }
1720                 map_selection_destroy(sel);
1721                 map_rect_destroy(mr);
1722         }
1723         mapset_close(h);
1724
1725         if (!ret->street || mindist > max_dist*max_dist) {
1726                 if (ret->street) {
1727                         street_data_free(ret->street);
1728                         dbg(1,"Much too far %d > %d\n", mindist, max_dist);
1729                 }
1730                 g_free(ret);
1731                 ret = NULL;
1732         }
1733
1734         return ret;
1735 }
1736
1737 /**
1738  * @brief Destroys a route_info
1739  *
1740  * @param info The route info to be destroyed
1741  */
1742 void
1743 route_info_free(struct route_info *inf)
1744 {
1745         if (inf->street)
1746                 street_data_free(inf->street);
1747         g_free(inf);
1748 }
1749
1750
1751 #include "point.h"
1752
1753 /**
1754  * @brief Returns street data for a route info
1755  *
1756  * @param rinf The route info to return the street data for
1757  * @return Street data for the route info
1758  */
1759 struct street_data *
1760 route_info_street(struct route_info *rinf)
1761 {
1762         return rinf->street;
1763 }
1764
1765 #if 0
1766 struct route_crossings *
1767 route_crossings_get(struct route *this, struct coord *c)
1768 {
1769       struct route_point *pnt;
1770       struct route_segment *seg;
1771       int crossings=0;
1772       struct route_crossings *ret;
1773
1774        pnt=route_graph_get_point(this, c);
1775        seg=pnt->start;
1776        while (seg) {
1777                 printf("start: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1778                crossings++;
1779                seg=seg->start_next;
1780        }
1781        seg=pnt->end;
1782        while (seg) {
1783                 printf("end: 0x%x 0x%x\n", seg->item.id_hi, seg->item.id_lo);
1784                crossings++;
1785                seg=seg->end_next;
1786        }
1787        ret=g_malloc(sizeof(struct route_crossings)+crossings*sizeof(struct route_crossing));
1788        ret->count=crossings;
1789        return ret;
1790 }
1791 #endif
1792
1793
1794 struct map_rect_priv {
1795         struct route_info_handle *ri;
1796         enum attr_type attr_next;
1797         int pos;
1798         struct map_priv *mpriv;
1799         struct item item;
1800         int length;
1801         unsigned int last_coord;
1802         struct route_path_segment *seg,*seg_next;
1803         struct route_graph_point *point;
1804         struct route_graph_segment *rseg;
1805         char *str;
1806         struct coord *coord_sel;        /**< Set this to a coordinate if you want to filter for just a single route graph point */
1807         struct route_graph_point_iterator it;
1808 };
1809
1810 static void
1811 rm_coord_rewind(void *priv_data)
1812 {
1813         struct map_rect_priv *mr = priv_data;
1814         mr->last_coord = 0;
1815 }
1816
1817 static void
1818 rm_attr_rewind(void *priv_data)
1819 {
1820         struct map_rect_priv *mr = priv_data;
1821         mr->attr_next = attr_street_item;
1822 }
1823
1824 static int
1825 rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1826 {
1827         struct map_rect_priv *mr = priv_data;
1828         struct route_path_segment *seg=mr->seg;
1829         struct route *route=mr->mpriv->route;
1830         attr->type=attr_type;
1831         switch (attr_type) {
1832                 case attr_any:
1833                         while (mr->attr_next != attr_none) {
1834                                 if (rm_attr_get(priv_data, mr->attr_next, attr))
1835                                         return 1;
1836                         }
1837                         return 0;
1838                 case attr_street_item:
1839                         mr->attr_next=attr_direction;
1840                         if (seg && seg->item.map)
1841                                 attr->u.item=&seg->item;
1842                         else
1843                                 return 0;
1844                         return 1;
1845                 case attr_direction:
1846                         mr->attr_next=attr_route;
1847                         if (seg)
1848                                 attr->u.num=seg->direction;
1849                         else
1850                                 return 0;
1851                         return 1;
1852                 case attr_route:
1853                         mr->attr_next=attr_length;
1854                         attr->u.route = mr->mpriv->route;
1855                         return 1;
1856                 case attr_length:
1857                         if (seg)
1858                                 attr->u.num=seg->length;
1859                         else
1860                                 attr->u.num=mr->length;
1861                         mr->attr_next=attr_time;
1862                         return 1;
1863                 case attr_time:
1864                         mr->attr_next=attr_none;
1865                         if (seg)
1866                                 attr->u.num=route_time(route->speedlist, &seg->item, seg->length);
1867                         else
1868                                 return 0;
1869                         return 1;
1870                 case attr_label:
1871                         mr->attr_next=attr_none;
1872                         return 0;
1873                 default:
1874                         mr->attr_next=attr_none;
1875                         attr->type=attr_none;
1876                         return 0;
1877         }
1878         return 0;
1879 }
1880
1881 static int
1882 rm_coord_get(void *priv_data, struct coord *c, int count)
1883 {
1884         struct map_rect_priv *mr = priv_data;
1885         struct route_path_segment *seg = mr->seg;
1886         int i,rc=0;
1887         struct route *r = mr->mpriv->route;
1888         enum projection pro = route_projection(r);
1889
1890         if (! seg)
1891                 return 0;
1892         for (i=0; i < count; i++) {
1893                 if (mr->last_coord >= seg->ncoords)
1894                         break;
1895                 if (i >= seg->ncoords)
1896                         break;
1897                 if (pro != projection_mg)
1898                         transform_from_to(&seg->c[mr->last_coord++], pro,
1899                                 &c[i],projection_mg);
1900                 else
1901                         c[i] = seg->c[mr->last_coord++];
1902                 rc++;
1903         }
1904         dbg(1,"return %d\n",rc);
1905         return rc;
1906 }
1907
1908 static struct item_methods methods_route_item = {
1909         rm_coord_rewind,
1910         rm_coord_get,
1911         rm_attr_rewind,
1912         rm_attr_get,
1913 };
1914
1915 static void
1916 rp_attr_rewind(void *priv_data)
1917 {
1918         struct map_rect_priv *mr = priv_data;
1919         mr->attr_next = attr_label;
1920 }
1921
1922 static int
1923 rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
1924 {
1925         struct map_rect_priv *mr = priv_data;
1926         struct route_graph_point *p = mr->point;
1927         struct route_graph_segment *seg = mr->rseg;
1928         switch (attr_type) {
1929         case attr_any: // works only with rg_points for now
1930                 if (mr->item.type != type_rg_point)
1931                         return 0;
1932                 while (mr->attr_next != attr_none) {
1933                         if (rp_attr_get(priv_data, mr->attr_next, attr))
1934                                 return 1;
1935                 }
1936                 return 0;
1937         case attr_label:
1938                 if (mr->item.type != type_rg_point)
1939                         return 0;
1940                 attr->type = attr_label;
1941                 if (mr->str)
1942                         g_free(mr->str);
1943                 if (p->value != INT_MAX)
1944                         mr->str=g_strdup_printf("%d", p->value);
1945                 else
1946                         mr->str=g_strdup("-");
1947                 attr->u.str = mr->str;
1948                 mr->attr_next=attr_none;
1949                 return 1;
1950         case attr_street_item:
1951                 if (mr->item.type != type_rg_segment)
1952                         return 0;
1953                 mr->attr_next=attr_none;
1954                 if (seg && seg->item.map)
1955                         attr->u.item=&seg->item;
1956                 else
1957                         return 0;
1958                 return 1;
1959         case attr_direction:
1960                 // This only works if the map has been opened at a single point, and in that case indicates if the
1961                 // segment returned last is connected to this point via its start (1) or its end (-1)
1962                 if (!mr->coord_sel || (mr->item.type != type_rg_segment))
1963                         return 0;
1964                 if (seg->start == mr->point) {
1965                         attr->u.num=1;
1966                 } else if (seg->end == mr->point) {
1967                         attr->u.num=-1;
1968                 } else {
1969                         return 0;
1970                 }
1971                 return 1;
1972         case attr_debug:
1973                 if (mr->item.type != type_rg_point)
1974                         return 0;
1975                 attr->type = attr_debug;
1976                 if (mr->str)
1977                         g_free(mr->str);
1978                 mr->str=g_strdup_printf("x=%d y=%d", p->c.x, p->c.y);
1979                 attr->u.str = mr->str;
1980                 mr->attr_next=attr_none;
1981                 return 1;
1982         default:
1983                 mr->attr_next=attr_none;
1984                 attr->type=attr_none;
1985                 return 0;
1986         }
1987 }
1988
1989 /**
1990  * @brief Returns the coordinates of a route graph item
1991  *
1992  * @param priv_data The route graph item's private data
1993  * @param c Pointer where to store the coordinates
1994  * @param count How many coordinates to get at a max?
1995  * @return The number of coordinates retrieved
1996  */
1997 static int
1998 rp_coord_get(void *priv_data, struct coord *c, int count)
1999 {
2000         struct map_rect_priv *mr = priv_data;
2001         struct route_graph_point *p = mr->point;
2002         struct route_graph_segment *seg = mr->rseg;
2003         int rc = 0,i,dir;
2004         struct route *r = mr->mpriv->route;
2005         enum projection pro = route_projection(r);
2006
2007         for (i=0; i < count; i++) {
2008                 if (mr->item.type == type_rg_point) {
2009                         if (mr->last_coord >= 1)
2010                                 break;
2011                         if (pro != projection_mg)
2012                                 transform_from_to(&p->c, pro,
2013                                         &c[i],projection_mg);
2014                         else
2015                                 c[i] = p->c;
2016                 } else {
2017                         if (mr->last_coord >= 2)
2018                                 break;
2019                         dir=0;
2020                         if (seg->end->seg == seg)
2021                                 dir=1;
2022                         if (mr->last_coord)
2023                                 dir=1-dir;
2024                         if (dir) {
2025                                 if (pro != projection_mg)
2026                                         transform_from_to(&seg->end->c, pro,
2027                                                 &c[i],projection_mg);
2028                                 else
2029                                         c[i] = seg->end->c;
2030                         } else {
2031                                 if (pro != projection_mg)
2032                                         transform_from_to(&seg->start->c, pro,
2033                                                 &c[i],projection_mg);
2034                                 else
2035                                         c[i] = seg->start->c;
2036                         }
2037                 }
2038                 mr->last_coord++;
2039                 rc++;
2040         }
2041         return rc;
2042 }
2043
2044 static struct item_methods methods_point_item = {
2045         rm_coord_rewind,
2046         rp_coord_get,
2047         rp_attr_rewind,
2048         rp_attr_get,
2049 };
2050
2051 static void
2052 rp_destroy(struct map_priv *priv)
2053 {
2054         g_free(priv);
2055 }
2056
2057 static void
2058 rm_destroy(struct map_priv *priv)
2059 {
2060         g_free(priv);
2061 }
2062
2063 static struct map_rect_priv *
2064 rm_rect_new(struct map_priv *priv, struct map_selection *sel)
2065 {
2066         struct map_rect_priv * mr;
2067         dbg(1,"enter\n");
2068         if (! route_get_pos(priv->route))
2069                 return NULL;
2070         if (! route_get_dst(priv->route))
2071                 return NULL;
2072         if (! priv->route->path2)
2073                 return NULL;
2074         mr=g_new0(struct map_rect_priv, 1);
2075         mr->mpriv = priv;
2076         mr->item.priv_data = mr;
2077         mr->item.type = type_street_route;
2078         mr->item.meth = &methods_route_item;
2079         mr->seg_next=priv->route->path2->path;
2080         return mr;
2081 }
2082
2083 /**
2084  * @brief Opens a new map rectangle on the route graph's map
2085  *
2086  * This function opens a new map rectangle on the route graph's map.
2087  * The "sel" parameter enables you to only search for a single route graph
2088  * point on this map (or exactly: open a map rectangle that only contains
2089  * this one point). To do this, pass here a single map selection, whose
2090  * c_rect has both coordinates set to the same point. Otherwise this parameter
2091  * has no effect.
2092  *
2093  * @param priv The route graph map's private data
2094  * @param sel Here it's possible to specify a point for which to search. Please read the function's description.
2095  * @return A new map rect's private data
2096  */
2097 static struct map_rect_priv *
2098 rp_rect_new(struct map_priv *priv, struct map_selection *sel)
2099 {
2100         struct map_rect_priv * mr;
2101
2102         dbg(1,"enter\n");
2103         if (! priv->route->graph || ! priv->route->graph->route_points)
2104                 return NULL;
2105         mr=g_new0(struct map_rect_priv, 1);
2106         mr->mpriv = priv;
2107         mr->item.priv_data = mr;
2108         mr->item.type = type_rg_point;
2109         mr->item.meth = &methods_point_item;
2110         if (sel) {
2111                 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)) {
2112                         mr->coord_sel = g_malloc(sizeof(struct coord));
2113                         *(mr->coord_sel) = sel->u.c_rect.lu;
2114                 }
2115         }
2116         return mr;
2117 }
2118
2119 static void
2120 rm_rect_destroy(struct map_rect_priv *mr)
2121 {
2122         if (mr->str)
2123                 g_free(mr->str);
2124         if (mr->coord_sel) {
2125                 g_free(mr->coord_sel);
2126         }
2127
2128         g_free(mr);
2129 }
2130
2131 static struct item *
2132 rp_get_item(struct map_rect_priv *mr)
2133 {
2134         struct route *r = mr->mpriv->route;
2135         struct route_graph_point *p = mr->point;
2136         struct route_graph_segment *seg = mr->rseg;
2137
2138         if (mr->item.type == type_rg_point) {
2139                 if (mr->coord_sel) {
2140                         // We are supposed to return only the point at one specified coordinate...
2141                         if (!p) {
2142                                 p = r->graph->hash[HASHCOORD(mr->coord_sel)];
2143                                 while ((p) && ((p->c.x != mr->coord_sel->x) || (p->c.y != mr->coord_sel->y))) {
2144                                         p = p->hash_next;
2145                                 }
2146                                 if ((!p) || !((p->c.x == mr->coord_sel->x) && (p->c.y == mr->coord_sel->y))) {
2147                                         mr->point = NULL; // This indicates that no point has been found
2148                                 } else {
2149                                         mr->it = rp_iterator_new(p);
2150                                 }
2151                         } else {
2152                                 p = NULL;
2153                         }
2154                 } else {
2155                         if (!p)
2156                                 p = r->graph->route_points;
2157                         else
2158                                 p = p->next;
2159                 }
2160                 if (p) {
2161                         mr->point = p;
2162                         mr->item.id_lo++;
2163                         rm_coord_rewind(mr);
2164                         rp_attr_rewind(mr);
2165                         return &mr->item;
2166                 } else
2167                         mr->item.type = type_rg_segment;
2168         }
2169
2170         if (mr->coord_sel) {
2171                 if (!mr->point) { // This means that no point has been found
2172                         return NULL;
2173                 }
2174                 seg = rp_iterator_next(&(mr->it));
2175         } else {
2176                 if (!seg)
2177                         seg=r->graph->route_segments;
2178                 else
2179                         seg=seg->next;
2180         }
2181
2182         if (seg) {
2183                 mr->rseg = seg;
2184                 mr->item.id_lo++;
2185                 rm_coord_rewind(mr);
2186                 rp_attr_rewind(mr);
2187                 return &mr->item;
2188         }
2189         return NULL;
2190
2191 }
2192
2193 static struct item *
2194 rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2195 {
2196         struct item *ret=NULL;
2197         while (id_lo-- > 0)
2198                 ret=rp_get_item(mr);
2199         return ret;
2200 }
2201
2202
2203 static struct item *
2204 rm_get_item(struct map_rect_priv *mr)
2205 {
2206         dbg(1,"enter\n", mr->pos);
2207
2208         mr->seg=mr->seg_next;
2209         if (! mr->seg)
2210                 return NULL;
2211         mr->seg_next=mr->seg->next;
2212         mr->last_coord = 0;
2213         mr->item.id_lo++;
2214         rm_attr_rewind(mr);
2215         return &mr->item;
2216 }
2217
2218 static struct item *
2219 rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
2220 {
2221         struct item *ret=NULL;
2222         while (id_lo-- > 0)
2223                 ret=rm_get_item(mr);
2224         return ret;
2225 }
2226
2227 static struct map_methods route_meth = {
2228         projection_mg,
2229         "utf-8",
2230         rm_destroy,
2231         rm_rect_new,
2232         rm_rect_destroy,
2233         rm_get_item,
2234         rm_get_item_byid,
2235         NULL,
2236         NULL,
2237         NULL,
2238 };
2239
2240 static struct map_methods route_graph_meth = {
2241         projection_mg,
2242         "utf-8",
2243         rp_destroy,
2244         rp_rect_new,
2245         rm_rect_destroy,
2246         rp_get_item,
2247         rp_get_item_byid,
2248         NULL,
2249         NULL,
2250         NULL,
2251 };
2252
2253 void
2254 route_toggle_routegraph_display(struct route *route)
2255 {
2256         if (route->flags & RF_SHOWGRAPH) {
2257                 route->flags &= ~RF_SHOWGRAPH;
2258         } else {
2259                 route->flags |= RF_SHOWGRAPH;
2260         }
2261 }
2262
2263 static struct map_priv *
2264 route_map_new_helper(struct map_methods *meth, struct attr **attrs, int graph)
2265 {
2266         struct map_priv *ret;
2267         struct attr *route_attr;
2268
2269         route_attr=attr_search(attrs, NULL, attr_route);
2270         if (! route_attr)
2271                 return NULL;
2272         ret=g_new0(struct map_priv, 1);
2273         if (graph)
2274                 *meth=route_graph_meth;
2275         else
2276                 *meth=route_meth;
2277         ret->route=route_attr->u.route;
2278
2279         return ret;
2280 }
2281
2282 static struct map_priv *
2283 route_map_new(struct map_methods *meth, struct attr **attrs)
2284 {
2285         return route_map_new_helper(meth, attrs, 0);
2286 }
2287
2288 static struct map_priv *
2289 route_graph_map_new(struct map_methods *meth, struct attr **attrs)
2290 {
2291         return route_map_new_helper(meth, attrs, 1);
2292 }
2293
2294 static struct map *
2295 route_get_map_helper(struct route *this_, struct map **map, char *type, char *description)
2296 {
2297         if (! *map)
2298                 *map=map_new(NULL, (struct attr*[]){
2299                                 &(struct attr){attr_type,{type}},
2300                                 &(struct attr){attr_route,.u.route=this_},
2301                                 &(struct attr){attr_data,{""}},
2302                                 &(struct attr){attr_description,{description}},
2303                                 NULL});
2304
2305         return *map;
2306 }
2307
2308 /**
2309  * @brief Returns a new map containing the route path
2310  *
2311  * This function returns a new map containing the route path.
2312  *
2313  * @important Do not map_destroy() this!
2314  *
2315  * @param this_ The route to get the map of
2316  * @return A new map containing the route path
2317  */
2318 struct map *
2319 route_get_map(struct route *this_)
2320 {
2321         return route_get_map_helper(this_, &this_->map, "route","Route");
2322 }
2323
2324
2325 /**
2326  * @brief Returns a new map containing the route graph
2327  *
2328  * This function returns a new map containing the route graph.
2329  *
2330  * @important Do not map_destroy()  this!
2331  *
2332  * @param this_ The route to get the map of
2333  * @return A new map containing the route graph
2334  */
2335 struct map *
2336 route_get_graph_map(struct route *this_)
2337 {
2338         return route_get_map_helper(this_, &this_->graph_map, "route_graph","Route Graph");
2339 }
2340
2341 void
2342 route_set_projection(struct route *this_, enum projection pro)
2343 {
2344 }
2345
2346 void
2347 route_init(void)
2348 {
2349         plugin_register_map_type("route", route_map_new);
2350         plugin_register_map_type("route_graph", route_graph_map_new);
2351 }