navit  0.5.1-trunk
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros Groups
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 <math.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 "xmlconfig.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"

Data Structures

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
 Data for a segment in the route graph. More...
 
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
 

Functions

static struct route_inforoute_find_nearest_street (struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc)
 Finds the nearest street to a given coordinate. More...
 
static struct route_graph_pointroute_graph_get_point (struct route_graph *this, struct coord *c)
 Gets the first route_graph_point with the specified coordinates. More...
 
static void route_graph_update (struct route *this, struct callback *cb, int async)
 Updates the route graph. More...
 
static void route_graph_build_done (struct route_graph *rg, int cancel)
 Releases all resources needed to build the route graph. More...
 
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. More...
 
static void route_process_street_graph (struct route_graph *this, struct item *item, struct vehicleprofile *profile)
 Adds an item to the route graph. More...
 
static void route_graph_destroy (struct route_graph *this)
 Destroys a route graph. More...
 
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. More...
 
static int route_time_seg (struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
 Returns the time needed to travel along a segment, or. More...
 
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. More...
 
static void route_graph_reset (struct route_graph *this)
 Resets all nodes. More...
 
static enum projection route_projection (struct route *route)
 Returns the projection used for this route. More...
 
static struct
route_graph_point_iterator 
rp_iterator_new (struct route_graph_point *p)
 Creates a new graph point iterator. More...
 
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. More...
 
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. More...
 
static void route_path_get_distances (struct route_path *path, struct coord *c, int count, int *distances)
 
void route_get_distances (struct route *this, struct coord *c, int count, int *distances)
 
static void route_path_destroy (struct route_path *this, int recurse)
 Destroys a route_path. More...
 
struct routeroute_new (struct attr *parent, struct attr **attrs)
 Creates a completely new route structure. More...
 
struct routeroute_dup (struct route *orig)
 Duplicates a route object. More...
 
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. More...
 
void route_set_mapset (struct route *this, struct mapset *ms)
 Sets the mapset of the route passwd. More...
 
void route_set_profile (struct route *this, struct vehicleprofile *prof)
 Sets the vehicle profile of a route. More...
 
struct mapsetroute_get_mapset (struct route *this)
 Returns the mapset of the route passed. More...
 
struct route_inforoute_get_pos (struct route *this)
 Returns the current position within the route passed. More...
 
struct route_inforoute_get_dst (struct route *this)
 Returns the destination of the route passed. More...
 
int route_get_path_set (struct route *this)
 Checks if the path is calculated for the route passed. More...
 
int route_contains (struct route *this, struct item *item)
 Checks if the route passed contains a certain item within the route path. More...
 
static struct route_inforoute_next_destination (struct route *this)
 
int route_destination_reached (struct route *this)
 Checks if a route has reached its destination. More...
 
static struct route_inforoute_previous_destination (struct route *this)
 Returns the position from which to route to the current destination of the route. More...
 
static void route_path_update_done (struct route *this, int new_graph)
 Updates or recreates the route graph. More...
 
static void route_path_update_flags (struct route *this, enum route_path_flags flags)
 Updates the route graph and the route path if something changed with the route. More...
 
static void route_info_distances (struct route_info *ri, enum projection pro)
 This will calculate all the distances stored in a route_info. More...
 
static int route_set_position_flags (struct route *this, struct pcoord *pos, enum route_path_flags flags)
 This sets the current position of the route passed. More...
 
void route_set_position (struct route *this, struct pcoord *pos)
 This sets the current position of the route passed. More...
 
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. More...
 
struct map_selectionroute_rect (int order, struct coord *c1, struct coord *c2, int rel, int abs)
 Returns a single map selection. More...
 
static struct map_selectionroute_rect_add (struct map_selection *sel, int order, struct coord *c1, struct coord *c2, int rel, int abs)
 Appends a map selection to the selection list. Selection list may be NULL. More...
 
static struct map_selectionroute_calc_selection (struct coord *c, int count, struct vehicleprofile *profile)
 Returns a list of map selections useable to create a route graph. More...
 
static void route_free_selection (struct map_selection *sel)
 Destroys a list of map selections. More...
 
static void route_clear_destinations (struct route *this_)
 
void route_set_destinations (struct route *this, struct pcoord *dst, int count, int async)
 Sets the destination of a route. More...
 
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. More...
 
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]) More...
 
void route_set_destination (struct route *this, struct pcoord *dst, int async)
 Start a route given set of coordinates. More...
 
void route_append_destination (struct route *this, struct pcoord *dst, int async)
 Append a waypoint to the route. More...
 
void route_remove_nth_waypoint (struct route *this, int n)
 Remove the nth waypoint of the route. More...
 
void route_remove_waypoint (struct route *this)
 
static struct route_graph_pointroute_graph_get_point_next (struct route_graph *this, struct coord *c, struct route_graph_point *last)
 Gets the next route_graph_point with the specified coordinates. More...
 
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. More...
 
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. More...
 
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. More...
 
static void route_graph_free_points (struct route_graph *this)
 Frees all the memory used for points in the route graph passed. More...
 
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. More...
 
static int route_segment_data_size (int flags)
 Calculates the size of a route_segment_data struct with given flags. More...
 
static int route_graph_segment_is_duplicate (struct route_graph_point *start, struct route_graph_segment_data *data)
 Checks if the route graph already contains a particular segment. More...
 
static void route_graph_add_segment (struct route_graph *this, struct route_graph_point *start, struct route_graph_point *end, struct route_graph_segment_data *data)
 Inserts a new segment into the route graph. More...
 
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. More...
 
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. More...
 
static void route_path_add_segment (struct route_path *this, struct route_path_segment *segment)
 Adds a segment and the end of a path. More...
 
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. More...
 
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. More...
 
static void route_graph_free_segments (struct route_graph *this)
 Destroys all segments of a route graph. More...
 
static int route_seg_speed (struct vehicleprofile *profile, struct route_segment_data *over, struct route_traffic_distortion *dist)
 Returns the estimated speed on a segment, or 0 for an impassable segment. More...
 
static int route_get_traffic_distortion (struct route_graph_segment *seg, struct route_traffic_distortion *ret)
 Returns the traffic distortion for a segment. More...
 
static int route_through_traffic_allowed (struct vehicleprofile *profile, struct route_graph_segment *seg)
 
static int route_value_seg (struct vehicleprofile *profile, struct route_graph_point *from, struct route_graph_segment *over, int dir)
 Returns the "cost" of driving from point. More...
 
static int route_graph_segment_match (struct route_graph_segment *s1, struct route_graph_segment *s2)
 Whether two route graph segments match. More...
 
static void route_graph_set_traffic_distortion (struct route_graph *this, struct route_graph_segment *seg, int delay)
 Sets or clears a traffic distortion for a segment. More...
 
