c++ - 点からの無限直線 (一方向) が 2D の線分と交差するかどうかを判断する

Question

(無限) 線と線分の間に交点が存在するかどうかを見つけるために最適化されたアルゴリズムを見つけようとしています。

ここSOおよび他のサイトで、私は多くの線分 - 線分の交点と線 - 線の交点アルゴリズムを見てきましたが、「より単純ですか？」1 つの無限線 (一方向の点から) と線分のバージョンは非常に困難です。

私は現在（線分 - 線分の交点）のようなものを持っています：

bool lineSegmentsIntersect(float pX, float pY, float p2X, float p2Y, float qX, float qY, float q2X, float q2Y)
{
    // p and p2 define the first line segment
    Point2D p(pX, pY);
    Point2D p2(p2X, p2Y);

    // q and q2 define the second line segment
    Point2D q(qX, qY);
    Point2D q2(q2X, q2Y);

    Point2D r = p2 - p;
    Point2D s = q2 - q;

    float uNumerator = (q-p)*r;
    float denominator = r*s;

    if (uNumerator == 0 && denominator == 0) {
        // co-linear, so do they overlap?
        return ((q.x - p.x < 0) != (q.x - p2.x < 0) != (q2.x - p.x < 0) != (q2.x - p2.x < 0)) ||
            ((q.y - p.y < 0) != (q.y - p2.y < 0) != (q2.y - p.y < 0) != (q2.y - p2.y < 0));
    }

    if (denominator == 0) {
        // lines are parallel
        return false;
    }

    float u = uNumerator / denominator;
    float t = ((q-p)*s) / denominator;

    return (t >= 0) && (t <= 1) && (u >= 0) && (u <= 1);

}

* 演算子は次のように定義されます。

float Point2D::operator*(const Point2D &rhs)
{
    return x*rhs.y - y*rhs.x;
}

私はもっ​​とシンプルで速いものを探していますが。ポイントが閉じた形状内にあるかどうかを確認しようとしています (形状は、いくつかのポイントとそれらの間の (線形補間) 直線によって定義されます)。

その点から、あらかじめ決められた方向に光線を放ちます。

できれば [1, 0] または [0, 1] (これは与えられた定数として使用できます) それが数学をより簡単にするなら、私はそう思うかもしれません。

次に、光線が各線分と交差するかどうかを確認し、それが奇数の場合は形状の内側にあります。

私が考えているいくつかのこと：

光線を常に真上に向けると決めた場合、線分の両方の点がその点より下にあれば、交差しないことがすでにわかっています。