Logo Search packages:      
Sourcecode: navit version File versions

route.c File Reference

Detailed Description

Contains code related to finding a route from a position to a destination.

Navit, a modular navigation system. Copyright (C) 2005-2008 Navit Team

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2 as published by the Free Software Foundation.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. Routing uses segments, points and items. Items are items from the map: Streets, highways, etc. Segments represent such items, or parts of it. Generally, a segment is a driveable path. An item can be represented by more than one segment - in that case it is "segmented". Each segment has an "offset" associated, that indicates at which position in a segmented item this segment is - a segment representing a not-segmented item always has the offset 1. A point is located at the end of segments, often connecting several segments.

The code in this file will make navit find a route between a position and a destination. It accomplishes this by first building a "route graph". This graph contains segments and points.

After building this graph in route_graph_build(), the function route_graph_flood() assigns every point and segment a "value" which represents the "costs" of traveling from this point to the destination. This is done by Dijkstra's algorithm.

When the graph is built a "route path" is created, which is a path in this graph from a given position to the destination determined at time of building the graph.

Definition in file route.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <glib.h>
#include "config.h"
#include "debug.h"
#include "profile.h"
#include "coord.h"
#include "projection.h"
#include "item.h"
#include "map.h"
#include "mapset.h"
#include "route.h"
#include "track.h"
#include "point.h"
#include "graphics.h"
#include "transform.h"
#include "plugin.h"
#include "fib.h"
#include "event.h"
#include "callback.h"
#include "vehicleprofile.h"
#include "roadprofile.h"

Go to the source code of this file.


struct  map_priv
struct  map_rect_priv
struct  route
 A complete route. More...
struct  route_graph
 A complete route graph. More...
struct  route_graph_point
 A point in the route graph. More...
struct  route_graph_point_iterator
 Iterator to iterate through all route graph segments in a route graph point. More...
struct  route_graph_segment
 A segment in the route graph. More...
struct  route_info
 Usually represents a destination or position. More...
struct  route_path
 A complete route path. More...
struct  route_path_segment
 A segment in the route path. More...
struct  route_segment_data
 A segment in the route graph or path. More...
struct  route_traffic_distortion
 A traffic distortion. More...


#define HASH_SIZE   8192
#define HASHCOORD(c)   ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))
#define RSD_MAXSPEED(x)   *((int *)route_segment_data_field_pos((x), attr_maxspeed))
#define RSD_OFFSET(x)   *((int *)route_segment_data_field_pos((x), attr_offset))


static int get_item_seg_coords (struct item *i, struct coord *c, int max, struct coord *start, struct coord *end)
 Gets all the coordinates of an item.
static int is_turn_allowed (struct route_graph_point *p, struct route_graph_segment *from, struct route_graph_segment *to)
static int rm_attr_get (void *priv_data, enum attr_type attr_type, struct attr *attr)
static void rm_attr_rewind (void *priv_data)
static int rm_coord_get (void *priv_data, struct coord *c, int count)
static void rm_coord_rewind (void *priv_data)
static void rm_destroy (struct map_priv *priv)
static struct item * rm_get_item (struct map_rect_priv *mr)
static struct item * rm_get_item_byid (struct map_rect_priv *mr, int id_hi, int id_lo)
static void rm_rect_destroy (struct map_rect_priv *mr)
static struct map_rect_priv * rm_rect_new (struct map_priv *priv, struct map_selection *sel)
int route_add_attr (struct route *this_, struct attr *attr)
static struct map_selectionroute_calc_selection (struct coord *c1, struct coord *c2)
 Returns a list of map selections useable to create a route graph.
static int route_check_roundabout (struct route_graph_segment *seg, int level, int direction, struct route_graph_segment *origin)
 Checks if a segment is part of a roundabout.
int route_contains (struct route *this, struct item *item)
 Checks if the route passed contains a certain item within the route path.
int route_destination_reached (struct route *this)
 Checks if a route has reached its destination.
static struct route_path_segmentroute_extract_segment_from_path (struct route_path *path, struct item *item, int offset)
 Returns and removes one segment from a path.