static void route_process_traffic_distortion (struct route_graph *this, struct item *item)
 Adds a traffic distortion item to the route graph. More...
 
static void route_process_turn_restriction (struct route_graph *this, struct item *item)
 Adds a turn restriction item to the route graph. More...
 
static struct route_graph_segmentroute_graph_get_segment (struct route_graph *graph, struct street_data *sd, struct route_graph_segment *last)
 Gets the next route_graph_segment belonging to the specified street. More...
 
static struct route_pathroute_path_new_offroad (struct route_graph *this, struct route_info *pos, struct route_info *dst)
 Starts an "offroad" path. More...
 
struct coord route_get_coord_dist (struct route *this_, int dist)
 Returns a coordinate at a given distance. More...
 
static int route_graph_build_next_map (struct route_graph *rg)
 
static int is_turn_allowed (struct route_graph_point *p, struct route_graph_segment *from, struct route_graph_segment *to)
 
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_process_restriction_segment (struct route_graph *this, struct route_graph_point *p, struct route_graph_segment *s, int dir)
 
static void route_graph_process_restriction_point (struct route_graph *this, struct route_graph_point *p)
 
static void route_graph_process_restrictions (struct route_graph *this)
 
static void route_graph_build_idle (struct route_graph *rg, struct vehicleprofile *profile)
 
static struct route_graphroute_graph_build (struct mapset *ms, struct coord *c, int count, struct callback *done_cb, int async, struct vehicleprofile *profile)
 Builds a new route graph from a mapset. More...
 
static void route_graph_update_done (struct route *this, struct callback *cb)
 
struct street_datastreet_get_data (struct item *item)
 Gets street data for an item. More...
 
struct street_datastreet_data_dup (struct street_data *orig)
 Copies street data. More...
 
void street_data_free (struct street_data *sd)
 Frees street data. More...
 
void route_info_free (struct route_info *inf)
 Destroys a route_info. More...
 
struct street_dataroute_info_street (struct route_info *rinf)
 Returns street data for a route info. More...
 
struct route_crossingsroute_crossings_get (struct route *this, struct coord *c)
 
static void rm_coord_rewind (void *priv_data)
 
static void rm_attr_rewind (void *priv_data)
 
static int rm_attr_get (void *priv_data, enum attr_type attr_type, struct attr *attr)
 
static int rm_coord_get (void *priv_data, struct coord *c, int count)
 
static void rp_attr_rewind (void *priv_data)
 
static int rp_attr_get (void *priv_data, enum attr_type attr_type, struct attr *attr)
 
static int rp_coord_get (void *priv_data, struct coord *c, int count)
 Returns the coordinates of a route graph item. More...
 
static void rp_destroy (struct map_priv *priv)
 
static void rm_destroy (struct map_priv *priv)
 
static struct map_rect_privrm_rect_new (struct map_priv *priv, struct map_selection *sel)
 
static struct map_rect_privrp_rect_new (struct map_priv *priv, struct map_selection *sel)
 Opens a new map rectangle on the route graph's map. More...
 
static void rm_rect_destroy (struct map_rect_priv *mr)
 
static struct itemrp_get_item (struct map_rect_priv *mr)
 
static struct itemrp_get_item_byid (struct map_rect_priv *mr, int id_hi, int id_lo)
 
static struct itemrm_get_item (struct map_rect_priv *mr)
 
static struct itemrm_get_item_byid (struct map_rect_priv *mr, int id_hi, int id_lo)
 
static struct map_privroute_map_new_helper (struct map_methods *meth, struct attr **attrs, int graph)
 
