mechanizmos58

line_segment_intersection_2021.py

May 17th, 2021
1,238
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. # line_segments_intersection_2021.py
  3. #
  4. # 18_05_21
  5.  
  6.  
  7. import sys
  8. from tkinter import Tk, Canvas, Button, FIRST, LAST, ALL
  9. from math import sqrt, isclose
  10. import numpy as np
  11.  
  12. '''
  13. DEFAULTS:
  14. numpy.isclose(a, b, rtol=1e-05, atol=1e-08, equal_nan=False)
  15.  
  16. math.isclose(a, b, *, rel_tol=1e-09, abs_tol=0.0)
  17. return abs(a-b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)
  18. '''
  19.  
  20. class g: pass
  21.  
  22. # DIVIDE_PROTECT = sys.float_info.min # prone to causing overflow errors
  23. DIVIDE_PROTECT = 1e-50
  24.  
  25.  
  26. def main():
  27.  
  28.     g.window = Tk()
  29.  
  30.     g.inside_bx1 = g.inside_bx2 = g.inside_bx3 = g.inside_bx4 = False
  31.  
  32.     g.p1 = vec((617.0, 120.0))
  33.     g.p2 = vec((700.0, 400.0))
  34.     g.p3 = vec((200.0, 400.0))
  35.     g.p4 = vec((1200.0, 100.0))
  36.  
  37.     g.window.title('line line intersection')
  38.     g.window.configure(bg='gray3')
  39.  
  40.     sw, sh = g.window.winfo_screenwidth(), g.window.winfo_screenheight()
  41.  
  42.     g.window.geometry('%dx%d+%d+%d' % (sw, 1060, 0, 0))
  43.     g.window.resizable(False, False)
  44.  
  45.     canvas_width, canvas_height = 1900, 1040
  46.     g.canvas = Canvas(g.window, width=canvas_width, height=canvas_height,
  47.         bg='black', border=5, relief='raised')
  48.     g.canvas.grid(columnspan=20, column=0, row=0, padx=(4,4), pady=(4,4))
  49.  
  50.     g.segment = True
  51.     g.cross = False
  52.     def keypressed(e):
  53.         if e.char.lower() == 's':
  54.             g.segment = not g.segment
  55.             refresh_canvas()
  56.         elif e.char.lower() == 'c':
  57.             g.cross = not g.cross
  58.             refresh_canvas()
  59.     g.window.bind('<Key>', lambda e: keypressed(e))
  60.  
  61.     g.canvas.bind('<Button-1>', buttondown)
  62.     g.canvas.bind('<B1-Motion>', mousemoving)
  63.     g.canvas.bind('<ButtonRelease-1>', buttonup)
  64.  
  65.     g.window.bind('<Return>', lambda _: sys.exit())
  66.     g.window.bind('<Escape>', lambda _: sys.exit())
  67.     g.window.protocol('WM_DELETE_WINDOW', lambda: sys.exit())
  68.  
  69.     refresh_canvas()
  70.     g.window.mainloop()
  71.  
  72.  
  73. def line_segment_intersection(p1, p2, p3, p4):
  74.     """
  75.    cf. Geometry for Computer Graphics by John Vince, p. 49
  76.  
  77.    Given four endpoints of two line segments:
  78.    return:
  79.    possible point of intersection, or None if lines are parallel
  80.    there is an intersection of line segments (boolean),
  81.    lines are parallel (boolean)
  82.    lines are at a right angle (boolean)
  83.    """
  84.  
  85.     a = p2 - p1
  86.     b = p4 - p3
  87.     c = p3 - p1
  88.  
  89.     select = 1
  90.  
  91.     if select == 0:
  92.         D = (a.x * b.y - a.y * b.x) + DIVIDE_PROTECT
  93.  
  94.     if select == 1:
  95.         D = vec.det(a, b) + DIVIDE_PROTECT
  96.  
  97.     if select == 2:
  98.         D = np.linalg.det((a.get, b.get)) + DIVIDE_PROTECT
  99.  
  100.     if 0:
  101.         if isclose(D, 0.0, abs_tol=1e-03):  # if -1000 <= D <= 1000:
  102.             # LINES ARE PARALLEL
  103.             return None, False, True, False
  104.  
  105.     select = 3
  106.  
  107.     if select == 0:
  108.         ε = (a.y * (p3.x - p1.x) - a.x * (p3.y - p1.y)) / D
  109.         λ = (b.y * (p3.x - p1.x) - b.x * (p3.y - p1.y)) / D
  110.  
  111.     if select == 1:
  112.         ax, ay = p2 - p1
  113.         bx, by = p4 - p3
  114.         cx, cy = p3 - p1
  115.         ε = (ay * cx - ax * cy) / D
  116.         λ = (by * cx - bx * cy) / D
  117.  
  118.     if select == 2:
  119.         ε = (a.y * c.x - a.x * c.y) / D
  120.         λ = (b.y * c.x - b.x * c.y) / D
  121.  
  122.     if select == 3:
  123.         ε = -vec.det(a, c) / D
  124.         λ = -vec.det(b, c) / D
  125.  
  126.     # intersection of extended lines
  127.     p = p1 + λ * (p2 - p1)
  128.     q = p3 + ε * (p4 - p3)
  129.     if not vec.areclose(p, q):
  130.         print('intersection discrepancy!')
  131.  
  132.     intersects = True
  133.     if g.segment:
  134.         if not (0.0 <= λ <= 1.0 and 0.0 <= ε <= 1.0):
  135.             intersects = False
  136.  
  137.     u = vec.norm(p2 - p1)
  138.     v = vec.norm(p4 - p3)
  139.  
  140.     if 1:
  141.         g.d = vec.det(u, v)
  142.     else:
  143.         g.d = np.linalg.det((u.get, v.get))
  144.  
  145.     if 1:
  146.         if isclose(g.d, 0.0, abs_tol=1e-2):
  147.             # LINES ARE PARALLEL
  148.             return None, False, True, False
  149.  
  150.     right = True if isclose(abs(g.d), 1.0, abs_tol=1e-05) else False
  151.  
  152.     return p, intersects, False, right
  153.  
  154.  
  155. def buttondown(e):
  156.  
  157.     (x1,y1, x2,y2) = g.canvas.coords(g.bx1)
  158.     if x1 < e.x < x2 and y1 < e.y < y2:
  159.         g.bx1_lastx, g.bx1_lasty = e.x, e.y
  160.         g.inside_bx1 = True
  161.         g.window.config(cursor = 'hand2')
  162.         return
  163.  
  164.     (x1,y1, x2,y2) = g.canvas.coords(g.bx2)
  165.     if x1 < e.x < x2 and y1 < e.y < y2:
  166.         g.bx2_lastx, g.bx2_lasty = e.x, e.y
  167.         g.inside_bx2 = True
  168.         g.window.config(cursor = 'hand2')
  169.         return
  170.  
  171.     (x1,y1, x2,y2) = g.canvas.coords(g.bx3)
  172.     if x1 < e.x < x2 and y1 < e.y < y2:
  173.         g.bx3_lastx, g.bx3_lasty = e.x, e.y
  174.         g.inside_bx3 = True
  175.         g.window.config(cursor = 'hand2')
  176.         return
  177.  
  178.     (x1,y1, x2,y2) = g.canvas.coords(g.bx4)
  179.     if x1 < e.x < x2 and y1 < e.y < y2:
  180.         g.bx4_lastx, g.bx4_lasty = e.x, e.y
  181.         g.inside_bx4 = True
  182.         g.window.config(cursor = 'hand2')
  183.         return
  184.  
  185.  
  186. def mousemoving(e):
  187.  
  188.     if g.inside_bx1:
  189.         g.p1.x += e.x - g.bx1_lastx
  190.         g.p1.y += e.y - g.bx1_lasty
  191.         refresh_canvas()
  192.         g.bx1_lastx, g.bx1_lasty = e.x, e.y
  193.  
  194.     elif g.inside_bx2:
  195.         g.p2.x += e.x - g.bx2_lastx
  196.         g.p2.y += e.y - g.bx2_lasty
  197.         refresh_canvas()
  198.         g.bx2_lastx, g.bx2_lasty = e.x, e.y
  199.  
  200.     elif g.inside_bx3:
  201.         g.p3.x += e.x - g.bx3_lastx
  202.         g.p3.y += e.y - g.bx3_lasty
  203.         refresh_canvas()
  204.         g.bx3_lastx, g.bx3_lasty = e.x, e.y
  205.  
  206.     elif g.inside_bx4:
  207.         g.p4.x += e.x - g.bx4_lastx
  208.         g.p4.y += e.y - g.bx4_lasty
  209.         refresh_canvas()
  210.         g.bx4_lastx, g.bx4_lasty = e.x, e.y
  211.  
  212.  
  213. def buttonup(e):
  214.  
  215.     g.inside_bx1 = g.inside_bx2 = g.inside_bx3 = g.inside_bx4 = False
  216.     g.window.config(cursor = '')
  217.  
  218. def refresh_canvas():
  219.  
  220.     p, intersects, parallel, right = line_segment_intersection(g.p1, g.p2, g.p3, g.p4)
  221.  
  222.     line_color = 'red' if parallel or right else 'blue'
  223.  
  224.     font = 'Verdana 20 normal'
  225.  
  226.     x0 = g.window.winfo_screenwidth()/2
  227.  
  228.     txt1 = 'Left click and hold end of line segment to drag to a new position.'
  229.     txt2 = 'Press S to toggle segment detection.'
  230.     txt3 = 'Press C to toggle cross3d test'
  231.     txt4 = 'Esc or Enter exits.'
  232.     txt5 = 'normalized determinant = ' + '{0:.3f}'.format(g.d)
  233.  
  234.     (x1, y1), (x2, y2), (x3, y3), (x4, y4) = g.p1, g.p2, g.p3, g.p4
  235.  
  236.     ####################
  237.     g.canvas.delete(ALL)
  238.     ####################
  239.  
  240.     g.canvas.create_text(x0, 870, text=txt1, font=font, fill='gray25')
  241.     g.canvas.create_text(x0, 910, text=txt2, font=font, fill='gray25')
  242.     g.canvas.create_text(x0, 950, text=txt3, font=font, fill='gray25')
  243.     g.canvas.create_text(x0, 990, text=txt4, font=font, fill='gray25')
  244.  
  245.     g.canvas.create_line(x1, y1, x2, y2, width=1, fill=line_color)
  246.     g.canvas.create_line(x3, y3, x4, y4, width=1, fill=line_color)
  247.  
  248.     r = 8
  249.     g.bx1 = g.canvas.create_oval(bbox((x1, y1), r), width=0, fill=line_color,
  250.         outline=line_color)
  251.  
  252.     g.bx2 = g.canvas.create_oval(bbox((x2, y2), r), width=0, fill=line_color,
  253.         outline=line_color)
  254.  
  255.     g.bx3 = g.canvas.create_oval(bbox((x3, y3), r), width=0, fill=line_color,
  256.         outline=line_color)
  257.  
  258.     g.bx4 = g.canvas.create_oval(bbox((x4, y4), 7), width=0, fill=line_color,
  259.         outline=line_color)
  260.  
  261.     g.canvas.create_text(20, 30, text=txt5, font=font, fill='blue', anchor='w')
  262.  
  263.     font = 'Verdana 14 normal'
  264.     fill = 'grey30'
  265.     g.canvas.create_text(g.p1.x+20, g.p1.y, text='p1', font=font,
  266.         fill=fill, anchor='w')
  267.     g.canvas.create_text(g.p2.x+20, g.p2.y, text='p2', font=font,
  268.         fill=fill, anchor='w')
  269.     g.canvas.create_text(g.p3.x+20, g.p3.y, text='p3', font=font,
  270.         fill=fill, anchor='w')
  271.     g.canvas.create_text(g.p4.x+20, g.p4.y, text='p4', font=font,
  272.         fill=fill, anchor='w')
  273.  
  274.     if g.cross:
  275.         c = vec.cross3d((x2-x1, y2-y1, 0.0), (0.0, 0.0, 1.0))
  276.         w = g.p1 + c
  277.         g.canvas.create_line(g.p1.x, g.p1.y, w.x, w.y, tag='tag',
  278.             width=1, fill='grey56', arrow=LAST)
  279.         g.canvas.tag_lower('tag')
  280.  
  281.     if intersects:
  282.         b = bbox(p, 7)
  283.         tag = g.canvas.create_oval(b, width=1, fill='red', outline='yellow')
  284.         g.canvas.tag_raise(tag)
  285.  
  286.  
  287. def bbox(p, r):
  288.     return p[0]-r, p[1]-r, p[0]+r, p[1]+r
  289.  
  290.  
  291.  
  292. from math import sqrt, isclose
  293.  
  294. class vec:
  295.     """Selected modified methods from a minimalist 2d vector class"""
  296.  
  297.     def __init__(self, t=(0.0, 0.0)):
  298.         self.x, self.y = t
  299.  
  300.     def __str__(self):
  301.         return '({}, {})'.format(self.x, self.y)
  302.  
  303.     def __repr__(self):
  304.         return __class__.__name__ + '(({}, {}))'.format(self.x, self.y)
  305.  
  306.     @property
  307.     def get(self):
  308.         return self.x, self.y
  309.  
  310.     @property
  311.     def copy(self):
  312.         return self
  313.  
  314.     def __getitem__(self, i):
  315.         return (self.x, self.y)[i]
  316.  
  317.     def __setitem__(self, i, n):
  318.         if i == 0: self.x = n
  319.         elif i == 1: self.y = n
  320.         else: raise IndexError
  321.  
  322.     def __add__(self, other):
  323.         if isinstance(other, (int, float)):
  324.             return vec((self.x + other, self.y + other))
  325.         else:
  326.             return vec((self.x + other.x, self.y + other.y))
  327.  
  328.     def __sub__(self, other):
  329.         if isinstance(other, (int, float)):
  330.             return vec((self.x - other, self.y - other))
  331.         else:
  332.             return vec((self.x - other.x, self.y - other.y))
  333.  
  334.     def __mul__(self, other):
  335.         if isinstance(other, (int, float)):
  336.             return vec((self.x * other, self.y * other))
  337.         else:
  338.             return vec((self.x * other.x, self.y * other.y))
  339.  
  340.     def __rmul__(self, other):
  341.         if isinstance(other, (int, float)):
  342.             return vec((other * self.x, other * self.y))
  343.         else:
  344.             return vec((other.x * self.x, other.y * self.y))
  345.  
  346.     def __truediv__(self, other):
  347.         if isinstance(other, (int, float)):
  348.             return vec((self.x / other, self.y / other))
  349.         else:
  350.             return vec((self.x / other.x, self.y / other.y))
  351.  
  352.     @staticmethod
  353.     def norm(v):
  354.         return v / (sqrt(sum(v*v)) + DIVIDE_PROTECT)
  355.  
  356.     @staticmethod
  357.     def det(u, v):
  358.         return u.x * v.y - u.y * v.x
  359.  
  360.  
  361.     @staticmethod
  362.     def cross3d(u, v):
  363.         """
  364.        cross product:
  365.        u = 3dvector(a, b, c)
  366.        v = 3dvector(d, e, f)
  367.        3dcross(u, v) = (bf - ce, cd - af, ae - bd)
  368.        return (bf - ce, cd - af)
  369.        """
  370.         x = u[1]*v[2] - u[2]*v[1]
  371.         y = u[2]*v[0] - u[0]*v[2]
  372.         return vec((x, y))
  373.  
  374.     @staticmethod
  375.     def cross(u, v):
  376.         return u.x * v.y - u.y * v.x
  377.  
  378.  
  379.     """
  380.    return u[0] * v[0] + u[1] * v[1]
  381.    583 ns ± 1.37 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
  382.  
  383.    return u.x * v.x + u.y * v.y
  384.    183 ns ± 0.28 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
  385.    """
  386.  
  387.     @staticmethod
  388.     def dot(u, v):
  389.         return u[0] * v[0] + u[1] * v[1]
  390.  
  391.     @staticmethod
  392.     def fasterdot(u, v):
  393.         return u.x * v.x - u.y * v.y
  394.  
  395.  
  396.     def npdot(self, u, v=None):
  397.         # d = a.npdot(b) = vec.npdot(a, b)
  398.         if v == None:
  399.             return self.x * u.x + self.y * u.y
  400.         return u.x * v.x + u.y * v.y
  401.  
  402.  
  403.     def areclose(u, v):
  404.         if (isclose(u.x, v.x) and isclose(u.y, v.y)):
  405.             return True
  406.         return False
  407.  
  408.  
  409.  
  410. if __name__ == '__main__':
  411.     sys.exit(main())
  412.  
  413.  
RAW Paste Data