Navit SVN
Classes | Defines | Functions | Variables

/work/compile/navit/src/navit/route.c File Reference

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "navit_nls.h"
#include "glib_slice.h"
#include "config.h"
#include "point.h"
#include "graphics.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 "transform.h"
#include "plugin.h"
#include "fib.h"
#include "event.h"
#include "callback.h"
#include "vehicle.h"
#include "vehicleprofile.h"
#include "roadprofile.h"
#include "debug.h"

Classes

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

Defines

#define RP_TRAFFIC_DISTORTION   1
#define RP_TURN_RESTRICTION   2
#define RP_TURN_RESTRICTION_RESOLVED   4
#define RSD_OFFSET(x)   *((int *)route_segment_data_field_pos((x), attr_offset))
#define RSD_MAXSPEED(x)   *((int *)route_segment_data_field_pos((x), attr_maxspeed))
#define RSD_SIZE_WEIGHT(x)   *((struct size_weight_limit *)route_segment_data_field_pos((x), attr_vehicle_width))
#define RSD_DANGEROUS_GOODS(x)   *((int *)route_segment_data_field_pos((x), attr_vehicle_dangerous_goods))
#define HASH_SIZE   8192
#define HASHCOORD(c)   ((((c)->x +(c)->y) * 2654435761UL) & (HASH_SIZE-1))

Functions

struct routeroute_new (struct attr *parent, struct attr **attrs)
 Creates a completely new route structure.
void route_set_mapset (struct route *this, struct mapset *ms)
 Sets the mapset of the route passwd.
void route_set_profile (struct route *this, struct vehicleprofile *prof)
 Sets the vehicle profile of a route.
struct mapsetroute_get_mapset (struct route *this)
 Returns the mapset of the route passed.
struct route_inforoute_get_pos (struct route *this)
 Returns the current position within the route passed.
struct route_inforoute_get_dst (struct route *this)
 Returns the destination of the route passed.
int route_get_path_set (struct route *this)
 Checks if the path is calculated for the route passed.
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.
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.
struct map_selectionroute_rect (int order, struct coord *c1, struct coord *c2, int rel, int abs)
 Returns a single map selection.
void route_set_destinations (struct route *this, struct pcoord *dst, int count, int async)
 Sets the destination of a route.
int route_get_destinations (struct route *this, struct pcoord *pc, int count)
int route_get_destination_count (struct route *this)
 Get the destinations count for the route.
char * route_get_destination_description (struct route *this, int n)
 Returns a description for a waypoint as (type or street_name_systematic) + (label or WayID[osm_wayid])
void route_set_destination (struct route *this, struct pcoord *dst, int async)
 Start a route given set of coordinates.
void route_append_destination (struct route *this, struct pcoord *dst, int async)
 Append a given set of coordinates for route computing.
void route_remove_nth_waypoint (struct route *this, int n)
 Remove the nth waypoint of the route.
void route_remove_waypoint (struct route *this)
struct coord route_get_coord_dist (struct route *this_, int dist)
 Returns a coordinate at a given distance.
struct street_datastreet_get_data (struct item *item)
 Gets street data for an item.
struct street_datastreet_data_dup (struct street_data *orig)
 Copies street data.
void street_data_free (struct street_data *sd)
 Frees street data.
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.
struct maproute_get_map (struct route *this_)
 Returns a new map containing the route path.
struct maproute_get_graph_map (struct route *this_)
 Returns a new map containing the route graph.