static struct map_privroute_map_new (struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
 
static struct map_privroute_graph_map_new (struct map_methods *meth, struct attr **attrs, struct callback_list *cbl)
 
static struct maproute_get_map_helper (struct route *this_, struct map **map, char *type, char *description)
 
struct maproute_get_map (struct route *this_)
 Returns a new map containing the route path. More...
 
struct maproute_get_graph_map (struct route *this_)
 Returns a new map containing the route graph. More...
 
enum route_path_flags route_get_flags (struct route *this_)
 Returns the flags for the route. More...
 
int route_has_graph (struct route *this_)
 Whether the route has a valid graph. More...
 
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
 
static struct item_methods methods_route_item
 
static struct item_methods methods_point_item
 
static struct map_methods route_meth
 
static struct map_methods route_graph_meth
 
struct object_func route_func
 

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

static int get_item_seg_coords ( struct item i,
struct coord c,
int  max,
struct coord start,
struct coord end 
)
static

Gets all the coordinates of an item.

This will get all the coordinates of the item i and return them in c, up to max coordinates. Additionally it is possible to limit the coordinates returned to all the coordinates of the item between the two coordinates start end end.

Make sure that whatever c points to has enough memory allocated to hold max coordinates!

Parameters
iThe item to get the coordinates of
cPointer to memory allocated for holding the coordinates
maxMaximum number of coordinates to return
startFirst coordinate to get
endLast coordinate to get
Returns
The number of coordinates returned

References c1, item::id_hi, item::id_lo, item, item_coord_get(), item::map, map_rect_destroy(), map_rect_get_item_byid(), map_rect_new(), p, coord::x, and coord::y.

Referenced by route_path_add_item_from_graph().

static void rm_attr_rewind ( void *  priv_data)
static

References map_rect_priv::attr_next.

Referenced by rm_get_item().

static void rm_coord_rewind ( void *  priv_data)
static

References map_rect_priv::last_coord.

Referenced by rp_get_item().

static void rm_destroy ( struct map_priv priv)
static
static struct item* rm_get_item_byid ( struct map_rect_priv mr,
int  id_hi,
int  id_lo 
)
static
int route_add_attr ( struct route this_,
struct attr attr 
)
void route_append_destination ( struct route this,
struct pcoord dst,
int  async 
)

Append a waypoint to the route.

This appends a waypoint to the current route, targetting the street nearest to the coordinates passed, and updates the route.

Parameters
thisThe route to set the destination for
dstCoordinates of the new waypoint
asyncIf set, do routing asynchronously

References pcoord::pro, route_find_nearest_street(), route_get_dst(), route_graph_destroy(), route_info_distances(), route_path_update(), and route_set_destinations().

Referenced by navit_set_destination().

void route_attr_iter_destroy ( struct attr_iter iter)
struct attr_iter* route_attr_iter_new ( void  )
static struct map_selection* route_calc_selection ( struct coord c,
int  count,
struct vehicleprofile profile 
)
static

Returns a list of map selections useable to create a route graph.

Returns a list of map selections useable to get a map rect from which items can be retrieved to build a route graph.

Parameters
cArray containing route points, including start, intermediate and destination ones.
countnumber of route points
proiflevehicleprofile

References coord_rect_extend(), coord_rect::lu, coord_rect::rl, vehicleprofile::route_depth, and route_rect_add().

Referenced by route_graph_build().

static int route_check_roundabout ( struct route_graph_segment seg,
int  level,
int  direction,
struct route_graph_segment origin 
)
static

Checks if a segment is part of a roundabout.

This function checks if a segment is part of a roundabout.

Parameters
segThe segment to be checked
levelHow deep to scan the route graph
directionSet this to 1 if we're entering the segment through its end, to 0 otherwise
originUsed internally, set to NULL
Returns
1 If a roundabout was detected, 0 otherwise

References AF_ONEWAY, AF_ONEWAYREV, AF_ROUNDABOUT, AF_ROUNDABOUT_VALID, route_graph_segment::data, route_graph_segment::end, route_segment_data::flags, route_segment_data::item, rp_iterator_end(), rp_iterator_new(), rp_iterator_next(), route_graph_segment::start, and item::type.

Referenced by route_path_add_item_from_graph().

static void route_clear_destinations ( struct route this_)
static
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 item_hash_lookup(), item_is_equal, and startup::pos.

Referenced by tracking_is_on_route().

struct route_crossings* route_crossings_get ( struct route this,
struct coord c 
)
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 AF_ONEWAY, AF_ONEWAYREV, street_data::flags, street_data::item, item_is_equal, route_info::lenneg, route_info::lenpos, route_info::lp, startup::pos, projection_none, route_next_destination(), route_projection(), route_info::street, and transform_distance().

Referenced by navit_vehicle_update_position().

struct route* route_dup ( struct route orig)

Duplicates a route object.

Returns
The duplicated route

References callback_list_new(), route::cbl2, route::destination_distance, route::flags, route::ms, navit_object_ref(), route_func, and route::vehicleprofile.

Referenced by request_route_dup().

static struct route_path_segment* route_extract_segment_from_path ( struct route_path path,
struct item item,
int  offset 
)
static

Returns and removes one segment from a path.

Parameters
pathThe path to take the segment from
itemThe item whose segment to remove
offsetOffset of the segment within the item to remove. If the item is not segmented this should be 1.
Returns
The segment removed

References AF_SEGMENTED, item_hash_remove(), item_is_equal, route_path_segment::next, route_path::path, and route_path::path_hash.

Referenced by route_path_add_item_from_graph().

static void route_free_selection ( struct map_selection sel)
static

Destroys a list of map selections.

Parameters
selStart of the list to be destroyed

References map_selection::next, and next.

Referenced by route_graph_build_done().

struct coord route_get_coord_dist ( struct route this_,
int  dist 
)

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_path_segment::c, route_info::c, route_path_segment::data, int(), route_segment_data::len, route_path_segment::ncoords, route_path_segment::next, projection_none, route_get_dst(), route_projection(), transform_polyline_length(), 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_get_destination_count(), navit_remove_nth_waypoint(), navit_remove_waypoint(), navit_set_destination(), and navit_vehicle_update_position().

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 _, attr_to_text(), item::id_hi, item::id_lo, item, street_data::item, item_attr_get(), item_to_name(), label, item::map, map_rect_destroy(), map_rect_get_item_byid(), map_rect_new(), route_info::street, item::type, type, and attr::type.

Referenced by navit_get_destination_description(), and navit_vehicle_update_position().

int route_get_destinations ( struct route this,
struct pcoord pc,
int  count 
)
void route_get_distances ( struct route this,
struct coord c,
int  count,
int distances 
)
struct route_info* route_get_dst ( struct route this)

Returns the destination of the route passed.

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

Referenced by rm_coord_get(), rm_rect_new(), route_append_destination(), route_get_attr(), route_get_coord_dist(), route_projection(), route_remove_nth_waypoint(), and route_set_destinations().

enum route_path_flags route_get_flags ( struct route this_)

Returns the flags for the route.

References route::flags.

Referenced by navigation_update().

struct map* route_get_graph_map ( struct route this_)

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

References route::graph_map, and route_get_map_helper().

Referenced by navigation_itm_new(), and navit_init().

struct map* route_get_map ( struct route this_)

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

References route::map, and route_get_map_helper().

Referenced by gui_internal_cmd2_route_height_profile(), gui_internal_select_waypoint(), navigation_update(), navit_init(), navit_zoom_to_route(), route_get_attr(), route_get_map_py(), and vehicle_demo_timer().

static struct map* route_get_map_helper ( struct route this_,
struct map **  map,
char *  type,
char *  description 
)
static
struct mapset* route_get_mapset ( struct route this)

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)

Returns the current position within the route passed.

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

References startup::pos.

Referenced by rm_rect_new().

static int route_get_traffic_distortion ( struct route_graph_segment seg,
struct route_traffic_distortion ret 
)
static

Returns the traffic distortion for a segment.

Parameters
segThe segment for which the traffic distortion is to be returned
retPoints to a , whose members will be filled
Returns
true if a traffic distortion was found, 0 if not

References AF_SPEED_LIMIT, route_graph_segment::data, route_traffic_distortion::delay, route_graph_point::end, route_graph_segment::end, route_graph_segment::end_next, route_segment_data::flags, route_segment_data::item, route_segment_data::len, route_traffic_distortion::maxspeed, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, and item::type.

Referenced by route_value_seg().

static struct route_graph_point* route_graph_add_point ( struct route_graph this,
struct coord f 
)
static

Inserts a point into the route graph at the specified coordinates.

This will insert a point into the route graph at the coordinates passed in f. Note that the point is not yet linked to any segments.

If the route graph already contains a point at the specified coordinates, the existing point will be returned.

Parameters
thisThe route graph to insert the point into
fThe coordinates at which the point should be inserted
Returns
The point inserted or NULL on failure

References p, route_graph_get_point(), and route_graph_point_new().

Referenced by route_process_street_graph(), route_process_traffic_distortion(), and route_process_turn_restriction().

static void route_graph_add_segment ( struct route_graph this,
struct route_graph_point start,
struct route_graph_point end,
struct route_graph_segment_data data 
)
static

Inserts a new segment into the route graph.

Parameters
thisThe route graph to insert the segment into
startThe graph point which should be connected to the start of this segment
endThe graph point which should be connected to the end of this segment
lenThe length of this segment
itemThe item that is represented by this segment
flagsFlags for this segment
offsetIf the item passed in "item" is segmented (i.e. divided into several segments), this indicates the position of this segment within the item
maxspeedThe maximum speed allowed on this segment in km/h. -1 if not known.

References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, route_graph_point::c, route_graph_segment::data, dbg_assert, debug_route, route_graph_point::end, route_graph_segment::end, route_segment_data::flags, route_segment_data::item, route_graph_segment::next, size, route_graph_point::start, route_graph_segment::start, coord::x, and coord::y.

