Daniel@0: .TH LIBPATH 3 "01 APRIL 1997"
Daniel@0: .SH NAME
Daniel@0: \fBlibpathplan\fR \- finds and smooths shortest paths
Daniel@0: .SH SYNOPSIS
Daniel@0: .ta .75i 1.5i 2.25i 3i 3.75i 4.5i 5.25i 6i
Daniel@0: .PP
Daniel@0: .nf
Daniel@0: \f5
Daniel@0: #include <graphviz/pathplan.h>
Daniel@0: 
Daniel@0: typedef struct Pxy_t {
Daniel@0:     double x, y;
Daniel@0: } Pxy_t;
Daniel@0: 
Daniel@0: typedef struct Pxy_t Ppoint_t;
Daniel@0: typedef struct Pxy_t Pvector_t;
Daniel@0: 
Daniel@0: typedef struct Ppoly_t {
Daniel@0:     Ppoint_t *ps;
Daniel@0:     int pn;
Daniel@0: } Ppoly_t;
Daniel@0: 
Daniel@0: typedef Ppoly_t Ppolyline_t;
Daniel@0: 
Daniel@0: typedef struct Pedge_t {
Daniel@0:     Ppoint_t a, b;
Daniel@0: } Pedge_t;
Daniel@0: 
Daniel@0: typedef struct vconfig_s vconfig_t;
Daniel@0: 
Daniel@0: #define POLYID_NONE	
Daniel@0: #define POLYID_UNKNOWN
Daniel@0: 
Daniel@0: \fP
Daniel@0: .fi
Daniel@0: .SH FUNCTIONS
Daniel@0: 
Daniel@0: .nf
Daniel@0: \f5
Daniel@0: int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);
Daniel@0: \fP
Daniel@0: .fi
Daniel@0: Finds a shortest path between two points in a simple polygon.
Daniel@0: You pass endpoints interior to the polygon boundary.
Daniel@0: A shortest path connecting the points that remains in the polygon
Daniel@0: is returned in output_route.  If either endpoint does not lie in
Daniel@0: the polygon, an error code is returned. (what code!!)
Daniel@0: 
Daniel@0: .nf
Daniel@0: \f5
Daniel@0: vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
Daniel@0: .br
Daniel@0: int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route);
Daniel@0: .br
Daniel@0: void Pobsclose(vconfig_t *config);
Daniel@0: \fP
Daniel@0: .fi
Daniel@0: These functions find a shortest path between two points in a
Daniel@0: simple polygon that possibly contains polygonal obstacles (holes).
Daniel@0: \f5Pobsopen\fP creates a configuration (an opaque struct of type
Daniel@0: \f5vconfig_t\fP) on a set of obstacles. \f5Pobspath\fP finds
Daniel@0: a shortest path between the endpoints that remains outside the
Daniel@0: obstacles.  If the endpoints are known to lie inside obstacles,
Daniel@0: \f5poly0\fP or \f5poly1\fP should be set to the index in the
Daniel@0: \f5obstacles\fP array.  If an endpoint is definitely not inside
Daniel@0: an obstacle, then \f5POLYID_NONE\fP should be passed.  If the
Daniel@0: caller has not checked, then \f5POLYID_UNKNOWN\fP should be passed,
Daniel@0: and the path library will perform the test.
Daniel@0: 
Daniel@0: (!! there is no boundary polygon in this model?!!!)
Daniel@0: 
Daniel@0: .nf
Daniel@0: \f5
Daniel@0: int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2],
Daniel@0: 	Ppolyline_t *output_route);
Daniel@0: \fP
Daniel@0: .fi
Daniel@0: 
Daniel@0: This function fits a Bezier curve to a polyline path. 
Daniel@0: The curve must avoid a set of barrier segments. The polyline
Daniel@0: is usually the \f5output_route\fP of one of the shortest path
Daniel@0: finders, but it can be any simple path that doesn't cross
Daniel@0: any obstacles.  The input also includes endpoint slopes and
Daniel@0: 0,0 means unconstrained slope.  
Daniel@0: 
Daniel@0: Finally, this utility function converts an input list of polygons
Daniel@0: into an output list of barrier segments:
Daniel@0: .nf
Daniel@0: \f5
Daniel@0: int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);
Daniel@0: \fP
Daniel@0: .fi
Daniel@0: 
Daniel@0: .SH AUTHORS
Daniel@0: David Dobkin (dpd@cs.princeton.edu),
Daniel@0: Eleftherios Koutsofios (ek@research.att.com),
Daniel@0: Emden Gansner (erg@research.att.com).