""" Line-line intersection algorithm """
# vector class from pygame cookbook http://www.pygame.org/wiki/2DVectorClass
from vec2d import *
def lineline(A,B,C,D):
""" Line-line intersection algorithm,
returns point of intersection or None
"""
# ccw from http://www.bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
def ccw(A,B,C):
return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)
if ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D):
# formula from http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
ua = float(((D.x-C.x)*(A.y-C.y))-((D.y-C.y)*(A.x-C.x)))/ \
float(((D.y-C.y)*(B.x-A.x))-((D.x-C.x)*(B.y-A.y)))
ub = float(((B.x-A.x)*(A.y-C.y))-((B.y-A.y)*(A.x-C.y)))/ \
float(((D.y-C.y)*(B.x-A.x))-((D.x-C.x)*(B.y-A.y)))
return vec2d( A.x+(ua*(B.x-A.x)), \
A.y+(ua*(B.y-A.y)))
return None
def linelinedemo():
""" Graphical demo showing the line line intersection algorithm.
Click and hold left mouse button to place first line,
right mouse button places second line.
A white circle will be draw at the point of intersection.
"""
import pygame
from pygame.locals import QUIT,KEYDOWN,MOUSEBUTTONDOWN,MOUSEBUTTONUP
pygame.init()
screen = pygame.display.set_mode((256,256))
clock = pygame.time.Clock()
A,B,C,D = None,None,None,None
running = True
while running:
for event in pygame.event.get():
if event.type in (QUIT, KEYDOWN):
running = False
elif event.type == MOUSEBUTTONDOWN and event.button == 1:
A = vec2d(pygame.mouse.get_pos())
B = None
elif event.type == MOUSEBUTTONDOWN and event.button == 3:
C = vec2d(pygame.mouse.get_pos())
D = None
elif event.type == MOUSEBUTTONUP and event.button == 1:
B = vec2d(pygame.mouse.get_pos())
elif event.type == MOUSEBUTTONUP and event.button == 3:
D = vec2d(pygame.mouse.get_pos())
screen.fill((0,0,0))
if A is not None:
endpos = B or pygame.mouse.get_pos()
pygame.draw.line(screen, (255,0,0), A, endpos)
if C is not None:
endpos = D or pygame.mouse.get_pos()
pygame.draw.line(screen, (0,255,0), C, endpos)
if A and B and C and D:
v = lineline(A,B,C,D)
if v:
pygame.draw.circle(screen, (255,255,255), (int(v.x),int(v.y)), 5, 1)
pygame.display.flip()
clock.tick(100)
if __name__=="__main__":
linelinedemo()
Refactorings
No refactoring yet !
Line-line intersection algorithm with graphical demo.