void route_set_projection (struct route *this_, enum projection pro)
int route_set_attr (struct route *this_, struct attr *attr)
int route_add_attr (struct route *this_, struct attr *attr)
int route_remove_attr (struct route *this_, struct attr *attr)
int route_get_attr (struct route *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
struct attr_iterroute_attr_iter_new (void)
void route_attr_iter_destroy (struct attr_iter *iter)
void route_init (void)
void route_destroy (struct route *this_)

Variables

int debug_route = 0
struct map_selectionroute_selection

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.


Function Documentation

void route_append_destination ( struct route this,
struct pcoord dst,
int  async 
)

Append a given set of coordinates for route computing.

Parameters:
thisThe route instance
cThe coordinate to start routing to
async1 for async
Returns:
nothing

References route_get_dst(), and route_set_destinations().

Referenced by navit_set_destination().

int route_contains ( struct route this,
struct item item 
)

Checks if the route passed contains a certain item within the route path.

This function checks if a certain items exists in the path that navit will guide the user to his destination. It does *not* check if this item exists in the route graph!

Parameters:
thisThe route to check for this item
itemThe item to search for
Returns:
True if the item was found, false if the item was not found or the route was not calculated

References route_info::pos.

int route_destination_reached ( struct route this)

Checks if a route has reached its destination.

Parameters:
thisThe route to be checked
Returns:
True if the destination is "reached", false otherwise.

References street_data::item, route_info::lenneg, route_info::lenpos, route_info::lp, route_info::pos, and route_info::street.

struct coord route_get_coord_dist ( struct route this_,
int  dist 
) [read]

Returns a coordinate at a given distance.

This function returns the coordinate, where the user will be if he follows the current route for a certain distance.

Parameters:
this_The route we're driving upon
distThe distance in meters
Returns:
The coordinate where the user will be in that distance

References route_info::c, route_path_segment::c, route_path_segment::data, route_segment_data::len, route_path_segment::ncoords, route_path_segment::next, route_get_dst(), coord::x, and coord::y.

int route_get_destination_count ( struct route this)

Get the destinations count for the route.

Parameters:
thisThe route instance
Returns:
destination count for the route

Referenced by navit_set_destination().

char* route_get_destination_description ( struct route this,
int  n 
)

Returns a description for a waypoint as (type or street_name_systematic) + (label or WayID[osm_wayid])

Parameters:
thisThe route instance
nThe nth waypoint
Returns:
The description

References street_data::item, map_rect_destroy(), map_rect_get_item_byid(), map_rect_new(), and route_info::street.

struct route_info* route_get_dst ( struct route this) [read]

Returns the destination of the route passed.

Parameters:
thisThe route to get the destination for
Returns:
The destination of the route passed

Referenced by route_append_destination(), route_get_coord_dist(), route_remove_nth_waypoint(), and route_set_destinations().

struct map* route_get_graph_map ( struct route this_) [read]

Returns a new map containing the route graph.

This function returns a new map containing the route graph.

Do not map_destroy() this!

Parameters:
this_The route to get the map of
Returns:
A new map containing the route graph
struct map* route_get_map ( struct route this_) [read]

Returns a new map containing the route path.

This function returns a new map containing the route path.

Do not map_destroy() this!

Parameters:
this_The route to get the map of
Returns:
A new map containing the route path
struct mapset* route_get_mapset ( struct route this) [read]

Returns the mapset of the route passed.

Parameters:
thisThe route to get the mapset of
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.

Parameters:
thisThe route to check
Returns:
True if the path is calculated, false if not

Referenced by navit_check_route().

struct route_info* route_get_pos ( struct route this) [read]

Returns the current position within the route passed.

Parameters:
thisThe route to get the position for
Returns:
The position within the route passed

References route_info::pos.

void route_info_free ( struct route_info inf)

Destroys a route_info.

Parameters:
infoThe route info to be destroyed

References route_info::street, and street_data_free().

Referenced by route_remove_nth_waypoint(), route_set_position(), and route_set_position_from_tracking().

struct street_data* route_info_street ( struct route_info rinf) [read]

Returns street data for a route info.

Parameters:
rinfThe route info to return the street data for
Returns:
Street data for the route info

References route_info::street.

struct route* route_new ( struct attr parent,
struct attr **  attrs 
) [read]

Creates a completely new route structure.

Parameters:
attrsNot used
Returns:
The newly created route
void route_remove_nth_waypoint ( struct route this,
int  n 
)

Remove the nth waypoint of the route.

Parameters:
thisThe route instance
nThe waypoint to remove
Returns:
nothing

References route_get_dst(), and route_info_free().

void route_set_destination ( struct route this,
struct pcoord dst,
int  async 
)

Start a route given set of coordinates.

Parameters:
thisThe route instance
cThe coordinate to start routing to
async1 for async
Returns:
nothing

References route_set_destinations().

Referenced by navit_set_destination().

void route_set_destinations ( struct route this,
struct pcoord dst,
int  count,
int  async 
)

Sets the destination of a route.

This sets the destination of a route to the street nearest to the coordinates passed and updates the route.

Parameters:
thisThe route to set the destination for
dstCoordinates to set as destination
count,:Number of destinations (last one is final)
async,:If set, do routing asynchronously

References route_get_dst().

Referenced by navit_set_destinations(), route_append_destination(), route_set_destination(), and route_set_profile().

void route_set_mapset ( struct route this,
struct mapset ms 
)

Sets the mapset of the route passwd.

Parameters:
thisThe route to set the mapset for
msThe mapset to set for this route
void route_set_position ( struct route this,
struct pcoord pos 
)

This sets the current position of the route passed.

This will set the current position of the route passed to the street that is nearest to the passed coordinates. It also automatically updates the route.

Parameters:
thisThe route to set the position of
posCoordinates to set as position

References route_info_free().

Referenced by navit_set_position().

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.

Parameters:
thisThe route to set the current position of
trackingThe tracking to get the coordinates from

References street_data::c, route_info::c, street_data::count, street_data::item, route_info::lenneg, route_info::lenpos, route_info::lp, route_info::pos, route_info_free(), route_info::street, street_data_dup(), route_info::street_direction, coord::x, and coord::y.

void route_set_profile ( struct route this,
struct vehicleprofile prof 
)

Sets the vehicle profile of a route.

Parameters:
thisThe route to set the profile for
profThe vehicle profile

References route_set_destinations().

struct street_data* street_data_dup ( struct street_data orig) [read]

Copies street data.

Parameters:
origThe street data to copy
Returns:
The copied street data

Referenced by route_set_position_from_tracking().

void street_data_free ( struct street_data sd)

Frees street data.

Parameters:
sdStreet data to be freed

Referenced by route_info_free().

struct street_data* street_get_data ( struct item item) [read]

Gets street data for an item.

Parameters:
itemThe item to get the data for
Returns:
Street data for the item

References street_data::c, street_data::count, street_data::item, and street_data::maxspeed.


Variable Documentation

FIXME

Parameters:
<>
Returns:
<>
Author:
Martin Schaller (04/2008)