两段算法之间的交集遗漏了交点

Question

我目前正在研究为小型 2D 游戏制作一个简单的阴影投射算法。在使用优化库之前，我想尽可能多地尝试一下。

我觉得我快到了，但出于某种原因，我用来检测线源光线与线段（障碍物或屏幕边缘的任一侧）之间的交点的方法似乎没有捕捉到所有碰撞。

我将错误缩小到这个函数，但我找不到其中的错误。我已经经历过很多次了，但仍然不明白为什么它并不总是有效。我所有的光线都延伸出屏幕，所以我至少应该检测到与屏幕边缘的碰撞。我还检查了算法是否循环遍历所有光线和线段。

这是检查碰撞的方法：

def check_col(self, ray, source):
    ''' 
    segment1 = (self.start,self.end)
    segment2 = (source.pos,ray.far_pt)'''
    X1,Y1 = self.start #start pt of segment 1
    X2,Y2 = self.end #end pt of segment 1
    X3,Y3 = source.pos #start pt of segment 2
    X4,Y4 = ray.far_pt #end pt of segment 2

    '''we are looking to express the segments as:
    A*x + b = y '''

    '''ensuring mutual abscisse exists'''
    if (max(X1,X2) < min(X3,X4)) or (min(X1,X2) > max(X3,X4))\
    or (max(Y1,Y2) < min(Y3,Y4)) or (min(Y1,Y2) > max(Y3,Y4)):
        return False,0 #no mutual abscisse, 0 added to return a tulpe

    '''ensures no division by 0
    when calculating the segment
    slopes A1 and A2'''
    if float(X1-X2) == 0:
        X1 +=0.1 #add a small increment to avoid difference to be null
    if  float(X3-X4) == 0:
        X3 += 0.1 #add a small increment to avoid difference to be null

    '''calculating segment slopes'''
    A1 = (Y1-Y2)/float(X1-X2) # Pay attention to not dividing by zero
    A2 = (Y3-Y4)/float(X3-X4) # Pay attention to not dividing by zero

    b1 = Y1-A1*X1# = Y2-A1*X2
    b2 = Y3-A2*X3# = Y4-A2*X4    

    '''if slopes are the same, offsets one slightly
    to avoid dividing by 0 later on'''
    if (A1 == A2):
        A1 += 0.0001

    '''finding out intersect between the two segments at (Xa,Ya)'''    
    #A1 * Xa + b1 = A2 * Xa + b2
    Xa = int((b2 - b1) / (A1 - A2))# Once again, pay attention to not dividing by zero
    Ya = int(A1 * Xa + b1)
    #Ya = int(A2 * Xa + b2)
    col_pt = (Xa,Ya)      

    '''make sure intersection is within bounds'''
    if max(min(X1,X2),min(X3,X4)) <= Xa <= min(max(X1,X2),max(X3,X4)):
            '''calculates distance between the light source and the collision point'''
            dist = sqrt((source.pos[0]-col_pt[0])**2+(source.pos[1]-col_pt[1])**2)
            return True,col_pt,dist
    else:
        return False,0 #0 added to return a tulpe

这里是一个屏幕截图，显示一些光线没有与蓝色障碍物或墙壁碰撞，而它们显然应该碰撞：

Answer 1

您的功能有缺陷 - 像 X1 +=0.1 这样的部分会导致奇怪的行为（在垂直段的末端附近很明显）。使用一些强大的实现，例如 this simple one
（Alexander Hristov。Java 但很容易理解）。

/**
 * Computes the intersection between two segments. 
 * @param x1 Starting point of Segment 1
 * @param y1 Starting point of Segment 1
 * @param x2 Ending point of Segment 1
 * @param y2 Ending point of Segment 1
 * @param x3 Starting point of Segment 2
 * @param y3 Starting point of Segment 2
 * @param x4 Ending point of Segment 2
 * @param y4 Ending point of Segment 2
 * @return Point where the segments intersect, or null if they don't
 */
public Point intersection(
    int x1,int y1,int x2,int y2, 
    int x3, int y3, int x4,int y4
) {
    int d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
    if (d == 0) return null;

    int xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
    int yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;

    Point p = new Point(xi,yi);
    if (xi < Math.min(x1,x2) || xi > Math.max(x1,x2)) return null;
    if (xi < Math.min(x3,x4) || xi > Math.max(x3,x4)) return null;
    return p;
}

另一个 very long discussion 在 SO。

注意有一些特殊的（更有效的）方法可以找到线与轴对齐框的边缘的交点（Line clipping). I'd recommend Liang-Barski one。

两段算法之间的交集遗漏了交点

Intersection between two segments algorithm misses out intersections

python

algorithm

pygame

shadow

python-2.7