1LIBPATH(3)                 Library Functions Manual                 LIBPATH(3)
2
3
4

NAME

6       libpathplan - finds and smooths shortest paths
7

SYNOPSIS

9       #include <graphviz/pathplan.h>
10
11       typedef struct Pxy_t {
12           double x, y;
13       } Pxy_t;
14
15       typedef struct Pxy_t Ppoint_t;
16       typedef struct Pxy_t Pvector_t;
17
18       typedef struct Ppoly_t {
19           Ppoint_t *ps;
20           int pn;
21       } Ppoly_t;
22
23       typedef Ppoly_t Ppolyline_t;
24
25       typedef struct Pedge_t {
26           Ppoint_t a, b;
27       } Pedge_t;
28
29       typedef struct vconfig_s vconfig_t;
30
31       #define POLYID_NONE
32       #define POLYID_UNKNOWN
33
34

FUNCTIONS

36       int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);
37       Finds a shortest path between two points in a simple polygon.  You pass
38       endpoints interior to the polygon boundary.  A shortest path connecting
39       the points that remains in the polygon is returned in output_route.  If
40       either endpoint does not lie in the polygon, an error code is returned.
41       (what code!!)
42
43       vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
44       int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route);
45       void Pobsclose(vconfig_t *config);
46       These  functions  find  a  shortest path between two points in a simple
47       polygon that possibly contains polygonal obstacles  (holes).   Pobsopen
48       creates  a  configuration (an opaque struct of type vconfig_t) on a set
49       of obstacles. Pobspath finds a shortest path between the endpoints that
50       remains  outside  the  obstacles.   If  the  endpoints are known to lie
51       inside obstacles, poly0 or poly1 should be set  to  the  index  in  the
52       obstacles  array.  If an endpoint is definitely not inside an obstacle,
53       then POLYID_NONE should be passed.  If the caller has not checked, then
54       POLYID_UNKNOWN  should be passed, and the path library will perform the
55       test.
56
57       (!! there is no boundary polygon in this model?!!!)
58
59       int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2],
60              Ppolyline_t *output_route);
61
62       This function fits a Bezier curve to a polyline path.  The  curve  must
63       avoid  a  set  of  barrier  segments.  The polyline is usually the out‐
64       put_route of one of the shortest path finders, but it can be any simple
65       path  that  doesn't  cross any obstacles.  The input also includes end‐
66       point slopes and 0,0 means unconstrained slope.
67
68       Finally, this utility function converts an input list of polygons  into
69       an output list of barrier segments:
70       int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);
71
72

AUTHORS

74       David    Dobkin    (dpd@cs.princeton.edu),    Eleftherios    Koutsofios
75       (ek@research.att.com), Emden Gansner (erg@research.att.com).
76
77
78
79                                 01 APRIL 1997                      LIBPATH(3)
Impressum