"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "navit/route.c" between
navit-0.5.5.tar.gz and navit-0.5.6.tar.gz

About: NavIt is a car navigation system with GPS tracking and a routing engine.

route.c  (navit-0.5.5)	:	route.c  (navit-0.5.6)
skipping to change at line 938		skipping to change at line 938
if (this->destinations)		if (this->destinations)
route_path_update(this, 0, 1);		route_path_update(this, 0, 1);
dbg(lvl_info,"ret");		dbg(lvl_info,"ret");
}		}
/* Used for debuging of route_rect, what routing sees */		/* Used for debuging of route_rect, what routing sees */
struct map_selection *route_selection;		struct map_selection *route_selection;
/**		/**
* @brief Returns a single map selection		* @brief 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.
		*
		* @param order Map order (deepest tile level) to select
		* @param c1 First coordinate
		* @param c2 Second coordinate
		* @param rel Relative padding to add to the selection rectangle, in percent
		* @param abs Absolute padding to add to the selection rectangle
*/		*/
struct map_selection *		struct map_selection *
route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs) {		route_rect(int order, struct coord *c1, struct coord *c2, int rel, int abs) {
int dx,dy,sx=1,sy=1,d,m;		int dx,dy,sx=1,sy=1,d,m;
struct map_selection *sel=g_new(struct map_selection, 1);		struct map_selection *sel=g_new(struct map_selection, 1);
if (!sel) {		if (!sel) {
printf("%s:Out of memory\n", __FUNCTION__);		printf("%s:Out of memory\n", __FUNCTION__);
return sel;		return sel;
}		}
sel->order=order;		sel->order=order;
skipping to change at line 1046		skipping to change at line 1057
}		}
/**		/**
* @brief Retrieves the map selection for the route.		* @brief Retrieves the map selection for the route.
*/		*/
struct map_selection * route_get_selection(struct route * this_) {		struct map_selection * route_get_selection(struct route * this_) {
struct coord *c = g_alloca(sizeof(struct coord) * (1 + g_list_length(this_-> destinations)));		struct coord *c = g_alloca(sizeof(struct coord) * (1 + g_list_length(this_-> destinations)));
int i = 0;		int i = 0;
GList *tmp;		GList *tmp;
c[i++] = this_->pos->c;		if (this_->pos)
		c[i++] = this_->pos->c;
tmp = this_->destinations;		tmp = this_->destinations;
while (tmp) {		while (tmp) {
struct route_info *dst = tmp->data;		struct route_info *dst = tmp->data;
c[i++] = dst->c;		c[i++] = dst->c;
tmp = g_list_next(tmp);		tmp = g_list_next(tmp);
}		}
return route_calc_selection(c, i, this_->vehicleprofile);		return route_calc_selection(c, i, this_->vehicleprofile);
}		}
/**		/**
* @brief Destroys a list of map selections		* @brief Destroys a list of map selections
*		*
* @param sel Start of the list to be destroyed		* @param sel Start of the list to be destroyed
*/		*/
static void route_free_selection(struct map_selection *sel) {		void route_free_selection(struct map_selection *sel) {
struct map_selection *next;		struct map_selection *next;
while (sel) {		while (sel) {
next=sel->next;		next=sel->next;
g_free(sel);		g_free(sel);
sel=next;		sel=next;
}		}
}		}
/* for compatibility to GFunc */		/* for compatibility to GFunc */
static void route_info_free_g(struct route_info *inf, void * unused) {		static void route_info_free_g(struct route_info *inf, void * unused) {
skipping to change at line 1127		skipping to change at line 1139
profile(1,"find_nearest_street");		profile(1,"find_nearest_street");
/* The graph has to be destroyed and set to NULL, otherwise route_path_updat e() doesn't work */		/* The graph has to be destroyed and set to NULL, otherwise route_path_updat e() doesn't work */
route_graph_destroy(this->graph);		route_graph_destroy(this->graph);
this->graph=NULL;		this->graph=NULL;
this->current_dst=route_get_dst(this);		this->current_dst=route_get_dst(this);
route_path_update(this, 1, async);		route_path_update(this, 1, async);
profile(0,"end");		profile(0,"end");
}		}
		/**
		* @brief Retrieves destinations from the route
		*
		* Prior to calling this method, you may want to retrieve the number of destinat
		ions by calling
		* {@link 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 o
		r too small to hold the
		* entire list of destinations; there is no way to tell from the result which is
		the case.
		*
		* @param this The route instance
		* @param pc Pointer to an array of projected coordinates which will receive the
		destination coordinates
		* @param count Capacity of `pc`
		* @return The number of destinations stored in `pc`, never greater than `count`
		*/
