Graphviz: スプライン-o-マティック

スプライン-o-マティックは、図にベジェ曲線を描画するエッジルータです。テストとデモのためのTCL/tkインターフェースが付属しています。

このライブラリは入力として以下を受け取ります。

• 2つの端点

• オプションの端点接線ベクトル

• 端点を接続するために曲線を描画できる許容領域

これにより、端点を接続し、許容領域内に収まるベジェ曲線が返されます。曲線は滑らかで最短経路に近いものです。

スプライン-o-マティックが解決する2つの問題

最初の場合、入力は単純なポリゴンであり、2つの端点がその内部になければなりません。結果の曲線は、制御ポリゴン内に収まります。

2番目の場合、入力は、端点とともに、回避すべき多角形の障害物または「穴」のリストです。結果の曲線は、障害物を通過しません。（端点が障害物の中にある場合、そのルートでは無視されます。これは、ノードリンク図のルーティングに便利です。）

曲線はグローバルではなく個別にルーティングされるため、エッジルータはそれらが交差するのを防ぎません。このライブラリの興味深い改善点は、不要なエッジの交差を防ぐためのグローバルプランニングの概念を導入することでしょう。スプライン-o-マティックへのライブラリインターフェースは、効率と柔軟性のために個別に呼び出すことができるように、その主要なアルゴリズムを公開しています。

曲線は2つのフェーズで計算されます。最初のフェーズでは、端点間の最短経路（折れ線）を見つけます。前述のように、2つのバリアントがあります。ポリゴン内部のルーティングは、OvermarsとWelzlによる効率的なアルゴリズムで解決されますが、障害物を回避するルーティングには、障害物の頂点の可視グラフの計算が含まれます。これには、標準のO（N ^ 3）アルゴリズムを使用します。複数のエッジルートを見つける必要がある場合、ルートごとに計算するよりも、可視グラフを事前に計算して再利用する方がはるかに高速です。

2番目のフェーズでは、任意の単純なパス（通常は最初のフェーズで計算された最短パス）と、バリアセグメント（通常は制御ポリゴンまたは障害物の側面）のリストを取り、端点を除いてバリアに触れないベジェ曲線を生成します。バリアがポリゴンを形成する必要はないことに注意してください。

ライブラリ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ビデオ。