さて、曲線が$y = f(x),\ y = g(x)$の時は良いのだが、パタメータ表示されている場合が面倒くさい。簡単のためにパラメータの動く範囲を有界閉区間に制限して
\begin{equation}
p(s) = \{ x_1(s),\ y_1(s) \},\ 0 \le s \le 1,\ q(t) = \{ x_2(t),\ y_2(t) \},\ 0 \le t \le 1
\end{equation}
とし、$p(s),\ q(t)$の交点を求めるとなると大変だ。理屈的には、
\begin{equation}
\{ (s,\ t) \in [0,\ 1]^2;\ \exists (s,\ t)\ \mathrm{s.t}\ x_1(s) = x_2(t),\ y_1(s) = y_2(t) \}
\end{equation}
が解集合で、良かったねといったところだが、具体的に求めるのが大変だ。
\begin{equation}
x_1(s) = s^2 - s,\ y_1(s) = s^2 - s,\ x_2(t) = t^3 - 2 t^2 + 5,\ y_2(t) = t^3 - 2 t^2 + 5
\end{equation}
とかでも大変だ。実のところどちらも$y=x$内を動いていて、へたすると重なって解集合は非可算無限集合だゎということになるが、どこ動いているか計算しないと場合によっては空集合$\varnothing$かもしれない。
ここで、$s,\ t$の変域を有界閉区間上に制限しているので、その上の連続函数は最大値(および最小値)を持つという定理から$p(s),\ q(t)$はそれぞれある長方形に含まれる。たぶんこれをBounding boxとか言うんだと思う...。暗黙のうちの最小のものを考えたいのでMinimum bounding box - Wikipedia, the free encyclopediaか。
解集合を求めるのは大変だ。
- 可能なら開集合(交点の座標)を厳密に求めたい
- それが難しいなら、2つの曲線が交点を持っているかだけを求めたい
- それでも難しいなら、2つの曲線が交点を持っている可能性がありそうかを求めたい
といったことを考えたい。というか考えている。しかも極力シンプルなロジックで高速に求めたい。
3番目の条件は更に粗くすると「2つの曲線が交点を絶対に持たない」条件の否定を考えるとシンプルっちゃーシンプルかもしれない。$P=$「2つの曲線が交点を絶対に持たない」として、$\lnot P$を考えるぞ！とか。条件と命題をごっちゃにするなとか色々なりそうなので、雰囲気のみで。
ではいつ持たないか。ベジエ曲線の交点について - s.h’s pageなどを参考にすると、Minimum bounding box(の内点集合)同士がintersectionを持たなければまぁ、交点はないよねとなりそうだ。最大値最小値を求めて、Minimum bounding boxを割り出しても良いかもしれないが、若干面倒くさいかもしれない。3次Bézierスプラインなら導函数が2次方程式になるので、簡単に最大値と最小値の候補が見つかるので、Minimum bounding box を簡単に求めることができるはずだ。
或は、Bézier曲線の特徴として、曲線がコントロールポイント全体の凸包(convex hull, 凸包 - Wikipedia)に含まれるというのがあるので、3次Bézierスプラインなら、2本のハンドルを構成する4点の凸包である四辺形を考えれば良い。
とはいえ、Minimum bounding boxも凸包も求めたり扱ったりするのがちょっと面倒だ。ということで、曲線自体のMinimum bounding boxではなく、ちょっと大きくなるかもしれないけど、コントロールポイントに対するMinimum bounding boxを使えば超絶楽だ。このboxは先の凸包を含むので、曲線を丸ごと含むbounding boxであり、従って曲線自体のMinimum bounding boxも包含する。
2つの3次Bézierスプラインについて、それらのコントロールポイントに対するMinimum bounding box同士のintersectionが空なら、曲線は交差しないと判断できる。この判定は軽量なので、偽の時に更に追い込めば全体として軽量な比較になるだろう。そうそう交差するもんでもないだろうから。
先のblogからリンクされているA Primer on Bézier Curvesはなかなか手頃なBézier曲線のテキストが見つからない中で貴重かもしれない。
しかし、Bézier曲線の場合その性質を利用して交点を追い込めるが、一般の曲線の場合は難しそうだなぁ...。
まぁ、ムズカシイことは追々考えるとしよう...。
