path_simplifier.h File Reference

#include "pathqueue.h"

Include dependency graph for path_simplifier.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	_Line
struct	_PathPoint
Typedefs
typedef struct _Line	Line
typedef struct _PathPoint	PathPoint
Functions
int	path_simplifier (double *path, int nbpoints, PathPoint *first_point, double *angle)
void	freePathMemory (PathPoint *simple_path)

---

Detailed Description

Header file of path_simplifier.c

Author:

Jose Maria Martin Laguna <jmmartin@etud.insa-toulouse.fr>

Definition in file path_simplifier.h.

---

Typedef Documentation

typedef struct _Line Line

Definition of line parameters. See details. line : a1 * x + a2 * y = b

typedef struct _PathPoint PathPoint

Implementation of a list of points

---

Function Documentation

int path_simplifier	(	double *	path,
		int	nbpoints,
		PathPoint *	first_point,
		double *	angle
	)

Simplify a given path

Parameters:

	path	A pointer to a list of points of the original path
	nbpoints	Number of points of the original path
	first_point	[out] A pointer to the list of points of simplest path
	angle	[out] Angle of the last line

Returns:

Number of point of the simplest path

This is an algorithm who tries to simplify the path given by A* Algorithm (

See also:

aalgorithm()). Basically, the algorithm works that follows: # Takes two points of the original path. # Calculates the line between them. # Calculates the distance between this line and all the points of the original path. If this distance is acceptable (less than PATH_ERROR), the line is part of the simply path. If not, goes to 1 taking two closer points . # The process finish when the last point is the final point.

In pseudo-code:

 first_index = 0;
 last_index = nbpoints;
 step = (last_index - first_index)/2
 WHILE (the first index less than nbpoints )
        Calc the line
        FOR all the points between path[first_index] and path[last_index]
                calc the distance betwen the point and the line
                Take the max_error
        END FOR
        IF max_error less than ACCEPTABLE_ERROR THEN
                The line is part of the simple path.
                first_index = last_index
                last_index = last_index + step
        ELSE reduce last_index
                step = (last_index - first_index)/2
                last_index = last_index - step;
        END IF
 END WHILE

Definition at line 106 of file path_simplifier.c.

References calc_dist(), calc_line(), newPathPoint(), _PathPoint::next, PATH_ERROR, _PathPoint::x, and _PathPoint::y.

Here is the call graph for this function:

---