26

2D平面上に無限に伸びる2つの光線がありますが、どちらにも開始点があります。それらは両方とも、開始点と、無限に伸びる光線の方向のベクトルによって記述されます。2つの光線が交差するかどうかを確認したいのですが、交差する場所を知る必要はありません（これは衝突検出アルゴリズムの一部です）。

これまで見てきたことはすべて、2本の線または線分の交点を見つけることを説明しています。これを解決するための高速アルゴリズムはありますか？

4

9 に答える 9

36

PeterWalserの回答に同意できないことをお詫び申し上げます。方程式を解くと私の机になります：

u = ((bs.y - as.y) * bd.x - (bs.x - as.x) * bd.y) / (bd.x * ad.y - bd.y * ad.x)
v = ((bs.y - as.y) * ad.x - (bs.x - as.x) * ad.y) / (bd.x * ad.y - bd.y * ad.x)

一般的な用語を除外すると、これは次のようになります。

dx = bs.x - as.x
dy = bs.y - as.y
det = bd.x * ad.y - bd.y * ad.x
u = (dy * bd.x - dx * bd.y) / det
v = (dy * ad.x - dx * ad.y) / det

5つの減算、6つの乗算、2つの除算。

光線が交差するかどうかだけを知る必要がある場合は、uとvの符号で十分であり、これら2つの分割は、何に応じてnum * denom <0または（sign（num）！= sign（denom））に置き換えることができます。ターゲットマシンでより効率的です。

det == 0のまれなケースは、光線が交差しないことを意味することに注意してください（1つの追加の比較）。

于 2010-05-28T21:18:04.733 に答える
30

与えられたもの：2つの光線a、b、開始点（原点ベクトル）as、bs、および方向ベクトルad、bd。

交点pがある場合、2本の線は交差します。

p = as + ad * u
p = bs + bd * v

この連立方程式にu>=0およびv>=0の解がある場合（正の方向が光線になります）、光線は交差します。

2Dベクトルのx/y座標の場合、これは次のことを意味します。

p.x = as.x + ad.x * u
p.y = as.y + ad.y * u
p.x = bs.x + bd.x * v
p.y = bs.y + bd.y * v

さらなるステップ：

as.x + ad.x * u = bs.x + bd.x * v
as.y + ad.y * u = bs.y + bd.y * v

vに対する解決：

v := (as.x + ad.x * u - bs.x) / bd.x

uに対する挿入と解決：

as.y + ad.y * u = bs.y + bd.y * ((as.x + ad.x * u - bs.x) / bd.x) 
u := (as.y*bd.x + bd.y*bs.x - bs.y*bd.x - bd.y*as.x ) / (ad.x*bd.y - ad.y*bd.x)

uを計算し、次にvを計算します。両方が正の場合は光線が交差し、そうでない場合は交差しません。

于 2010-05-28T18:52:44.037 に答える
3

光線は点のセットで表すことができますA + Vt。ここAで、は開始点、Vは光線の方向を示すベクトル、t >= 0はパラメータです。したがって、2つの光線が交差するかどうかを判断するには、次のようにします。

bool DoRaysIntersect(Ray r1, Ray r2)
{
    // Solve the following equations for t1 and t2:
    //   r1.A.x + r1.V.x * t1 == r2.A.x + r2.V.x * t2
    //   r1.A.y + r1.V.y * t1 == r2.A.y + r2.V.y * t2
    if(no solution)  // (e.g. parallel lines)
    {
        if(r1 == r2)  // same ray?
            return true;
        else
            return false;  // parallel, non-intersecting
    }
    else  // unique solution
    {
        if(t1 >= 0 && t2 >= 0)
            return true;
        else
            return false;  // they would intersect if they are lines, but they are not lines
    }
}
于 2010-05-28T18:54:45.113 に答える
2

ここでの他の回答に基づいて、2つの光線の交点を見つけようとしているときに、この投稿を見つけました。他の誰かが同じ答えを探してここに到着した場合に備えて、ここにTypeScript/JavaScriptの答えがあります。

/**
 * Get the intersection of two rays, with origin points p0 and p1, and direction vectors n0 and n1.
 * @param p0 The origin point of the first ray
 * @param n0 The direction vector of the first ray
 * @param p1 The origin point of the second ray
 * @param n1 The direction vector of the second ray
 * @returns
 */