int route_get_destinations(struct route *this, struct pcoord *pc, int count) {		int route_get_destinations(struct route *this, struct pcoord *pc, int count) {
int ret=0;		int ret=0;
GList *l=this->destinations;		GList *l=this->destinations;
while (l && ret < count) {		while (l && ret < count) {
struct route_info *dst=l->data;		struct route_info *dst=l->data;
pc->x=dst->c.x;		pc->x=dst->c.x;
pc->y=dst->c.y;		pc->y=dst->c.y;
pc->pro=projection_mg; /* FIXME */		pc->pro=projection_mg; /* FIXME */
pc++;		pc++;
ret++;		ret++;
skipping to change at line 2269		skipping to change at line 2295
}		}
}		}
s=s->start_next;		s=s->start_next;
}		}
}		}
}		}
/**		/**
* @brief Adds a traffic distortion item to the route graph		* @brief 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 buildi
		ng the route graph.
		*
* @param this The route graph to add to		* @param this The route graph to add to
* @param profile The vehicle profile to use for cost calculations		* @param profile The vehicle profile to use for cost calculations
* @param item The item to add, must be of {@code type_traffic_distortion}		* @param item The item to add, must be of {@code type_traffic_distortion}
* @param update Whether to update the point (true for LPA*, false for Dijkstra)		* @param update Whether to update the end points
*/		*/
static void route_graph_add_traffic_distortion(struct route_graph *this, struct vehicleprofile *profile,		static void route_graph_add_traffic_distortion(struct route_graph *this, struct vehicleprofile *profile,
struct item *item, int update) {		struct item *item, int update) {
struct route_graph_point *s_pnt,*e_pnt;		struct route_graph_point *s_pnt,*e_pnt;
struct coord c,l;		struct coord c,l;
struct attr flags_attr, delay_attr, maxspeed_attr;		struct attr flags_attr, delay_attr, maxspeed_attr;
struct route_graph_segment_data data;		struct route_graph_segment_data data;
data.item=item;		data.item=item;
data.len=0;		data.len=0;
skipping to change at line 2669		skipping to change at line 2698
* currently not necessary because the route graph is always flooded completely) .		* 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 poin ts in the graph needs to be evaluated.		* This tends to be faster than full recalculation, as only a subset of all poin ts 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		* 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.		* to, removed from or updated in the route graph before this method is called.
*		*
* After recalculation, the route path is updated.		* After recalculation, the route path is updated.
*		*
* The function uses a modified LPA* algorithm for recalculations. Most modifica tions were made for compatibility with		* The function uses a modified LPA* algorithm for recalculations. Most modifica tions were made for compatibility with
* the algorithm used for the initial routing:		* the old routing algorithm:
* \li The `value` of a node represents the cost to reach the destination and th		* \li The heuristic is always assumed to be zero (which would turn A* into Dijk
us decreases along the route		stra, formerly the basis of the routing
* (eliminating the need for recalculations as the vehicle moves within the rout
e graph)
* \li The heuristic is always assumed to be zero (which would turn A* into Dijk
stra, the basis of the main routing
* algorithm, and makes our keys one-dimensional)		* algorithm, and makes our keys one-dimensional)
* \li Currently, each pass evaluates all locally inconsistent points, leaving a n empty heap at the end (though this		* \li Currently, each pass evaluates all locally inconsistent points, leaving a n empty heap at the end (though this
* may change in the future).		* may change in the future).
*		*
* @param this_ The route		* @param this_ The route
*/		*/
/* TODO This is absolutely not thread-safe and will wreak havoc if run concurren tly with route_graph_flood(). This is		/* TODO This is absolutely not thread-safe and will wreak havoc if run concurren tly with route_graph_flood(). This is
* not an issue as long as the two never overlap: Currently both this function a nd route_graph_flood() run without		* not an issue as long as the two never overlap: Currently both this function a nd route_graph_flood() run without
* interruption until they finish, and are both on the main thread. If that chan ges, we need to revisit this. */		* interruption until they finish, and are both on the main thread. If that chan ges, we need to revisit this. */
void route_recalculate_partial(struct route *this_) {		void route_recalculate_partial(struct route *this_) {
skipping to change at line 3151		skipping to change at line 3178
}		}
}		}
/**		/**
* @brief Builds a new route graph from a mapset		* @brief Builds a new route graph from a mapset
*		*
* This function builds a new route graph from a map. Please note that this func tion does not		* This function builds a new route graph from a map. Please note that this func tion does not
* add any routing information to the route graph - this has to be done via the route_graph_flood()		* add any routing information to the route graph - this has to be done via the route_graph_flood()
* function.		* function.
*		*
* The function does not create a graph covering the whole map, but only coverin
g the rectangle
* between c1 and c2.
*
* @param ms The mapset to build the route graph from		* @param ms The mapset to build the route graph from
* @param c The coordinates of the destination or next waypoint		* @param c An array of coordinates for the current position, waypoints (if any)
* @param c1 Corner 1 of the rectangle to use from the map		and destination
* @param c2 Corner 2 of the rectangle to use from the map		* @param count Number of coordinates in `c`
* @param done_cb The callback which will be called when graph is complete		* @param done_cb The callback which will be called when graph is complete
* @return The new route graph.		* @return The new route graph.
*/		*/
// FIXME documentation does not match argument list
static struct route_graph *route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb,		static struct route_graph *route_graph_build(struct mapset *ms, struct coord *c, int count, struct callback *done_cb,
int async,		int async,
struct vehicleprofile *profile) {		struct vehicleprofile *profile) {
struct route_graph *ret=g_new0(struct route_graph, 1);		struct route_graph *ret=g_new0(struct route_graph, 1);
dbg(lvl_debug,"enter");		dbg(lvl_debug,"enter");
ret->sel=route_calc_selection(c, count, profile);		ret->sel=route_calc_selection(c, count, profile);
ret->h=mapset_open(ms);		ret->h=mapset_open(ms);
ret->done_cb=done_cb;		ret->done_cb=done_cb;
End of changes. 10 change blocks.
18 lines changed or deleted		49 lines changed or added

---