line_segment_intersection_2021.py

# line_segments_intersection_2021.py
#
# 18_05_21


import sys
from tkinter import Tk, Canvas, Button, FIRST, LAST, ALL
from math import sqrt, isclose
import numpy as np

'''
DEFAULTS:
numpy.isclose(a, b, rtol=1e-05, atol=1e-08, equal_nan=False)

math.isclose(a, b, *, rel_tol=1e-09, abs_tol=0.0)
return abs(a-b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)
'''

class g: pass

# DIVIDE_PROTECT = sys.float_info.min # prone to causing overflow errors
DIVIDE_PROTECT = 1e-50


def main():

    g.window = Tk()

    g.inside_bx1 = g.inside_bx2 = g.inside_bx3 = g.inside_bx4 = False

    g.p1 = vec((617.0, 120.0))
    g.p2 = vec((700.0, 400.0))
    g.p3 = vec((200.0, 400.0))
    g.p4 = vec((1200.0, 100.0))

    g.window.title('line line intersection')
    g.window.configure(bg='gray3')

    sw, sh = g.window.winfo_screenwidth(), g.window.winfo_screenheight()

    g.window.geometry('%dx%d+%d+%d' % (sw, 1060, 0, 0))
    g.window.resizable(False, False)

    canvas_width, canvas_height = 1900, 1040
    g.canvas = Canvas(g.window, width=canvas_width, height=canvas_height,
        bg='black', border=5, relief='raised')
    g.canvas.grid(columnspan=20, column=0, row=0, padx=(4,4), pady=(4,4))

    g.segment = True
    g.cross = False
    def keypressed(e):
        if e.char.lower() == 's':
            g.segment = not g.segment
            refresh_canvas()
        elif e.char.lower() == 'c':
            g.cross = not g.cross
            refresh_canvas()
    g.window.bind('<Key>', lambda e: keypressed(e))

    g.canvas.bind('<Button-1>', buttondown)
    g.canvas.bind('<B1-Motion>', mousemoving)
    g.canvas.bind('<ButtonRelease-1>', buttonup)

    g.window.bind('<Return>', lambda _: sys.exit())
    g.window.bind('<Escape>', lambda _: sys.exit())
    g.window.protocol('WM_DELETE_WINDOW', lambda: sys.exit())

    refresh_canvas()
    g.window.mainloop()


def line_segment_intersection(p1, p2, p3, p4):
    """
    cf. Geometry for Computer Graphics by John Vince, p. 49

    Given four endpoints of two line segments:
    return:
    possible point of intersection, or None if lines are parallel
    there is an intersection of line segments (boolean),
    lines are parallel (boolean)
    lines are at a right angle (boolean)
    """

    a = p2 - p1
    b = p4 - p3
    c = p3 - p1

    select = 1

    if select == 0:
        D = (a.x * b.y - a.y * b.x) + DIVIDE_PROTECT

    if select == 1:
        D = vec.det(a, b) + DIVIDE_PROTECT

    if select == 2:
        D = np.linalg.det((a.get, b.get)) + DIVIDE_PROTECT

    if 0:
        if isclose(D, 0.0, abs_tol=1e-03):  # if -1000 <= D <= 1000:
            # LINES ARE PARALLEL
            return None, False, True, False

    select = 3

    if select == 0:
        ε = (a.y * (p3.x - p1.x) - a.x * (p3.y - p1.y)) / D
        λ = (b.y * (p3.x - p1.x) - b.x * (p3.y - p1.y)) / D

    if select == 1:
        ax, ay = p2 - p1
        bx, by = p4 - p3
        cx, cy = p3 - p1
        ε = (ay * cx - ax * cy) / D
        λ = (by * cx - bx * cy) / D

    if select == 2:
        ε = (a.y * c.x - a.x * c.y) / D
        λ = (b.y * c.x - b.x * c.y) / D

    if select == 3:
        ε = -vec.det(a, c) / D
        λ = -vec.det(b, c) / D

    # intersection of extended lines
    p = p1 + λ * (p2 - p1)
    q = p3 + ε * (p4 - p3)
    if not vec.areclose(p, q):
        print('intersection discrepancy!')

    intersects = True
    if g.segment:
        if not (0.0 <= λ <= 1.0 and 0.0 <= ε <= 1.0):
            intersects = False

    u = vec.norm(p2 - p1)
    v = vec.norm(p4 - p3)

    if 1:
        g.d = vec.det(u, v)
    else:
        g.d = np.linalg.det((u.get, v.get))

    if 1:
        if isclose(g.d, 0.0, abs_tol=1e-2):
            # LINES ARE PARALLEL
            return None, False, True, False

    right = True if isclose(abs(g.d), 1.0, abs_tol=1e-05) else False

    return p, intersects, False, right


