Intersection entre deux segments L'algorithme passe à côté des intersections

Question

Je suis en train d'étudier la possibilité de créer un algorithme de coulée d'ombre simple pour un petit jeu 2D. Autant que possible, je voudrais essayer moi-même avant d'utiliser des librairies optimisées. Je me sens comme je suis presque là mais pour une raison quelconque, la méthode que j'utilise pour détecter l'intersection entre le rayon de ma source de ligne et un segment (de chaque côté d'un obstacle ou bord d'écran) ne semble pas capturer tous les collisions.

Je ai réduit l'erreur à cette fonction, mais je ne trouve pas l'erreur en elle. Je l'ai traversé de nombreuses fois et n'arrive toujours pas à comprendre pourquoi cela ne fonctionne pas toujours. Tous mes rayons sortent de l'écran et je devrais au moins détecter une collision avec les bords de l'écran. J'ai également vérifié que l'algorithme circulait dans tous les rayons et segments.

C'est la méthode de vérification des collisions:

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 

Et voici une capture d'écran montrant que certains rayons ne sont pas entrer en collision avec l'obstacle bleu ou le mur quand ils doivent clairement:

Answer 1

Votre fonction est défectueuse - des pièces comme X1 +=0.1 provoquent un comportement étrange (il est clair que les extrémités des segments verticaux sont proches). Utilisez une implémentation robuste comme this simple one
(Alexander Hristov Java mais facile à comprendre).

/** 
* 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; 
} 

Un autre very long discussion à SO.

Remarque il existe des méthodes spéciales (plus efficaces) destinées à trouver l'intersection de la ligne avec les bords de la boîte alignée sur l'axe (Line clipping). Je recommande Liang-Barski one.