はじめに
d3.jsでベジェ曲線をドラッグで変形するサンプル - Qiitaを発展させて、交点を求めて表示するようにしてみました。
デモ: http://bl.ocks.org/hnakamur/73af30f05fced219a33f
ソース: https://github.com/hnakamur/d3.js-drag-bezier-curves-example/tree/use-kld-intersections
交点が見つからない場合があることが判明
交点の計算には kld-intersections を使いました。
大体の場合は良いのですが、位置によっては交点の一部が見つからない場合があります。初期表示の状態がまさにそうなっていて本当は交点が2つあるのに1つしか見つかっていません。制御点を移動すると2つになるのですが、最初の位置に戻すと1つになってしまいます。
別の交点の計算方法を調査中
A Primer on Bézier CurvesのCurve/curve intersectionでは曲線を分割していってバウンディングボックスが重なるかどうかを判定していき、ピクセルサイズより小さくなったらそこが交点という方法が説明されていました。
一方、Computer Aided Geometric DesignというタイトルのPDFの"7.3 Intersection of a Parametric Curve and an Implicit Curve"では片方の曲線をx(t), y(t)で表して、もう片方の曲線をf(x,y)で表してg(t)=f(x(t), y(t))=0をtについて解くという方式で交点を求めています。
"a polynomial root finding problem"になるので非常に効率がいいとのことなのですが、具体的にどのように方程式を作って解けばいいのか、私の理解が追いついておらず、さらなる勉強が必要です。