LIBPATH(3) | Library Functions Manual | LIBPATH(3) |

# NAME

**libpathplan** - finds and smooths shortest paths

# SYNOPSIS

#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);

# DESCRIPTION

**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.

## int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);

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*.

## 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);

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.

## int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route);

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*.

## int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);

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.

# BUGS

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.

# AUTHORS

David Dobkin (dpd@cs.princeton.edu), Eleftherios Koutsofios (ek@research.att.com), Emden Gansner (erg@research.att.com).

01 APRIL 1997 |