1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

""" 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()