Ray到Line Segment Intersection

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

几年前，我在我的简单绘图项目中使用了这个。我找到了这个算法，并根据我的需要进行调整。我希望它会以某种方式帮助你。

            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

事实证明问题不是算法，而是我的代码中的其他地方的错误。我花了一段时间来弄清楚它，但是一旦我做了算法就完美了。