- Generated by
1.9.1
|
navit
0.5.3-trunk
|
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_protected.h"Data Structures | |
| struct | map_priv |
| Represents the map from a single binfile. 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_point_iterator |
| Iterator to iterate through all route graph segments in a route graph point. More... | |
| struct | attr_iter |
| struct | map_rect_priv |
| Implementation-specific map rect data. More... | |
Functions | |
| static struct route_info * | route_find_nearest_street (struct vehicleprofile *vehicleprofile, struct mapset *ms, struct pcoord *pc) |
| Finds the nearest street to a given coordinate. More... | |
| static void | route_graph_update (struct route *this, struct callback *cb, int async) |
| Updates the route graph. More... | |
| 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) |
| Creates a new route path. More... | |
| static void | route_graph_add_street (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_compute_shortest_path (struct route_graph *graph, struct vehicleprofile *profile, struct callback *cb) |
| Expands (i.e. calculates the costs for) the points on the route graph’s heap. More... | |
| static int | route_graph_is_path_computed (struct route_graph *this_) |
| Whether cost (re)calculation of route graph points has reached the start point. More... | |
| static struct route_graph_segment * | route_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 int | route_value_seg (struct vehicleprofile *profile, struct route_graph_point *from, struct route_graph_segment *over, int dir) |
Returns the "cost" of traveling along segment over in direction dir More... | |
| static void | route_graph_init (struct route_graph *this, struct route_info *dst, struct vehicleprofile *profile) |
| Initializes potential destination nodes. 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_segment * | rp_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 route * | route_new (struct attr *parent, struct attr **attrs) |
| Creates a completely new route structure. More... | |
| struct route * | route_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 mapset * | route_get_mapset (struct route *this) |
| Returns the mapset of the route passed. More... | |
| struct route_info * | route_get_pos (struct route *this) |
| Returns the current position within the route passed. More... | |
| struct route_info * | route_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_info * | route_next_destination (struct route *this) |
| int | route_destination_reached (struct route *this) |
| Checks if a route has reached its destination. More... | |
| static struct route_info * | route_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_selection * | route_rect (int order, struct coord *c1, struct coord *c2, int rel, int abs) |
| Returns a single map selection. More... | |
| static struct map_selection * | route_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_selection * | route_calc_selection (struct coord *c, int count, struct vehicleprofile *profile) |
| Returns a list of map selections useable to create a route graph. More... | |
| struct map_selection * | route_get_selection (struct route *this_) |
| Retrieves the map selection for the route. More... | |
| void | route_free_selection (struct map_selection *sel) |
| Destroys a list of map selections. More... | |
| static void | route_info_free_g (struct route_info *inf, void *unused) |
| 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) |
| Retrieves destinations from the route. More... | |
| 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) |
| struct route_graph_point * | route_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... | |
| struct route_graph_point * | route_graph_get_point (struct route_graph *this, struct coord *c) |
| Gets the first route_graph_point with the specified coordinates. More... | |
| static struct route_graph_point * | route_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_point * | route_graph_point_new (struct route_graph *this, struct coord *f) |
| Create a new point for the route graph with the specified coordinates. More... | |
| struct route_graph_point * | route_graph_add_point (struct route_graph *this, struct coord *f) |
| Inserts a point into the route graph at the specified coordinates. More... | |
| void | route_graph_free_points (struct route_graph *this) |
| Frees all the memory used for points in the route graph passed. More... | |
| 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... | |
| 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... | |
| 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 struct route_path_segment * | route_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 segment into the path. More... | |
| 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, int dir, struct vehicleprofile *profile, 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_graph_segment_match (struct route_graph_segment *s1, struct route_graph_segment *s2) |
| Whether two route graph segments match. More... | |
| static int | route_value_add (int val1, int val2) |
| Adds two route values with protection against integer overflows. More... | |
| static void | route_graph_point_update (struct vehicleprofile *profile, struct route_graph_point *p, struct fibheap *heap) |
| Updates the lookahead value of a point in the route graph and updates its heap membership. 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_graph_add_traffic_distortion (struct route_graph *this, struct vehicleprofile *profile, struct item *item, int update) |
| Adds a traffic distortion item to the route graph. More... | |
| static void | route_graph_remove_traffic_distortion (struct route_graph *this, struct vehicleprofile *profile, struct item *item) |
| Removes a traffic distortion item from the route graph. More... | |
| static void | route_graph_change_traffic_distortion (struct route_graph *this, struct vehicleprofile *profile, struct item *item) |
| Changes a traffic distortion item in the route graph. More... | |
| void | route_graph_add_turn_restriction (struct route_graph *this, struct item *item) |
| Adds a turn restriction item to the route graph. More... | |
| void | route_recalculate_partial (struct route *this_) |
| Triggers partial recalculation of the route, based on the existing route graph. More... | |
| static struct route_path * | route_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) |
| void | route_graph_build_done (struct route_graph *rg, int cancel) |
| Releases all resources needed to build the route graph. More... | |
| static void | route_graph_build_idle (struct route_graph *rg, struct vehicleprofile *profile) |
| static struct route_graph * | route_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_data * | street_get_data (struct item *item) |
| Gets street data for an item. More... | |
| struct street_data * | street_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_data * | route_info_street (struct route_info *rinf) |
| Returns street data for a route info. More... | |
| 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_priv * | rm_rect_new (struct map_priv *priv, struct map_selection *sel) |
| 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. More... | |
| static void | rm_rect_destroy (struct map_rect_priv *mr) |
| 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 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 struct map_priv * | route_map_new_helper (struct map_methods *meth, struct attr **attrs, int graph) |
| static struct map_priv * | route_map_new (struct map_methods *meth, struct attr **attrs, struct callback_list *cbl) |
| static struct map_priv * | route_graph_map_new (struct map_methods *meth, struct attr **attrs, struct callback_list *cbl) |
| static struct map * | route_get_map_helper (struct route *this_, struct map **map, char *type, char *description) |
| void | route_add_traffic_distortion (struct route *this_, struct item *item) |
| Adds a traffic distortion item to the route. More... | |
| void | route_change_traffic_distortion (struct route *this_, struct item *item) |
| Changes a traffic distortion item on the route. More... | |
| struct map * | route_get_map (struct route *this_) |
| Returns a new map containing the route path. More... | |
| struct map * | route_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... | |
| struct route_graph * | route_get_graph (struct route *this_) |
| Retrieves the route graph. More... | |
| int | route_has_graph (struct route *this_) |
| Whether the route has a valid graph. More... | |
| void | route_remove_traffic_distortion (struct route *this_, struct item *item) |
| Removes a traffic distortion item from the route. 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_iter * | route_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_selection * | route_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 |
Contains code related to finding a route from a position to a destination.
Navit, a modular navigation system. Copyright (C) 2005-2018 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.
Routing now relies on the Lifelong Planning A* (LPA*) algorithm, which builds upon the A* algorithm but allows for partial updates after the cost of some segments has changed. (With A*, one would need to recalculate the entire route graph from scratch.) A*, in turn, is an extension of the Dijkstra algorithm, with the added improvement that A* introduces a heuristic (essentially, a lower boundary for the yet-to-be-calculated remainder of the route from a given point onwards) and chooses the next point to analyze based on the sum of its cost and its heuristic, where Dijkstra uses simply the cost of the node. This makes A* more efficient than Dijkstra in some scenarios. (Navit, however, is not one of them, as we currently analyze only a subset of the entire map, and calculating the heuristic for each node turned out to cost more than it saved in tests.)
Wikipedia has articles on all three algorithms; refer to these for an in-depth discussion of the algorithms.
If the heuristic is assumed to be zero in all cases, A* behaves exactly as Dijkstra would. Similarly, LPA* behaves identically to A* if all segment costs are known prior to route calculation and do not change once route calculation has started.
Earlier versions of Navit used Dijkstra for routing. This was upgraded to LPA* when the traffic module was introduced, as it became necessary to do fast partial recalculations of the route when the traffic situation changes. Navit’s LPA* implementation differs from the canonical implementation in two important ways:
The cost of a node is always the cost to reach the destination, and route calculation is done “backwards”, i.e. starting at the destination and working its way to the current position (or previous waypoint). This is mandatory in LPA*, while A* and Dijkstra can also work from the start to the destination. The latter is found in most textbook descriptions of these algorithms. Navit has always calculated routes from destination to start, even with Dijkstra, as this made it easier to react to changes in the vehicle position (the start of the route).
A route graph first needs to be built with route_graph_build(), which fetches the segments from the map. Next route_graph_init() is called to initialize the destination point candidates. Then route_graph_compute_shortest_path() is called to assign a value to each node, which represents the cost of traveling from this point to the destination. Each point is also assigned a “next segment” to take in order to reach the destination from this point. Eventually a “route path” is created, i.e. the sequence of segments from the current position to the destination are extracted from the route graph and turn instructions are added where necessary.
When segment costs change, route_graph_point_update() is called for each end point which may have changed. Then route_graph_compute_shortest_path() is called to update parts of the route which may have changed, and finally the route path is recreated. This is used by the traffic module when traffic reports change the cost of individual segments.
A completely new route can be created from an existing graph, which happens e.g. between sections of a route when waypoints are used. This is done by calling route_graph_reset(), which resets all nodes to their initial state. Then route_graph_init() is called, followed by route_graph_compute_shortest_path() and eventually creation of the route path.
|
static |
References route_graph_point::c, route_graph_segment::data, dbg, route_graph_segment::end, route_graph_segment::end_next, item::id_hi, item::id_lo, route_segment_data::item, item_is_equal, item_to_name(), lvl_debug, next, p, route_graph_segment::start, route_graph_segment::start_next, item::type, coord::x, and coord::y.
Referenced by route_graph_process_restriction_segment().
References AF_SPEED_LIMIT, map_rect_priv::attr_next, route_path_segment::data, map_rect_priv::dest, route::destinations, route_path_segment::direction, route_segment_data::flags, attr::item, map_rect_priv::item, route_segment_data::item, route_segment_data::len, item::map, map_rect_priv::mpriv, attr::num, route::reached_destinations_count, attr::route, map_priv::route, route_seg_speed(), route_time_seg(), RSD_MAXSPEED, map_rect_priv::seg, attr::str, map_rect_priv::str, attr::type, item::type, attr::u, and route::vehicleprofile.
|
static |
References map_rect_priv::attr_next.
Referenced by rm_get_item().
|
static |
|
static |
References map_rect_priv::last_coord.
Referenced by rp_get_item().
|
static |
|
static |
References map_rect_priv::dest, route::destinations, route_info::dir, route_path::in_use, map_rect_priv::item, item_id_from_ptr(), map_rect_priv::last_coord, map_rect_priv::mpriv, route_path_segment::next, route_path::next, p, route_path::path, map_rect_priv::path, route::pos, rm_attr_rewind(), map_priv::route, map_rect_priv::seg, map_rect_priv::seg_next, route_info::street_direction, and item::type.
Referenced by rm_get_item_byid().
|
static |
References item::id_hi, item::id_lo, and rm_get_item().
|
static |
|
static |
References attr::callback, callback_list_add(), route::cbl2, attr::type, and attr::u.
Referenced by gui_gtk_init(), navigation_set_route(), navit_init(), and request_route_add_attr().
Adds a traffic distortion item to the route.
| this_ | The route |
| item | The item to add, must be of type_traffic_distortion
|
References route::graph, route_graph_add_traffic_distortion(), route_has_graph(), and route::vehicleprofile.
Referenced by tm_item_update_attrs().
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.
| this | The route to set the destination for |
| dst | Coordinates of the new waypoint |
| async | If 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 | ) |
References attr_iter::iter.
Referenced by NGQProxyRoute::dropIterFunc().
| struct attr_iter* route_attr_iter_new | ( | void | ) |
Referenced by NGQProxyRoute::getIterFunc().
|
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.
| c | Array containing route points, including start, intermediate and destination ones. |
| count | number of route points |
| proifle | vehicleprofile |
References c, coord_rect_extend(), coord_rect::lu, profile, coord_rect::rl, and route_rect_add().
Referenced by route_get_selection(), and route_graph_build().
Changes a traffic distortion item on the route.
Attempting to change an idem which is not in the route graph will add it.
| this_ | The route |
| item | The item to change, must be of type_traffic_distortion
|
References route::graph, route_graph_change_traffic_distortion(), route_has_graph(), and route::vehicleprofile.
Referenced by tm_item_update_attrs().
|
static |
Checks if a segment is part of a roundabout.
This function checks if a segment is part of a roundabout.
| seg | The segment to be checked |
| level | How deep to scan the route graph |
| direction | Set this to 1 if we're entering the segment through its end, to 0 otherwise |
| origin | Used internally, set to NULL |
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 |
References route::destinations, and route_info_free_g().
Referenced by route_destroy(), and route_set_destinations().
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!
| this | The route to check for this item |
| item | The item to search for |
References item_hash_lookup(), item_is_equal, and startup::pos.
Referenced by tracking_is_on_route().
| int route_destination_reached | ( | struct route * | this | ) |
Checks if a route has reached its destination.
| this | The route to be checked |
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().
| void route_destroy | ( | struct route * | this_ | ) |
References route::graph, route::graph_map, route::map, map_destroy(), route::path2, route::pos, route_clear_destinations(), route_graph_destroy(), route_info_free(), and route_path_destroy().
Referenced by navit_destroy(), and request_route_destroy().
Duplicates a route object.
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 |
Returns and removes one segment from a path.
| path | The path to take the segment from |
| item | The item whose segment to remove |
| offset | Offset of the segment within the item to remove. If the item is not segmented this should be 1. |
References AF_SEGMENTED, item_hash_remove(), item_is_equal, route_path_segment::next, offset, route_path::path, and route_path::path_hash.
Referenced by route_path_add_item_from_graph().
|
static |
Finds the nearest street to a given coordinate.
| ms | The mapset to search in for the street |
| pc | The coordinate to find a street nearby |
References c, route_info::c, street_data::c, street_data::count, dbg, street_data::flags, vehicleprofile::flags, vehicleprofile::flags_forward_mask, vehicleprofile::flags_reverse_mask, item::id_hi, item::id_lo, item, item_get_default_flags(), route_info::lp, lvl_debug, map_projection(), map_rect_destroy(), map_rect_get_item(), map_rect_new(), map_selection_destroy(), mapset_close(), mapset_next(), mapset_open(), startup::pos, route_info::pos, pcoord::pro, route_rect(), route_info::street, street_data_free(), street_get_data(), transform_distance_polyline_sq(), transform_from_geo(), transform_to_geo(), item::type, pcoord::x, and pcoord::y.
Referenced by route_append_destination(), route_set_destinations(), and route_set_position_flags().
| void route_free_selection | ( | struct map_selection * | sel | ) |
Destroys a list of map selections.
| sel | Start of the list to be destroyed |
References map_selection::next, and next.
Referenced by route_graph_build_done(), traffic_traff_android_destroy(), and traffic_traff_android_set_selection().
| int route_get_attr | ( | struct route * | this_, |
| enum attr_type | type, | ||
| struct attr * | attr, | ||
| struct attr_iter * | iter | ||
| ) |
References route_info::c, dbg, route::destinations, attr_iter::list, lvl_debug, attr::map, route_path_segment::next, attr::num, route_path::path, route::path2, route::pc, attr::pcoord, pcoord::pro, projection_mg, route_get_dst(), route_get_map(), route::route_status, route_status_path_done_incremental, route_status_path_done_new, attr::type, type, attr::u, attr_iter::u, route::v, attr::vehicle, attr::vehicleprofile, route::vehicleprofile, coord::x, pcoord::x, coord::y, and pcoord::y.
Referenced by NGQProxyRoute::getAttrFunc(), gui_gtk_route_callback(), gui_internal_cmd_pois(), gui_internal_populate_route_table(), map_route_occluded_rect_new(), navigation_set_route(), navigation_update(), pedestrian_draw_arrows(), pedestrian_navit_init(), request_route_get_attr(), and traffic_process_messages_int().
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.
| this_ | The route we're driving upon |
| dist | The distance in meters |
References route_info::c, route_path::in_use, item_hash_new(), route_info::lenextra, route_path::path_hash, startup::pos, route_path_add_line(), and route_path::updated.
| int route_get_destination_count | ( | struct route * | this | ) |
Get the destinations count for the route.
| this | The route instance |
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])
| this | The route instance |
| n | The nth waypoint |
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, attr::type, item::type, and type.
Referenced by navit_get_destination_description(), and navit_vehicle_update_position().
Retrieves destinations from the route.
Prior to calling this method, you may want to retrieve the number of destinations by calling route_get_destination_count(struct route *) and assigning a buffer of sufficient capacity.
If the return value equals count, the buffer was either just large enough or too small to hold the entire list of destinations; there is no way to tell from the result which is the case.
| this | The route instance |
| pc | Pointer to an array of projected coordinates which will receive the destination coordinates |
| count | Capacity of pc |
pc, never greater than count References route_info::c, pcoord::pro, projection_mg, coord::x, pcoord::x, coord::y, and pcoord::y.
Referenced by navit_get_destinations(), navit_set_destination(), navit_vehicle_update_position(), and route_set_profile().
References c, distances, and route_path_get_distances().
Referenced by gui_internal_cmd_pois_item().
| struct route_info* route_get_dst | ( | struct route * | this | ) |
Returns the destination of the route passed.
| this | The route to get the destination for |
Referenced by route_append_destination(), route_get_attr(), 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::graph_map, and route_get_map_helper().
Referenced by navigation_update().
| struct route_graph* route_get_graph | ( | struct route * | this_ | ) |
Retrieves the route graph.
References route::graph.
Returns a new map containing the route graph.
This function returns a new map containing the route graph.
@important Do not map_destroy() this!
| this_ | The route to get the map of |
Referenced by navigation_itm_new(), and navit_init().
Returns a new map containing the route path.
This function returns a new map containing the route path.
@important Do not map_destroy() this!
| this_ | The route to get the map of |
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 |
References attr::attrs, data, description(), attr::map, map_new(), attr::navigation, navit_object_ref(), navigation::route, attr::str, attr::type, type, and attr::u.
Referenced by route_get_flags(), and route_get_map().
Returns the mapset of the route passed.
| this | The route to get the mapset of |
| int route_get_path_set | ( | struct route * | this | ) |
Checks if the path is calculated for the route passed.
| this | The route to check |
Referenced by navit_check_route().
| struct route_info* route_get_pos | ( | struct route * | this | ) |
Returns the current position within the route passed.
| this | The route to get the position for |
References startup::pos.
Referenced by traffic_process_messages_int().
| struct map_selection* route_get_selection | ( | struct route * | this_ | ) |
Retrieves the map selection for the route.
References c, route_info::c, route::destinations, route::pos, route_calc_selection(), and route::vehicleprofile.
Referenced by traffic_process_messages_int(), and traffic_traff_android_set_selection().
|
static |
Returns the traffic distortion for a segment.
If multiple traffic distortions match a segment, the return value will report the lowest speed limit and greatest delay of all matching segments.
| seg | The segment for which the traffic distortion is to be returned |
| dir | The direction of seg for which to return traffic distortions. Positive values indicate travel in the direction of the segment, negative values indicate travel against it. |
| profile | The current vehicle profile |
| ret | Points to a struct route_traffic_distortion
|
References AF_SPEED_LIMIT, route_graph_segment::data, dbg, 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, lvl_warning, route_traffic_distortion::maxspeed, profile, RSD_MAXSPEED, route_graph_point::seg, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, and item::type.
Referenced by route_value_seg().
| struct route_graph_point* route_graph_add_point | ( | struct route_graph * | this, |
| struct coord * | f | ||
| ) |
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.
| this | The route graph to insert the point into |
| f | The coordinates at which the point should be inserted |
References p, route_graph_get_point(), and route_graph_point_new().
Referenced by route_graph_add_street(), route_graph_add_traffic_distortion(), route_graph_add_turn_restriction(), and traffic_location_populate_route_graph().
| 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.
| this | The route graph to insert the segment into |
| start | The graph point which should be connected to the start of this segment |
| end | The graph point which should be connected to the end of this segment |
| data | The segment data |
References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, route_graph_point::c, data, route_graph_segment::data, dbg_assert, debug_route, 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_graph_segment::next, route_segment_data_size(), RSD_MAXSPEED, route_segment_data::score, size, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, coord::x, and coord::y.
Referenced by route_graph_add_street(), route_graph_add_traffic_distortion(), route_graph_add_turn_restriction(), route_graph_clone_segment(), route_graph_set_traffic_distortion(), and traffic_location_populate_route_graph().
|
static |
Adds an item to the route graph.
This adds an item (e.g. a street) to the route graph, creating as many segments as needed for a segmented item.
| this | The route graph to add to |
| item | The item to add |
| profile | The vehicle profile currently in use |
References AF_ALL, AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, c, data, dbg_assert, default_flags, item, item_attr_get(), item_attr_rewind(), item_coord_get(), item_coord_is_node(), item_coord_rewind(), item_get_default_flags(), route_graph_segment_data::len, item::map, map_projection(), attr::num, profile, route_graph_add_point(), route_graph_add_segment(), route_graph_segment_is_duplicate(), transform_distance(), item::type, attr::u, and vehicleprofile_get_roadprofile().
Referenced by route_graph_build_idle().
|
static |
Adds a traffic distortion item to the route graph.
If update is true, the end points of the traffic distortion will have their cost recalculated. Set this to true for a partial recalculation of an existing route, false when initially building the route graph.
| this | The route graph to add to |
| profile | The vehicle profile to use for cost calculations |
| item | The item to add, must be of type_traffic_distortion
|
| update | Whether to update the end points |
References AF_DISTORTIONMASK, AF_ONEWAY, AF_ONEWAYREV, AF_SPEED_LIMIT, c, data, route_graph_point::flags, item, item_attr_get(), item_attr_rewind(), item_coord_get(), item_coord_rewind(), attr::num, profile, route_graph_add_point(), route_graph_add_segment(), route_graph_point_update(), RP_TRAFFIC_DISTORTION, and attr::u.
Referenced by route_add_traffic_distortion(), route_graph_build_idle(), and route_graph_change_traffic_distortion().
| void route_graph_add_turn_restriction | ( | struct route_graph * | this, |
| struct item * | item | ||
| ) |
Adds a turn restriction item to the route graph.
| this | The route graph to add to |
| item | The item to add, must be of type_street_turn_restriction_no or type_street_turn_restriction_only |
References c, data, dbg, route_graph_point::flags, item, item_coord_get(), item_coord_rewind(), item_to_name(), lvl_debug, route_graph_add_point(), route_graph_add_segment(), RP_TURN_RESTRICTION, item::type, pcoord::x, and pcoord::y.
Referenced by route_graph_build_idle(), and traffic_location_populate_route_graph().
|
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.
| ms | The mapset to build the route graph from |
| c | An array of coordinates for the current position, waypoints (if any) and destination |
| count | Number of coordinates in c |
| done_cb | The callback which will be called when graph is complete |
References route_graph::busy, c, callback_cast, callback_new_2, dbg, route_graph::done_cb, event_add_idle(), fh_makekeyheap(), route_graph::h, route_graph::heap, route_graph::idle_cb, route_graph::idle_ev, lvl_debug, mapset_open(), profile, 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().
| void route_graph_build_done | ( | struct route_graph * | rg, |
| int | cancel | ||
| ) |
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.
The traffic module will always call this method with cancel set to true, as it does not process restrictions and has no callback. Inside the routing module, cancel will be true if, and only if, navigation has been aborted.
| rg | Points to the route graph |
| cancel | True 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(), route_graph_destroy(), traffic_location_get_matching_points(), and traffic_location_populate_route_graph().
|
static |
|
static |
References route_graph::h, route_graph::m, map_rect_destroy(), map_rect_new(), mapset_next(), route_graph::mr, and route_graph::sel.
Referenced by route_graph_build(), and route_graph_build_idle().
|
static |
Changes a traffic distortion item in the route graph.
Attempting to change an idem which is not in the route graph will add it.
| this | The route graph to change |
| profile | The vehicle profile to use for cost calculations |
| item | The item to change, must be of type_traffic_distortion
|
References profile, route_graph_add_traffic_distortion(), and route_graph_remove_traffic_distortion().
Referenced by route_change_traffic_distortion().
|
static |
References AF_SEGMENTED, AF_SPEED_LIMIT, route_graph_point::c, data, route_graph_segment::data, dbg, route_segment_data::flags, route_segment_data::item, route_segment_data::len, lvl_debug, route_graph_add_segment(), RSD_MAXSPEED, route_segment_data::score, coord::x, and coord::y.
Referenced by route_graph_process_restriction_segment().
|
static |
Expands (i.e. calculates the costs for) the points on the route graph’s heap.
This calculates the cost for every point on the route graph’s heap, as well as any neighbors affected by the cost change, and sets the next segment.
This is part of a modified LPA* implementation.
| graph | The route graph |
| profile | The vehicle profile to use for routing. This determines which ways are passable and how their costs are calculated. |
| cb | The callback function to call when flooding is complete (can be NULL) |
References callback_call_0, route_graph_segment::data, route_graph_point::el, route_graph_point::end, route_graph_segment::end, route_graph_segment::end_next, fh_extractmin(), route_graph::heap, route_segment_data::item, profile, route_graph_point::rhs, route_graph_is_path_computed(), route_graph_point_update(), route_item_first, route_item_last, route_value_seg(), route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, item::type, and route_graph_point::value.
Referenced by route_graph_update_done(), route_path_new(), route_path_update_done(), route_recalculate_partial(), and route_remove_waypoint().
|
static |
Destroys a route graph.
| this | The route graph to be destroyed |
References fh_deleteheap(), route_graph_build_done(), route_graph_free_points(), and route_graph_free_segments().
Referenced by route_append_destination(), route_destroy(), route_graph_update(), route_path_update_flags(), route_remove_nth_waypoint(), and route_set_destinations().
| void route_graph_free_points | ( | struct route_graph * | this | ) |
Frees all the memory used for points in the route graph passed.
| this | The route graph to delete all points from |
References route_graph_point::hash_next, HASH_SIZE, and next.
Referenced by route_graph_destroy(), and traffic_message_add_segments().
| void route_graph_free_segments | ( | struct route_graph * | this | ) |
Destroys all segments of a route graph.
| this | The graph to destroy all segments from |
References data, next, route_graph_segment::next, route_segment_data_size(), and size.
Referenced by route_graph_destroy(), and traffic_message_add_segments().
| struct route_graph_point* route_graph_get_point | ( | struct route_graph * | this, |
| struct coord * | c | ||
| ) |
Gets the first route_graph_point with the specified coordinates.
| this | The route in which to search |
| c | Coordinates to search for |
References c, and route_graph_get_point_next().
Referenced by route_graph_add_point(), route_graph_remove_traffic_distortion(), and traffic_location_get_matching_points().
|
static |
Gets the last route_graph_point with the specified coordinates.
| this | The route in which to search |
| c | Coordinates to search for |
References c, p, pcoord::x, and pcoord::y.
Referenced by rp_get_item().
| struct route_graph_point* route_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.
| this | The route in which to search |
| c | Coordinates to search for |
| last | The last route graph point returned to iterate over multiple points with the same coordinates, or NULL
|
References c, p, pcoord::x, and pcoord::y.
Referenced by route_graph_get_point(), route_graph_get_segment(), route_graph_set_traffic_distortion(), and traffic_location_get_matching_points().
|
static |
Gets the next route_graph_segment belonging to the specified street.
| graph | The route graph in which to search |
| sd | The street to search for |
| last | The last route graph segment returned to iterate over multiple segments of the same item. If NULL
|
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, route_graph_segment::start, and route_graph_segment::start_next.
Referenced by route_graph_init(), and route_path_new().
|
static |
Initializes potential destination nodes.
This method is normally called after building a fresh route graph, or resetting an existing one. It iterates over all potential destination nodes (i.e. all nodes which are part of the destination’s street) and initializes them: The dst_val and rhs values are set according to their cost to reach the destination.
| this | The route graph to initialize |
| dst | The destination of the route |
| profile | The vehicle profile to use for routing. This determines which ways are passable and how their costs are calculated. |
References route_graph_point::dst_seg, route_graph_point::dst_val, route_graph_point::el, route_graph_segment::end, fh_insertkey(), route_info::percent, profile, route_graph_point::rhs, route_graph_get_segment(), route_value_seg(), route_graph_point::seg, route_graph_segment::start, route_info::street, and route_graph_point::value.
Referenced by route_graph_update_done(), route_path_new(), route_path_update_done(), and route_remove_waypoint().
|
static |
Whether cost (re)calculation of route graph points has reached the start point.
This method serves as the exit criterion for cost calculation in our LPA* implementation. When it returns true, it means that calculation of node cost has proceeded far enough to determine the cost of, and cheapest path from, the start point.
The current implementation returns true only when the heap is empty, i.e. all points have been calculated. This is not optimal in terms of efficiency, as the cost of the start point and the cheapest path from there no longer change during the last few cycles. Future versions may report true before the heap is completely empty, as soon as the cost of the start point and the cheapest path are final. However, this needs to be considered for recalculations which happen when the vehicle leaves the cheapest path: right now, any point in the route graph has its final cost and cheapest path, thus no recalculation is needed if the vehicle leaves the cheapest path. In the future, however, a (partial) recalculation may be needed if the vehicle deviates from the cheapest path.
| this_ | The route graph |
References fh_min(), and route_graph::heap.
Referenced by route_graph_compute_shortest_path(), and route_recalculate_partial().
|
static |
References route_map_new_helper().
Referenced by route_init().
|
static |
Create a new point for the route graph with the specified coordinates.
| this | The route to insert the point into |
| f | The coordinates at which the point should be created |
References debug_route, p, coord::x, and coord::y.
Referenced by route_graph_add_point(), and route_graph_process_restriction_segment().
|
static |
Updates the lookahead value of a point in the route graph and updates its heap membership.
This recalculates the lookahead value (the rhs member) of point p, based on the value of each neighbor and the cost to reach that neighbor. If the resulting p->rhs differs from p->value, p is inserted into heap using the lower of the two as its key (if p is already a member of heap, its key is changed accordingly). If the resulting p->rhs is equal to p->value and p is a member of heap, it is removed.
This is part of a modified LPA* implementation.
| profile | The vehicle profile to use for routing. This determines which ways are passable and how their costs are calculated. |
| p | The point to evaluate |
| heap | The heap |
References route_graph_segment::data, route_graph_segment::end, route_graph_segment::end_next, fh_delete(), fh_insertkey(), route_segment_data::item, item_is_equal, p, profile, route_value_add(), route_value_seg(), route_graph_point::seg, route_graph_segment::start, route_graph_segment::start_next, and route_graph_point::value.
Referenced by route_graph_add_traffic_distortion(), route_graph_compute_shortest_path(), and route_graph_remove_traffic_distortion().
|
static |
|
static |
References AF_ONEWAY, AF_ONEWAYREV, c, route_graph_point::c, route_graph_segment::data, dbg, route_graph_segment::end, route_graph_segment::end_next, route_segment_data::flags, is_turn_allowed(), route_segment_data::item, item_to_name(), lvl_debug, p, route_graph_clone_segment(), route_graph_point_new(), route_graph_segment::start, route_graph_segment::start_next, item::type, coord::x, pcoord::x, coord::y, and pcoord::y.
Referenced by route_graph_process_restriction_point().
|
static |
References dbg, route_graph_point::flags, route_graph_point::hash_next, HASH_SIZE, lvl_debug, route_graph_process_restriction_point(), and RP_TURN_RESTRICTION.
Referenced by route_graph_build_done().
|
static |
Removes a traffic distortion item from the route graph.
Removing a traffic distortion which is not in the graph is a no-op.
| this | The route graph to remove from |
| profile | The vehicle profile to use for cost calculations |
| item | The item to remove, must be of type_traffic_distortion
|
References c, data, route_graph_segment::data, route_graph_point::end, route_graph_segment::end, route_graph_segment::end_next, route_graph_point::flags, route_segment_data::item, item_coord_get(), item_coord_rewind(), item_is_equal, route_graph_segment::next, profile, route_graph_get_point(), route_graph_point_update(), route_segment_data_size(), RP_TRAFFIC_DISTORTION, size, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, and item::type.
Referenced by route_graph_change_traffic_distortion(), and route_remove_traffic_distortion().
|
static |
Resets all nodes.
This iterates through all the points in the route graph, resetting them to their initial state. The value (cost to reach the destination via seg) and dst_val (cost to destination if this point is the last in the route) members of each point are reset toINT_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.
The Fibonacci heap is also cleared. Inconsistencies between el and Fibonacci heap membership are handled gracefully, i.e. el is reset even if it is invalid, and points are removed from the heap regardless of their el value.
After this method returns, the caller should call route_graph_init(struct route_graph *, struct route_info *, struct vehicleprofile *) to initialize potential end points. After that a route can be calculated.
References to elements of the route graph which were obtained prior to calling this function remain valid after it returns.
| this | The route graph to reset |
References route_graph_point::dst_seg, route_graph_point::dst_val, route_graph_point::el, fh_extractmin(), route_graph_point::hash_next, HASH_SIZE, route_graph_point::rhs, route_graph_point::seg, and route_graph_point::value.
Referenced by route_path_new(), route_path_update_done(), and route_remove_waypoint().
| 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.
This function compares the item IDs of both segments. If the item is segmented, the segment offset is also compared.
| start | The starting point of the segment |
| data | The data for the segment |
References AF_SEGMENTED, data, route_graph_segment::data, route_segment_data::item, item_is_equal, route_graph_point::start, route_graph_segment::start, and route_graph_segment::start_next.
Referenced by route_graph_add_street(), and traffic_location_populate_route_graph().
|
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.
| s1 | The first segment |
| s2 | The second segment |
References route_graph_point::c, route_graph_segment::end, s1, route_graph_segment::start, coord::x, and coord::y.
Referenced by route_graph_set_traffic_distortion(), and route_path_new().
|
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.
| this | The route graph |
| seg | The segment to which the traffic distortion applies |
| delay | Delay in tenths of a second, or 0 to clear an existing traffic distortion |
References AF_DISTORTIONMASK, route_graph_point::c, data, route_graph_segment::data, route_graph_segment::end, route_graph_point::flags, route_segment_data::flags, item, route_segment_data::item, route_graph_add_segment(), route_graph_get_point_next(), route_graph_segment_match(), RP_TRAFFIC_DISTORTION, route_graph_point::start, route_graph_segment::start, route_graph_segment::start_next, and item::type.
Referenced by route_path_new().
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().
| this | The route to update the graph for |
| cb | The callback function to call when the route graph update is complete (used only in asynchronous mode) |
| async | Set to nonzero in order to update the route graph asynchronously |
References c, route_info::c, callback_cast, callback_destroy(), callback_new_2, startup::pos, route_graph_build(), route_graph_build_idle(), route_graph_destroy(), route_graph_update_done(), route_set_attr(), and route_status_building_graph.
Referenced by route_path_update_flags().
References route_graph_compute_shortest_path(), and route_graph_init().
Referenced by route_graph_update().
| int route_has_graph | ( | struct route * | this_ | ) |
Whether the route has a valid graph.
References route::graph.
Referenced by navigation_update_idle(), route_add_traffic_distortion(), route_change_traffic_distortion(), route_recalculate_partial(), and route_remove_traffic_distortion().
|
static |
This will calculate all the distances stored in a route_info.
| ri | The route_info to calculate the distances for |
| pro | The projection used for this route |
References route_info::c, street_data::c, street_data::count, route_info::lenextra, route_info::lenneg, route_info::lenpos, route_info::lp, route_info::percent, route_info::pos, route_info::street, transform_distance(), and transform_polyline_length().
Referenced by route_append_destination(), route_set_destinations(), route_set_position_flags(), and route_set_position_from_tracking().
| void route_info_free | ( | struct route_info * | inf | ) |
Destroys a route_info.
| info | The route info to be destroyed |
References route_info::street, and street_data_free().
Referenced by route_destroy(), route_info_free_g(), route_remove_nth_waypoint(), route_remove_waypoint(), route_set_position_flags(), and route_set_position_from_tracking().
|
static |
References route_info_free().
Referenced by route_clear_destinations().
| struct street_data* route_info_street | ( | struct route_info * | rinf | ) |
Returns street data for a route info.
| rinf | The route info to return the street data for |
References route_info::street.
| void route_init | ( | void | ) |
References route_graph_map_new(), and route_map_new().
Referenced by main_real().
|
static |
References route_map_new_helper().
Referenced by route_init().
|
static |
References attr_search(), attr::attrs, attr::route, map_priv::route, route_graph_meth, route_meth, and attr::u.
Referenced by route_graph_map_new(), and route_map_new().
Creates a completely new route structure.
| attrs | Not used |
References attr_generic_get_attr(), attr::attrs, callback_list_new(), navit_object_ref(), attr::num, route_func, and attr::u.
|
static |
Referenced by route_destination_reached().
|
static |
Inserts a new segment into the path.
This function adds a new segment to the route path. The segment is copied from the route graph. If rgs is part of a segmented item, only rgs will be added to the route path, not the other segments.
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.
| this | The path to add the item to |
| oldpath | Old path containing the segment to be added. Speeds up the function, but can be NULL. |
| rgs | Segment of the route graph that should be "copied" to the route path |
| dir | Order in which to add the coordinates. See route_path_add_item() |
| pos | Information about start point if this is the first segment |
| dst | Information about end point if this is the last segment |
References AF_ROUNDABOUT, AF_SEGMENTED, c, route_path_segment::c, street_data::c, route_graph_point::c, street_data::count, route_path_segment::data, route_graph_segment::data, dbg, route_path_segment::direction, route_graph_segment::end, route_segment_data::flags, item::id_hi, item::id_lo, route_segment_data::item, item_coord_get_within_range(), 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, startup::pos, 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, coord::y, and pcoord::y.
Referenced by route_path_new().
|
static |
Adds a two coordinate line to a path.
This adds a new line to a path, creating a new segment for it.
| this | The path to add the item to |
| start | coordinate to add to the start of the item. If none should be added, make this NULL. |
| end | coordinate to add to the end of the item. If none should be added, make this NULL. |
| len | The 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_get_coord_dist(), and route_path_new().
|
static |
Adds a segment and the end of a path.
| this | The path to add the segment to |
| segment | The segment to add |
References route_path_segment::next.
Referenced by route_path_add_item_from_graph(), and route_path_add_line().
|
static |
Destroys a route_path.
| this | The route_path to be destroyed |
References c, route_path::in_use, item_hash_destroy(), next, route_path::path, and route_path::path_hash.
Referenced by route_destroy(), route_path_update_done(), route_path_update_flags(), and route_remove_waypoint().
|
static |
References c, route_path_segment::c, distances, route_path_segment::ncoords, route_path_segment::next, route_path::next, route_path::path, and transform_distance_polyline_sq().
Referenced by route_get_distances().
|
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.
| this | The 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. |
| pos | The starting position of the route |
| dst | The destination of the route |
| preferences | The routing preferences |
References 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, map_projection(), route_path::path_hash, startup::pos, profile, route_graph_compute_shortest_path(), route_graph_get_segment(), route_graph_init(), 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, transform_distance(), route_path::updated, and route_graph_point::value.
Referenced by route_path_update_done().
|
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.
| this | Not used |
| pos | The starting position for the new path |
| dst | The destination of the new path |
| dir | Not used |
Referenced by route_path_new().
|
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).
| this | The route to update |
| cancel | If true, cancel navigation, clear route graph and route path |
| async | If 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 |
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.
| this | The route object |
| new_graph | FIXME 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, startup::pos, route_graph_compute_shortest_path(), route_graph_init(), 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, and route_time_seg().
Referenced by rm_rect_destroy(), route_path_update_flags(), and route_recalculate_partial().
|
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.
| this | The route to update |
| flags | Flags 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 |
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
member of the route. Failing that, the current position of the route is returned.
| this | The route object |
References startup::pos.
Referenced by route_path_update_done().
|
static |
Returns the projection used for this route.
| route | The route to return the projection for |
Referenced by route_destination_reached().
| void route_recalculate_partial | ( | struct route * | this_ | ) |
Triggers partial recalculation of the route, based on the existing route graph.
This is currently used when traffic distortions have been added, changed or removed. Future versions may also use it if the current position has changed to a portion of the route graph which has not been flooded (which is currently not necessary because the route graph is always flooded completely).
This tends to be faster than full recalculation, as only a subset of all points in the graph needs to be evaluated.
If segment costs have changed (as is the case with traffic distortions), all affected segments must have been added to, removed from or updated in the route graph before this method is called.
After recalculation, the route path is updated.
The function uses a modified LPA* algorithm for recalculations. Most modifications were made for compatibility with the old routing algorithm:
| this_ | The route |
References route_graph::busy, route::graph, route_graph_compute_shortest_path(), route_graph_is_path_computed(), route_has_graph(), route_path_update_done(), route_set_attr(), route_status_building_graph, attr::type, and route::vehicleprofile.
Referenced by traffic_process_messages_int().
| struct map_selection* route_rect | ( | int | order, |
| struct coord * | c1, | ||
| struct coord * | c2, | ||
| int | rel, | ||
| int | abs | ||
| ) |
Returns a single map selection.
The boundaries of the selection are determined as follows: First a rectangle spanning c1 and c2 is built (the two coordinates can be any two opposite corners of the rectangle). Then its maximum extension (height or width) is determined and multiplied with the percentage specified by rel. The resulting amount of padding is added to each edge. After that, the amount specified by abs is added to each edge.
| order | Map order (deepest tile level) to select |
| c1 | First coordinate |
| c2 | Second coordinate |
| rel | Relative padding to add to the selection rectangle, in percent |
| abs | Absolute padding to add to the selection rectangle |
References c1, c2, map_selection::c_rect, dbg, coord_rect::lu, lvl_debug, item_range::max, map_selection::next, map_selection::order, map_selection::range, coord_rect::rl, route_item_first, route_item_last, map_selection::u, coord::x, and coord::y.
Referenced by route_find_nearest_street(), route_rect_add(), tracking_doupdate_lines(), and traffic_location_get_rect().
|
static |
Appends a map selection to the selection list. Selection list may be NULL.
References c1, c2, map_selection::next, map_selection::order, and route_rect().
Referenced by route_calc_selection().
References attr::callback, callback_list_remove(), route::cbl2, dbg, lvl_debug, attr::type, attr::u, and route::v.
Referenced by navigation_set_route(), and request_route_remove_attr().
| void route_remove_nth_waypoint | ( | struct route * | this, |
| int | n | ||
| ) |
Remove the nth waypoint of the route.
| this | The route instance |
| n | The waypoint to remove |
References route_get_dst(), route_graph_destroy(), route_info_free(), and route_path_update().
Referenced by navit_remove_nth_waypoint().
Removes a traffic distortion item from the route.
Removing a traffic distortion which is not in the route graph is a no-op.
| this_ | The route |
| item | The item to remove, must be of type_traffic_distortion
|
References route::graph, route_graph_remove_traffic_distortion(), route_has_graph(), and route::vehicleprofile.
Referenced by tm_item_unref().
| void route_remove_waypoint | ( | struct route * | this | ) |
|
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:
| profile | The routing preferences |
| over | The segment which is passed |
| dist | A traffic distortion if applicable, or NULL
|
References AF_DANGEROUS_GOODS, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, size_weight_limit::axle_weight, route_segment_data::flags, size_weight_limit::height, route_segment_data::item, size_weight_limit::length, roadprofile::maxspeed, route_traffic_distortion::maxspeed, maxspeed_enforce, maxspeed_ignore, maxspeed_restrict, profile, roadprofile::route_weight, RSD_MAXSPEED, roadprofile::speed, item::type, vehicleprofile_get_roadprofile(), size_weight_limit::weight, and size_weight_limit::width.
Referenced by rm_attr_get(), route_time_seg(), and rp_attr_get().
| 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.
This function returns a pointer to a field that is appended to a route graph segment.
| seg | The route graph segment the field is appended to |
| type | Type of the field that should be returned |
References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, AF_SPEED_LIMIT, route_segment_data::flags, route_graph_point::seg, and type.
|
static |
Calculates the size of a route_segment_data struct with given flags.
| flags | The flags of the route_segment_data |
References AF_DANGEROUS_GOODS, AF_SEGMENTED, AF_SIZE_OR_WEIGHT_LIMIT, and AF_SPEED_LIMIT.
Referenced by route_graph_add_segment(), route_graph_free_segments(), route_graph_remove_traffic_distortion(), and route_path_add_item_from_graph().
References attr_to_name(), c, callback_list_call_attr_2, route::cbl2, attr::coord_geo, dbg, lvl_error, attr::num, attr::pcoord, pcoord::pro, projection_mg, route_path_flag_async, route_path_flag_no_rebuild, route_set_destination(), route_set_position(), route_set_position_flags(), route::route_status, transform_from_geo(), attr::type, attr::u, route::v, attr::vehicle, vehicle_get_attr(), pcoord::x, and pcoord::y.
Referenced by request_route_set_attr(), route_graph_update(), route_path_update_done(), route_recalculate_partial(), route_set_destinations(), and NGQProxyRoute::setAttrFunc().
Start a route given set of coordinates.
| this | The route instance |
| dst | The coordinate to start routing to |
| async | Set to 1 to do route calculation asynchronously |
References route_set_destinations().
Referenced by navit_add_former_destinations_from_file(), navit_set_destination(), and route_set_attr().
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.
| this | The route to set the destination for |
| dst | Points 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) |
| count | Number of items in dst
|
| async | If set, do routing asynchronously |
References callback_list_call_attr_1, 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, and route_status_no_destination.
Referenced by NGQProxyRoute::addDestination(), navit_add_former_destinations_from_file(), navit_set_destinations(), route_append_destination(), route_set_destination(), and route_set_profile().
Sets the mapset of the route passwd.
| this | The route to set the mapset for |
| ms | The mapset to set for this route |
Referenced by navit_init().
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.
| this | The route to set the position of |
| pos | Coordinates to set as position |
References startup::pos, route_path_flag_async, and route_set_position_flags().
Referenced by navit_set_position(), navit_vehicle_update_position(), and route_set_attr().
|
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.
| this | The route to set the position of |
| pos | Coordinates to set as position |
| flags | Flags to use for building the graph |
References dbg, lvl_debug, startup::pos, 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 | ||
| ) |
Sets a route's current position based on coordinates from tracking.
| this | The route to set the current position of |
| tracking | The tracking to get the coordinates from |
References c, route_info::c, street_data::c, street_data::count, dbg, item::id_hi, item::id_lo, street_data::item, route_info::lenneg, route_info::lenpos, route_info::lp, lvl_debug, lvl_info, startup::pos, route_info::pos, route_info_distances(), route_info_free(), route_path_update(), route_info::street, street_data_dup(), route_info::street_direction, tracking_get_pos(), tracking_get_segment_pos(), tracking_get_street_data(), tracking_get_street_direction(), coord::x, pcoord::x, coord::y, and pcoord::y.
Referenced by navit_vehicle_update_position().
| void route_set_profile | ( | struct route * | this, |
| struct vehicleprofile * | prof | ||
| ) |
Sets the vehicle profile of a route.
| this | The route to set the profile for |
| prof | The 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 |
References AF_THROUGH_TRAFFIC_LIMIT, route_graph_segment::data, and route_segment_data::flags.
Referenced by route_value_seg().
|
static |
Returns the time needed to travel along a segment, or.
if the segment is impassable.
This function returns the time needed to travel along the entire length of
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
argument is given.
| profile | The vehicle profile (routing preferences) |
| over | The segment which is passed |
| dist | A traffic distortion if applicable, or NULL
|
References route_traffic_distortion::delay, route_segment_data::len, profile, and route_seg_speed().
Referenced by rm_attr_get(), route_path_update_done(), route_value_seg(), and rp_attr_get().
|
static |
Adds two route values with protection against integer overflows.
Unlike regular addition, this function is safe to use if one of the two arguments is INT_MAX (which Navit uses to express that a segment cannot be traversed or a point cannot be reached): If any of the two arguments is INT_MAX, then INT_MAX is returned; else the sum of the two arguments is returned.
Note that this currently does not cover cases in which both arguments are less than INT_MAX but add up to val1 + val2 >= INT_MAX. With Navit’s internal cost definition, INT_MAX (2^31) is equivalent to approximately 7 years, making this unlikely to become a real issue.
Referenced by route_graph_point_update().
|
static |
Returns the "cost" of traveling 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.
If from is specified, it must be the point at which we leave the segment (over->end if dir is positive, over->start if dir is negative); anything else will produce invalid results. If from is non-NULL, additional checks are done on from->seg (the next segment to follow after over):
from->seg equals over (indicating that, after traversing over in direction dir, we would immediately traverse it again in the opposite direction), INT_MAX is returned. over loops back to itself (i.e. its start and end members are equal), INT_MAX is returned. over does not allow through traffic but from->seg does, the through traffic penalty of the vehicle profile (profile) is applied.| profile | The routing preferences |
| from | The point currently being visited (or NULL), see description |
| over | The segment we are using |
| dir | The direction of segment which we are traveling. Positive values indicate we are traveling in the direction of the segment (from over->start to over->end), negative values indicate we are traveling in the opposite direction. Values of +2 or -2 cause the function to ignore traffic distortions. |
References route_graph_segment::data, dbg, route_graph_segment::end, route_graph_point::flags, route_segment_data::flags, route_segment_data::item, lvl_warning, profile, route_get_traffic_distortion(), route_through_traffic_allowed(), route_time_seg(), RP_TRAFFIC_DISTORTION, RP_TURN_RESTRICTION, route_graph_point::seg, route_graph_segment::start, and item::type.
Referenced by route_graph_compute_shortest_path(), route_graph_init(), route_graph_point_update(), and route_path_new().
References AF_SPEED_LIMIT, map_rect_priv::attr_next, attr_to_name(), map_rect_priv::coord_sel, route_graph_segment::data, dbg, route_graph_segment::end, route_graph_segment::end_next, route_segment_data::flags, attr::item, map_rect_priv::item, route_segment_data::item, route_segment_data::len, lvl_debug, item::map, map_rect_priv::mpriv, attr::num, p, map_rect_priv::point, map_priv::route, route_seg_speed(), route_time_seg(), RSD_MAXSPEED, map_rect_priv::rseg, route_graph_segment::start, route_graph_segment::start_next, attr::str, map_rect_priv::str, attr::type, item::type, attr::u, and route::vehicleprofile.
|
static |
References map_rect_priv::attr_next.
Referenced by rp_get_item().
|
static |
Returns the coordinates of a route graph item.
| priv_data | The route graph item's private data |
| c | Pointer where to store the coordinates |
| count | How many coordinates to get at a max? |
|
static |
|
static |
References map_rect_priv::coord_sel, route::graph, route_graph::hash, map_rect_priv::hash_bucket, HASH_SIZE, item::id_lo, map_rect_priv::it, map_rect_priv::item, map_rect_priv::mpriv, route_graph_segment::next, p, map_rect_priv::point, rm_coord_rewind(), map_priv::route, route_graph_get_point_last(), route_graph::route_segments, rp_attr_rewind(), rp_iterator_new(), rp_iterator_next(), map_rect_priv::rseg, and item::type.
Referenced by rp_get_item_byid().
|
static |
References item::id_lo, and rp_get_item().
|
static |
Checks if the last segment returned from a route_graph_point_iterator comes from the end.
| it | The route graph point iterator to be checked |
References route_graph_point_iterator::end, route_graph_point::end, route_graph_point_iterator::next, and route_graph_point_iterator::p.
Referenced by route_check_roundabout().
|
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.
| p | The route graph point to create the iterator from |
Referenced by route_check_roundabout(), and rp_get_item().
|
static |
Gets the next segment connected to a route graph point from an iterator.
| it | The route graph point iterator to get the segment from |
References route_graph_point_iterator::end, route_graph_point::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 |
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.
| priv | The route graph map's private data |
| sel | Here it's possible to specify a point for which to search. Please read the function's description. |
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, map_rect_priv::sel, item::type, map_selection::u, coord::x, and coord::y.
| struct street_data* street_data_dup | ( | struct street_data * | orig | ) |
Copies street data.
| orig | The street data to copy |
References street_data::count, and size.
Referenced by route_set_position_from_tracking().
| void street_data_free | ( | struct street_data * | sd | ) |
Frees street data.
| sd | Street data to be freed |
Referenced by NGQPoint::_coordName(), item_get_heightline(), map_route_occluded_buildings_free(), map_route_occluded_get_item(), map_route_occluded_rect_destroy(), route_find_nearest_street(), route_info_free(), tracking_doupdate_lines(), and tracking_flush().
| struct street_data* street_get_data | ( | struct item * | item | ) |
Gets street data for an item.
| item | The item to get the data for |
References AF_SPEED_LIMIT, c, street_data::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().
| int debug_route =0 |
Referenced by route_graph_add_segment(), and route_graph_point_new().
|
static |
Referenced by rp_rect_new().
|
static |
Referenced by rm_rect_new().
| struct object_func route_func |
Referenced by object_func_lookup(), route_dup(), and route_new().
|
static |
Referenced by route_map_new_helper().
|
static |
Referenced by route_map_new_helper().
| struct map_selection* route_selection |
1.9.1