libpathplan - finds and smooths shortest paths

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

                                                  01 APRIL 1997                                       LIBPATH(3)

       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.

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.

      intPshortestpath(Ppoly_t*boundary,Ppoint_tendpoints[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,intn_obstacles);Pobspath(vconfig_t*config,Ppoint_tp0,intpoly0,Ppoint_tp1,intpoly1,Ppolyline_t*output_route);voidPobsclose(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)onasetofobstacles.Then_obstaclesobstaclesaregiveninthearrayobstacles;thepointsofeachpolygonshouldbeinclockwiseorder.ThefunctionPobsclosefreesthedataallocatedinPobsopen.

       Pobspath  findsashortestpathbetweentheendpointsthatremainsoutsidetheobstacles.Iftheendpointsareknowntolieinsideobstacles,poly0 or poly1 shouldbesettotheindexintheobstacles
       array.   If  an endpoint is definitely not inside an obstacle, then POLYID_NONE shouldbepassed.Ifthecallerhasnotchecked,thenPOLYID_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.

        intProutespline(Pedge_t*barriers,intn_barriers,Ppolyline_tinput_route,Pvector_tendpoint_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  providesatemplateforthefinalpath;itisusuallytheoutput_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.

      intPpolybarriers(Ppoly_t**polys,intn_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.

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