我正在尝试找到一种优化的算法，用于查找（无限）线和线段之间是否存在交集 .
在SO和其他网站上我看过很多线段 - 线段交叉点和线 - 线交叉算法，但却发现'更简单？'一条无限线（从一个方向上的一个点）和一个线段的版本非常难 .
我目前有类似的东西（线段 - 线段交叉点）：
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]（这可以用作常数），如果这使数学更容易，我认为它可能 .
然后我检查光线是否与每个线段相交，如果是奇数，则它在形状内 .
我正在考虑的一些事情：
如果我们决定总是直射射线，那么如果线段的两个点都低于该点，我们就知道它不相交 .
1 回答
参见Hormann和Agathos，“The point in polygon problem for arbitrary polygons”，Computational Geometry 20（2001）131-144 . 为了有效实现绕组算法 .