def buttondown(e):

    (x1,y1, x2,y2) = g.canvas.coords(g.bx1)
    if x1 < e.x < x2 and y1 < e.y < y2:
        g.bx1_lastx, g.bx1_lasty = e.x, e.y
        g.inside_bx1 = True
        g.window.config(cursor = 'hand2')
        return

    (x1,y1, x2,y2) = g.canvas.coords(g.bx2)
    if x1 < e.x < x2 and y1 < e.y < y2:
        g.bx2_lastx, g.bx2_lasty = e.x, e.y
        g.inside_bx2 = True
        g.window.config(cursor = 'hand2')
        return

    (x1,y1, x2,y2) = g.canvas.coords(g.bx3)
    if x1 < e.x < x2 and y1 < e.y < y2:
        g.bx3_lastx, g.bx3_lasty = e.x, e.y
        g.inside_bx3 = True
        g.window.config(cursor = 'hand2')
        return

    (x1,y1, x2,y2) = g.canvas.coords(g.bx4)
    if x1 < e.x < x2 and y1 < e.y < y2:
        g.bx4_lastx, g.bx4_lasty = e.x, e.y
        g.inside_bx4 = True
        g.window.config(cursor = 'hand2')
        return


def mousemoving(e):

    if g.inside_bx1:
        g.p1.x += e.x - g.bx1_lastx
        g.p1.y += e.y - g.bx1_lasty
        refresh_canvas()
        g.bx1_lastx, g.bx1_lasty = e.x, e.y

    elif g.inside_bx2:
        g.p2.x += e.x - g.bx2_lastx
        g.p2.y += e.y - g.bx2_lasty
        refresh_canvas()
        g.bx2_lastx, g.bx2_lasty = e.x, e.y

    elif g.inside_bx3:
        g.p3.x += e.x - g.bx3_lastx
        g.p3.y += e.y - g.bx3_lasty
        refresh_canvas()
        g.bx3_lastx, g.bx3_lasty = e.x, e.y

    elif g.inside_bx4:
        g.p4.x += e.x - g.bx4_lastx
        g.p4.y += e.y - g.bx4_lasty
        refresh_canvas()
        g.bx4_lastx, g.bx4_lasty = e.x, e.y


def buttonup(e):

    g.inside_bx1 = g.inside_bx2 = g.inside_bx3 = g.inside_bx4 = False
    g.window.config(cursor = '')

def refresh_canvas():

    p, intersects, parallel, right = line_segment_intersection(g.p1, g.p2, g.p3, g.p4)

    line_color = 'red' if parallel or right else 'blue'

    font = 'Verdana 20 normal'

    x0 = g.window.winfo_screenwidth()/2

    txt1 = 'Left click and hold end of line segment to drag to a new position.'
    txt2 = 'Press S to toggle segment detection.'
    txt3 = 'Press C to toggle cross3d test'
    txt4 = 'Esc or Enter exits.'
    txt5 = 'normalized determinant = ' + '{0:.3f}'.format(g.d)

    (x1, y1), (x2, y2), (x3, y3), (x4, y4) = g.p1, g.p2, g.p3, g.p4

    ####################
    g.canvas.delete(ALL)
    ####################

    g.canvas.create_text(x0, 870, text=txt1, font=font, fill='gray25')
    g.canvas.create_text(x0, 910, text=txt2, font=font, fill='gray25')
    g.canvas.create_text(x0, 950, text=txt3, font=font, fill='gray25')
    g.canvas.create_text(x0, 990, text=txt4, font=font, fill='gray25')

    g.canvas.create_line(x1, y1, x2, y2, width=1, fill=line_color)
    g.canvas.create_line(x3, y3, x4, y4, width=1, fill=line_color)

    r = 8
    g.bx1 = g.canvas.create_oval(bbox((x1, y1), r), width=0, fill=line_color,
        outline=line_color)

    g.bx2 = g.canvas.create_oval(bbox((x2, y2), r), width=0, fill=line_color,
        outline=line_color)

    g.bx3 = g.canvas.create_oval(bbox((x3, y3), r), width=0, fill=line_color,
        outline=line_color)

    g.bx4 = g.canvas.create_oval(bbox((x4, y4), 7), width=0, fill=line_color,
        outline=line_color)

    g.canvas.create_text(20, 30, text=txt5, font=font, fill='blue', anchor='w')

    font = 'Verdana 14 normal'
    fill = 'grey30'
    g.canvas.create_text(g.p1.x+20, g.p1.y, text='p1', font=font,
        fill=fill, anchor='w')
    g.canvas.create_text(g.p2.x+20, g.p2.y, text='p2', font=font,
        fill=fill, anchor='w')
    g.canvas.create_text(g.p3.x+20, g.p3.y, text='p3', font=font,
        fill=fill, anchor='w')
    g.canvas.create_text(g.p4.x+20, g.p4.y, text='p4', font=font,
        fill=fill, anchor='w')

    if g.cross:
        c = vec.cross3d((x2-x1, y2-y1, 0.0), (0.0, 0.0, 1.0))
        w = g.p1 + c
        g.canvas.create_line(g.p1.x, g.p1.y, w.x, w.y, tag='tag',
            width=1, fill='grey56', arrow=LAST)
        g.canvas.tag_lower('tag')

    if intersects:
        b = bbox(p, 7)
        tag = g.canvas.create_oval(b, width=1, fill='red', outline='yellow')
        g.canvas.tag_raise(tag)