Referenced by route_graph_clone_segment(), route_graph_set_traffic_distortion(), route_process_street_graph(), route_process_traffic_distortion(), and route_process_turn_restriction().

static struct route_graph* route_graph_build ( struct mapset ms,
struct coord c,
int  count,
struct callback done_cb,
int  async,
struct vehicleprofile profile 
)
static

Builds a new route graph from a mapset.

This function builds a new route graph from a map. Please note that this function does not add any routing information to the route graph - this has to be done via the route_graph_flood() function.

The function does not create a graph covering the whole map, but only covering the rectangle between c1 and c2.

Parameters
msThe mapset to build the route graph from
cThe coordinates of the destination or next waypoint
c1Corner 1 of the rectangle to use from the map
c2Corner 2 of the rectangle to use from the map
done_cbThe callback which will be called when graph is complete
Returns
The new route graph.

References route_graph::busy, callback_cast, callback_new_2, dbg, route_graph::done_cb, event_add_idle(), route_graph::h, route_graph::idle_cb, route_graph::idle_ev, lvl_debug, mapset_open(), route_calc_selection(), route_graph_build_done(), route_graph_build_idle(), route_graph_build_next_map(), and route_graph::sel.

Referenced by route_graph_update().

static void route_graph_build_done ( struct route_graph rg,
int  cancel 
)
static

Releases all resources needed to build the route graph.

If

cancel

is false, this function will start processing restrictions and ultimately call the route graph's

done_cb

callback.

Parameters
rgPoints to the route graph
cancelTrue if the process was aborted before completing, false if it completed normally

References route_graph::busy, callback_call_0, callback_destroy(), dbg, route_graph::done_cb, event_remove_idle(), route_graph::h, route_graph::idle_cb, route_graph::idle_ev, lvl_debug, map_rect_destroy(), mapset_close(), route_graph::mr, route_free_selection(), route_graph_process_restrictions(), and route_graph::sel.

Referenced by route_graph_build(), route_graph_build_idle(), and route_graph_destroy().

static int route_graph_build_next_map ( struct route_graph rg)
static
static void route_graph_destroy ( struct route_graph this)
static
static void route_graph_flood ( struct route_graph this,
struct route_info dst,
struct vehicleprofile profile,
struct callback cb 
)
static

Calculates the routing costs for each point.

This function is the heart of routing. It assigns each point in the route graph a cost at which one can reach the destination from this point on. Additionally it assigns each point a segment one should follow from this point on to reach the destination at the stated costs.

This function uses Dijkstra's algorithm to do the routing. To understand it you should have a look at this algorithm.

References to elements of the route graph which were obtained prior to calling this function remain valid after it returns.

Parameters
this_The route graph to flood
dstThe destination of the route
profileThe vehicle profile to use for routing. This determines which ways are passable and how their costs are calculated.
cbThe callback function to call when flooding is complete

References route_graph_point::c, callback_call_0, route_graph_segment::data, dbg, debug_route, route_graph_point::el, route_graph_point::end, route_graph_segment::end, route_graph_segment::end_next, fh_deleteheap(), fh_extractmin(), fh_insertkey(), fh_makekeyheap(), fh_replacekey(), route_segment_data::item, item_is_equal, lvl_debug, route_info::percent, route_graph_get_segment(), route_value_seg(), route_graph_point::seg, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, route_info::street, vehicleprofile::turn_around_penalty2, route_graph_point::value, coord::x, and coord::y.

Referenced by route_graph_update_done(), route_path_new(), route_path_update_done(), and route_remove_waypoint().

static void route_graph_free_points ( struct route_graph this)
static

Frees all the memory used for points in the route graph passed.

Parameters
thisThe route graph to delete all points from

References route_graph_point::hash_next, HASH_SIZE, and next.

Referenced by route_graph_destroy().

static void route_graph_free_segments ( struct route_graph this)
static

Destroys all segments of a route graph.

Parameters
thisThe graph to destroy all segments from

References route_graph_segment::next, next, and size.

Referenced by route_graph_destroy().

static struct route_graph_point * route_graph_get_point ( struct route_graph this,
struct coord c 
)
static

Gets the first route_graph_point with the specified coordinates.

Parameters
thisThe route in which to search
cCoordinates to search for
Returns
The point at the specified coordinates or NULL if not found

References route_graph_get_point_next().

Referenced by route_crossings_get(), and route_graph_add_point().

static struct route_graph_point* route_graph_get_point_last ( struct route_graph this,
struct coord c 
)
static

Gets the last route_graph_point with the specified coordinates.

Parameters
thisThe route in which to search
cCoordinates to search for
Returns
The point at the specified coordinates or NULL if not found

References route_graph_point::c, route_graph_point::hash_next, p, coord::x, and coord::y.

Referenced by rp_get_item().

static struct route_graph_point* route_graph_get_point_next ( struct route_graph this,
struct coord c,
struct route_graph_point last 
)
static

Gets the next route_graph_point with the specified coordinates.

Parameters
thisThe route in which to search
cCoordinates to search for
lastThe last route graph point returned to iterate over multiple points with the same coordinates, or
NULL
to return the first point
Returns
The point at the specified coordinates or NULL if not found

References route_graph_point::c, route_graph_point::hash_next, p, coord::x, and coord::y.

Referenced by route_graph_get_point(), route_graph_get_segment(), and route_graph_set_traffic_distortion().

static struct route_graph_segment* route_graph_get_segment ( struct route_graph graph,
struct street_data sd,
struct route_graph_segment last 
)
static

Gets the next route_graph_segment belonging to the specified street.

Parameters
graphThe route graph in which to search
sdThe street to search for
lastThe last route graph segment returned to iterate over multiple segments of the same item. If
NULL
, the first matching segment will be returned.
Returns
The route graph segment, or
NULL
if none was found.

References street_data::c, route_graph_segment::data, street_data::item, route_segment_data::item, item_is_equal, route_graph_get_point_next(), route_graph_point::start, and route_graph_segment::start_next.

Referenced by route_graph_flood(), and route_path_new().

static struct map_priv* route_graph_map_new ( struct map_methods meth,
struct attr **  attrs,
struct callback_list cbl 
)
static

References route_map_new_helper().

Referenced by route_init().

static struct route_graph_point* route_graph_point_new ( struct route_graph this,
struct coord f 
)
static

Create a new point for the route graph with the specified coordinates.

Parameters
thisThe route to insert the point into
fThe coordinates at which the point should be created
Returns
The point created

References route_graph_point::c, debug_route, route_graph_point::hash_next, p, route_graph_point::value, coord::x, and coord::y.

Referenced by route_graph_add_point(), and route_graph_process_restriction_segment().

static void route_graph_process_restrictions ( struct route_graph this)
static
static void route_graph_reset ( struct route_graph this)
static

Resets all nodes.

