多次元方程式を解いて交点を求める方式は不安定
JavaScript - kld-intersectionsを使って2つのベジェ曲線の交点を求めてみた - Qiitaでは、kld-intersectionsとkld-polynomialを使って2つの曲線の交点を多次元方程式の解を求める方式を使いましたが、あるべき交点を見落とすケースがありました。
その後、自分でもDurand–Kerner法を使って多次元方程式の解を求める方式を試してみたのですが、さらに見落としが増えてしまうという残念な結果になりました。
Computer Aided Geometric Design - Dr. Thomas W. Sederberg (PDF, 12.1MB)を読むとm次曲線とn次曲線の交点は無限遠点と複素数座標も含めるとmn個あるという話が書いてあります。このうちの実数の解で曲線パラメータtが0と1の間にあるものが求める交点というわけです。
が、実装してみると誤差が大きくてうまく行きませんでした。多次元方程式を数値計算で解くアルゴリズムは多数あるので、極めれば行けるかもしれませんが、曲線を分割する方式を試すことにしました。
曲線を分割して交点を求める方式のほうが安定
デモ
An example of drawing intersections of a cubic bezier curve and an elliptic arc
3次ベジェ曲線と楕円弧の交点を求めて表示するデモです。
交点は青い丸で表示しています。
3次曲線の制御点はドラッグで移動可能です。
今回の実装についてのメモ
曲線の分割方式
曲線を分割して交点を求める方式にもBezier Clippingなどいろいろあるようなのですが、今回はシンプルな方法を選びました。
Computer Aided Geometric Design - Dr. Thomas W. Sederberg (PDF, 12.1MB)の"7.6 Interval subdivision"の"Figure 7.3: Interval preprocess and subdivision"のように、最初はX軸かY軸に平行な点で分割します。
X軸とY軸に平行なバウンディングボックスを求めて相手の曲線を分割したセグメントのバウンディングボックスと重ならないものは除外し、重なるものは曲線パラメータtを半分の点で分割します。
これを繰り返して曲線のセグメントが十分直線に近くなったら、2つの曲線のセグメントを2つの直線と近似して交点を求める、という方法です。
本来は十分直線に近くなったらというのを計算で判定すべきところですが、今回の実装では判定をサボって、分割を一定回数繰り返したら直線で近似しています。
具体的には、最初にX軸Y軸に平行な点で分割した後、2分割を5回繰り返し、つまり32分割したら直線として近似しています。
SVGの楕円弧のパラメータ指定から中心と開始角度と終了角度を求める方式
SVGでは楕円弧は中心の座標は指定しないで
8.3.8 The elliptical arc curve commandsのようにパラメータを指定するようになっています。これはパスを書く処理を現在位置から目標位置まで曲線を書くという方式に揃えたいからのようです。
ですが、曲線の交点を求めるためには中心の座標も知りたいところです。Implementation Requirements – SVG 1.1 (Second Edition)にアルゴリズムの説明があるのですが、StackOverflowで見つけたコメントによると一部動かない場合があるので
http://svn.apache.org/repos/asf/xmlgraphics/batik/branches/svg11/sources/org/apache/batik/ext/awt/geom/ExtendedGeneralPath.java を参照したほうが良いとのことでした。このファイルの computeArc を移植して楕円弧上の点を計算するようにしました。
今後の課題
上記の曲線分割方式で交点を求めるのは幾何学的に解釈できるので非常にわかりやすいので良かったです。ただ、曲線が接する場合は、分割した直線が交わるのではなく重なることになると思うので、その場合をどうするかが課題です。現状は接する場合は交点として検出していないです。