如果确定两条射线相交 [英] Determining if two rays intersect

问题描述

我有一个2D平面延伸到无穷两条射线，但两者都有一个起点。它们都是由一个起点和在延伸到无穷远的光线的方向的向量描述。我想了解，如果两条射线相交，但是我并不需要知道它们相交（这是一个碰撞检测算法的一部分）。

I have two rays on a 2D plane that extend to infinity, but both have a starting point. They are both described by a starting point and a vector in the direction of the ray extending to infinity. I want to find out if the two rays intersect, but I don't need to know where they intersect (it's part of a collision detection algorithm).

一切我已经看过到目前为止介绍找到交集的两条线或线段点。是否有一个快速的算法来解决这个问题？

Everything I have looked at so far describes finding the intersection point of two lines or line segments. Is there a fast algorithm to solve this?

推荐答案

假设：两条射线A，B与起点（原点矢量），BS和方向向量的广告，BD

Given: two rays a, b with starting points (origin vectors) as, bs, and direction vectors ad, bd.

这两条线相交，如果有一个交点号码：

The two lines intersect if there is an intersection point p:

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

如果该方程系统有一个解决方案为U> = 0和v> = 0（正方向是什么使他们射线），该射线相交

If this equation system has a solution for u>=0 and v>=0 (the positive direction is what makes them rays), the rays intersect.

有关二维向量的x / y坐标，这意味着：

For the x/y coordinates of the 2d vectors, this means:

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

进一步的步骤：

Further steps:

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

解决对五：

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

插入和解决对U：

Inserting and solving against 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，如果两个都是正的射线相交，否则不行。

Calculate u, then calculate v, if both are positive the rays intersect, else not.

这篇关于如果确定两条射线相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！