1LIBPATH(3) Library Functions Manual LIBPATH(3)
2
6 libpathplan - finds and smooths shortest paths
7
9 #include <graphviz/pathplan.h>
10 typedef struct Pxy_t {
12 double x, y;
13 } Pxy_t;
14 typedef struct Pxy_t Ppoint_t;
16 typedef struct Pxy_t Pvector_t;
17 typedef struct Ppoly_t {
19 Ppoint_t *ps;
20 int pn;
21 } Ppoly_t;
22 typedef Ppoly_t Ppolyline_t;
24 typedef struct Pedge_t {
26 Ppoint_t a, b;
27 } Pedge_t;
28 typedef struct vconfig_s vconfig_t;
30 #define POLYID_NONE
32 #define POLYID_UNKNOWN
33 int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);
35 vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
37 int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route);
38 void Pobsclose(vconfig_t *config);
39 int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2],
41 Ppolyline_t *output_route);
42 int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);
44
46 libpathplan provides functions for creating spline paths in the plane
47 that are constrained by a polygonal boundary or obstacles to avoid.
48 All polygons must be simple, but need not be convex.
49 int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t
51 *output_route);
52 The function Pshortestpath finds a shortest path between two points in
53 a simple polygon. The polygon is specified by a list of its vertices,
54 in either clockwise or counterclockwise order. You pass endpoints
55 interior to the polygon boundary. A shortest path connecting the
56 points that remains in the polygon is returned in output_route. If
57 either endpoint does not lie in the polygon, -1 is returned; otherwise,
58 0 is returned on success. The array of points in output_route is
59 static to the library. It should not be freed, and should be used
60 before another call to Pshortestpath.
61 vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
63 Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int
64 poly1, Ppolyline_t *output_route);
65 void Pobsclose(vconfig_t *config);
66 These functions find a shortest path between two points in the plane
67 that contains polygonal obstacles (holes). Pobsopen creates a configu‐
68 ration (an opaque struct of type vconfig_t) on a set of obstacles. The
69 n_obstacles obstacles are given in the array obstacles; the points of
70 each polygon should be in clockwise order. The function Pobsclose
71 frees the data allocated in Pobsopen.
72 Pobspath finds a shortest path between the endpoints that remains out‐
74 side the obstacles. If the endpoints are known to lie inside obsta‐
75 cles, poly0 or poly1 should be set to the index in the obstacles array.
76 If an endpoint is definitely not inside an obstacle, then POLYID_NONE
77 should be passed. If the caller has not checked, then POLYID_UNKNOWN
78 should be passed, and the path library will perform the test. The
79 resulting shortest path is returned in output_route. Note that this
80 function does not provide for a boundary polygon. The array of points
81 stored in output_route are allocated by the library, but should be
82 freed by the user.
83 int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t
85 input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route);
86 This function fits a cubic B-spline curve to a polyline path. The
87 curve is constructed to avoid a set of n_barriers barrier line segments
88 specified in the array barriers. If you start with polygonal obstacles,
89 you can supply each polygon's edges as part of the barrier list. The
90 polyline input_route provides a template for the final path; it is usu‐
91 ally the output_route of one of the shortest path finders, but it can
92 be any simple path that doesn't cross any barrier segment. The input
93 also allows the specification of desired slopes at the endpoints via
94 endpoint_slopes. These are specified as vectors. For example, to have
95 an angle of T at an endpoing, one could use (cos(T),sin(T)). A vector
96 (0,0) means unconstrained slope. The output is returned in out‐
97 put_route and consists of the control points of the B-spline. The func‐
98 tion return 0 on success; a return value of -1 indicates failure. The
99 array of points in output_route is static to the library. It should not
100 be freed, and should be used before another call to Proutespline.
101 int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int
103 *n_barriers);
104 This is a utility function that converts an input list of polygons into
105 an output list of barrier segments. The array of points in barriers is
106 static to the library. It should not be freed, and should be used
107 before another call to Ppolybarriers. The function returns 1 on suc‐
108 cess.
109
111 The function Proutespline does not guarantee that it will preserve the
112 topology of the input path as regards the boundaries. For example, if
113 some of the segments correspond to a small polygon, it may be possible
114 that the final path has flipped over the obstacle.
115
117 David Dobkin (dpd@cs.princeton.edu), Eleftherios Koutsofios
118 (ek@research.att.com), Emden Gansner (erg@research.att.com).
119 01 APRIL 1997 LIBPATH(3)