检测线与多边形的交点数

Question

我已经在信号处理堆栈交换上问过这个问题，但没有得到任何答案。你是我唯一的希望 StackOverflow。请帮忙谢谢：

作为数学论文的一部分，我正在编写一个程序来检测用输入的形状绘制的线的交点。

例如，在下面的形状中，多边形是给定大小的输入图像。光线已从多边形内部开始绘制到多边形上。如何检测光线穿过多边形边界的次数。

此外，多边形始终是闭合多边形。

请看这里的图片：

我最初想到的一个想法是用与边框相同的颜色（黑色）填充多边形。然后计算光线遇到黑色然后遇到白色的次数。

我对这种方法的问题是我真的不知道如何沿着一条线追踪并检查每个点，而且我猜测沿着这条线连续检查将是一个非常昂贵的过程。

我现在正在使用 Processing 3，但我可以使用除 MatLab 之外的任何其他软件/平台，因为我现在无法访问它。

Answer 1

如果您有一条由点P和归一化方向R定义的无限线Q和由点和方向定义的第二条无限线，则无限线S的交点X为：

alpha ... angle between Q-P and R
beta  ... angle between R and S

gamma  =  180° - alpha - beta

h  =  | Q - P | * sin(alpha)
u  =  h / sin(beta)

t  = | Q - P | * sin(gamma) / sin(beta)

t  =  dot(Q-P, (S.y, -S.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, S)) / determinant(mat2(R, S))
u  =  dot(Q-P, (R.y, -R.x)) / dot(R, (S.y, -S.x))  =  determinant(mat2(Q-P, R)) / determinant(mat2(R, S))

X  =  P + R * t  =  Q + S * u

_{另见找到与方向无关的两个向量的交点}

如果你有一个 ine from l1p1tol1p2和第二行 from l2p1to l2p2then：

P = l1p1
Q = l2p1;
R = normalize(l1p2 - l1p1)
S = normalize(l2p2 - l2p1)

normalize计算向量的单位向量。单位向量的长度为 1。

由于线不是无限的，您必须评估交点是否在线段上。计算线的长度，以及从连线起点到交点的距离。验证距离（由点积计算）是否大于 >= 0 且 <= 线的长度。
在下面的

P = l1p1
Q = l2p1;
R = normalize(l1p2 - l1p1)
S = normalize(l2p2 - l2p1)

这可以通过使用 计算PVector，如下所示：

len1 = | l1p2 - l1p1 |
len2 = | l2p2 - l2p1 |

distOnL1 = dot(X - P, R);
distOnL2 = dot(X - Q, S);

intersecting = distOnL1 >= 0 AND distOnL1 <= len1 AND distOnL2 >= 0 AND distOnL2 <= len2

函数的返回值类型为TIntersection。属性valid是true如果有交点并且线不平行。pointtype的属性PVector是交点，如果有的话。

看例子：

class TIntersection {
   boolean valid = false;
   PVector point = new PVector(0.0, 0.0);
}

// Intersect 2 endless  lines
// line 1: line segment from `l1p1` to `l1p2`
// line 2: line segment from `l2p1` to `l2p2`
TIntersection Intersect(PVector l1p1, PVector l1p2, PVector l2p1, PVector l2p2) {

    PVector P = l1p1;
    PVector Q = l2p1;
    PVector R = PVector.sub(l1p2, l1p1);
    PVector S = PVector.sub(l2p2, l2p1);
    float   len1 = R.mag();
    float   len2 = S.mag();
    R.normalize();
    S.normalize();

    PVector QP  = PVector.sub(Q, P);
    PVector SNV = new PVector(S.y, -S.x);  
    TIntersection isect = new TIntersection();
    float t =  QP.dot(SNV) / R.dot(SNV); 
    isect.point = PVector.add(P, PVector.mult(R, t));

    if (!Float.isInfinite(isect.point.x) || !Float.isInfinite(isect.point.y)) {
        float distOnL1 = PVector.sub(isect.point, P).dot(R);
        float distOnL2 = PVector.sub(isect.point, Q).dot(S);
        isect.valid = distOnL1 >= 0.0 && distOnL1 <= len1 && distOnL2 >= 0.0 && distOnL2 <= len2; 
    } else {
        isect.valid = false; 
    }
    return isect;
}