私は .NET を使用して、Visio に似た描画面を持つアプリケーションを作成しています。UI は、画面上の 2 つのオブジェクトを Graphics.DrawLine で接続します。この単純な実装は問題なく機能しますが、表面がより複雑になるにつれて、オブジェクトを表現するためのより堅牢な方法が必要になります。これらの堅牢な要件の 1 つは、2 つの線の交点を決定することです。これにより、何らかのグラフィックで分離を示すことができます。
だから私の質問は、誰かがこれを行う方法を提案できますか? おそらく、別の手法 (GraphViz など) またはアルゴリズムを使用しているのでしょうか?
y = mx + c による線の表現は、コンピュータ グラフィックスでは問題があります。垂直線では m が無限大である必要があるからです。
さらに、コンピュータ グラフィックスの線には、範囲が無限である数学的な線とは異なり、始点と終点があります。通常、交点が問題の両方の線分上にある場合にのみ、線の交点に関心があります。
ベクトル x1 から x1+v1 までの 1 つとベクトル x2 から x2+v2 までの 2 つの線分がある場合、次のように定義します。
a = (v2.v2 v1.(x2-x1) - v1.v2 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
b = (v1.v2 v1.(x2-x1) - v1.v1 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
ここで、ベクトル p=(px,py)、q=(qx,qy) の場合、pq は内積 (px * qx + py * qy) です。最初に (v1.v1)(v2.v2) = (v1.v2)^2 かどうかを確認します。そうであれば、線は平行で交差していません。
それらが平行でない場合、0<=a<=1 かつ 0<=b<=1 の場合、交点は両方の線分上にあり、点によって与えられます。
x1 + a * v1
編集a と b の方程式の導出は次のとおりです。交点はベクトル方程式を満たします
x1 + a*v1 = x2 + b*v2
v1この方程式と、およびの内積を取ると、次のv22 つの方程式が得られます。
v1.v1*a - v2.v1*b = v1.(x2-x1)
v1.v2*a - v2.v2*b = v2.(x2-x1)
これは、a と b の 2 つの線形方程式を形成します。この連立方程式を解くと (最初の方程式に v2.v2 を掛け、2 番目の方程式に v1.v1 を掛けて引き算するなどして)、a と b の方程式が得られます。
参照フレームを回転して最初の線分に合わせると (原点が最初の線の始点になり、最初の線のベクトルが X 軸に沿って伸びます)、2 番目の線はどこにあるのかという問題になります。新しい座標系で X 軸にヒットします。これは、はるかに答えやすい質問です。最初の線が呼び出されA、それが線の原点として定義さA.Oれ、'AV' が線のベクトルであるため、それA.O + A.Vが線の終点になります。参照フレームは、マトリックスによって定義できます。
| A.V.X A.V.Y A.O.X |
M = | A.V.Y -A.V.X A.O.Y |
| 0 0 1 |
A同次座標では、この行列はX 軸の 0 から 1 にラインをマッピングする基準フレームの基礎を提供します。変換された行Bを次のように定義できます。
C.O = M*(B.O)
C.V = M*(B.O + B.V) - C.O
*演算子が同次座標 (この場合は 3 空間から 2 空間への射影) に対して適切に定義されている場所。あとは、 が X 軸に当たる場所をチェックして確認するだけです。これは、 forのパラメトリック方程式の側面をC解くのと同じです。YCt
C.O.Y + t * C.V.Y = 0
-C.O.Y
t = --------
C.V.Y
tが 0 から 1 の範囲内にある場合C、線分の内側の X 軸に当たります。X 軸上で着地する場所は、 のパラメトリック方程式の X 側によって与えられCます。
x = C.O.X + t * C.V.X
が 0 から 1 の範囲にある場合x、交点はA線分上にあります。次に、元の座標系でポイントを見つけることができます。
p = A.O + A.V * x
もちろん、どちらかの線分の長さがゼロかどうかを最初に確認する必要があります。また、C.V.Y = 0平行線分がある場合。もゼロの場合C.V.X、同一直線上にある線分があります。