This iterates through all the points in the route graph, resetting them to their initial state. The

member of each point (cost to reach the destination) is reset to

INT_MAX

, the

seg

member (cheapest way to destination) is reset to

NULL

and the

el

member (pointer to element in Fibonacci heap) is also reset to

NULL

.

References to elements of the route graph which were obtained prior to calling this function remain valid after it returns.

Parameters
thisThe route graph to reset

References route_graph_point::el, route_graph_point::hash_next, HASH_SIZE, route_graph_point::seg, and route_graph_point::value.

Referenced by route_path_new(), route_path_update_done(), and route_remove_waypoint().

static int route_graph_segment_is_duplicate ( struct route_graph_point start,
struct route_graph_segment_data data 
)
static

Checks if the route graph already contains a particular segment.

This function compares the item IDs of both segments. If the item is segmented, the segment offset is also compared.

Parameters
startThe starting point of the segment
dataThe data for the segment

References AF_SEGMENTED, route_graph_segment::data, route_graph_segment_data::flags, route_segment_data::item, route_graph_segment_data::item, item_is_equal, route_graph_segment_data::offset, route_graph_point::start, and route_graph_segment::start_next.

Referenced by route_process_street_graph().

static int route_graph_segment_match ( struct route_graph_segment s1,
struct route_graph_segment s2 
)
static

Whether two route graph segments match.

Two segments match if both start and end at the exact same points. Other points are not considered.

Parameters
s1The first segment
s2The second segment
Returns
true if both segments match, false if not

References route_graph_point::c, route_graph_segment::end, route_graph_segment::start, coord::x, and coord::y.

Referenced by route_graph_set_traffic_distortion(), and route_path_new().

static void route_graph_set_traffic_distortion ( struct route_graph this,
struct route_graph_segment seg,
int  delay 
)
static

Sets or clears a traffic distortion for a segment.

This sets a delay (setting speed is not supported) or clears an existing traffic distortion. Note that, although setting a speed is not supported, calling this function with a delay of 0 will also clear an existing speed constraint.

Parameters
thisThe route graph
segThe segment to which the traffic distortion applies
delayDelay in tenths of a second, or 0 to clear an existing traffic distortion

References route_graph_point::c, route_graph_segment::data, route_graph_segment::end, route_graph_point::flags, item, route_segment_data::item, route_graph_segment_data::item, route_graph_segment_data::len, route_graph_add_segment(), route_graph_get_point_next(), route_graph_segment_match(), route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, and item::type.

Referenced by route_path_new().

static void route_graph_update ( struct route this,
struct callback cb,
int  async 
)
static

Updates the route graph.

This updates the route graph after settings in the route have changed. It also adds routing information afterwards by calling route_graph_flood().

Parameters
thisThe route to update the graph for
cbThe callback function to call when the route graph update is complete (used only in asynchronous mode)
asyncSet to nonzero in order to update the route graph asynchronously

References route_info::c, c, callback_cast, callback_destroy(), callback_new_2, attr::num, startup::pos, route_graph_build(), route_graph_build_idle(), route_graph_destroy(), route_graph_update_done(), route_set_attr(), route_status_building_graph, attr::type, and attr::u.

Referenced by route_path_update_flags().

static void route_graph_update_done ( struct route this,
struct callback cb 
)
static

References route_graph_flood().

Referenced by route_graph_update().

int route_has_graph ( struct route this_)

Whether the route has a valid graph.

Returns
True if the route has a graph, false if not.

References route::graph.

Referenced by navigation_update_idle().

static void route_info_distances ( struct route_info ri,
enum projection  pro 
)
static
void route_info_free ( struct route_info inf)
struct street_data* route_info_street ( struct route_info rinf)

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.

void route_init ( void  )

References route_graph_map_new(), and route_map_new().

Referenced by main_real().

static struct map_priv* route_map_new ( struct map_methods meth,
struct attr **  attrs,
struct callback_list cbl 
)
static

References route_map_new_helper().

Referenced by route_init().

static struct map_priv* route_map_new_helper ( struct map_methods meth,
struct attr **  attrs,
int  graph 
)
static
struct route* route_new ( struct attr parent,
struct attr **  attrs 
)

Creates a completely new route structure.

Parameters
attrsNot used
Returns
The newly created route

References attr_generic_get_attr(), callback_list_new(), navit_object_ref(), attr::num, route_func, and attr::u.

static struct route_info* route_next_destination ( struct route this)
static
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 
)
static

Inserts a new item into the path.

This function does almost the same as "route_path_add_item()", but identifies the item to add by a segment from the route graph. Another difference is that it "copies" the segment from the route graph, i.e. if the item is segmented, only the segment passed in rgs will be added to the route path, not all segments of the item.

The function can be sped up by passing an old path already containing this segment in oldpath - the segment will then be extracted from this old path. Please note that in this case the direction parameter has no effect.

Parameters
thisThe path to add the item to
oldpathOld path containing the segment to be added. Speeds up the function, but can be NULL.
rgsSegment of the route graph that should be "copied" to the route path
dirOrder in which to add the coordinates. See route_path_add_item()
posInformation about start point if this is the first segment
dstInformation about end point if this is the last segment

References AF_ROUNDABOUT, AF_SEGMENTED, street_data::c, route_graph_point::c, route_path_segment::c, c, street_data::count, route_graph_segment::data, route_path_segment::data, dbg, route_info::dir, route_path_segment::direction, route_graph_segment::end, route_segment_data::flags, get_item_seg_coords(), item::id_hi, item::id_lo, route_segment_data::item, item_hash_insert(), item_hash_lookup(), route_segment_data::len, route_info::lenneg, route_info::lenpos, route_info::lp, lvl_debug, route_path_segment::ncoords, route_path_segment::next, offset, route_path::path_hash, route_info::pos, route_check_roundabout(), route_extract_segment_from_path(), route_path_add_segment(), route_segment_data_size(), route_graph_segment::start, route_info::street, coord::x, and coord::y.

Referenced by route_path_new().

static void route_path_add_line ( struct route_path this,
struct coord start,
struct coord end,
int  len 
)
static

Adds a two coordinate line to a path.

This adds a new line to a path, creating a new segment for it.

Parameters
thisThe path to add the item to
startcoordinate to add to the start of the item. If none should be added, make this NULL.
endcoordinate to add to the end of the item. If none should be added, make this NULL.
lenThe length of the item

References route_path_segment::c, route_path_segment::data, dbg, route_path_segment::direction, route_segment_data::len, lvl_debug, route_path_segment::ncoords, route_path_add_segment(), coord::x, and coord::y.

Referenced by route_path_new(), and route_path_new_offroad().

static void route_path_add_segment ( struct route_path this,
struct route_path_segment segment 
)
static

Adds a segment and the end of a path.

Parameters
thisThe path to add the segment to
segmentThe segment to add

