Bresenham.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bresenham "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.rcParams['figure.figsize'] = 12, 12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your task is to implement the bresenham function given two points $p_1$ and $p_2$ as inputs. The function should return the list of grid cells required to draw the line.\n",
    "\n",
    "What conditions would warrant a move by 1 unit along the x-axis? What about along the y-axis?\n",
    "\n",
    "The idea is to move based on whether the next $y$ value will be above or below the line from $p_1$ to $p_2$. We can keep track of the current line value, effectively $f(x)$ where $f$ is the line equation by incrementing a counter variable by the slope $m$ whenever we move in the x-axis.\n",
    "\n",
    "The condition is then (in pseudocode):\n",
    "\n",
    "```\n",
    "if f(x+1) > y + 1:\n",
    "    y += 1\n",
    "else:\n",
    "    x += 1\n",
    "```\n",
    "\n",
    "So, if moving along the y-axis results in a y value that is below the line, then move along the y-axis, otherwise,  move in the x-axis.\n",
    "\n",
    "But what about the case where `f(x+1) == y+1`? This will be the result of every test case when the line slope `m = 1`. In this case you have a choice to make:\n",
    "* Only identify cells that as \"in collision\" when the line actually passes through those cells (less conservative obstacle avoidance)\n",
    "* When the line passes directly through a corner of grid cells, identify all cells that share that corner as \"in collision\" (more conservative obstacle avoidance). \n",
    "\n",
    "These two options look like this for a line from (0, 0) to (5, 5):\n",
    "\n",
    "![comparison](./bresenham_comparison.png)\n",
    "\n",
    "Try coding up both! In the event that you've padded obstacles  in your grid map with a sufficient safety margin, you can likely get away with the less conservative approach (or computer graphics based Bresenham implementation in the Python package shown below).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bres(p1, p2): \n",
    "    \"\"\"\n",
    "    Note this solution requires `x1` < `x2` and `y1` < `y2`.\n",
    "    \"\"\"\n",
    "    x1, y1 = p1\n",
    "    x2, y2 = p2\n",
    "    cells = []\n",
    "    \n",
    "    # TODO: Determine valid grid cells\n",
    "    # Here's a quick explanation in math terms of our approach\n",
    "    # First, set dx = x2 - x1 and dy = y2 - y1\n",
    "    dx, dy = x2 - x1, y2 - y1\n",
    "    # Then define a new quantity: d = x dy - y dx.\n",
    "    # and set d = 0 initially\n",
    "    d = 0\n",
    "    # The condition we care about is whether \n",
    "    # (x + 1) * m < y + 1 or moving things around a bit: \n",
    "    # (x + 1) dy / dx < y + 1 \n",
    "    # which implies: x dy - y dx < dx - dy\n",
    "    # or in other words: d < dx - dy is our new condition\n",
    "    \n",
    "    # Initialize i, j indices\n",
    "    i = x1\n",
    "    j = y1\n",
    "    \n",
    "    while i < x2 and j < y2:\n",
    "        cells.append([i, j])\n",
    "        if d < dx - dy:\n",
    "            d += dy\n",
    "            i += 1\n",
    "        elif d == dx - dy:\n",
    "            # uncomment these two lines for conservative approach\n",
    "            #cells.append([i+1, j])\n",
    "            #cells.append([i, j+1])\n",
    "            d += dy\n",
    "            i += 1  \n",
    "            d -= dx\n",
    "            j += 1\n",
    "        else:\n",
    "            d -= dx\n",
    "            j += 1\n",
    "        \n",
    "    return np.array(cells)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plotting the line with the cells which it crosses. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEWCAYAAABliCz2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAHedJREFUeJzt3XuYHHWd7/H3dyZNCIHJKGGHq2R1RWVUHIggDwijIoeriC4iBznrZY3gUWHVVeRwhHXRB/coi4CysOIiIiByURZYxHPMREBQkjDITTQiJA2BcJuEyYQwPf09f9RvoDKZ6fRMprp+3fV5PU8/Mz1V3b9vV1d/uqa+Vd3m7oiISOtry7sAERFpDAW+iEhBKPBFRApCgS8iUhAKfBGRglDgi4gUhAJfJs3M+szs73Ou4VIzOyvPGjaXmX3UzG7Pu46xzGyembmZzcjo/h8ws94a03Nfv1qVAj8nZvaomR1U57x6AUxCCNIRMxsMl0fM7KS865KEu3e7ex+AmZ1pZpfnXFJhKPClJjNrz7uGKbrT3bd2962BvwX+xcx6xpsxqy1Z2ZCWc/4U+BEY/dfezL5lZs+b2V/M7NAw7evAO4ELwtbqBeHvbzSzX5rZc2b2sJl9KHV/25rZf5rZGjO728zOSu862MRtLzWzC83sZjNbC7xrgrJfZ2a/M7PVZvZzM3t16j5+amZPhmm/NrPu1LTDzOxBM3vBzB43sy+mph1hZv1mNmBmvzGzt6am9ZjZ0nC7nwBb1rt83X0p8BDwpnBfo7ssPmFmy4Ffhb+/I4w7YGb3pnc7hOfokTD+X8zs+NS0j5vZQ+G5+4WZ7Zqa5mZ2opn9KUz/rplZur7xnvfw94+F+30hjP2p1LReMyub2ZfMbJWZrTSz94fl+8fw3J420TIxs8PN7J6wjqwwszNrzPvX4Xl8wcz+b3gMl6emv8+S3TQD4b/RN6WmPWpmXzaz3wNrzWxG+NtBZnYIcBpwbFi3700Nu6uZ3RHGvNXM5o557j4W6n4+LN+3m9nvQw0XTPRYCs/ddcnhAjwKHBR+/ygwDHwSaAdOAp4ALEzvA/4+ddvZwArgY8AMYE/gGaA7TL8qXLYCdg/z3l7nbS8FVgP7kWwQbDlO7X3A48Cbw/1dC1yemv5xYBtgJnAu0J+athJ4Z/j9VcCe4fc9gVXAPmEZ/F1YRjOBLYDHgH8ASiRb7MPAWRMs24+OPt5w/e3AALBbuD4PcOCyUP8sYCfgWeCw8LjfG65vF+ZZA7wh3H6H1PJ6P7CM5M1kBnA68JvU2A7cCHQCrwGeBg6p83k/HHgdYMCBwFBqefUCFeCrYZl8Mtz3FWHZdwMvAq+dYBn1Am8Jj/WtwFPA+8csnxnh+p3At8LzsH9YFpeHabsBa8PyKgFfCstji9R63g/sAswaZ90/k9S6k1q//hzue1a4fvaY2v6N5E3/4PA4fwb8VXgeVwEH5v0aj/GSewFFvbBx4C9LTdsqrNTbh+t9bBj4xwK3jbm/i4AzQnAME8IpTDuLVwJ/wtuG3y8FLttE7S+/AMP13YGXgPZx5u0Mj2VOuL4c+BTQMWa+C4F/HvO3h0mC7gBSQRim/YbagV8hCfnBMP75vBKko6Hx2tRtvgz8aMz9/ILkjWd2uK8PjoZWap7/Aj6Rut5GEsy7husO7J+afjVwaj3P+ziP62fAyeH3XmDd6DInCXkH9knNv4QQ4nWsj+cC/zpm+cwgeZOqAFul5r2cVwL/fwNXj3n8jwO9qfX84zXW/TMZP/BPT13/NHDLmNp2Sk1/Fjg2df1a4JRGvp6b5aJdOvF4cvQXdx8Kv249wby7AvuEf18HzGwAOB7YnmSLdAbJVvyoFXXedrz5J5Ke5zGSrbu5ZtZuZmeb2Z/NbA3Jixtgbvj5QZKt6MfMbJGZ7Zuq6wtj6toF2DFcHvfwak6NWctd7t7pyT787Um2eL9R4zHsChwzZvz9gR3cfS3JG+WJwEozu8nM3pi63XdSt3mOZIt8p9R9P5n6fYgNn9cJn3czO9TM7gq7ZwZIltvc1G2fdfeR8Pu68POp1PR1TLAOmdk+ZrbQzJ42s9Xhsc0dZ9YdgedStcGGy21HUs+Fu1fD9J0mmL9etZYZbPw463rcRafAbw5jP9J0BbAoBNroZWt3P4nk3/oKsHNq/l3qvO1E440nfZ+vIfmv4hngvwNHAQcBc0i2yCAJQdz9bnc/iuTf75+RbPGO1vX1MXVt5e5XkuwG2mnMvu/X1FEjYcynSLb6jhw7KfX7CpIt/PT4s9397HAfv3D395LszvkD8O+p231qzO1muftv6q1vPGY2M9T8LaDL3TuBmwnLcRpcAdwA7OLuc0h2kYx33yuBV5vZVqm/pZ/7J0je9EbrtjD98dQ8tdYnfVxvAynwm8NTwGtT128EdjOzE8ysFC5vN7M3hS2+64AzzWyrsCX6P+q57SRr+oiZ7R6C4GvANWHsbYD1JP9mb0Vqq9rMtjCz481sjrsPk+wLHt1C/XfgxLDlaWY2OzQWtyHZh1wBPheafh8A9q63UDPbFjgaeKDGbJcDR5rZfwv/pWwZGqM7m1lXaEzODo9tMFX3vwFfsdCYNrM5ZnZMvbXVsAVJ/+JpoGJJM/fgabjfUduQbLm/aGZ7k7xRb8TdHwMWk6xPW4T/yNJvnFcDh5vZe8ysBHyBZBnV+4b3FDDPzJRFDaCF3By+A/xtOCLhPHd/geTF/2GSLawngW+SBATAZ0i2rp8EfgRcSfIipI7b1utHJPv7nyRpnn0u/P0ykn/xHwceBO4ac7sTgEfD7p4TgY+EuhaTNB4vAJ4nafx9NEx7CfhAuP48ye6V6zZR377hyI9BkiN0ngY+O9HM7r6C5D+T08K8K4B/JHmNtJEE2RMku2wOJNmvjLtfT7L8rgqP6X7g0LH3P1nhefocSaA+TxLIN2zu/aZ8Gviamb1A0vi9usa8xwP7kryJnwX8hFfWp4dJnsPzSf7DOxI4Mjxn9fhp+PmsmS2d7IOQyRltYkkLM7NvkjQC/y7vWqT5WXJY7B/c/Yy8a5HJ0RZ+C7LkOPu3hl0jewOfAK7Puy5pTmGX3+vMrC0cO38USf9FmozOfGtN25DsxtmR5JjkbwM/z7UiaWbbk+xC2xYoAye5+z35liRToV06IiIFoV06IiIFEdUunblz5/q8efMaOubatWuZPXt2Q8esV8y1Qdz1xVwbxF1fzLVB3PXlUduSJUuecfft6po571N905e99trLG23hwoUNH7NeMdfmHnd9MdfmHnd9MdfmHnd9edQGLHZ9tIKIiKQp8EVECkKBLyJSEAp8EZGCUOCLiBREpodlmtmjwAsknyxYcff5WY4nIiITa8Rx+O9y92caMI6IiNQQ1YlXIpKvnp4eyuUy3d3dm545B3fccQfuzv777593KRt5+I9/Yrh9S1Y9toy2tun6nprplXXgO3CrmTlwkbtfPHYGM1sALADo6uqir68v45I2NDg42PAx6xVzbRB3fTHXBvHWVy6XGRoaYmBgIO9SxlWpVACiq2/1emfVcwO0bTGLq25eyI5bR9oerfcMralcgB3Dz78C7gUOqDW/zrTdUMy1ucddX8y1ucdb34EHHuh77LFH3mVMaM6cOT579uy8y3jZ6nUv+WevWOq7fvlG3+71Pb77Wxq/7IjlTFt3fyL8XEXyeex1fy2diEjM7n70OQ499zZuum8lXzx4N960YwelSDfsR2VWXvhO0m1Gfyf5Wr37sxpPRKQRKiNVzrn1YY696E7a24xrTtyXz7z79dP27fJZynIffhdwffIl9swArnD3WzIcT0QkU8ufHeLkn9zDPcsH+OCeO/NPR3Wz9czmOfYls0rd/RFgj6zuX0SkUdyd6+95nK/+/AHM4Pzjejhyjx3zLmvSmuetSUQkB2teHOb06+/nhnufYO95r+ZfP/w2duqclXdZU6LAFxGZwN2PPscpV/Xz5JoX+eLBu3FS79/QHukx9vVQ4IuIjFEZqXLe//sTFyxcxs6v2oprTtyXnte8Ku+yNpsCX0Qkpdkbs7W0xqMQEdlMrdKYrUWBLyKF10qN2VoU+CJSaK3WmK1FgS8ihdSqjdlaFPgiUjit3JitpfUfoYhIUITGbC0KfBEphKI0ZmtR4ItIyytSY7YWBb6ItKwiNmZrUeCLSEsqamO2lmI/ehFpOUVvzNaiwBeRlqHGbG0KfBFpCWrMbpoCX0Samhqz9VPgi0jTUmN2crRkRKTpqDE7NQp8EWk6J1/Vr8bsFCjwRaRpjFSddRW46b6VasxOgQJfRKI32phd+1IFw9SYnSIFvohELd2YLbW3UTJX2E9RW94FiIiMx925bmmZw867jWWrBjn/uB5mldrzLqupaQtfRKKjM2azocAXkajojNnsKPBFJAo6YzZ7CnwRyZ3OmG0MLVERyY3OmG0sBb6I5EKN2cbLPPDNrB1YDDzu7kdkPZ6IxE+N2Xw0Ygv/ZOAhoKMBY4lIxNSYzVemgW9mOwOHA18HPp/lWCLNoqenh3K5THd3d96lbGTRokUAdHZ2Tvt9Vx3WDVcYqTql9jaeLbXzrm9M7j5Wr14NQG9v77TXt7n6+/splUp5l1FT1lv45wJfAraZaAYzWwAsAOjq6qKvry/jkjY0ODjY8DHrFXNtEHd9MddWLpcZGhpiYGAg71ImVKlUpvf+qjBcdQBmthvt5oxsxhgxLrtSqURHR0e06x1kGPhmdgSwyt2XmFnvRPO5+8XAxQDz58/3Rr9z9/X1Rbm1AHHXBnHXF3Nt3d3dDAwM0N/fn3cpG+ns7KRSqTA4ODgt9zfdjdne3t5olx3Evd5Btlv4+wHvM7PDgC2BDjO73N0/kuGYIhIJNWbjk1ngu/tXgK8AhC38LyrsRVqfGrPx0nH4IjJtdMZs3BryTLh7H9DXiLFEpPF0xmxz0FuviGwWnTHbPBT4IjJlasw2FwW+iEyaGrPNSYEvIpOixmzz0rMkInVRY7b5KfBFZJPUmG0NCnwRqUmN2dahwBeRcakx23oU+CKyETVmW5OeQRHZQKUKh513mxqzLUiBLyJA0phdNzzCcNXZfYcONWZbkAJfRF5uzA6POKU248oF71BjtgW15V2AiOSnMlLlnFsf5tiL7qS9zZi9RTulNhT2LUqBL1JQy58d4piL7uS8Xy3j6J6dufnkdyroW5x26YgUjM6YLS4FvkiB6IzZYlPgixSEzpgVBb5Ii9MZszJKgS/SwnTGrKTpmRdpQWrMyngU+CItRo1ZmYgCX6SFqDErtSjwRVqAGrNSDwW+SJNTY1bqpbVCpEmpMSuTpcAXaUJqzMpUKPBFmowaszJVCnyRJqHGrGwuBb5IE1BjVqaD1hiRiKkxK9Mps8A3sy2BXwMzwzjXuPsZWY0n0mrUmJXpluUW/nrg3e4+aGYl4HYz+y93vyvDMUVaghqzkoXMAt/dHRgMV0vh4lmNJ43V09NDuVymu7s771I2cscdd+Du7L///nmXMq5FixYB0NnZOe709ZUq6ysjtJkxq9TO6d8zTm9QbatXrwagt7e3QSNOTn9/P6VSKe8ymlam+/DNrB1YAvwN8F13/+048ywAFgB0dXXR19eXZUkbGRwcbPiY9Yq5tnK5zNDQEAMDA3mXspFKpQIQZW1po3WOcmD9CFTdmWHGFu3g1REq1cbXFuuyK5VKdHR0RPu6iPk1C2DJhnjGg5h1AtcDn3X3+yeab/78+b548eLM60nr6+uLdmsm5tp6e3sZGBigv78/71I20tnZSaVSYXBwcNMz52BsfWMbs984+i25NWZjfl5Hxfy6yKM2M1vi7vPrmbchR+m4+4CZ9QGHABMGvkjRqDErjZTlUTrbAcMh7GcBBwHfzGo8kWajxqw0WpZb+DsAPwz78duAq939xgzHE2kaw1U49qI7dcasNFSWR+n8HujJ6v5FmtHyZ4dY+1KFkapzdI/OmJXG0pom0gDpxmy1CjPbjW9/aI+8y5KCUeCLZGxsY3b5zBlURyqbvqHINFPgi2RovMbstqdCDofWiyjwRbKgjzKWGCnwRaaZPspYYqW1UGSa6KOMJXYKfJFpoDNmpRko8EU2k86YlWahwBeZIjVmpdko8EWmQI1ZaUZaQ0UmQY1ZaWYKfJE6qTErzW7CwDezm4FPu/ujjStHJE5qzEorqLWFfylwq5n9EPgXdx9uTEki8VBjVlrJhIHv7leb2U3AV4HFZvYjUh8B4u7nNKA+kdyoMSutZlNr7zCwFpgJbIM+80kKQI1ZaVW19uEfApwD3ADs6e5DDatKJCdqzEorq7WF/7+AY9z9gUYVI5InNWal1dXah//ORhYikhc1ZqUo1IGSQlNjVopEa7YUkhqzUkQKfCkcNWalqBT4UihqzEqRKfClENSYFVHgSwGoMSuS0FovLUuNWZENKfClZZ18Vb8asyIpCnxpOSNVZ10FbrpvpRqzIikKfGkZo43ZtS9VMEyNWZExFPjSEtKN2VJ7GyVzhb3IGG15FyCyOdyd65aWOey821i2apDzj+thVqk977JEopTZFr6Z7QJcBmxP8jn6F7v7d7IaT4pHZ8yKTE6Wu3QqwBfcfamZbQMsMbNfuvuDGY4pBaEzZkUmL7PAd/eVwMrw+wtm9hCwE6DAr0NPTw/lcpnu7u68SxnXokWLAOjs7Gz42OsrVdZXRmgzY1apndO/Z5yemr569WoAent7G15bPdasWYO7R1lff38/pVIp7zIkIw1p2prZPKAH+O040xYACwC6urro6+trREkvGxwcbPiY9SiXywwNDTEwMJB3KTVVKpWGjeXA+hGoujPDjC3awasjVCb44s1Yl11bW9I6i7G+UqlER0dHlK+JUbG+ZiHu2oCk6ZXlBdgaWAJ8YFPz7rXXXt5oCxcubPiY9TjwwAN9jz32yLuMCc2ZM8dnz57dkLGq1apfu2SFd3/1Fn/zGbf4Df2P15w/9mXnHu965x53be5x15dHbcBirzOPM93CN7MScC3wY3e/LsuxpDWpMSsyfbI8SseAS4CH3P2crMaR1qXGrMj0ynILfz/gBOA+M+sPfzvN3W/OcExpAfooY5FsZHmUzu2ANsdkUvRRxiLZ0StJouD6KGORzCnwJXdqzIo0hgJfcqXGrEjjKPAlF2rMijSeAl8aTo1ZkXzoVSYNo8asSL4U+NIQasyK5E+BL5lTY1YkDgp8yYwasyJxUeBLJtSYFYmPXoEyrdSYFYmXAl+mjRqzInFT4Mu0UGNWJH4KfNksasyKNA8FvkyZA8dcdKcasyJNQq9OmTR3Z3ikyosVZ9mqQTVmRZqEAl8mZbQxu254hHYzbjnlADVmRZqEAl/qlm7MzpzRTjtVhb1IE2nLuwCJX2Wkyjm3PsyxF91Je5txzYn7MnOGVh2RZqMtfKlJZ8yKtA69cmVcOmNWpPUo8GUjOmNWpDUp8GUDOmNWpHUp8AXQGbMiRaDAFzVmRQpCr+oCU2NWpFgU+AWlxqxI8SjwC0iNWZFiUuAXiBqzIsWmwC8INWZFJLNXvJn9ADgCWOXub85qHKlNjVkRGZXlJt6lwAXAZRmOITWoMSsiaZkFvrv/2szmZXX/06Gnp4dyuUx3d3fepWxk0aJFAHR2dk7p9iNVZ93wCFWHmTPauHVGG92nTl99q1evBqC3t3f67nSa9Pf3UyqV8i5DJDq578Q1swXAAoCuri76+voaNna5XGZoaIiBgYGGjTlZlUpl0rcZrsJw1TGMLduhjSqVSjWD6ohy2ZVKJTo6Ohq6Lk3W4OBgtPXFXBvEXV/MtUEEge/uFwMXA8yfP98bucXY3d3NwMAA/f39DRuzXp2dnVQqFQYHB+u+TSMbs729vdEuO4C+vr4o//sYFXN9MdcGcdcXc20QQeDL5lNjVkTqocBvcmrMiki9sjws80qgF5hrZmXgDHe/JKvxikhnzIrIZGR5lM5xWd130emMWRGZCu3SaTI6Y1ZEpkpJ0STUmBWRzaXAbwJqzIrIdFDgR06NWRGZLgr8iA1X4diL7lRjVkSmhQI/QsufHWLtSxVGqs7RPWrMisj0UIpEJN2YrVZhZrvx7Q/tkXdZItIiFPiRGNuYXT5zBtWRyX9wmojIRBT4ERivMbvtqZDN51uKSFEp8HOkM2ZFpJEU+DnRGbMi0mhKmAbTGbMikhcFfgPpjFkRyZMCv0F0xqyI5E2BnzE1ZkUkFgr8DKkxKyIxUfpkQI1ZEYmRAn+aqTErIrFS4E8jNWZFJGYK/GmgxqyINAMF/mZSY1ZEmoWSaYrUmBWRZqPAnwI1ZkWkGSnwJ0mNWRFpVgr8OqkxKyLNToFfBzVmRaQVKLVqUGNWRFqJAn8CasyKSKtR4I9DjVkRaUUK/BQ1ZkWklSnwAzVmRaTVZZpoZnYI8B2gHfi+u5+d5XhTdd3SshqzItLyMgt8M2sHvgu8FygDd5vZDe7+YFZjTtZI1XlisMrnr75XjVkRaXlZbuHvDSxz90cAzOwq4CggisBftuoFfnfvgwyvH+J1t3yNpzpncfxVeVf1ijVr1uDu9Pb25l3KuPr7+ymVSnmXISKTkGXg7wSsSF0vA/uMncnMFgALALq6uujr68uwpFe8WHG23LqDWe3ObNazemB9Q8atV1tbGwADAwM5VzK+UqlER0dHw56vyRocHIy2Noi7vphrg7jri7k2IDm5KIsLcAzJfvvR6ycA59e6zV577eWNtnDhwoaPWa+Ya3OPu76Ya3OPu76Ya3OPu748agMWe5253Jbhe0kZ2CV1fWfgiQzHExGRGrIM/LuB15vZX5vZFsCHgRsyHE9ERGrIbB++u1fM7DPAL0gOy/yBuz+Q1XgiIlJbpsfhu/vNwM1ZjiEiIvXJcpeOiIhERIEvIlIQCnwRkYJQ4IuIFIQlx+3HwcyeBh5r8LBzgWcaPGa9Yq4N4q4v5tog7vpirg3iri+P2nZ19+3qmTGqwM+DmS129/l51zGemGuDuOuLuTaIu76Ya4O464u5NtAuHRGRwlDgi4gUhAIfLs67gBpirg3iri/m2iDu+mKuDeKuL+batA9fRKQotIUvIlIQCnwRkYIobOCb2SFm9rCZLTOzU/OuJ83MfmBmq8zs/rxrGcvMdjGzhWb2kJk9YGYn511TmpltaWa/M7N7Q33/lHdNY5lZu5ndY2Y35l3LWGb2qJndZ2b9ZrY473rSzKzTzK4xsz+E9W/fvGsaZWZvCMts9LLGzE7Ju66xCrkPP3zB+h9JfcE6cJxH8gXrZnYAMAhc5u5vzrueNDPbAdjB3Zea2TbAEuD9ES07A2a7+6CZlYDbgZPd/a6cS3uZmX0emA90uPsRedeTZmaPAvPdPboTm8zsh8Bt7v798B0bW7l7dN8BGvLlcWAfd2/0iaQ1FXUL/+UvWHf3l4DRL1iPgrv/Gngu7zrG4+4r3X1p+P0F4CGS7y+OQvjWt8FwtRQu0WzVmNnOwOHA9/OupZmYWQdwAHAJgLu/FGPYB+8B/hxb2ENxA3+8L1iPJrSahZnNA3qA3+ZbyYbCLpN+YBXwS3ePqb5zgS8B1bwLmYADt5rZEjNbkHcxKa8Fngb+I+wO+76Zzc67qAl8GLgy7yLGU9TAt3H+Fs1WYDMws62Ba4FT3H1N3vWkufuIu7+N5HuU9zazKHaLmdkRwCp3X5J3LTXs5+57AocC/zPsXozBDGBP4EJ37wHWAlH13gDCrqb3AT/Nu5bxFDXw9QXrmyHsG78W+LG7X5d3PRMJ//L3AYfkXMqo/YD3hf3kVwHvNrPL8y1pQ+7+RPi5CrieZPdnDMpAOfXf2jUkbwCxORRY6u5P5V3IeIoa+PqC9SkKTdFLgIfc/Zy86xnLzLYzs87w+yzgIOAP+VaVcPevuPvO7j6PZJ37lbt/JOeyXmZms0MjnrC75GAgiiPF3P1JYIWZvSH86T1AFAcKjHEcke7OgYy/0zZWsX/BupldCfQCc82sDJzh7pfkW9XL9gNOAO4L+8kBTgvfXxyDHYAfhiMl2oCr3T26wx8j1QVcn7ynMwO4wt1vybekDXwW+HHYSHsE+FjO9WzAzLYiOfLvU3nXMpFCHpYpIlJERd2lIyJSOAp8EZGCUOCLiBSEAl9EpCAU+CIiBaHAF5lA+GTQv5jZq8P1V4Xru+Zdm8hUKPBFJuDuK4ALgbPDn84GLo7xQ7FE6qHj8EVqCB8jsQT4AfBJoCd8wqpI0ynkmbYi9XL3YTP7R+AW4GCFvTQz7dIR2bRDgZVAFJ+6KTJVCnyRGszsbSSfj/IO4B/CN36JNCUFvsgEwieDXkjymf/Lgf8DfCvfqkSmToEvMrFPAsvd/Zfh+veAN5rZgTnWJDJlOkpHRKQgtIUvIlIQCnwRkYJQ4IuIFIQCX0SkIBT4IiIFocAXESkIBb6ISEH8f/lZERUw+3LSAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fe61509b6d8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "p1 = (0, 0)\n",
    "p2 = (7, 5)\n",
    "\n",
    "cells = bres(p1, p2)\n",
    "# print(cells)\n",
    "\n",
    "plt.plot([p1[0], p2[0]], [p1[1], p2[1]])\n",
    "\n",
    "\n",
    "for q in cells:\n",
    "    plt.plot([q[0], q[0]+1], [q[1], q[1]], 'k')\n",
    "    plt.plot([q[0], q[0]+1], [q[1]+1, q[1]+1], 'k')\n",
    "    plt.plot([q[0], q[0]], [q[1],q[1]+1], 'k')\n",
    "    plt.plot([q[0]+1, q[0]+1], [q[1], q[1]+1], 'k')\n",
    "\n",
    "plt.grid()\n",
    "plt.axis('equal')\n",
    "plt.xlabel(\"X\")\n",
    "plt.ylabel(\"Y\")\n",
    "plt.title(\"Integer based Bresenham algorithm\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check out our solution [here](/notebooks/Bresenham-Solution.ipynb)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Python Bresenham Package\n",
    "For comparison let's have a look at the Python Bresenham package! As mentioned above, if you've added a safety margin around obstacles you are probably fine using this package or one like it that misses some cells in collision with the line.\n",
    "\n",
    "First we need to import it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from bresenham import bresenham"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we can run the same experiment as above and plot it up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 4), (6, 4), (7, 5)]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEWCAYAAABliCz2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAHUNJREFUeJzt3XuYXHWd5/H3p5MmadLElou9EJAo2cUxrNCxVxxEaa/DbdRVeQTWG88+ZHAUYbxfdgZdddcRL5NnxUsQ74pCEIdVBHSHWiMKYyKtApElRi4NgTQZm6SSTuhOvvvHOY1FJ91dfTn9q+rzeT1PnlTXOXXOt351zqdPn2+dKkUEZmY297WkLsDMzGaHA9/MrCQc+GZmJeHANzMrCQe+mVlJOPDNzErCgd8kJN0r6WWp65iqZq9/Nkn6sKRvpa5jNEk9kvoKXH5V0jPHme5taJoc+AXKN9DBfEN+RNJXJbXX8bivSfrYbNRYJnmQDuWvR1XSBkmvTV2XZSKiPSI2gfeBojjwi/fXEdEOrAD+E/DfEtdTdt/Lg6UduBj4lqTO/c0oaf7sllZOHufZ48CfJRHxIPBj4DhJZ0laXztd0rsk/UDSSuC/AO/Nj0L/d81sJ0j6raTHJH1P0sKax58vaaOkf5N0naQjaqaFpAsk3SPpT5Iuk6T91ZkfBa/Jl79d0q8lHV8z/f2S/pBPu0vSfx71+PPzI+eR6Sv2s45nSfqjpLMnWqakeZI+LenR/DFvz5/P/Hz6UyRdIWmzpAclfUzSvDpfkxuB7cAx+bJ6JPVJep+kh4Gv5vefKalX0oCkX0h6Tk1978vXu13S3ZJemt/fUvO8tkq6StLB+bSl+XN4s6T78+f2oVHlHSDpG/ly75TUXc9rIOktkm6R9Nm83k2STsrvf0DSFklvHmtMJJ1X8/ptkvQ348y7QtLt+bxX59vMx2qmT7RNvk3SPcA9Nfctm8o+UPPavTd/jpslvVrS6ZL+X17DB8d6LqUREf5X0D/gXuBl+e2jgDuBjwILgH8D/qJm3tuB1+a3vwZ8bD/L+lfgCOBgYANwQT7tJcCjZH9FLAD+F/CzmscG8EOgA3g60A+cOkbNHwaGgNcBrcC7gT8Crfn0s/IaWoDXAzuAw2umPUj2l4yAZcDRtWOR13g/cGbNOsdb5gXAXcCRwFOBn+bPZ34+/QfAl4BFwNPyMfqbcZ7bt/LbAs4ABoCO/L4eYBj4x3wc2/J6twAnAvOAN+fPZQFwLPAAcET++KXAMfnti4Fb87oX5DVeWTNfAJfn6zge2D2yPeR17gJOz9f5P4Fb6xyvt+TP4bz8sR/Lx/uyvI5XkP2Sax9jjM4g+wUo4BRgJ7CiZnz68tsHAPcBF5FtJ68BHiffbqlvm/wJ2bbcVnPfsinuAyOv3T/k9ZxPtp1/BzgIWJ6P6TNT50LSTEpdwFz+l2+gVbJQuQ/4fM3G/QXg4/nt5cCfgAX5z2Nt7G+o+fmTwBfz21cAn6yZ1k4W2kvznwM4uWb6VcD7x6j5w6PCpQXYDLxwjPl7gVflt28ELhpnLD4C9AEvnmDcapf5L9QEONkvjQDmA51kQdlWM/0c4OZxntvj+euxE9gDvLdmek8+fWHNfV8APjpqOXeTheEysl8GLyP/hVgzzwbgpTU/H56/JvP5c+AfWTP9X4Gza+r8ac20ZwODdY7XW4B7aqb9x3xdnTX3bQVOqHMb/sHIa8qTA/9FZL/cVTPvz/lz4NezTb5k1LrqCfyx9oEeYBCYl/98UL68E2vmXw+8eqb382b651M6xXt1RHRExNER8bcRMZjf/3Xg3PzUyhuBqyJi9wTLerjm9k6ynQiyI577RiZERJVsp15Sx2P354GaZe0lC+kjACS9qeb0xgBwHHBoPvtRwB/GWe4FwC8i4ubaOydY5hG19Yy6fTTZ0dzmmsd+iexIfyxX5a/HgWRHsm8addqiPyJ2jVrHu0aWn6/jKLKj+o1kR/IfBrZI+m7NaYujgWtrHrOB7BdMbb9gvNdk9LSFNaexxhsvgEdqbg8CRMTo+/b7+ks6TdKt+SmQAbK/Mg7dz6xHAA9GnqS5B0ZNn2ibrJ2/XuON2daI2JPfHtnP6nreZeHATyQibiU7mnwhcC7wzdrJk1zcQ2QBA4CkRcAhZEdgU3FUzbJayE5LPCTpaLLTEG8HDomIDuAOsj//IduBjxlnuRcAT5f02ZrlT7TMzfn696ktX99u4NA8xDsiYnFELK/nSUbEvWR9lb+uvXvUbA+Q/SXWUfPvwIi4Ml/GdyLiZLLxD7LTQSOPO23U4xZG1suZsjrGazrLXgBcA3yK7C+CDuD6MZa9GViSH7CMqH1t6tkmx9vO/TG+BXDgp/UN4HPAcET8vOb+R4Ax34+8H98BzpN0Qr7T/g/gtjzQpuK5kl6TH1FeTBaqt5KdJw+yc6NIOo/s6HLEl4F3S3quMsvygBqxHTgVeJGkT+T3TbTMq4CLJC2R1AG8b2RCRGwGbgI+LWlx3ig9RtIp9TxJSUfm9dw5zmyXAxdIOjF/TosknSHpIEnHSnpJPua7yI4gR44wvwh8fOT5SzpM0qvqqWsCE43XdBxAdr69HxiWdBrZOf/9+SXZc327pPn5c3tezfTpbpOT3QesDg78tL5JtrN+c9T9VwDPzv9k/8FEC4mI/wP8PdnR2Wayo+yzp1HXP5M1A/9EdrrpNRExFBF3AZ8m29kfITs/fEtNHVcDHyfb2beTnf89eFStA8DLgdMkfXSiZZIF7k3Ab8ka29eTNedGgvVNZEF1V17vGrLz5WN5ff7Ojyrwq3xdHxlr5ohYR9YA/Fy+/I1k58khC8dPkDUnHyY7lTTyTpBVwHXATZK2k/3CPHGcuupSx3hNZ9nbgXeQ/ZL9E9lfnteNMe/jZI3a/0rWE3kD2RsDdufTp7tNTmofsProyafgbDZJaiNr+q2IiHtS1wPZ2zLJGmdvSF3L/uRHnV+MiKMnnNlmlaTbyF6br6auxfbPR/hpvRX4VaOEfSOS1Ja/l3q+pCXAJcC1qesykHSKpH+XvzZvBp4D3JC6Lhubr3BLRNK9ZM2wVycupdGJ7JTL98jOkf+I7L3Wlt6xZKd/2snenfW6vK9iDcqndMzMSsKndMzMSqKhTukceuihsXTp0tRlALBjxw4WLVqUuozkPA4Zj0PG45BppHFYv379oxFxWD3zNlTgL126lHXr1qUuA4BKpUJPT0/qMpLzOGQ8DhmPQ6aRxkHSfRPPlfEpHTOzknDgm5mVhAPfzKwkHPhmZiXhwDczK4lCA19Sh7Kvy/u9sq9N+8si12dmZmMr+m2Zq4AbIuJ1kg4ADix4fWZmNobCAl/SYrKvQXsLPPFxqo8XtT4zm/u6urro7+9n2bJlyWrYuHEjbW1t3HNP833mYZFH+M8k+yKFr0o6nuz7JC+KiB21Myn7hvqVAJ2dnVQqlQJLql+1Wm2YWlLyOGQ8DpnU49DX18fg4CADAwPJahgYGGDXrl1NuT0U9uFpkrrJvvThBRFxm6RVwLaI+PuxHtPd3R2+0raxeBwyHodM6nEYWXfKsO3p6WFgYIDe3t5kNdSStD4iuuuZt8imbR/ZN9zflv+8BlhR4PrMzGwchQV+RDwMPCDp2Pyul5J9DZ2ZmSVQ9Lt0LgS+nb9DZxNwXsHrMzOzMRQa+BHRC9R1bsnMzIrlK23NzErCgW9mVhIOfDOzknDgm5mVhAPfzKwkHPhmZiXhwDczKwkHvplZSTjwzcxKwoFvZlYSDnwzs5Jw4JuZlYQD38ysJBz4ZmYl4cA3MysJB76ZWUk48M3MSsKBb2ZWEg58M7OScOCbmZWEA9/MrCQc+GZmJeHANzMrCQe+mVlJzC9y4ZLuBbYDe4DhiOgucn1mZja2QgM/9+KIeHQW1mNmZuOYjcA3s2nq6uqiv7+fZcuWJavhlltuISI4+eSTk6w/AtauXYsEPT09SWoA6O3tpbW1Ndn6p6PowA/gJkkBfCkiVo+eQdJKYCVAZ2cnlUql4JLqU61WG6aWlDwOmdTj0NfXx+DgIAMDA8lqGB4eBkhSw9BeeKi6lyCISFPDiNbWVhYvXtyU+4UioriFS0dExEOSngb8BLgwIn421vzd3d2xbt26wuqZjEqlkvQoolF4HDKpx2Fk3SlDpqOjg+HhYarV6qytMyK45tcPcsk/38G8FhE/+giHLDogedim3h5qSVpfb3+00HfpRMRD+f9bgGuB5xW5PjObOx4bHOLCK2/n3Vf/huVLnsKPL34Rhyw6IHVZTa2wUzqSFgEtEbE9v/0K4L8XtT4zmztu27SVd171Gx7Ztov3/NWxXHDKMcxrUeqyml6R5/A7gWsljaznOxFxQ4HrM7MmN7RnL6t+eg+fr2zkqIMPZM1bT+KEozpSlzVnFBb4EbEJOL6o5ZvZ3HLf1h1c9N1eeh8Y4KznHsklr1xO+wK/kXAmeTTNLKnRjdnLzl3BGc85PHVZc5ID38ySeWxwiA9d+zt++NvNPO8ZB/PZ15/Ako621GXNWQ58M0vCjdnZ58A3s1nlxmw6DnwzmzVuzKblkTazwrkx2xgc+GZWKDdmG4cD38wK48ZsY3Hgm9mMc2O2MTnwzWxGuTHbuPwqmNmMcGO28TnwzWza3JhtDg58M5sWN2abhwPfzKbEjdnm48A3s0lzY7Y5+RUys0lZs77Pjdkm5cA3s7oE8PgeePfVv3Fjtkk58M1sQrdt2sqO3cPsjXBjtok58M1sTLWNWYCF88TbXrwscVU2VQ58M9uv0Y3Z1Qvms2d4OHVZNg0tqQsws8YSEaxZ38fpq9ayqb/KZeeu4NKzjscncJqfj/DN7Am+YnZuc+CbGeArZsvAgW9Wcr5itjwKD3xJ84B1wIMRcWbR6zOz+vmK2XKZjVf2ImADsHgW1mVmdfBHGZdToYEv6UjgDODjwDuLXJdZUbq6uujr62P58uXJali7di0APT09017W8N7gj4/uYGt1N4sXtnLM09q5tNLCpRM8btu2bUTEjNQwVb29vbS3tydbf7Mr+gj/n4D3AgeNNYOklcBKgM7OTiqVSsEl1adarTZMLSl5HKCvr4+dO3cyMDCQrIaIAJh2DTuHg83VYHhvcFhbC4e07WWwuo3BOh7b0tIyIzVMR2trK21tbcm3yWbdLwoLfElnAlsiYr2knrHmi4jVwGqA7u7uSHn0UKtSqSQ9kmkUHgdYvnw5AwMD9Pb2Jqth5DWYasjUNmZXHHwgq87umlJj1ttDplnHocgj/BcAr5R0OrAQWCzpWxHxhgLXaWajuDFrIwp71SPiA8AHAPIj/Hc77M1mjxuzNpp/zZvNQb5i1vZnVgI/IipAZTbWZVZ2vmLWxuIjfLM5wlfM2kQc+GZzgBuzVg9vEWZNzI1ZmwwHvlmTcmPWJsuBb9aE3Ji1qXDgmzWR2sbs092YtUly4Js1iV1Dezjri798ojH74VcuZ5EbszYJ3lrMGlxE0L99N/du3cHO/Dtm3Zi1qXDgmzWwkcbsH/qrLF7Yyo8vfpEbszZlDnyzBlXbmD3q4AM5oqPNYW/T0pK6ADN7sqE9e/nUjXdzzuW30jpPrHnrSSzpaMPvwbHp8hG+WQMZfcWsG7M2k7wlmTUAXzFrs8GBb5aYr5i12eLAN0vIV8zabHLgmyXgK2YtBQe+2SxzY9ZS8VZmNkvcmLXUHPhms8CNWWsEDnyzgrkxa43CgW9WEDdmrdE48M0K4MasNSJvgWYzyI1Za2QOfLMZ4sasNbrCAl/SQuBnwIJ8PWsi4pKi1meWkhuz1gzGDHxJ1wN/GxH3TnHZu4GXRERVUivwc0k/johbp7g8s4bjxqw1k/GO8L8G3CTp68AnI2JoMguOiACq+Y+t+b+YSpFWXl1dXfT397Ns2bJkNaxdu5aIoKen50n37xraw8YtVaq7hznsoAXsOWQRF/+omKP63t5e2tvbC1m2lceYgR8RV0n6EfAPwDpJ3wT21kz/zEQLlzQPWA8sAy6LiNv2M89KYCVAZ2cnlUplss+hENVqtWFqSSn1OPT19TE4OMjAwECyGrJjF55Uw2O7g0d27kXAkvYWDmodZvu2xwqrobW1lba2tuTbZOrtoVE06zhMdA5/CNhBdh7+IGoCvx4RsQc4QVIHcK2k4yLijlHzrAZWA3R3d8foo6hUKpXKPkd0ZZR6HJYvX/5EHan09PQwMDBAb2/vkxqzZ5awMZt6e2gUzToO453DPxX4DHAdsCIidk51JRExIKkCnArcMcHsZg3JjVlrduMd4X8IOCsi7pzKgiUdBgzlYd8GvAz4x6ksyyylCOgfDM65/FY3Zq2pjXcO/4XTXPbhwNfz8/gtwFUR8cNpLtNsVt23dQd3PvQY1d17uXCFr5i15lbYlhsRvwW6ilq+WZFqr5jdNbSHJe0tXHrW8anLMpsWH6qYjTL6itnFR3YwWN2WuiyzaWtJXYBZI7lt01ZOX7WWG+54mPf81bFcef7zWTDfu4nNDT7CN8NXzFo5OPCt9PxRxlYW3qqttPxRxlY2DnwrJX+UsZWRA99Kx1fMWlk58K003Ji1snPgWym4MWvmwLc5zo1Zsz9z4Nuc5cas2ZM58G1OcmPWbF8OfJtT3Jg1G5sD3+YMN2bNxue9wZqeG7Nm9XHgW1OrbcyemDdmj3Bj1my/HPjWtNyYNZscB741HTdmzabGgW9NxY1Zs6nznmJNwY1Zs+lz4FvDG94bXHjl7W7Mmk2TA98a2rZdQ/xhyw4ezr9j1o1Zs6lz4FtDGmnMbnhoGwta57kxazYDHPjWcGobs4cetIClhyxy2JvNgJaiFizpKEk3S9og6U5JFxW1LpsbIoI16/s4fdVaNvVXuezcFRxzWLtP4ZjNkCKP8IeBd0XEryUdBKyX9JOIuKvAdVqTGuuK2UtTF2Y2hxQW+BGxGdic394uaQOwBHDg16Grq4v+/n6WLVuWrIZbbrmFiODkk08udD0jjdnH9+zlyKe28XBHG+demU1bu3YtAD09PYXWMJ7e3l5aW1uTrd9spszKOXxJS4Eu4Lb9TFsJrATo7OykUqnMRkkTqlarSWvp6+tjcHCQgYGBZDUMDw8DFFZDAI8OBlsH93LAPHH0QWIhu3lsYPef54kotIZ6tLa2snjx4obZNlNKvV80imYdB43sUIWtQGoH/i/w8Yj4/njzdnd3x7p16wqtp16VSiXpUeXIulNuVB0dHQwPD1OtVmd82fVeMdsI4zCy/pTbQ6PwOGQaaRwkrY+I7nrmLfQIX1IrcA3w7YnC3srBV8yapVNY4EsScAWwISI+U9R6rHn4o4zN0iryCP8FwBuB30nqze/7YERcX+A6rUH5o4zN0ivyXTo/B7xHl5w/ytiscfhKWyuMP8rYrLF477MZ58asWWNy4NuMcmPWrHE58G3GuDFr1tgc+DZtbsyaNQcHvk2LG7NmzcN7pk2JG7NmzceBb5PmxqxZc3Lg26S4MWvWvBz4Vhc3Zs2anwPfJuTGrNnc4L3WxjW8F05ftdaNWbM5wIFv+/XY4BCDQ3sY2hsct+QpbsyazQEOfNvHSGN2aE/Q2iK+c/7z3Zg1mwMc+PaE0Y3ZRQfMI/bucdibzREtqQuwxnDf1h2c9cVf8rmbN/LaFUfyo3e80EFvNsf4CL/kfMWsWXk48EvMV8yalYsDv6R8xaxZ+TjwS8ZXzJqVlwO/RHzFrFm5eW8vATdmzQwc+HOeG7NmNsKBP4e5MWtmtQoLfElfAc4EtkTEcUWtx/Y1ujF7zVtP4ng3Zs1Kr8gj/K8BnwO+UeA6bBQ3Zs1sLIUlQUT8TNLSopZfpK6uLvr6+li+fHmyGtauXQtAT09P3Y/p376be7fuQMAzDmvnV7cewBmXTb2Gbdu2ERGTqmGm9fb20t7enmz9ZnNJ8kM/SSuBlQCdnZ1UKpW0BQF9fX3s3LmTgYGBZDVEBEBdNewJeGTHXrY9Hhw4Xxze3sK8oZ0MDOycVg0tLS1111CU1tZW2trakm8X1Wo1eQ2NwOOQadZxSB74EbEaWA3Q3d0dKY8mRyxfvpyBgQF6e3uT1TAyDhNtVCON2cFtu7jk5f9hxhuzlUol6RF+o/A4ZDwOmWYdh+SBb1PjxqyZTZYDvwm5MWtmU1Hk2zKvBHqAQyX1AZdExBVFra8MfMWsmU1Hke/SOaeoZZeRr5g1s+nyeYAm4CtmzWwmOPAbWAR86sa73Zg1sxnhwG9Qu4b2sHFLlftu3ujGrJnNCCdIgxlpzP7uwccQ8HU3Zs1shjjwG0htY3bRAfNZ9rR2h72ZzRgHfoMY3Zi96tbFuC1rZjOpJXUBZTe0Zy+fuvFuzrn8VlrniWveehJve/Eyh72ZzTgf4SfkK2bNbDY5XRLwFbNmloIDf5b5ilkzS8WBP4t8xayZpeTAnwX+KGMzawQO/IK5MWtmjcLJUxA3Zs2s0TjwC+DGrJk1Igf+DHNj1swalQN/hrgxa2aNzoE/A9yYNbNm4FSaBjdmzayZOPCnyI1ZM2s2DvwpcGPWzJqRA38S3Jg1s2bmwK+TG7Nm1uycWBNwY9bM5opCA1/SqcAqYB7w5Yj4RJHrm2luzJrZXFJY4EuaB1wGvBzoA34l6bqIuKuodc6kncPB6avWujFrZnNGkUf4zwM2RsQmAEnfBV4FNHzg/+bO3/PY9u1sufydLHtaO1f/Yj5Xz3INvb29tLe3z/JazWwuKzLwlwAP1PzcB5w4eiZJK4GVAJ2dnVQqlQJLqs+Bi9rZPTTM09theLDKwODs19Da2kpbW1vy8ahWq8lraAQeh4zHIdOs41Bk4O/v/Efsc0fEamA1QHd3d/T09BRYUn0evHcjlUqFRqglNY9DxuOQ8ThkmnUcWgpcdh9wVM3PRwIPFbg+MzMbR5GB/yvg30t6hqQDgLOB6wpcn5mZjaOwUzoRMSzp7cCNZG/L/EpE3FnU+szMbHyFvg8/Iq4Hri9yHWZmVp8iT+mYmVkDceCbmZWEA9/MrCQc+GZmJaGIfa6FSkZSP3Bf6jpyhwKPpi6iAXgcMh6HjMch00jjcHREHFbPjA0V+I1E0rqI6E5dR2oeh4zHIeNxyDTrOPiUjplZSTjwzcxKwoE/ttWpC2gQHoeMxyHjccg05Tj4HL6ZWUn4CN/MrCQc+GZmJeHA3w9Jp0q6W9JGSe9PXU8Kko6SdLOkDZLulHRR6ppSkTRP0u2Sfpi6llQkdUhaI+n3+Tbxl6lrSkHS3+X7wx2SrpS0MHVNk+HAH6Xmy9dPA54NnCPp2WmrSmIYeFdE/AXwfOBtJR0HgIuADamLSGwVcENEPAs4nhKOh6QlwDuA7og4juxj389OW9XkOPD39cSXr0fE48DIl6+XSkRsjohf57e3k+3gS9JWNfskHQmcAXw5dS2pSFoMvAi4AiAiHo+IgbRVJTMfaJM0HziQJvsWPwf+vvb35eulC7pakpYCXcBtaStJ4p+A9wJ7UxeS0DOBfuCr+amtL0talLqo2RYRDwKfAu4HNgOPRcRNaauaHAf+vur68vWykNQOXANcHBHbUtczmySdCWyJiPWpa0lsPrAC+EJEdAE7gNL1tiQ9leyv/WcARwCLJL0hbVWT48Dfl798PSeplSzsvx0R309dTwIvAF4p6V6yU3svkfSttCUl0Qf0RcTIX3hryH4BlM3LgD9GRH9EDAHfB05KXNOkOPD35S9fBySJ7Jzthoj4TOp6UoiID0TEkRGxlGw7+JeIaKojupkQEQ8DD0g6Nr/rpcBdCUtK5X7g+ZIOzPePl9JkzetCv9O2GfnL15/wAuCNwO8k9eb3fTD/nmIrnwuBb+cHQZuA8xLXM+si4jZJa4Bfk72L7Xaa7CMW/NEKZmYl4VM6ZmYl4cA3MysJB76ZWUk48M3MSsKBb2ZWEg58szHknxj6R0kH5z8/Nf/56NS1mU2FA99sDBHxAPAF4BP5XZ8AVkfEfemqMps6vw/fbBz5x0usB74CnA905Z+iatZ0fKWt2TgiYkjSe4AbgFc47K2Z+ZSO2cROI/s43ONSF2I2HQ58s3FIOgF4Odm3fv2dpMMTl2Q2ZQ58szHkn4j4BbLvArgfuJTsCzDMmpID32xs5wP3R8RP8p8/DzxL0ikJazKbMr9Lx8ysJHyEb2ZWEg58M7OScOCbmZWEA9/MrCQc+GZmJeHANzMrCQe+mVlJ/H8uytW8eHvhaQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fe612f0ce10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Note: you can run this for any (x1, y1, x2, y2)\n",
    "line = (0, 0, 7, 5)\n",
    "\n",
    "cells = list(bresenham(line[0], line[1], line[2], line[3]))\n",
    "print(cells)\n",
    "\n",
    "plt.plot([line[0], line[2]], [line[1], line[3]])\n",
    "\n",
    "\n",
    "for q in cells:\n",
    "    plt.plot([q[0], q[0]+1], [q[1], q[1]], 'k')\n",
    "    plt.plot([q[0], q[0]+1], [q[1]+1, q[1]+1], 'k')\n",
    "    plt.plot([q[0], q[0]], [q[1],q[1]+1], 'k')\n",
    "    plt.plot([q[0]+1, q[0]+1], [q[1], q[1]+1], 'k')\n",
    "\n",
    "plt.grid()\n",
    "plt.axis('equal')\n",
    "plt.xlabel(\"X\")\n",
    "plt.ylabel(\"Y\")\n",
    "plt.title(\"Python package Bresenham algorithm\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}