Graphviz: Spline-o-Matic
Spline-o-matic 是一个边路由器，它在图表中绘制贝塞尔曲线。它带有一个 TCL/tk 界面，用于测试和演示。
该库接受以下输入
-
两个端点
-
可选的端点切线向量
-
一个允许区域，曲线可以在其中绘制以连接端点
它返回一个连接端点并保持在允许区域内的贝塞尔曲线。该曲线平滑且接近最短路径。
Spline-o-matic 解决两类问题
在第一种情况下，输入是一个简单的多边形，两个端点必须在它内部。结果曲线保持在控制多边形内。
在第二种情况下，输入是待避开的多个多边形障碍物或“孔”，以及端点。结果曲线不穿过任何障碍物。（如果端点在障碍物内，则在给定路线中将其忽略。这对于路由节点链接图非常方便。）
曲线是单独路由的，而不是全局路由的，因此边路由器不会阻止它们交叉。对该库的一个有趣的改进是引入全局规划的概念，以防止不需要的边交叉。Spline-o-matic 的库接口公开了其主要算法，因此可以独立调用它们以提高效率和灵活性。
曲线计算分为两个阶段。第一阶段找到端点之间的最短路径（一条折线）。如前所述，有两种变体。在一个多边形内路由通过 Overmars 和 Welzl 的有效算法解决，但在绕过障碍物路由则涉及计算障碍物顶点的可见性图，为此我们采用标准的 O(N^3) 算法。当需要找到多个边路线时，预先计算和重新使用可见性图要比为每条路线计算它快得多。
第二阶段采用任意简单路径（通常是第一阶段计算的最短路径）和一个障碍段列表（通常是控制多边形或障碍物的边）并生成一个贝塞尔曲线，该曲线除了在端点处外，不与障碍物接触。请注意，障碍物不需要形成多边形。
以下是库 API。多边形必须始终以顺时针顺序呈现！
#include <pathgeom.h>
/* open a visibility graph */
vconfig_t *Pobsopen(Ppoly_t **obstacles, int n_obstacles);
/* close a visibility graph, freeing its storage */
void Pobsclose(vconfig_t *config);
/* route a polyline from p0 to p1, avoiding obstacles.
* if an endpoint is inside an obstacle, pass the polygon's index >=0
* if the endpoint is not inside an obstacle, pass POLYID_NONE
* if the endpoint location is not known, pass POLYID_UNKNOWN
*/
int Pobspath(vconfig_t *config, Ppoint_t p0, int poly0,
Ppoint_t p1, int poly1,
Ppolyline_t *output_route);
#define POLYID_NONE -1111
#define POLYID_UNKNOWN -2222
/* find shortest euclidean path within a simple polygon */
extern int Pshortestpath(Ppoly_t *boundary, Ppoint_t endpoints[2],
Ppolyline_t *output_route);
/* fit a spline to an input polyline, without touching barrier segments */
extern int Proutespline (Pedge_t *barriers, int n_barriers,
Ppolyline_t input_route, Pvector_t endpoint_slopes[2],
Ppolyline_t *output_route);
/* utility function to convert from a set of polygonal obstacles to barriers */
extern int Ppolybarriers(Ppoly_t **polys, int npolys, Pedge_t **barriers, int *n
_barriers);
#endif
分布
源代码发行版位于我们的 下载页面 上。需要相当多的软件专业知识才能使用它。GUI是用 TCL 编写的。路径规划器被构建为一个静态库。TCL 层将此和其他函数包含为一个动态库。
GUI
该软件包具有 C 库接口和 TCL/tk GUI（由 John Ellson 贡献，ellson@research.att.com）用于演示和调试。运行 pathtest.tcl（或tclsh pathtest.tcl）。GUI 允许绘制障碍物多边形（使用按钮 1 放置顶点，使用按钮 2 放置多边形的最后一个顶点）。
pathtest 附带了一些示例障碍物配置。要尝试它，请运行pathtest.tcl，加载一个示例，单击贝塞尔单选按钮，然后使用鼠标按钮 1 和 2 来扫描线段。将在其端点之间路由一条曲线。在多边形内部路由还是绕过障碍物路由的选择取决于端点。
参考资料
实现通用边路由器：论文，Quicktime 视频。