LIBPATH(3)

💖 LIBPATH(3) — the path-planning girlies know 💖

okay so bestie, you found it: libpathplan, section 3 of the library functions manual. It finds and smooths shortest paths and it is, honestly, iconic. 🦋

✨ NAME ✨

libpathplan — finds and smooths shortest paths. That's it, that's the whole job, and it eats. 💅

🎀 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

int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);

vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route);
void Pobsclose(vconfig_t *config);

int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2],
       Ppolyline_t *output_route);

int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);

🌸 DESCRIPTION 🌸

libpathplan gives you functions for making spline paths in the plane, and those paths are constrained — either by a polygonal boundary, or by obstacles you have to dodge. 🚧

⚠️ Every polygon must be simple, but lowkey they do not need to be convex. Periodt.

💫 int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2], Ppolyline_t *output_route);

Pshortestpath finds the shortest path between two points inside a simple polygon. You hand it the polygon as a list of its vertices, in either clockwise or counterclockwise order (we're not picky, bestie, we support both 💖). The endpoints you pass in are interior to the polygon boundary.

A shortest path connecting those points that stays inside the polygon comes back in output_route. 🎀

• If either endpoint does not lie in the polygon → -1 comes back.
• Otherwise → 0 on success, slay.

🚨 The array of points in output_route is static to the library. Do not free it. Use it before you call Pshortestpath again, or it's giving... chaos. 😭

🦋 vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);

🦋 Pobspath(vconfig_t *config, Ppoint_t p0, int poly0, Ppoint_t p1, int poly1, Ppolyline_t *output_route);

🦋 void Pobsclose(vconfig_t *config);

These three are the obstacle course girlies: they find a shortest path between two points in the plane when there are polygonal obstacles (holes) in the way. 🕳️

Pobsopen creates a configuration — an opaque struct of type vconfig_t — over a set of obstacles. The n_obstacles obstacles come in through the array obstacles, and the points of each polygon should be in clockwise order. 🌀

Pobsclose frees the data that Pobsopen allocated. Clean up after yourself, bestie. 🧹

Pobspath finds a shortest path between the endpoints that stays outside the obstacles. Here's the vibe check on poly0 / poly1:

• If the endpoints are known to lie inside obstacles, set poly0 or poly1 to the index in the obstacles array.
• If an endpoint is definitely not inside an obstacle, pass POLYID_NONE.
• If the caller has not checked, pass POLYID_UNKNOWN and the path library will perform the test itself. 👑

The resulting shortest path comes back in output_route.

💀 Heads up: this function does not provide for a boundary polygon.

🫶 And unlike that other one: the array of points stored in output_route is allocated by the library, and it should be freed by the user. Not me handing you the cleanup duties... okay yes, me. Do it though.

🌈 int Proutespline (Pedge_t *barriers, int n_barriers, Ppolyline_t input_route, Pvector_t endpoint_slopes[2], Ppolyline_t *output_route);

This one fits a cubic B-spline curve to a polyline path. So glamorous. ✨

The curve is built to avoid a set of n_barriers barrier line segments, specified in the array barriers. If you're starting from polygonal obstacles, you can just supply each polygon's edges as part of the barrier list. Easiest thing ever. 🎀

• The polyline input_route is the template for the final path. Usually it's the output_route of one of the shortest path finders, but fr fr it can be any simple path that doesn't cross any barrier segment.
• The input also lets you specify the desired slopes at the endpoints via endpoint_slopes. These are given as vectors. For example, to have an angle of T at an endpoint, one could use (cos(T),sin(T)). A vector (0,0) means unconstrained slope. 🦋

The output comes back in output_route and consists of the control points of the B-spline.

• Return 0 → success, we ate. 👑
• Return -1 → failure, it's giving tragedy. 😭

🚨 The array of points in output_route is static to the library. Do not free it. Use it before another call to Proutespline.

🍓 int Ppolybarriers(Ppoly_t **polys, int n_polys, Pedge_t **barriers, int *n_barriers);

A cute little utility function: it converts an input list of polygons into an output list of barrier segments. Glow-up for your data structure. 💅

🚨 The array of points in barriers is static to the library. Do not free it. Use it before another call to Ppolybarriers.

The function returns 1 on success. ⭐

💀 BUGS 💀

Not me having to tell you this, but: Proutespline does not guarantee that it will preserve the topology of the input path as regards the boundaries. 😭

For example, if some of the segments correspond to a small polygon, it may be possible that the final path has flipped over the obstacle. The audacity. The betrayal. Be aware, bestie. 🫶

👑 AUTHORS 👑

The literal main characters who made this happen:

• David Dobkin (dpd@cs.princeton.edu)
• Eleftherios Koutsofios (ek@research.att.com)
• Emden Gansner (erg@research.att.com)

okay and that's the whole page, bestie — this was LIBPATH(3) from the Library Functions Manual, dated 01 APRIL 1997. Old enough to be a classic, still eating. No cap. 🎀✨💖