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