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 影片。