static struct route_inforoute_find_nearest_street (struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc)
 Finds the nearest street to a given coordinate.
static void route_free_selection (struct map_selection *sel)
 Destroys a list of map selections.
int route_get_attr (struct route *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
struct coord route_get_coord_dist (struct route *this_, int dist)
 Returns a coordinate at a given distance.
struct route_inforoute_get_dst (struct route *this)
 Returns the destination of the route passed.
struct maproute_get_graph_map (struct route *this_)
 Returns a new map containing the route graph.
struct maproute_get_map (struct route *this_)
 Returns a new map containing the route path.
static struct maproute_get_map_helper (struct route *this_, struct map **map, char *type, char *description)
struct mapsetroute_get_mapset (struct route *this)
 Returns the mapset of the route passed.
int route_get_path_set (struct route *this)
 Checks if the path is calculated for the route passed.
struct route_inforoute_get_pos (struct route *this)
 Returns the current position within the route passed.
static int route_get_traffic_distortion (struct route_graph_segment *seg, struct route_traffic_distortion *ret)
static struct route_graph_pointroute_graph_add_point (struct route_graph *this, struct coord *f)
 Inserts a point into the route graph at the specified coordinates.
static void route_graph_add_segment (struct route_graph *this, struct route_graph_point *start, struct route_graph_point *end, int len, struct item *item, int flags, int offset, int maxspeed)
 Inserts a new segment into the route graph.
static struct route_graphroute_graph_build (struct mapset *ms, struct coord *c1, struct coord *c2, struct callback *done_cb, int async)
 Builds a new route graph from a mapset.
static void route_graph_build_done (struct route_graph *rg, int cancel)
static void route_graph_build_idle (struct route_graph *rg)
static int route_graph_build_next_map (struct route_graph *rg)
static void route_graph_clone_segment (struct route_graph *this, struct route_graph_segment *s, struct route_graph_point *start, struct route_graph_point *end, int flags)
static void route_graph_destroy (struct route_graph *this)
 Destroys a route graph.
static void route_graph_flood (struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile, struct callback *cb)
 Calculates the routing costs for each point.
static void route_graph_free_points (struct route_graph *this)
 Frees all the memory used for points in the route graph passed.
static void route_graph_free_segments (struct route_graph *this)
 Destroys all segments of a route graph.
static struct route_graph_pointroute_graph_get_point (struct route_graph *this, struct coord *c)
 Gets the route_graph_point with the specified coordinates.
static struct route_graph_pointroute_graph_get_point_last (struct route_graph *this, struct coord *c)
 Gets the last route_graph_point with the specified coordinates.
static struct route_graph_segmentroute_graph_get_segment (struct route_graph *graph, struct street_data *sd)
static struct map_privroute_graph_map_new (struct map_methods *meth, struct attr **attrs)
static struct route_graph_pointroute_graph_point_new (struct route_graph *this, struct coord *f)
 Create a new point for the route graph with the specified coordinates.
static void route_graph_process_restriction_point (struct route_graph *this, struct route_graph_point *p)
static void route_graph_process_restriction_segment (struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
static void route_graph_process_restrictions (struct route_graph *this)
static int route_graph_segment_is_duplicate (struct route_graph_point *start, struct item *item, int flags, int offset)
static void route_graph_update (struct route *this, struct callback *cb, int async)
 Updates the route graph.
static void route_graph_update_done (struct route *this, struct callback *cb)
static void route_info_distances (struct route_info *ri, enum projection pro)
 This will calculate all the distances stored in a route_info.
void route_info_free (struct route_info *inf)
 Destroys a route_info.
struct street_dataroute_info_street (struct route_info *rinf)
 Returns street data for a route info.
void route_init (void)
static struct map_privroute_map_new (struct map_methods *meth, struct attr **attrs)
static struct map_privroute_map_new_helper (struct map_methods *meth, struct attr **attrs, int graph)
struct routeroute_new (struct attr *parent, struct attr **attrs)
 Creates a completely new route structure.
static int route_path_add_item_from_graph (struct route_path *this, struct route_path *oldpath, struct route_graph_segment *rgs, int dir, struct route_info *pos, struct route_info *dst)
 Inserts a new item into the path.
static void route_path_add_line (struct route_path *this, struct coord *start, struct coord *end, int len)
 Adds a two coordinate line to a path.
static void route_path_add_segment (struct route_path *this, struct route_path_segment *segment)
 Adds a segment and the end of a path.
static void route_path_destroy (struct route_path *this)
 Destroys a route_path.
static struct route_pathroute_path_new (struct route_graph *this, struct route_path *oldpath, struct route_info *pos, struct route_info *dst, struct vehicleprofile *profile)
 Creates a new route path.
static struct route_pathroute_path_new_offroad (struct route_graph *this, struct route_info *pos, struct route_info *dst)
 Starts an "offroad" path.
static void route_path_update (struct route *this, int cancel, int async)
 Updates the route graph and the route path if something changed with the route.
static void route_path_update_done (struct route *this, int new_graph)
static void route_process_street_graph (struct route_graph *this, struct item *item)
 Adds an item to the route graph.
static void route_process_traffic_distortion (struct route_graph *this, struct item *item)
 Adds a route distortion item to the route graph.
static void route_process_turn_restriction (struct route_graph *this, struct item *item)
 Adds a route distortion item to the route graph.
static enum projection route_projection (struct route *route)
 Returns the projection used for this route.
struct map_selectionroute_rect (int order, struct coord *c1, struct coord *c2, int rel, int abs)
 Returns a single map selection.
int route_remove_attr (struct route *this_, struct attr *attr)
static void * route_segment_data_field_pos (struct route_segment_data *seg, enum attr_type type)
 Returns the position of a certain field appended to a route graph segment.
static int route_segment_data_size (int flags)
 Calculates the size of a route_segment_data struct with given flags.
int route_set_attr (struct route *this_, struct attr *attr)
void route_set_destination (struct route *this, struct pcoord *dst, int async)
 Sets the destination of a route.
void route_set_mapset (struct route *this, struct mapset *ms)
 Sets the mapset of the route passwd.
void route_set_position (struct route *this, struct pcoord *pos)
 This sets the current position of the route passed.
void route_set_position_from_tracking (struct route *this, struct tracking *tracking, enum projection pro)
 Sets a route's current position based on coordinates from tracking.
void route_set_profile (struct route *this, struct vehicleprofile *prof)
 Sets the vehicle profile of a route.
void route_set_projection (struct route *this_, enum projection pro)
static int route_time_seg (struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
 Returns the time needed to drive len on item.
static int route_value_seg (struct vehicleprofile *profile, struct route_graph_point *from, struct route_graph_segment *over, int dir)
 Returns the "costs" of driving from point from over segment over in direction dir.
static int rp_attr_get (void *priv_data, enum attr_type attr_type, struct attr *attr)
static void rp_attr_rewind (void *priv_data)
static int rp_coord_get (void *priv_data, struct coord *c, int count)
 Returns the coordinates of a route graph item.
static void rp_destroy (struct map_priv *priv)
static struct item * rp_get_item (struct map_rect_priv *mr)
static struct item * rp_get_item_byid (struct map_rect_priv *mr, int id_hi, int id_lo)
static int rp_iterator_end (struct route_graph_point_iterator *it)
 Checks if the last segment returned from a route_graph_point_iterator comes from the end.
static struct
rp_iterator_new (struct route_graph_point *p)
 Creates a new graph point iterator.
static struct route_graph_segmentrp_iterator_next (struct route_graph_point_iterator *it)
 Gets the next segment connected to a route graph point from an iterator.
static struct map_rect_priv * rp_rect_new (struct map_priv *priv, struct map_selection *sel)
 Opens a new map rectangle on the route graph's map.
struct street_datastreet_data_dup (struct street_data *orig)
 Copies street data.
void street_data_free (struct street_data *sd)
 Frees street data.
struct street_datastreet_get_data (struct item *item)
 Gets street data for an item.


int debug_route = 0
static struct item_methods methods_point_item
static struct item_methods methods_route_item
static struct map_methods route_graph_meth
static struct map_methods route_meth
struct map_selectionroute_selection

Generated by  Doxygen 1.6.0   Back to index