def bbox(p, r):
    return p[0]-r, p[1]-r, p[0]+r, p[1]+r



from math import sqrt, isclose

class vec:
    """Selected modified methods from a minimalist 2d vector class"""

    def __init__(self, t=(0.0, 0.0)):
        self.x, self.y = t

    def __str__(self):
        return '({}, {})'.format(self.x, self.y)

    def __repr__(self):
        return __class__.__name__ + '(({}, {}))'.format(self.x, self.y)

    @property
    def get(self):
        return self.x, self.y

    @property
    def copy(self):
        return self

    def __getitem__(self, i):
        return (self.x, self.y)[i]

    def __setitem__(self, i, n):
        if i == 0: self.x = n
        elif i == 1: self.y = n
        else: raise IndexError

    def __add__(self, other):
        if isinstance(other, (int, float)):
            return vec((self.x + other, self.y + other))
        else:
            return vec((self.x + other.x, self.y + other.y))

    def __sub__(self, other):
        if isinstance(other, (int, float)):
            return vec((self.x - other, self.y - other))
        else:
            return vec((self.x - other.x, self.y - other.y))

    def __mul__(self, other):
        if isinstance(other, (int, float)):
            return vec((self.x * other, self.y * other))
        else:
            return vec((self.x * other.x, self.y * other.y))

    def __rmul__(self, other):
        if isinstance(other, (int, float)):
            return vec((other * self.x, other * self.y))
        else:
            return vec((other.x * self.x, other.y * self.y))

    def __truediv__(self, other):
        if isinstance(other, (int, float)):
            return vec((self.x / other, self.y / other))
        else:
            return vec((self.x / other.x, self.y / other.y))

    @staticmethod
    def norm(v):
        return v / (sqrt(sum(v*v)) + DIVIDE_PROTECT)

    @staticmethod
    def det(u, v):
        return u.x * v.y - u.y * v.x


    @staticmethod
    def cross3d(u, v):
        """
        cross product:
        u = 3dvector(a, b, c)
        v = 3dvector(d, e, f)
        3dcross(u, v) = (bf - ce, cd - af, ae - bd)
        return (bf - ce, cd - af)
        """
        x = u[1]*v[2] - u[2]*v[1]
        y = u[2]*v[0] - u[0]*v[2]
        return vec((x, y))

    @staticmethod
    def cross(u, v):
        return u.x * v.y - u.y * v.x


    """
    return u[0] * v[0] + u[1] * v[1]
    583 ns ± 1.37 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

    return u.x * v.x + u.y * v.y
    183 ns ± 0.28 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
    """

    @staticmethod
    def dot(u, v):
        return u[0] * v[0] + u[1] * v[1]

    @staticmethod
    def fasterdot(u, v):
        return u.x * v.x - u.y * v.y


    def npdot(self, u, v=None):
        # d = a.npdot(b) = vec.npdot(a, b)
        if v == None:
            return self.x * u.x + self.y * u.y
        return u.x * v.x + u.y * v.y


    def areclose(u, v):
        if (isclose(u.x, v.x) and isclose(u.y, v.y)):
            return True
        return False



if __name__ == '__main__':
    sys.exit(main())