射线与线段相交问题

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;
}

来源

然而，我不确定作者在这里所说的长度是什么意思，因为评论只是定义了叉积，并没有定义长度函数。

我的实现方式类似，但由于我不知道他所说的长度是什么意思，所以我只是在那里进行叉积运算。问题是，线段似乎被视为射线，因为我得到了不应该出现的交点，除非我正在相交射线。例如，一条穿过矩形中心的射线会报告通过其他矩形（我现在循环遍历线）的交点，它不应该与之相交。

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

这是我期望发生的事情和我认为正在发生的事情的粗略图示：

图示

- eliw00d

Answer 1

几年前，我在我的简单绘图项目中使用了这个算法。我找到了这个算法并根据我的需求进行了调整。希望它能在某种程度上对你有所帮助。

            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/

- vortex

Answer 2

事实证明问题并不在算法上，而是在我的代码中出现了其他错误。我花了一些时间才找到问题所在，但一旦解决，算法就完美地运行了。

- eliw00d