## "Fossies" - the Fresh Open Source Software Archive

### Member "graphviz-2.38.0/lib/pathplan/pathplan.3" (13 Apr 2014, 5386 Bytes) of archive /linux/misc/graphviz-2.38.0.tar.gz:

Table of Contents

**libpathplan** - finds and smooths shortest paths

#include <graphviz/pathplan.h>
typedef struct Pxy_t {
double x, y;
} Pxy_t;
typedef struct Pxy_t Ppoint_t;
typedef struct Pxy_t Pvector_t;
typedef struct Ppoly_t {
Ppoint_t *ps;
int pn;
} Ppoly_t;
typedef Ppoly_t Ppolyline_t;
typedef struct Pedge_t {
Ppoint_t a, b;
} Pedge_t;
typedef struct vconfig_s vconfig_t;
#define POLYID_NONE` ` ` `
#define POLYID_UNKNOWN
int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t
*output_route);
vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int
poly1, Ppolyline_t *output_route);
void Pobsclose(vconfig_t *config);
int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route,
Pvector_t endpoint_slopes[2],
` ` ` ` Ppolyline_t *output_route);
int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int
*n_barriers);

**libpathplan** provides functions for creating spline paths in
the plane that are constrained by a polygonal boundary or obstacles to
avoid. All polygons must be simple, but need not be convex.

The function
*Pshortestpath* finds a shortest path between two points in a simple polygon.
The polygon is specified by a list of its vertices, in either clockwise
or counterclockwise order. You pass endpoints interior to the polygon boundary.
A shortest path connecting the points that remains in the polygon is returned
in *output_route*. If either endpoint does not lie in the polygon, -1 is returned;
otherwise, 0 is returned on success. The array of points in *output_route*
is static to the library. It should not be freed, and should be used before
another call to *Pshortestpath*.

These functions find a shortest path between two points in the
plane that contains polygonal obstacles (holes). *Pobsopen* creates a configuration
(an opaque struct of type vconfig_t) on a set of obstacles. The *n_obstacles*
obstacles are given in the array *obstacles*; the points of each polygon
should be in clockwise order. The function *Pobsclose* frees the data allocated
in *Pobsopen*.

Pobspath finds a shortest path between the endpoints that remains
outside the obstacles. If the endpoints are known to lie inside obstacles,
poly0 or poly1 should be set to the index in the obstacles array. If an
endpoint is definitely not inside an obstacle, then POLYID_NONE should
be passed. If the caller has not checked, then POLYID_UNKNOWN should be
passed, and the path library will perform the test. The resulting shortest
path is returned in *output_route*. Note that this function does not provide
for a boundary polygon. The array of points stored in *output_route* are allocated
by the library, but should be freed by the user.

This function fits a cubic B-spline curve to
a polyline path. The curve is constructed to avoid a set of *n_barriers*
barrier line segments specified in the array *barriers*. If you start with
polygonal obstacles, you can supply each polygon’s edges as part of the
barrier list. The polyline input_route provides a template for the final
path; it is usually the output_route of one of the shortest path finders,
but it can be any simple path that doesn’t cross any barrier segment. The
input also allows the specification of desired slopes at the endpoints
via *endpoint_slopes*. These are specified as vectors. For example, to have
an angle of *T* at an endpoing, one could use *(cos(T),sin(T))*. A vector (0,0)
means unconstrained slope. The output is returned in *output_route* and
consists of the control points of the B-spline. The function return 0 on
success; a return value of -1 indicates failure. The array of points in *output_route*
is static to the library. It should not be freed, and should be used before
another call to *Proutespline*.

This is a utility function
that converts an input list of polygons into an output list of barrier
segments. The array of points in *barriers* is static to the library. It should
not be freed, and should be used before another call to *Ppolybarriers*. The
function returns 1 on success.
The function *Proutespline* does not guarantee
that it will preserve the topology of the input path as regards the boundaries.
For example, if some of the segments correspond to a small polygon, it
may be possible that the final path has flipped over the obstacle.
David
Dobkin (dpd@cs.princeton.edu), Eleftherios Koutsofios (ek@research.att.com),
Emden Gansner (erg@research.att.com).

**Table of Contents**

- Name
- Synopsis
- Description
- int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);
- vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
- Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route);
- void Pobsclose(vconfig_t *config);
- int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route);
- int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);

- Bugs
- Authors