pygame is
Python
Simple DirectMedia Layer
 
 
pygame.org is
Site Swing
Wiki

IntersectingLineDetection

      
Search:  
 
 

Here's some functions that I wrote to help with collision detection in a retro arcade remake of Asteroids using Python and Pygame. Some simple assertion tests are included at the bottom.

Features:

  • Calculate the point of intersection of two line segments
  • Handles lines segments rather than just infinitely long lines
  • Handles vertical lines (infinite gradient)
  • Handles horizontal lines (zero gradient)
  • Handles parallel lines (never intersect)
  • Calculate line gradients
  • Calculate Y axis intersect point

    The entry point for an intersect test is the getIntersectPoint function.

    #    geometry.py
    #
    #    Geometry functions to find intersecting lines.
    #    Thes calc's use this formula for a straight line:-
    #        y = mx + b where m is the gradient and b is the y value when x=0
    #
    #    See here for background http://www.mathopenref.com/coordintersection.html
    #    
    #    Throughout the code the variable p is a point tuple representing (x,y)
    #
    #    Copyright (C) 2008  Nick Redshaw
    #
    #    This program is free software: you can redistribute it and/or modify
    #    it under the terms of the GNU General Public License as published by
    #    the Free Software Foundation, either version 3 of the License, or
    #    (at your option) any later version.
    #
    #    This program is distributed in the hope that it will be useful,
    #    but WITHOUT ANY WARRANTY; without even the implied warranty of
    #    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    #    GNU General Public License for more details.
    #
    #    You should have received a copy of the GNU General Public License
    #    along with this program.  If not, see .
     
    from __future__ import division
    from pygame import Rect
     
    # Calc the gradient 'm' of a line between p1 and p2
    def calculateGradient(p1, p2):
      
       # Ensure that the line is not vertical
       if (p1[0] != p2[0]):
           m = (p1[1] - p2[1]) / (p1[0] - p2[0])
           return m
       else:
           return None
     
    # Calc the point 'b' where line crosses the Y axis
    def calculateYAxisIntersect(p, m):
       return  p[1] - (m * p[0])
     
    # Calc the point where two infinitely long lines (p1 to p2 and p3 to p4) intersect.
    # Handle parallel lines and vertical lines (the later has infinate 'm').
    # Returns a point tuple of points like this ((x,y),...)  or None
    # In non parallel cases the tuple will contain just one point.
    # For parallel lines that lay on top of one another the tuple will contain
    # all four points of the two lines
    def getIntersectPoint(p1, p2, p3, p4):
       m1 = calculateGradient(p1, p2)
       m2 = calculateGradient(p3, p4)
          
       # See if the the lines are parallel
       if (m1 != m2):
           # Not parallel
          
           # See if either line is vertical
           if (m1 is not None and m2 is not None):
               # Neither line vertical           
               b1 = calculateYAxisIntersect(p1, m1)
               b2 = calculateYAxisIntersect(p3, m2)   
               x = (b2 - b1) / (m1 - m2)       
               y = (m1 * x) + b1           
           else:
               # Line 1 is vertical so use line 2's values
               if (m1 is None):
                   b2 = calculateYAxisIntersect(p3, m2)   
                   x = p1[0]
                   y = (m2 * x) + b2
               # Line 2 is vertical so use line 1's values               
               elif (m2 is None):
                   b1 = calculateYAxisIntersect(p1, m1)
                   x = p3[0]
                   y = (m1 * x) + b1           
               else:
                   assert false
                  
           return ((x,y),)
       else:
           # Parallel lines with same 'b' value must be the same line so they intersect
           # everywhere in this case we return the start and end points of both lines
           # the calculateIntersectPoint method will sort out which of these points
           # lays on both line segments
           b1, b2 = None, None # vertical lines have no b value
           if m1 is not None:
               b1 = calculateYAxisIntersect(p1, m1)
              
           if m2 is not None:   
               b2 = calculateYAxisIntersect(p3, m2)
          
           # If these parallel lines lay on one another   
           if b1 == b2:
               return p1,p2,p3,p4
           else:
               return None
     
    # For line segments (ie not infinitely long lines) the intersect point
    # may not lay on both lines.
    #   
    # If the point where two lines intersect is inside both line's bounding
    # rectangles then the lines intersect. Returns intersect point if the line
    # intesect o None if not
    def calculateIntersectPoint(p1, p2, p3, p4):
      
       p = getIntersectPoint(p1, p2, p3, p4)
      
       if p is not None:               
           width = p2[0] - p1[0]
           height = p2[1] - p1[1]       
           r1 = Rect(p1, (width , height))
           r1.normalize()
          
           width = p4[0] - p3[0]
           height = p4[1] - p3[1]
           r2 = Rect(p3, (width, height))
           r2.normalize()              
     
           # Ensure both rects have a width and height of at least 'tolerance' else the
           # collidepoint check of the Rect class will fail as it doesn't include the bottom
           # and right hand side 'pixels' of the rectangle
           tolerance = 1
            if r1.width < tolerance:
                r1.width = tolerance
                        
            if r1.height < tolerance:
                r1.height = tolerance
            
            if r2.width < tolerance:
                r2.width = tolerance
                        
            if r2.height < tolerance:
                r2.height = tolerance
     
            for point in p:                 
                try:    
                    res1 = r1.collidepoint(point)
                    res2 = r2.collidepoint(point)
                    if res1 and res2:
                        point = [int(pp) for pp in point]                                
                        return point
                except:
                    # sometimes the value in a point are too large for PyGame's Rect class
                    str = "point was invalid  ", point                
                    print str
                    
            # This is the case where the infinately long lines crossed but 
            # the line segments didn't
            return None            
        
        else:
            return None
            
            
    # Test script below...
    if __name__ == "__main__":
     
        # line 1 and 2 cross, 1 and 3 don't but would if extended, 2 and 3 are parallel
        # line 5 is horizontal, line 4 is vertical
        p1 = (1,5)
        p2 = (4,7)
        
        p3 = (4,5)
        p4 = (3,7)
        
        p5 = (4,1)
        p6 = (3,3)
        
        p7 = (3,1)
        p8 = (3,10)
        
        p9 =  (0,6)
        p10 = (5,6)
        
        p11 = (472.0, 116.0)
        p12 = (542.0, 116.0)  
        
        assert None != calculateIntersectPoint(p1, p2, p3, p4), "line 1 line 2 should intersect"
        assert None != calculateIntersectPoint(p3, p4, p1, p2), "line 2 line 1 should intersect"
        assert None == calculateIntersectPoint(p1, p2, p5, p6), "line 1 line 3 shouldn't intersect"
        assert None == calculateIntersectPoint(p3, p4, p5, p6), "line 2 line 3 shouldn't intersect"
        assert None != calculateIntersectPoint(p1, p2, p7, p8), "line 1 line 4 should intersect"
        assert None != calculateIntersectPoint(p7, p8, p1, p2), "line 4 line 1 should intersect"
        assert None != calculateIntersectPoint(p1, p2, p9, p10), "line 1 line 5 should intersect"
        assert None != calculateIntersectPoint(p9, p10, p1, p2), "line 5 line 1 should intersect"
        assert None != calculateIntersectPoint(p7, p8, p9, p10), "line 4 line 5 should intersect"
        assert None != calculateIntersectPoint(p9, p10, p7, p8), "line 5 line 4 should intersect"
        
        print "\nSUCCESS! All asserts passed for doLinesIntersect"
  • spotlight

     
    our projects
    pygame.org welcomes all python game, art, music, sound, video and multimedia projects. If they use pygame or not.
     
    recent releases
    Aug 22, 2014

    Aug 21, 2014


    Aug 19, 2014

    Aug 18, 2014

    Aug 2, 2014


    Jul 28, 2014

    Jul 22, 2014

    Jul 21, 2014

    Jul 20, 2014

    Jul 19, 2014

    ... more!
     
    for pygame related questions, comments, and suggestions, please see help (lists, irc)