垂直線と交差する 2 つの線分の順序を決定するより良い方法はありますか? 順序は交点の y 座標に従います。単純なアプローチは、交点を計算して比較することです。
2 に答える
0
この問題を解決するためのヒントをいくつか教えてください。
- このウィキペディアのエントリに示すように、行列式を使用すると、線の交点をより迅速に見つけることができます。
- この問題のより一般的なバージョンを解決するアルゴリズムは、一連の線分に交差があるかどうかをテストするために作成されたBentley-Ottmann アルゴリズムです。
ウィキペディアのライン セグメントの交差点に関するこのエントリには、この件に関するお問い合わせが含まれていると思います。
于 2012-06-11T04:20:58.897 に答える
0
エンドポイントを使用して行が指定されていると仮定します。
端点 ( x0、y0)/( x1、y1) を持つ線と x 座標を持つ垂直線の交点は次のxとおりです。
y = (dy/dx)(x - x0) + y0
どこdx = x1 - x0とdy = y1 - y0。
2行あり、計算しています：
(day/dax)(x - ax0) + ay0 < (dby/dbx)(x - bx0) + by0
dax * dbx除算を取り除くために、両辺を掛けることができます。
(day * dbx)(x - ax0) + (ay0 * dax * dbx) < (dby * dax)(x - bx0) + (by0 * dax * dbx)
少し単純化します。
(day * dbx)(x - ax0) - (dby * dax)(x - bx0) + (ay0 - by0)(dax * dbx) < 0
これは必ずしも良いとは限りません。状況によって異なります。
- 座標が整数の場合、これによりテストを正確に実行できますが、
dax/dbx/etc が大きい場合はオーバーフローする傾向があります - 座標が浮動小数点なら浮動小数点除算が遅い方が早いかも
于 2012-06-11T04:24:53.420 に答える