References route_path_segment::next.

Referenced by route_path_add_item_from_graph(), and route_path_add_line().

static void route_path_destroy ( struct route_path this,
int  recurse 
)
static
static void route_path_get_distances ( struct route_path path,
struct coord c,
int  count,
int distances 
)
static
static struct route_path * route_path_new ( struct route_graph this,
struct route_path oldpath,
struct route_info pos,
struct route_info dst,
struct vehicleprofile profile 
)
static

Creates a new route path.

This creates a new non-trivial route. It therefore needs the routing information created by route_graph_flood, so make sure to run route_graph_flood() after changing the destination before using this function.

Parameters
thisThe route graph to create the route from
oldpath(Optional) old path which may contain parts of the new part - this speeds things up a bit. May be NULL.
posThe starting position of the route
dstThe destination of the route
preferencesThe routing preferences
Returns
The new route path

References route_graph_point::c, route_info::c, route_graph_segment::data, dbg, route_info::dir, route_graph_point::end, route_graph_segment::end, route_path::in_use, street_data::item, route_segment_data::item, item_hash_new(), item_is_equal, route_info::lenextra, route_info::lp, lvl_debug, lvl_error, item::map, map_projection(), vehicleprofile::mode, route_path::path_hash, route_info::percent, startup::pos, route_graph_flood(), route_graph_get_segment(), route_graph_reset(), route_graph_segment_match(), route_graph_set_traffic_distortion(), route_path_add_item_from_graph(), route_path_add_line(), route_path_new_offroad(), route_value_seg(), s1, route_graph_point::seg, route_graph_point::start, route_graph_segment::start, route_info::street, route_info::street_direction, transform_distance(), vehicleprofile::turn_around_penalty, route_path::updated, route_graph_point::value, coord::x, and coord::y.

Referenced by route_path_update_done().

static struct route_path* route_path_new_offroad ( struct route_graph this,
struct route_info pos,
struct route_info dst 
)
static

Starts an "offroad" path.

This starts a path that is not located on a street. It creates a new route path adding only one segment, that leads from pos to dest, and which is not associated with an item.

Parameters
thisNot used
posThe starting position for the new path
dstThe destination of the new path
dirNot used
Returns
The new path

References route_info::c, route_path::in_use, item_hash_new(), route_info::lenextra, route_path::path_hash, route_path_add_line(), and route_path::updated.

Referenced by route_path_new().

static void route_path_update ( struct route this,
int  cancel,
int  async 
)
static

Updates the route graph and the route path if something changed with the route.

This function is a wrapper around route_path_update_flags(route *, enum route_path).

Parameters
thisThe route to update
cancelIf true, cancel navigation, clear route graph and route path
asyncIf true, perform processing asynchronously

References route_path_flag_async, route_path_flag_cancel, and route_path_update_flags().

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

static void route_path_update_done ( struct route this,
int  new_graph 
)
static

Updates or recreates the route graph.

This function is called after the route graph has been changed or rebuilt and flooding has completed. It then updates the route path to reflect these changes.

If multiple destinations are set, this function will reset and re-flood the route graph for each destination, thus recursively calling itself for each destination.

Parameters
thisThe route object
new_graphFIXME Whether the route graph has been rebuilt from scratch

References route_path_segment::data, dbg, route_segment_data::len, lvl_debug, route_path_segment::next, route_path::next, attr::num, startup::pos, route_graph_flood(), route_graph_reset(), route_path_destroy(), route_path_new(), route_previous_destination(), route_set_attr(), route_status_building_path, route_status_not_found, route_status_path_done_incremental, route_status_path_done_new, route_time_seg(), attr::type, and attr::u.

Referenced by rm_rect_destroy(), and route_path_update_flags().

static void route_path_update_flags ( struct route this,
enum route_path_flags  flags 
)
static

Updates the route graph and the route path if something changed with the route.

This will update the route graph and the route path of the route if some of the route's settings (destination, position) have changed.

The behavior of this function can be controlled via flags:

These flags will be stored in the

member of the route object.

Attention
For this to work the route graph has to be destroyed if the route's
destination is changed somewhere!
Parameters
thisThe route to update
flagsFlags to control the behavior of this function, see description

References callback_cast, callback_new_2, dbg, lvl_debug, startup::pos, route_graph_destroy(), route_graph_update(), route_path_destroy(), route_path_flag_async, route_path_flag_cancel, route_path_flag_no_rebuild, and route_path_update_done().

Referenced by route_path_update(), and route_set_position_flags().

static struct route_info* route_previous_destination ( struct route this)
static

Returns the position from which to route to the current destination of the route.

This function examines the destination list of the route. If present, it returns the destination which precedes the one indicated by the

current_dst

member of the route. Failing that, the current position of the route is returned.

Parameters
thisThe route object
Returns
The previous destination or current position, see description

References startup::pos.

Referenced by route_path_update_done().

static void route_process_traffic_distortion ( struct route_graph this,
struct item item 
)
static
static void route_process_turn_restriction ( struct route_graph this,
struct item item 
)
static
static enum projection route_projection ( struct route route)
static

Returns the projection used for this route.

Parameters
routeThe route to return the projection for
Returns
The projection used for this route

References street_data::item, item::map, map_projection(), route::pos, projection_none, route_get_dst(), and route_info::street.

Referenced by rm_coord_get(), route_destination_reached(), route_get_coord_dist(), and rp_coord_get().

static struct map_selection* route_rect_add ( struct map_selection sel,
int  order,
struct coord c1,
struct coord c2,
int  rel,
int  abs 
)
static

Appends a map selection to the selection list. Selection list may be NULL.

References map_selection::next, and route_rect().

Referenced by route_calc_selection().

int route_remove_attr ( struct route this_,
struct attr attr 
)
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(), route_graph_destroy(), route_info_free(), and route_path_update().

Referenced by navit_remove_nth_waypoint().

static int route_seg_speed ( struct vehicleprofile profile,
struct route_segment_data over,
struct route_traffic_distortion dist 
)
static

Returns the estimated speed on a segment, or 0 for an impassable segment.

This function returns the estimated speed to be driven on a segment, calculated as follows:

  • Initially the route weight of the vehicle profile for the given item type is used. If the item type does not have a route weight in the vehicle profile given, it is considered impassable and 0 is returned.
  • If the attribute of the segment's item is set, either it or the previous speed estimate for the segment is used, as governed by the vehicle profile's attribute.
  • If a traffic distortion is present, its is taken into account in a similar manner. Unlike the regular , a resulting from a traffic distortion is always considered if it limits the speed, regardless of .
  • Access restrictions for dangerous goods, size or weight are evaluated, and 0 is returned if the given vehicle profile violates one of them.
