射线到线段相交

Question

我在光线与线段相交方面遇到了问题。我正在用 Lua 编写代码，但任何语言的示例也很有用。

我这周的大部分时间都在寻找可以作为我的基础的算法或现有函数，前几天我遇到了这个：

bool RayLineSegmentIntersection( const vec2 &o, const vec2 &d, const vec2 &a, const vec2 &b )
{
    vec2 ortho( -d.y, d.x );
    vec2 aToO( o - a );
    vec2 aToB( b - a );

    float denom = dot( aToB, ortho );

    // Here would be a good time to see if denom is zero in which case the line segment and
    // the ray are parallel.

    // The length of this cross product can also be written as aToB.x * aToO.y - aToO.x * aToB.y.
    float t1 = length( cross( aToB, aToO ) ) / denom;
    float t2 = dot( aToO, ortho ) / denom;

    return t2 >= 0 && t2 <= 1 && t1 >= 0;
}

Source

但是我不太清楚作者所说的长度是什么意思，因为注释只是定义了叉积，并没有定义函数长度。

我的实现是类似的，但由于我不知道他说的长度是什么意思，所以我就直接乘叉积了。问题是线段似乎被视为射线，因为除非我与射线相交，否则我得到的交叉点是不可能的。例如，一条直线穿过矩形中心的射线报告了它不应该相交的其他矩形的交点（我现在循环遍历线）。

有没有更好的方法来解决这个问题，或者缺失的长度函数是否可以解决这个问题？

这是我预期会发生的事情以及我认为正在发生的事情的粗略图：

Drawing

Answer 1

几年前我在我的简单 drawnig 项目中使用过这个。我找到了这个算法并根据我的需要进行了调整。希望对你有所帮助。

            public virtual bool IsPointInPolygon(PointF[] polygon, PointF point)
            {
                bool isInside = false;
                for (int i = 0, j = polygon.Length - 1; i < polygon.Length; j = i++)
                {
                    if (((polygon[i].Y > point.Y) != (polygon[j].Y > point.Y)) &&
                    (point.X < (polygon[j].X - polygon[i].X) * (point.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) + polygon[i].X))
                    {
                        isInside = !isInside;
                    }
                }
                return isInside;
            }

这是我认为的来源 - http://alienryderflex.com/polygon/

Answer 2

原来问题不是算法，而是我代码中其他地方的错误。我花了一段时间才弄明白，但一旦我弄明白了，算法就完美无缺了。

射线到线段相交

Ray to Line Segment Intersection

lua

intersection

segment