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                                LIBPATH(3)