2. Graphical Interface and Zoning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Graphical Interface and Zoning\n",
    "This jupyter noteboo will focus on the following:\n",
    "1. Using the `tkinter` library to create a graphical interface\n",
    "2. Tracing a polygon to draw Voronoi cells\n",
    "3. Calculate the Voronoi diagram to allow the construction of a netwokr without any interferances. Each Voronoi zone will be controlled by different frequencies to ensure the control and communication between the parcel distribution drones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# importing\n",
    "import tkinter as tk\n",
    "from Trie import *\n",
    "from math import sqrt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this part, we will be using the trie graph to search our database. Look at the jupyter notebook `1. Indexing` for more details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "database = generate_database(100)\n",
    "tree = database_to_trie(database)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below makes a window that allows us to search for all 'zones' that begin with a user entered text. On running the code, a window like the image below should open up.\n",
    "![Search window](images/search_window.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def onButtonSearch():\n",
    "    global results_listbox\n",
    "    global textbox\n",
    "    global tree\n",
    "    results_listbox.delete(0, tk.END)\n",
    "    print(tree)\n",
    "    _, result = list(find_prefix(tree, textbox.get()))\n",
    "    textbox.delete(0, tk.END)\n",
    "    for e in result:\n",
    "        results_listbox.insert(tk.END, e)\n",
    "\n",
    "window = tk.Tk()\n",
    "\n",
    "search_frame = tk.Frame(window, borderwidth=2)\n",
    "search_frame.pack(side=tk.TOP)\n",
    "\n",
    "textbox = tk.Entry(search_frame, width=32)\n",
    "textbox.pack(side=tk.LEFT, padx=5, pady=5)\n",
    "\n",
    "search_button = tk.Button(search_frame, text=\"Search\", command=onButtonSearch, height=\"2\")\n",
    "search_button.pack(side=tk.RIGHT, padx=5, pady=5)\n",
    "\n",
    "results_listbox = tk.Listbox(window)\n",
    "results_listbox.pack(padx=5, pady=5)\n",
    "\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we make a canvas to draw the zones and point. The functions below will help in drawing points and polygons to split the 2D coordinate space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "marginx = 20\n",
    "canvas_len = 600\n",
    "\n",
    "def draw_cartesian(canvas):\n",
    "    global marginx\n",
    "    canvas.create_line(marginx, canvas_len, marginx + canvas_len, canvas_len, arrow=\"last\")\n",
    "    canvas.create_line(marginx, canvas_len, 20, 0, arrow=\"last\")\n",
    "    canvas.create_text(marginx, canvas_len+10, text=\"(0,0)\")\n",
    "    canvas.create_text(canvas_len+10, canvas_len+10, text=\"x\")\n",
    "    canvas.create_text(10, 5, text=\"y\")\n",
    "\n",
    "def canvas_point(P):\n",
    "    '''Convert (x,y) coordinates to the canvas coordinates'''\n",
    "    global marginx\n",
    "    return P[0] + marginx, canvas_len - P[1]\n",
    "\n",
    "def cross(u, v):\n",
    "    w = [0, 0, 0]\n",
    "    w[0] = u[1] * v[2] - u[2] * v[1]\n",
    "    w[1] = u[2] * v[0] - u[0] * v[2]\n",
    "    w[2] = u[0] * v[1] - u[1] * v[0]\n",
    "    return w\n",
    "\n",
    "def to_left(pxmin, pxmax, p):\n",
    "    pxVec3D = [pxmax[0] - pxmin[0],pxmax[1] - pxmin[1],0]\n",
    "    pVec3D = [p[0] - pxmax[0], p[1] - pxmax[1], 0]\n",
    "    result = cross(pxVec3D, pVec3D)\n",
    "    return (result[2] >= 0)\n",
    "\n",
    "def get_x_min(poly):\n",
    "    L = sorted(poly)\n",
    "    return L[0]\n",
    "\n",
    "def get_x_max(poly):\n",
    "    L = sorted(poly)\n",
    "    return L[-1]\n",
    "\n",
    "def points_left(pxmin, pxmax, poly):\n",
    "    L = []\n",
    "    for p in poly:\n",
    "        if to_left(pxmin, pxmax, p) and p != pxmax and p != pxmin:\n",
    "            L.append(p)\n",
    "    return L\n",
    "\n",
    "def points_right(pxmin, pxmax, poly):\n",
    "    L = []\n",
    "    for p in poly:\n",
    "        if to_left(pxmin, pxmax, p) == False and p != pxmax and p != pxmin:\n",
    "            L.append(p)\n",
    "    return L\n",
    "\n",
    "def tri_polygone(poly):\n",
    "    '''Returns the points of a polygon sorted\n",
    "    in the correct order to draw a convex polygon'''\n",
    "    if(len(poly) == 0):\n",
    "        return []\n",
    "    pxmin = get_x_min(poly)\n",
    "    pxmax = get_x_max(poly)\n",
    "    LG = sorted(points_left(pxmin, pxmax, poly), reverse=1)\n",
    "    LD = sorted(points_right(pxmin, pxmax, poly))\n",
    "    return [pxmin] + LD + [pxmax] + LG\n",
    "\n",
    "def draw_polygon(canvas, points):\n",
    "    '''Draws a polygon on the screen'''\n",
    "    if(len(points) == 0):\n",
    "        return\n",
    "    temp = []\n",
    "    for p in points:\n",
    "        temp.append(canvas_point(p))\n",
    "    poly = tri_polygone(temp)\n",
    "    canvas.create_polygon(poly, fill=\"skyblue\")\n",
    "    for i in range(0, len(poly)):\n",
    "        p1i = i % len(poly)\n",
    "        p2i = (i + 1) % len(poly)\n",
    "        canvas.create_line(poly[p1i], poly[p2i], fill=\"darkgreen\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "window = tk.Tk()\n",
    "\n",
    "canvas = tk.Canvas(window, width=620, height=620)\n",
    "draw_cartesian(canvas)\n",
    "\n",
    "p01 = (20,50)\n",
    "p02 = (70,220)\n",
    "p03 = (250,190)\n",
    "p04 = (300,150)\n",
    "p05 = (150,20)\n",
    "poly0 = [p01, p02, p03, p04, p05]\n",
    "\n",
    "p11 = (100,0)\n",
    "p12 = (0,100)\n",
    "p13 = (250,550)\n",
    "p14 = (350,150)\n",
    "p15 = (450,450)\n",
    "poly1 = [p11, p12, p13, p14, p15]\n",
    "\n",
    "p21 = (100,0)\n",
    "p22 = (0,100)\n",
    "p23 = (200,100)\n",
    "p24 = (100,200)\n",
    "p25 = (90,50)\n",
    "p26 = (300,300)\n",
    "p27 = (400,0)\n",
    "poly2 = [p21, p22, p23, p24, p25, p24, p25, p26, p27]\n",
    "poly0m = tri_polygone(poly0)\n",
    "poly1m = tri_polygone(poly1)\n",
    "poly2m = tri_polygone(poly2)\n",
    "\n",
    "draw_polygon(canvas, poly0m)\n",
    "draw_polygon(canvas, poly1m)\n",
    "draw_polygon(canvas, poly2m)\n",
    "\n",
    "canvas.pack(padx=10, pady=10)\n",
    "\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Should give the output:\n",
    "![Ouput of above example run](images/polygons.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Voronoi Diagrams\n",
    "A voronoi diagram can be defined as a set of germs (points in space), which can be associated with a set of cells (polygons). Therefore, a voronoi diagram is implemented as:\n",
    "\n",
    "`voronoi_diagram = [ (germ0, cell0), (germ1, cell1), ... ] `"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "voronoi_diagram = [\n",
    "  ((351, 205),[ (214.23833962665532, 253.1386746795724),\n",
    "                (299.54702329594477, 275.4167385677308),\n",
    "                (408.01388888888886, 175.62722222222226),\n",
    "                (393.6515397082658, 106.11345218800648),\n",
    "                (366.34635483752254, 92.67307621536082) ]),\n",
    "  ((541, 104),[]),\n",
    "  ((449, 460),[]),\n",
    "  ((255, 114),[]),\n",
    "  ((496,  65),[]),\n",
    "  ((498, 296),[]),\n",
    "  ((479, 542),[]),\n",
    "  ((186, 569),[]),\n",
    "  ((375, 524),[]),\n",
    "  ((236, 448),[ (175.11498194945847, 493.6714801444043),\n",
    "                (278.0491051942384, 536.206241815801),\n",
    "                (300.4867582148112, 495.1689553702796),\n",
    "                (298.96055776892433, 457.0139442231076),\n",
    "                (213.7531365313653, 383.2767527675277) ]),\n",
    "  ((  3, 566),[]),\n",
    "  ((446,  12),[]),\n",
    "  ((310, 362),[ (183.6344062635929, 259.92583732057415),\n",
    "                (196.76223972988186, 294.7824985931345),\n",
    "                (328.3383541513593, 407.00918442321824),\n",
    "                (412.731848983543, 353.8725395288802),\n",
    "                (402.7564102564102, 325.45765345765335),\n",
    "                (299.54702329594477, 275.4167385677308),\n",
    "                (214.23833962665526, 253.1386746795724) ]),\n",
    "  ((374, 230),[ (299.54702329594477, 275.4167385677308),\n",
    "                (402.7564102564102, 325.4576534576536),\n",
    "                (444.4714240606252, 247.08399115882537),\n",
    "                (408.01388888888886, 175.62722222222226) ]),\n",
    "  ((496, 195),[]),\n",
    "  ((281, 396),[ (196.7622397298818, 294.7824985931345),\n",
    "                (213.75313653136533, 383.2767527675277),\n",
    "                (298.9605577689243, 457.01394422310756),\n",
    "                (328.3383541513593, 407.00918442321824) ]),\n",
    "  ((117,  69),[]),\n",
    "  ((361, 443),[ (298.9605577689243, 457.0139442231066),\n",
    "                (300.4867582148112, 495.1689553702796),\n",
    "                (399.8827285921625, 477.9894049346881),\n",
    "                (422.162037340321, 362.6612184736323),\n",
    "                (412.73184898354305, 353.8725395288803),\n",
    "                (328.3383541513592, 407.00918442321824) ]),\n",
    "  ((156, 420),[]),\n",
    "  ((472, 180),[ (393.6515397082658, 106.11345218800648),\n",
    "                (408.01388888888886, 175.62722222222214),\n",
    "                (444.4714240606252, 247.08399115882537),\n",
    "                (447.13283208020044, 246.4874686716792),\n",
    "                (510.28803777544596, 145.43913955928645),\n",
    "                (485.326705940108, 122.77687776141386),\n",
    "                (400.44403303902016, 105.06223298205637) ])\n",
    "  ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def draw_voronoi(canvas, diagram):\n",
    "    for i in range(0, len(diagram)):\n",
    "        cell = diagram[i][1]\n",
    "        germ = canvas_point(diagram[i][0])\n",
    "        draw_polygon(canvas, cell)\n",
    "        canvas.create_text(germ[0], germ[1], text=\"P\" + str(i))\n",
    "\n",
    "window = tk.Tk()\n",
    "\n",
    "canvas = tk.Canvas(window, width=620, height=620)\n",
    "draw_cartesian(canvas)\n",
    "\n",
    "draw_voronoi(canvas, voronoi_diagram)\n",
    "canvas.pack(padx=10, pady=10)\n",
    "\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Output window: ![Vornoi example output](images/voronoi_ex.jpg)\n",
    "Going forward, we will be using code from antoher library from this project, `graphic_library.py`. It has the following functions:\n",
    "\n",
    " - `belongs(diagram, point)`: Takes a voronoi diagram and a 2D point to be inserted, and returns the cell to which the point belongs to.\n",
    " - `perp_bisector(point1, point2)`: Returns the perpendicular bisector between two point, in the form of `(slope, point)`.\n",
    " - `intersection_segment(line, point1, point2)`: returns the point of intersection between `line` and the line formed by `point1` and `point2`. Returns `None` if the two lines do not intersect.\n",
    " \n",
    " ### Insertion of new germ into Voronoi diagram\n",
    " Adding a new germ to the voronoi diagram involves the following steps:\n",
    " 1. Determine the cell $C_p$ that the new germ $P_{n+1}$ belongs to\n",
    " 2. Determine the perpendicular bisector between $P_{n+1}$ and germ $P_p$ of the cell $C_p$\n",
    " 3. Determine the intersection points $S_0$ and $S_1$ of the bisector with the borders of the cell $C_p$ and the ends $a_0$ and $a_1$\n",
    " 4. Add $S_0$ in the list of vertices of cells $C_{n+1}$ and $C_p$\n",
    " 5. Add $S_1$ in the list of vertices of cell $C_p$\n",
    " 6. Determine the germ $P_i$ of cell linked to $C_p$ by the end $a_1$\n",
    " 7. Remove from $C_p$ the vertices between $S_0$ and $S_1$ that fall inside the new cell $C_{n+1}$\n",
    " 8. Loop to step 2 with the cell $C_i$ and continue until back to $S_0$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import graphic_library as gl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n",
      "((22, -20), (300.0, 351.0))\n",
      "[{'a': ((196.76223972988186, 294.7824985931345), (328.3383541513593, 407.00918442321824)), 's': (281.9309559939302, 367.4264036418817)}, {'a': ((299.54702329594477, 275.4167385677308), (402.7564102564102, 325.45765345765335)), 's': (354.0652173913043, 301.84980237154144)}]\n"
     ]
    }
   ],
   "source": [
    "def find_intersection(diagram, cellNumber, bisection):\n",
    "    '''Returns the two ends of the cell that cuts the perpendicular bisector\n",
    "    and the coordinates of the points of intersection'''\n",
    "    diagram[cellNumber] = (diagram[cellNumber][0], tri_polygone(diagram[cellNumber][1]))\n",
    "    cell = diagram[cellNumber][1]\n",
    "    result = []\n",
    "    for i in range(0, len(cell)):\n",
    "        p1i = i % len(cell)\n",
    "        p2i = (i + 1) % len(cell)\n",
    "        s = gl.intersection_segment(bisection, cell[p1i], cell[p2i])\n",
    "        if s != None:\n",
    "            a0, a1 = tri_polygone([cell[p1i], cell[p2i]])\n",
    "            result.append({'a':((a0[0], a0[1]),(a1[0], a1[1])), 's':(s[0], s[1])})\n",
    "    return sorted(result, key=lambda i: i['s'][0])\n",
    "\n",
    "# to test find_intersection()\n",
    "P12 = (310, 362)\n",
    "P20 = (290, 340)\n",
    "print(gl.belongs(voronoi_diagram,P20))\n",
    "m = gl.perp_bisector(P12,P20)\n",
    "print(m)\n",
    "inter = find_intersection(voronoi_diagram,12,m)\n",
    "print(inter)\n",
    "\n",
    "window = tk.Tk()\n",
    "\n",
    "canvas = tk.Canvas(window, width=620, height=620)\n",
    "draw_cartesian(canvas)\n",
    "\n",
    "draw_voronoi(canvas, voronoi_diagram)\n",
    "canvas.pack(padx=10, pady=10)\n",
    "a0_0 = canvas_point(inter[1]['a'][0])\n",
    "a0_1 = canvas_point(inter[1]['a'][1])\n",
    "s0 = canvas_point(inter[1]['s'])\n",
    "\n",
    "canvas.create_text(a0_0[0], a0_0[1], text='a0')\n",
    "canvas.create_text(a0_1[0], a0_1[1], text='a0')\n",
    "canvas.create_text(s0[0], s0[1], text='s0')\n",
    "\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_neighbor(diagram, cellNumber, edge):\n",
    "    point = diagram[cellNumber][0]\n",
    "    ligne = ((edge[1][0] - edge[0][0], edge[1][1] - edge[0][1]), (edge[0][0], edge[0][1]))\n",
    "    return gl.belongs(diagram, gl.symmetric_point(ligne, point))\n",
    "\n",
    "def same_point(p1, p2):\n",
    "    return (sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2) <= gl.EPSILON)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "P12 = (310, 362)\n",
    "P20 = (290, 340)\n",
    "m = gl.perp_bisector(P12,P20)\n",
    "inter = find_intersection(voronoi_diagram,12,m)\n",
    "print(find_neighbor(voronoi_diagram,12,inter[0]['a']))\n",
    "print(find_neighbor(voronoi_diagram,12,inter[1]['a']))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def keep_good_points(poly, S0, S1, Pn1, Pp):\n",
    "    L = [S0, S1]\n",
    "    for p in poly:\n",
    "        if p != S0 and p != S1 and gl.carre_distance(p,Pn1) >= gl.carre_distance(p,Pp):\n",
    "            L.append(p)\n",
    "    T = tri_polygone(L)\n",
    "    return T\n",
    "\n",
    "def insert_germ(diagram, point):\n",
    "    cellNumber = gl.belongs(diagram, point)\n",
    "    diagram.append((point, []))\n",
    "    Pp = diagram[cellNumber][0]\n",
    "    bisection = gl.perp_bisector(Pp, point)\n",
    "    inter = find_intersection(diagram, cellNumber, bisection)\n",
    "    firstS0 = inter[0]['s']\n",
    "\n",
    "    S0 = inter[0]['s']\n",
    "    S1 = inter[1]['s']\n",
    "    a1 = inter[1]['a']\n",
    "\n",
    "    diagram[-1][1].append(S0)\n",
    "    diagram[cellNumber][1].append(S0)\n",
    "    diagram[cellNumber][1].append(S1)\n",
    "\n",
    "    PiNumber = find_neighbor(diagram, cellNumber, a1)\n",
    "\n",
    "    temp = diagram[cellNumber][1].copy()\n",
    "    diagram[cellNumber] = (diagram[cellNumber][0], keep_good_points(temp, S0, S1, point, Pp))\n",
    "\n",
    "    while not same_point(S1, firstS0):\n",
    "        Pp = diagram[PiNumber][0]\n",
    "\n",
    "        bisection = gl.perp_bisector(Pp, point)\n",
    "        inter = find_intersection(diagram, PiNumber, bisection)\n",
    "\n",
    "        newS0 = inter[0]['s']\n",
    "        newS1 = inter[1]['s']\n",
    "\n",
    "        if same_point(S0, newS0) or same_point(S1, newS1):\n",
    "            S0 = newS1\n",
    "            S1 = newS0\n",
    "            a1 = inter[0]['a']\n",
    "        else:\n",
    "            S0 = newS0\n",
    "            S1 = newS1\n",
    "            a1 = inter[1]['a']\n",
    "\n",
    "        diagram[-1][1].append(S0)\n",
    "        diagram[PiNumber][1].append(S0)\n",
    "        diagram[PiNumber][1].append(S1)\n",
    "\n",
    "        newPiNumber = find_neighbor(diagram, PiNumber, a1)\n",
    "\n",
    "#         temp = diagram[PiNumber][1].copy()\n",
    "#         diagram[PiNumber] = (diagram[PiNumber][0], keep_good_points(temp, S0, S1, point, Pp))\n",
    "        PiNumber = newPiNumber"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "diagram_test = [((150.0, 150.0), [(0, 0), (300.0, 0.0), (300.0, 262.5), (-0.0, 412.5)]),\n",
    "                        ((450.0, 150.0), [(300.0, 0.0), (600, 0), (600.0, 412.5), (300.0, 262.5)]),\n",
    "                        ((300.0, 450.0), [(300.0, 262.5), (600.0, 412.5), (-0.0, 412.5), (0, 600), (600, 600)])]\n",
    "\n",
    "insert_germ(diagram_test,(300,300))\n",
    "\n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=620, height=620)\n",
    "draw_cartesian(canvas)\n",
    "draw_voronoi(canvas,diagram_test)\n",
    "canvas.pack(padx=10, pady=10)\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Output for test diagram:\n",
    "![Ouput of test for germ insert](images/test_insert.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "insert_germ(voronoi_diagram, (315, 400))\n",
    "window = tk.Tk()\n",
    "canvas = tk.Canvas(window, width=620, height=620)\n",
    "draw_cartesian(canvas)\n",
    "draw_voronoi(canvas,voronoi_diagram)\n",
    "canvas.pack(padx=10, pady=10)\n",
    "window.mainloop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ouput after insert:\n",
    "![Ouput after inserting new germ](images/voronoi_insert.jpg)\n",
    "\n",
    "At this instant, the `germ_insert()` function stops when it finds the point $S_0$ again. However, this can cause problems if the new cell to be constructed is at the border of the canvas. In such a case, it is necessary to capture the corners of the new cell, characterized by the points which are closer to the new cell than the previous cell.\n",
    "\n",
    "Below, the function `is_border()` tests if the point to be added is a border case. Subsequently, the function `capture_corners()` takes the new germ and returns the list of corners (among the 4 corners of the canvas) which are the closest to it. We then redefine `insert_germ()` to add this capability. This requires solving three problems:\n",
    "1. Once we reach a border, we need to restart from $S_0$, circling in the opposite direction this time. Therefore we need to memorize the information relative to $S_0$ at the beggining of the function.\n",
    "2. If we reach a border a second time, we must stop. For this, we can keep a boolean to distinguish between the two situations.\n",
    "3. Capture the corners belonging to the new cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_border(point):\n",
    "    return (abs(canvas_len - point[0]) <= gl.EPSILON) or \\\n",
    "           (abs(point[0]) <= gl.EPSILON) or \\\n",
    "           (abs(canvas_len - point[1]) <= gl.EPSILON) or \\\n",
    "           (abs(point[1]) <= gl.EPSILON)\n",
    "\n",
    "def capture_corners(seed):\n",
    "    L = [(0, 0),(0, canvas_len),(canvas_len, 0),(canvas_len, canvas_len)]\n",
    "    return sorted(L, key= lambda p: sqrt((p[0]-seed[0])**2 + (p[1]-seed[1])**2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_germ_v2(diagram, point):\n",
    "    '''NOT FULLY IMPLEMENTED YET!'''\n",
    "    secondBorder = False\n",
    "    cellNumber = gl.belongs(diagram, point)\n",
    "    diagram.append((point, []))\n",
    "    Pp = diagram[cellNumber][0]\n",
    "    bisection = gl.perp_bisector(Pp, point)\n",
    "    inter = find_intersection(diagram, cellNumber, bisection)\n",
    "\n",
    "    firstS0 = inter[0]['s']\n",
    "    firsta0 = inter[0]['a']\n",
    "    firstS1 = inter[1]['s']\n",
    "\n",
    "    S0 = inter[0]['s']\n",
    "    S1 = inter[1]['s']\n",
    "    a1 = inter[1]['a']\n",
    "    \n",
    "    if(is_border(S1) and is_border(S0)):\n",
    "        coins = capture_corners(point)\n",
    "        \n",
    "        diagram[-1][1].append(coins[0])\n",
    "        diagram[-1][1].append(S1)\n",
    "        diagram[-1][1].append(S0)\n",
    "        diagram[-1] = (diagram[-1][0], tri_polygone(diagram[-1][1]))\n",
    "\n",
    "        temp = diagram[cellNumber][1].copy()\n",
    "        diagram[cellNumber] = (diagram[cellNumber][0], keep_good_points(temp, S0, S1, point, Pp))\n",
    "        return\n",
    "\n",
    "    if(is_border(S1)):\n",
    "        S0, S1 = S1, S0\n",
    "        a1, firsta0 = firsta0, a1\n",
    "        secondBorder = True\n",
    "        coins = capture_corners(point)\n",
    "        diagram[-1][1].append(coins[0])\n",
    "        diagram[-1][1].append(S1)\n",
    "\n",
    "    diagram[-1][1].append(S0)\n",
    "    diagram[cellNumber][1].append(S0)\n",
    "    diagram[cellNumber][1].append(S1)\n",
    "\n",
    "    PiNumber = find_neighbor(diagram, cellNumber, a1)\n",
    "\n",
    "    temp = diagram[cellNumber][1].copy()\n",
    "    diagram[cellNumber] = (diagram[cellNumber][0], keep_good_points(temp, S0, S1, point, Pp))\n",
    "\n",
    "    while not same_point(S1, firstS0):\n",
    "        Pp = diagram[PiNumber][0]\n",
    "\n",
    "        bisection = gl.perp_bisector(Pp, point)\n",
    "        inter = find_intersection(diagram, PiNumber, bisection)\n",
    "#         if len(inter)==0:\n",
    "#             break\n",
    "        print(point, PiNumber, inter)\n",
    "        if secondBorder:\n",
    "            newS0 = inter[1]['s']\n",
    "            newS1 = inter[0]['s']\n",
    "        else:\n",
    "            newS0 = inter[0]['s']\n",
    "            newS1 = inter[1]['s']\n",
    "\n",
    "        if same_point(S0, newS0) or same_point(S1, newS1):\n",
    "            S0 = newS1\n",
    "            S1 = newS0\n",
    "            a1 = inter[0]['a']\n",
    "        else:\n",
    "            S0 = newS0\n",
    "            S1 = newS1\n",
    "            a1 = inter[1]['a']\n",
    "\n",
    "        diagram[-1][1].append(S0)\n",
    "        diagram[PiNumber][1].append(S0)\n",
    "        diagram[PiNumber][1].append(S1)\n",
    "\n",
    "        if not is_border(S1) and not is_border(S0):\n",
    "            newPiNumber = find_neighbor(diagram, PiNumber, a1)\n",
    "\n",
    "            temp = diagram[PiNumber][1].copy()\n",
    "            diagram[PiNumber] = (diagram[PiNumber][0], keep_good_points(temp, S0, S1, point, Pp))\n",
    "            PiNumber = newPiNumber\n",
    "        else:\n",
    "            if not secondBorder:\n",
    "                print('here')\n",
    "                secondBorder = True\n",
    "                coins = capture_corners(point)\n",
    "#                 diagram[-1][1].append(S1) \n",
    "                diagram[-1][1].append(coins[0])\n",
    "                S0, S1 = firstS0, firstS1\n",
    "                a1= firsta0\n",
    "                \n",
    "                newPiNumber = find_neighbor(diagram, PiNumber, firsta0)\n",
    "\n",
    "                temp = diagram[PiNumber][1].copy()\n",
    "                diagram[PiNumber] = (diagram[PiNumber][0], keep_good_points(temp, S0, S1, point, Pp))\n",
    "                PiNumber = newPiNumber\n",
    "            else:\n",
    "                print('here2')\n",
    "                coins = capture_corners(S0)\n",
    "                S1 = coins[0]\n",
    "                diagram[-1][1].append(S1)\n",
    "                diagram[-1] = (diagram[-1][0], tri_polygone(diagram[-1][1]))\n",
    "                return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-17-9a86bfe6a739>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[0mtest_diagram\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m[\u001b[0m \u001b[1;33m(\u001b[0m \u001b[0mlist_seeds\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m[\u001b[0m  \u001b[1;33m(\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m-\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m610\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m610\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;36m610\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m610\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m]\u001b[0m \u001b[1;33m)\u001b[0m \u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m \u001b[0minsert_germ\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtest_diagram\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlist_seeds\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      5\u001b[0m \u001b[0minsert_germ\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtest_diagram\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlist_seeds\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m \u001b[0minsert_germ\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtest_diagram\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlist_seeds\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-12-29e3575381c2>\u001b[0m in \u001b[0;36minsert_germ\u001b[1;34m(diagram, point)\u001b[0m\n\u001b[0;32m     34\u001b[0m         \u001b[0minter\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mfind_intersection\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mdiagram\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mPiNumber\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mbisection\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     35\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 36\u001b[1;33m         \u001b[0mnewS0\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0minter\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m's'\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     37\u001b[0m         \u001b[0mnewS1\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0minter\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;34m's'\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "list_seeds = [cell[0] for cell in voronoi_diagram]\n",
    "test_diagram = [ ( list_seeds[0], [  (-10, -10), (-10,610), (610,-10), (610,610) ] ) ]\n",
    "\n",
    "insert_germ(test_diagram, list_seeds[1])\n",
    "insert_germ(test_diagram, list_seeds[2])\n",
    "insert_germ(test_diagram, list_seeds[3])\n",
    "\n",
    "window = tk.Tk()\n",
    "\n",
    "canvas = tk.Canvas(window, width=620, height=620)\n",
    "\n",
    "draw_cartesian(canvas)\n",
    "\n",
    "draw_voronoi(canvas,test_diagram)\n",
    "\n",
    "canvas.pack(padx=10, pady=10)\n",
    "\n",
    "window.mainloop()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}