export function getRaysIntersection(
  p0: number[],
  n0: number[],
  p1: number[],
  n1: number[]
): number[] | undefined {
  const dx = p1[0] - p0[0];
  const dy = p1[1] - p0[1];
  const det = n1[0] * n0[1] - n1[1] * n0[0];
  const u = (dy * n1[0] - dx * n1[1]) / det;
  const v = (dy * n0[0] - dx * n0[1]) / det;
  if (u < 0 || v < 0) return undefined; // Might intersect as lines, but as rays.

  const m0 = n0[1] / n0[0];
  const m1 = n1[1] / n1[0];
  const b0 = p0[1] - m0 * p0[0];
  const b1 = p1[1] - m1 * p1[0];
  const x = (b1 - b0) / (m0 - m1);
  const y = m0 * x + b0;

  return Number.isFinite(x) ? [x, y] : undefined;
}

ここでのデモ：https ：//codesandbox.io/s/intersection-of-two-rays-mcwst

于 2021-04-17T20:59:52.913 に答える
1

GeomAlgorithms.comには、3Dの線を処理する非常に優れたアルゴリズムがいくつかあります...しかし、一般的に言えば、2本の線が3D空間で交差する確率は非常に低いです。

2Dでは、勾配を確認する必要があります。勾配が等しくない場合、それらは交差します。勾配が等しい場合、それらの点が同じx座標または同じy座標を持っていれば、それらは交差します。

于 2010-05-28T18:40:18.153 に答える
1

線は点pとベクトルvで表されます。

line = p + a * v（すべてのaに対して）

光線はその線の（正の）半分です：

ray = p + a * v（すべてのa> = 0の場合）

2つの線が交差するかどうかを判断するには、それらを等しく設定して次のように解きます。

共通部分は、p 1 + a 1 * v 1 = p 2 + a 2 * v 2の場合に発生します（ p 'sとv 'sは複数であるため、2つの未知数a1とa2、および2つの方程式
があることに注意してください。次元）

1と2を解きます-両方が負でない場合、それらは交差します。1つが負の場合、それらは交差しません。

于 2010-05-28T18:55:55.737 に答える
1

GuntnersソリューションのC++

bool RaysIntersection(const Point& as, const Point& ad, const Point& bs, const Point& bd, Point& result)
{
    if (as == bs) {
        result = as;
        return true;
    }
    auto dx = bs.X - as.X;
    auto dy = bs.Y - as.Y;
    auto det = bd.X * ad.Y - bd.Y * ad.X;
    if (det != 0) { // near parallel line will yield noisy results
        double u = (dy * bd.X - dx * bd.Y) / (double)det;
        double v = (dy * ad.X - dx * ad.Y) / (double)det;
        if (u >= 0 && v >= 0) {
            result = as + ad * u;
            return true;
        }
    }
    return false;
}
于 2020-08-25T11:01:27.637 に答える
0

2つの光線が交差するかどうかだけを確認したい。2つの光線から作成された2つの「三角形」の回転方向を計算することによってそれについて説明します。それらは実際には三角形ではありませんが、数学的な観点から、三角形の回転を計算するだけの場合、共通の開始点を持つ2つのベクトルのみが必要であり、残りは重要ではありません。

最初の三角形は、2つのベクトルと開始点によって形成されます。開始点は、最初の光線の開始点になります。最初のベクトルは、最初の光線の方向ベクトルになります。2番目のベクトルは、最初の光線の開始点から2番目の光線の開始点までのベクトルになります。ここから、2つのベクトルの外積を取り、符号に注意します。

2番目の三角形に対してもこれを行います。ここでも、開始点は2番目の光線の開始点です。最初のベクトルは2番目の光線の方向であり、2番目のベクトルは2番目の光線の開始点から最初の光線の開始点までです。ベクトルの外積を再度取り、符号に注意します。

ここで、2つの記号を取得して、それらが同じであるかどうかを確認します。それらが同じである場合、交差点はありません。それらが異なる場合は、交差点があります。それでおしまい！

これがいくつかの疑似コードです：

sign1 = cross(vector1, point1 - point2)
sign2 = cross(vector2, point2 - point1)

if (sign1 * sign2 < 0) // If signs are mismatched, they will multiply to be negative
    return intersection

これは、5回の乗算、6回の減算、および1回の比較であることがわかります。

于 2010-05-28T19:02:03.383 に答える
-2

線の長さが無限である場合、平行でない限り、線は常に交差します。それらが平行であるかどうかを確認するには、各線の傾きを見つけて比較します。傾きは（y2-y1）/（x2-x1）になります。

于 2010-05-28T18:37:02.800 に答える