Формула для определения пересечения бесконечной линии и сегмента линии?

Question

Учитывая точку на линии и наклон этой линии, как бы определить, пересекает ли линия, проходящую в каждом направлении бесконечно, с отрезком линии (x1,y1), (x2,y2) и, если да, то точка, в которой происходит пересечение?

Я нашел это, но я не уверен, что он здесь полезен.
Если кто-то хочет помочь мне понять «лучи», со мной все в порядке. http://www.realtimerendering.com/intersections.html

Извините, что я идиот.

Answer 1

произвольной точке на первой линии имеет параметрическое уравнение

dx = Cos(slope) 
dy = Sin(Slope) 
x = x0 + t * dx  (1) 
y = y0 + t * dy 

линии, содержащей второй сегмент

dxx = x2 - x1 
dyy = y2 - y1 
x = x1 + u * dxx (2) 
y = y1 + u * dyy 

Пересечение существует, если линейная система

x0 + t * dx = x1 + u * dxx (3)  
y0 + t * dy = y1 + u * dyy 

имеет решение для неизвестных t и u
и u лежит в диапазоне [0..1]

Точка пересечения может быть вычислена с заменой u найденной в паре уравнения (2)

Answer 2

Что вы ищете, это dot product. Линию можно представить в виде вектора.

Если у вас есть две линии, они пересекут их в какой-то момент. За исключением случая, когда они параллельны.

Параллельные векторы а, б (как нормализованное) имеют скалярное произведение 1 (точки (а, б) = 1).

Если у вас есть начальный и конечный пункт линии я, то вы можете также построить вектор я легко.

Answer 3

Пожалуйста, не спрашивайте меня, чтобы объяснить, как именно это работает, я имею просто экстраполировал/переписал его из какого-то древнего кода, который у меня был. (Actionscript 1)

некоторые функции, чтобы построить объекты для этого примера:

function point(x, y){ 
    return {x, y} 
} 
function line(x0, y0, x1, y1){ 
    return { 
    start: point(x0, y0), 
    end: point(x1, y1) 
    } 
} 
function ray(x, y, vx, vy){ 
    return { 
    start: point(x, y), 
    vector: point(vx, vy) 
    } 
} 
function ray2(x, y, angle){ 
    var rad = angle * Math.PI/180; 
    return ray(x, y, Math.cos(rad), Math.sin(rad)); 
} 

пересечение-код:

//returns the difference vector between two points (pointB - pointA) 
function delta(a, b){ return point(b.x - a.x, b.y - a.y) } 
//kind of a 2D-version of the cross-product 
function cp(a, b){ return a.y * b.x - a.x * b.y } 

function intersection(a, b){ 
    var d21 = a.vector || delta(a.start, a.end), 
     d43 = b.vector || delta(b.start, b.end), 
     d13 = delta(b.start, a.start), 
     d = cp(d43, d21); 

    //rays are paralell, no intersection possible 
    if(!d) return null; 
    //if(!d) return { a, b, position: null, hitsA: false, hitsB: false }; 

    var u = cp(d13, d21)/d, 
     v = cp(d13, d43)/d; 

    return { 
     a, b, 

     //position of the intersection 
     position: point(
      a.start.x + d21.x * v, 
      a.start.y + d21.y * v 
     ), 
     //is position on lineA? 
     hitsA: v >= 0 && v <= 1, 
     //is position on lineB? 
     hitsB: u >= 0 && u <= 1, 

     timeTillIntersection: v, 
    }; 
} 

и пример:

var a = line(0, 0, 50, 50); 

var b = line(0, 50, 50, 0);    //lines are crossing 
console.log(intersection(a, b)); 

var c = line(100, 50, 150, 0);   //lines are not crossing 
console.log(intersection(a, c)); 

var d = line(100, -1000, 100, 1000); //intersection is only on d, not on a 
console.log(intersection(a, d)); 

var e = ray(100, 50, -1, -1);   //paralell to a 
console.log(intersection(a, e)); 

возвращает информацию о точке пересечения, а также о проходящих линиях/лучах. Не важно, чтобы вы проходили линии или лучи.

о timeTillIntersection: если первый аргумент/луч представляет собой шар/пуля/независимо от текущего положения и движения вектора, а второй аргумент представляет собой стену или так, то v, иначе timeTillIntersection определяет, сколько времени это занимает до этот шар пересекает/попадает в стену (в текущих условиях) в той же единице, что и для скорости шара. Поэтому вы в основном получаете некоторую информацию бесплатно.