Parameters
profileThe routing preferences
overThe segment which is passed
distA traffic distortion if applicable, or
NULL
Returns
The estimated speed in km/h, or 0 if the segment is impassable

References AF_DANGEROUS_GOODS, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, vehicleprofile::axle_weight, size_weight_limit::axle_weight, vehicleprofile::dangerous_goods, route_segment_data::flags, vehicleprofile::height, size_weight_limit::height, route_segment_data::item, vehicleprofile::length, size_weight_limit::length, roadprofile::maxspeed, route_traffic_distortion::maxspeed, maxspeed_enforce, vehicleprofile::maxspeed_handling, maxspeed_ignore, maxspeed_restrict, roadprofile::route_weight, roadprofile::speed, item::type, vehicleprofile_get_roadprofile(), vehicleprofile::weight, size_weight_limit::weight, vehicleprofile::width, and size_weight_limit::width.

Referenced by rm_attr_get(), route_time_seg(), and rp_attr_get().

static void* route_segment_data_field_pos ( struct route_segment_data seg,
enum attr_type  type 
)
static

Returns the position of a certain field appended to a route graph segment.

This function returns a pointer to a field that is appended to a route graph segment.

Parameters
segThe route graph segment the field is appended to
typeType of the field that should be returned
Returns
A pointer to a field of a certain type, or NULL if no such field is present

References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, route_segment_data::flags, and int().

static int route_segment_data_size ( int  flags)
static

Calculates the size of a route_segment_data struct with given flags.

Parameters
flagsThe flags of the route_segment_data

References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, and int().

Referenced by route_path_add_item_from_graph().

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

Start a route given set of coordinates.

Parameters
thisThe route instance
dstThe coordinate to start routing to
asyncSet to 1 to do route calculation asynchronously
Returns
nothing

References route_set_destinations().

Referenced by navit_add_former_destinations_from_file(), navit_set_destination(), and route_set_attr().

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
dstPoints to an array of coordinates to set as destinations, which will be visited in the order in which they appear in the array (the last one is the final destination)
countNumber of items in
dst
, 0 to clear all destinations
asyncIf set, do routing asynchronously

References callback_list_call_attr_1, attr::num, pcoord::pro, profile, route_clear_destinations(), route_find_nearest_street(), route_get_dst(), route_graph_destroy(), route_info_distances(), route_path_update(), route_set_attr(), route_status_destination_set, route_status_no_destination, attr::type, and attr::u.

Referenced by NGQProxyRoute::addDestination(), navit_add_former_destinations_from_file(), 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

Referenced by navit_init().

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_path_flag_async, and route_set_position_flags().

Referenced by navit_set_position(), navit_vehicle_update_position(), and route_set_attr().

static int route_set_position_flags ( struct route this,
struct pcoord pos,
enum route_path_flags  flags 
)
static

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
flagsFlags to use for building the graph

References dbg, lvl_debug, pcoord::pro, route_find_nearest_street(), route_info_distances(), route_info_free(), and route_path_update_flags().

Referenced by route_set_attr(), and route_set_position().

void route_set_position_from_tracking ( struct route this,
struct tracking tracking,
enum projection  pro 
)
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_get_destinations(), and route_set_destinations().

Referenced by navit_set_vehicle(), and navit_set_vehicleprofile().

void route_set_projection ( struct route this_,
enum projection  pro 
)

Referenced by navit_init().

static int route_through_traffic_allowed ( struct vehicleprofile profile,
struct route_graph_segment seg 
)
static
static int route_time_seg ( struct vehicleprofile profile,
struct route_segment_data over,
struct route_traffic_distortion dist 
)
static

Returns the time needed to travel along a segment, or.

INT_MAX

if the segment is impassable.

This function returns the time needed to travel along the entire length of

over

in tenths of seconds. Restrictions for dangerous goods, weight or size are taken into account. Traffic distortions are also taken into account if a valid

dist

argument is given.

Parameters
profileThe vehicle profile (routing preferences)
overThe segment which is passed
distA traffic distortion if applicable, or
NULL
Returns
The time needed in tenths of seconds

References route_traffic_distortion::delay, route_segment_data::len, and route_seg_speed().

Referenced by rm_attr_get(), route_path_update_done(), route_value_seg(), and rp_attr_get().

static int route_value_seg ( struct vehicleprofile profile,
struct route_graph_point from,
struct route_graph_segment over,
int  dir 
)
static

Returns the "cost" of driving from point.

from

along segment

over

in direction

dir

Cost is relative to time, indicated in tenths of seconds.

This function considers traffic distortions as well as penalties. If the segment is impassable due to traffic distortions or restrictions,

INT_MAX

is returned in order to prevent use of this segment for routing.

Parameters
profileThe routing preferences
fromThe point where we are starting
overThe segment we are using
dirThe direction of segment which we are driving. Positive values indicate we are traveling in the direction of the segment, negative values indicate we are traveling against that direction. Values of +2 or -2 cause the function to ignore traffic distortions.
Returns
The "cost" needed to travel along the segment

References route_graph_segment::data, dbg, route_graph_segment::end, vehicleprofile::flags, route_graph_point::flags, route_segment_data::flags, vehicleprofile::flags_forward_mask, vehicleprofile::flags_reverse_mask, lvl_debug, route_get_traffic_distortion(), route_through_traffic_allowed(), route_time_seg(), route_graph_point::seg, route_graph_segment::start, and vehicleprofile::through_traffic_penalty.

Referenced by route_graph_flood(), and route_path_new().

static void rp_attr_rewind ( void *  priv_data)
static

References map_rect_priv::attr_next.

Referenced by rp_get_item().

static int rp_coord_get ( void *  priv_data,
struct coord c,
int  count 
)
static

Returns the coordinates of a route graph item.

Parameters
priv_dataThe route graph item's private data
cPointer where to store the coordinates
countHow many coordinates to get at a max?
Returns
The number of coordinates retrieved

References route_graph_point::c, route_graph_segment::end, map_rect_priv::item, map_rect_priv::last_coord, map_rect_priv::mpriv, p, map_rect_priv::point, projection_mg, projection_none, map_priv::route, route_projection(), map_rect_priv::rseg, route_graph_point::seg, route_graph_segment::start, transform_from_to(), and item::type.

static void rp_destroy ( struct map_priv priv)
static
static struct item* rp_get_item_byid ( struct map_rect_priv mr,
int  id_hi,
int  id_lo 
)
static

References rp_get_item().

static int rp_iterator_end ( struct route_graph_point_iterator it)
static

Checks if the last segment returned from a route_graph_point_iterator comes from the end.

Parameters
itThe route graph point iterator to be checked
Returns
1 if the last segment returned comes from the end of the route graph point, 0 otherwise

References route_graph_point::end, route_graph_point_iterator::end, route_graph_point_iterator::next, and route_graph_point_iterator::p.

