Provided by: libgraphviz-dev_2.26.3-10ubuntu1_amd64

**NAME**

libpathplan- finds and smooths shortest paths

**SYNOPSIS**

#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

**FUNCTIONS**

int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);Findsashortestpathbetweentwopointsinasimplepolygon.Youpassendpointsinteriortothepolygonboundary.Ashortestpathconnectingthepointsthatremainsinthepolygonisreturnedinoutput_route.Ifeitherendpointdoesnotlieinthepolygon,anerrorcodeisreturned.(whatcode!!)vconfig_t*Pobsopen(Ppoly_t**obstacles,intn_obstacles);intPobspath(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 a simple polygon that possibly contains polygonal obstacles (holes). Pobsopencreatesaconfiguration(anopaquestructoftypevconfig_t) on a set of obstacles. Pobspathfindsashortestpathbetweentheendpointsthatremainsoutsidetheobstacles.Iftheendpointsareknowntolieinsideobstacles,poly0or poly1shouldbesettotheindexintheobstaclesarray. If an endpoint is definitely not inside an obstacle, then POLYID_NONEshouldbepassed.Ifthecallerhasnotchecked,thenPOLYID_UNKNOWNshould be passed, and the path library will perform the test. (!! there is no boundary polygon in this model?!!!) int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route);ThisfunctionfitsaBeziercurvetoapolylinepath.Thecurvemustavoidasetofbarriersegments.Thepolylineisusuallytheoutput_routeof one of the shortest path finders, but it can be any simple path that doesn't cross any obstacles. The input also includes endpoint slopes and 0,0 means unconstrained slope. Finally, this utility function converts an input list of polygons into an output list of barrier segments: int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);

**AUTHORS**

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