現在TeXを勉強中の者です。
現状困っている訳でも、知ったからと言ってどうもないのですが、単純に興味本位です。
ご存知の方、もしくはプログラムに詳しい方、ご教授頂けると嬉しいです。
TikZの\intersectionが、たった1つのコマンドで複雑な曲線の交点を自動的に計算してくれることに、初めて使ったときは非常に感動しました。
自分は、pythonも学習しているのですが、そちらで2つの曲線の交点を求める(それも方程式で簡単に解けないようなもの)コマンドはなく(知らないだけかもしれないです)、自分でコードを書く必要がありました。
そこでは、グラフ上に等間隔に点をプロットして、2つのグラフの点の差分が1番小さい組み合わせ(丸め誤差を使う)を選出するというプログラムをつくりました。当然ごく微小のずれなどが出てきてしまう粗悪なアルゴリズムでしたが、それしか考えられませんでした。
実際、\intersectionというコマンドは裏でどのようなアルゴリズムで動いているのでしょうか。
それとも、wolframとまではいかないけれども、高精度の計算プログラムで実際に計算をしているのでしょうか。それだったらもう少し複雑な関数も書けて欲しいところなのですが(合成関数だとエラーを吐いてしまうので、結構困っています)。
有識者の方、何卒よろしくお願い致します。
有識者ではありませんし、ちょっと調べただけなので間違っているかもしれませんが……
tikz に \intersection というコマンドが見当たらなかったので intersections library の機能のことだと仮定します。
TikZ/PGF は「複雑な曲線」を「直線」と「3次ベジェ曲線」で近似しているようです。
「直線」と「3次ベジェ曲線」だけですので、交点は「直線-直線」、「直線-ベジェ」、「ベジェ-ベジェ」の 3 通りを考えればよいことになります。
さらに、「直線-ベジェ」は直線をまっすぐなベジェ曲線に変換することで「ベジェ-ベジェ」と同じ処理しているようなので、実質「直線-直線」と「ベジェ-ベジェ」の 2 通りです。
どちらも実装は pgflibraryintersections.code.tex にあり、コメントでどのような方法で求めているか書かれています。
「直線-直線」は以下のように求めているようです（理屈はわかってませんが……）
% Let L1 be represented by P1+(P2-P1)s where 0<=s<=1
% Let L2 be represented by P3+(P4-P3)t where 0<=t<=1
%
% Then L1 and L2 intersect at
%
% s = |x2-x1 x3-x1| / |x4-x3 x2-x1|
% |y2-y1 y3-y1| |y4-y3 y2-y1|
%
% t = |x4-x3 x3-x1| / |x4-x3 x2-x1|
% |y4-y3 y3-y1| |y4-y3 y2-y1|
%
% with 0<=s,t<=1
「ベジェ-ベジェ」以下のようにベジェ曲線をどんどん分割していってある程度小さくなったら
バウンディングボックスが重なっているところを交点としているようです。
% intersection(C1,C2)
% S = {};
% intersection'(C1,C2);
% return S;
%
% intersection'(C1,C2)
% B1 = boundingbox(C1);
% B2 = boundingbox(C2);
% if intersect(B1,B2)
% if (B1.width < q) and (B1.height < q) and
% (B2.width < q) and (B2.height < q)
% S = S + {average_of_all_points(B1,B2)}; \\ is there a better choice?
% else
% Q = subdivideLeft(C1);
% R = subdivideRight(C1);
% intersection'(C2,Q);
% intersection'(C2,R);
%
% where q is a small value (tolerance).
tikz に \intersection というコマンドが見当たらなかったので intersections library の機能のことだと仮定します。
TikZ/PGF は「複雑な曲線」を「直線」と「3次ベジェ曲線」で近似しているようです。
「直線」と「3次ベジェ曲線」だけですので、交点は「直線-直線」、「直線-ベジェ」、「ベジェ-ベジェ」の 3 通りを考えればよいことになります。
さらに、「直線-ベジェ」は直線をまっすぐなベジェ曲線に変換することで「ベジェ-ベジェ」と同じ処理しているようなので、実質「直線-直線」と「ベジェ-ベジェ」の 2 通りです。
どちらも実装は pgflibraryintersections.code.tex にあり、コメントでどのような方法で求めているか書かれています。
「直線-直線」は以下のように求めているようです（理屈はわかってませんが……）
% Let L1 be represented by P1+(P2-P1)s where 0<=s<=1
% Let L2 be represented by P3+(P4-P3)t where 0<=t<=1
%
% Then L1 and L2 intersect at
%
% s = |x2-x1 x3-x1| / |x4-x3 x2-x1|
% |y2-y1 y3-y1| |y4-y3 y2-y1|
%
% t = |x4-x3 x3-x1| / |x4-x3 x2-x1|
% |y4-y3 y3-y1| |y4-y3 y2-y1|
%
% with 0<=s,t<=1
「ベジェ-ベジェ」以下のようにベジェ曲線をどんどん分割していってある程度小さくなったら
バウンディングボックスが重なっているところを交点としているようです。
% intersection(C1,C2)
% S = {};
% intersection'(C1,C2);
% return S;
%
% intersection'(C1,C2)
% B1 = boundingbox(C1);
% B2 = boundingbox(C2);
% if intersect(B1,B2)
% if (B1.width < q) and (B1.height < q) and
% (B2.width < q) and (B2.height < q)
% S = S + {average_of_all_points(B1,B2)}; \\ is there a better choice?
% else
% Q = subdivideLeft(C1);
% R = subdivideRight(C1);
% intersection'(C2,Q);
% intersection'(C2,R);
%
% where q is a small value (tolerance).