Referenced by route_check_roundabout().

static struct route_graph_point_iterator rp_iterator_new ( struct route_graph_point p)
static

Creates a new graph point iterator.

This function creates a new route graph point iterator, that can be used to iterate through all segments connected to the point.

Parameters
pThe route graph point to create the iterator from
Returns
A new iterator.

References route_graph_point_iterator::end, route_graph_point_iterator::next, p, and route_graph_point_iterator::p.

Referenced by route_check_roundabout(), and rp_get_item().

static struct route_graph_segment* rp_iterator_next ( struct route_graph_point_iterator it)
static

Gets the next segment connected to a route graph point from an iterator.

Parameters
itThe route graph point iterator to get the segment from
Returns
The next segment or NULL if there are no more segments

References route_graph_point::end, route_graph_point_iterator::end, route_graph_segment::end_next, route_graph_point_iterator::next, route_graph_point_iterator::p, and route_graph_segment::start_next.

Referenced by route_check_roundabout(), and rp_get_item().

static struct map_rect_priv* rp_rect_new ( struct map_priv priv,
struct map_selection sel 
)
static

Opens a new map rectangle on the route graph's map.

This function opens a new map rectangle on the route graph's map. The "sel" parameter enables you to only search for a single route graph point on this map (or exactly: open a map rectangle that only contains this one point). To do this, pass here a single map selection, whose c_rect has both coordinates set to the same point. Otherwise this parameter has no effect.

Parameters
privThe route graph map's private data
selHere it's possible to specify a point for which to search. Please read the function's description.
Returns
A new map rect's private data

References map_selection::c_rect, map_rect_priv::coord_sel, dbg, route::graph, map_rect_priv::item, coord_rect::lu, lvl_debug, item::meth, methods_point_item, map_rect_priv::mpriv, item::priv_data, coord_rect::rl, map_priv::route, item::type, map_selection::u, coord::x, and coord::y.

struct street_data* street_data_dup ( struct street_data orig)

Copies street data.

Parameters
origThe street data to copy
Returns
The copied street data

References size.

Referenced by route_set_position_from_tracking().

struct street_data* street_get_data ( struct item item)

Gets street data for an item.

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

References AF_SPEED_LIMIT, street_data::c, c, street_data::count, street_data::flags, item, street_data::item, item_attr_get(), item_coord_get(), item_get_default_flags(), street_data::maxspeed, attr::num, item::type, and attr::u.

Referenced by route_find_nearest_street().

Variable Documentation

struct item_methods methods_point_item
static
Initial value:
= {
}
static int rp_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
Definition: route.c:3503
static void rp_attr_rewind(void *priv_data)
Definition: route.c:3496
static void rm_coord_rewind(void *priv_data)
Definition: route.c:3351
static int rp_coord_get(void *priv_data, struct coord *c, int count)
Returns the coordinates of a route graph item.
Definition: route.c:3638

Referenced by rp_rect_new().

struct item_methods methods_route_item
static
Initial value:
= {
}
static int rm_attr_get(void *priv_data, enum attr_type attr_type, struct attr *attr)
Definition: route.c:3365
static void rm_attr_rewind(void *priv_data)
Definition: route.c:3358
static void rm_coord_rewind(void *priv_data)
Definition: route.c:3351
static int rm_coord_get(void *priv_data, struct coord *c, int count)
Definition: route.c:3447

Referenced by rm_rect_new().

struct object_func route_func
Initial value:
= {
attr_route,
}
void(* object_func_destroy)(void *)
Definition: xmlconfig.h:62
void *(* object_func_dup)(void *)
Definition: xmlconfig.h:63
void(* object_func_iter_destroy)(struct attr_iter *)
Definition: xmlconfig.h:57
void navit_object_unref(struct navit_object *obj)
Definition: xmlconfig.c:1272
int route_remove_attr(struct route *this_, struct attr *attr)
Definition: route.c:4138
int(* object_func_init)(void *)
Definition: xmlconfig.h:61
void *(* object_func_ref)(void *)
Definition: xmlconfig.h:64
struct attr_iter *(* object_func_iter_new)(void *)
Definition: xmlconfig.h:56
struct route * route_new(struct attr *parent, struct attr **attrs)
Creates a completely new route structure.
Definition: route.c:484
void *(* object_func_unref)(void *)
Definition: xmlconfig.h:65
int route_add_attr(struct route *this_, struct attr *attr)
Definition: route.c:4126
int(* object_func_remove_attr)(void *, struct attr *attr)
Definition: xmlconfig.h:60
void *(* object_func_new)(struct attr *parent, struct attr **attrs)
Definition: xmlconfig.h:54
int(* object_func_set_attr)(void *, struct attr *attr)
Definition: xmlconfig.h:58
int route_set_attr(struct route *this_, struct attr *attr)
Definition: route.c:4084
void route_destroy(struct route *this_)
Definition: route.c:4247
int(* object_func_get_attr)(void *, enum attr_type type, struct attr *attr, struct attr_iter *iter)
Definition: xmlconfig.h:55
int route_get_attr(struct route *this_, enum attr_type type, struct attr *attr, struct attr_iter *iter)
Definition: route.c:4154
struct navit_object * navit_object_ref(struct navit_object *obj)
Definition: xmlconfig.c:1264
struct route * route_dup(struct route *orig)
Duplicates a route object.
Definition: route.c:509
int(* object_func_add_attr)(void *, struct attr *attr)
Definition: xmlconfig.h:59

Referenced by object_func_lookup(), route_dup(), and route_new().

struct map_methods route_graph_meth
static
Initial value:
= {
"utf-8",
NULL,
NULL,
NULL,
}
static void rp_destroy(struct map_priv *priv)
Definition: route.c:3694
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.
Definition: route.c:3749
Definition: projection.h:25
static void rm_rect_destroy(struct map_rect_priv *mr)
Definition: route.c:3771
static struct item * rp_get_item(struct map_rect_priv *mr)
Definition: route.c:3790
static struct item * rp_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
Definition: route.c:3857

Referenced by route_map_new_helper().

struct map_methods route_meth
static
Initial value:
= {
"utf-8",
NULL,
NULL,
NULL,
}
static struct item * rm_get_item(struct map_rect_priv *mr)
Definition: route.c:3867
static struct item * rm_get_item_byid(struct map_rect_priv *mr, int id_hi, int id_lo)
Definition: route.c:3933
Definition: projection.h:25
static void rm_rect_destroy(struct map_rect_priv *mr)
Definition: route.c:3771
static struct map_rect_priv * rm_rect_new(struct map_priv *priv, struct map_selection *sel)
Definition: route.c:3706
static void rm_destroy(struct map_priv *priv)
Definition: route.c:3700

Referenced by route_map_new_helper().

struct map_selection* route_selection

FIXME

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

Referenced by do_draw().