day 28 - convex hull.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from bokeh.plotting import figure, output_notebook, show"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def split(u, v, points):\n",
    "    # return points on left side of UV\n",
    "    return [p for p in points if np.cross(p - u, v - u) < 0]\n",
    "\n",
    "def extend(u, v, points):\n",
    "    if not points:\n",
    "        return []\n",
    "\n",
    "    # find furthest point W, and split search to WV, UW\n",
    "    w = min(points, key=lambda p: np.cross(p - u, v - u))\n",
    "    p1, p2 = split(w, v, points), split(u, w, points)\n",
    "    return extend(w, v, p1) + [w] + extend(u, w, p2)\n",
    "\n",
    "def convex_hull(points):\n",
    "    # find two hull points, U, V, and split to left and right search\n",
    "    u = min(points, key=lambda p: p[0])\n",
    "    v = max(points, key=lambda p: p[0])\n",
    "    left, right = split(u, v, points), split(v, u, points)\n",
    "    \n",
    "    # find convex hull on each side\n",
    "    return [v] + extend(u, v, left) + [u] + extend(v, u, right) + [v]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  9.95456010e-01,   7.65907653e-01],\n",
       "       [  9.64101937e-01,   9.47636262e-01],\n",
       "       [  7.49840951e-01,   9.68180575e-01],\n",
       "       [  2.13580026e-01,   9.91177434e-01],\n",
       "       [  1.18181500e-01,   9.56758533e-01],\n",
       "       [  3.77237324e-02,   8.81109123e-01],\n",
       "       [  2.75085295e-02,   2.27043559e-01],\n",
       "       [  5.72172004e-02,   2.45227737e-02],\n",
       "       [  4.40115492e-01,   5.46663495e-06],\n",
       "       [  7.37937895e-01,   6.71680586e-02],\n",
       "       [  8.47805083e-01,   9.26355385e-02],\n",
       "       [  8.97086651e-01,   1.21673019e-01],\n",
       "       [  9.57764617e-01,   1.98416655e-01],\n",
       "       [  9.95456010e-01,   7.65907653e-01]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "points = np.random.rand(100, 2)\n",
    "hull = np.array(convex_hull(points))\n",
    "hull"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <a href=\"http://bokeh.pydata.org\" target=\"_blank\" class=\"bk-logo bk-logo-small bk-logo-notebook\"></a>\n",
       "        <span id=\"fbaf469f-9b57-4056-8a23-b41b401a6262\">Loading BokehJS ...</span>\n",
       "    </div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "\n",
       "(function(global) {\n",
       "  function now() {\n",
       "    return new Date();\n",
       "  }\n",
       "\n",
       "  var force = true;\n",
       "\n",
       "  if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "    window._bokeh_onload_callbacks = [];\n",
       "    window._bokeh_is_loading = undefined;\n",
       "  }\n",
       "\n",
       "\n",
       "  \n",
       "  if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "    window._bokeh_timeout = Date.now() + 5000;\n",
       "    window._bokeh_failed_load = false;\n",
       "  }\n",
       "\n",
       "  var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "     \"<div style='background-color: #fdd'>\\n\"+\n",
       "     \"<p>\\n\"+\n",
       "     \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "     \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "     \"</p>\\n\"+\n",
       "     \"<ul>\\n\"+\n",
       "     \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "     \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "     \"</ul>\\n\"+\n",
       "     \"<code>\\n\"+\n",
       "     \"from bokeh.resources import INLINE\\n\"+\n",
       "     \"output_notebook(resources=INLINE)\\n\"+\n",
       "     \"</code>\\n\"+\n",
       "     \"</div>\"}};\n",
       "\n",
       "  function display_loaded() {\n",
       "    if (window.Bokeh !== undefined) {\n",
       "      document.getElementById(\"fbaf469f-9b57-4056-8a23-b41b401a6262\").textContent = \"BokehJS successfully loaded.\";\n",
       "    } else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(display_loaded, 100)\n",
       "    }\n",
       "  }\n",
       "\n",
       "  function run_callbacks() {\n",
       "    window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "    delete window._bokeh_onload_callbacks\n",
       "    console.info(\"Bokeh: all callbacks have finished\");\n",
       "  }\n",
       "\n",
       "  function load_libs(js_urls, callback) {\n",
       "    window._bokeh_onload_callbacks.push(callback);\n",
       "    if (window._bokeh_is_loading > 0) {\n",
       "      console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "      return null;\n",
       "    }\n",
       "    if (js_urls == null || js_urls.length === 0) {\n",
       "      run_callbacks();\n",
       "      return null;\n",
       "    }\n",
       "    console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "    window._bokeh_is_loading = js_urls.length;\n",
       "    for (var i = 0; i < js_urls.length; i++) {\n",
       "      var url = js_urls[i];\n",
       "      var s = document.createElement('script');\n",
       "      s.src = url;\n",
       "      s.async = false;\n",
       "      s.onreadystatechange = s.onload = function() {\n",
       "        window._bokeh_is_loading--;\n",
       "        if (window._bokeh_is_loading === 0) {\n",
       "          console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "          run_callbacks()\n",
       "        }\n",
       "      };\n",
       "      s.onerror = function() {\n",
       "        console.warn(\"failed to load library \" + url);\n",
       "      };\n",
       "      console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "      document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "    }\n",
       "  };var element = document.getElementById(\"fbaf469f-9b57-4056-8a23-b41b401a6262\");\n",
       "  if (element == null) {\n",
       "    console.log(\"Bokeh: ERROR: autoload.js configured with elementid 'fbaf469f-9b57-4056-8a23-b41b401a6262' but no matching script tag was found. \")\n",
       "    return false;\n",
       "  }\n",
       "\n",
       "  var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.4.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.4.min.js\"];\n",
       "\n",
       "  var inline_js = [\n",
       "    function(Bokeh) {\n",
       "      Bokeh.set_log_level(\"info\");\n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "      document.getElementById(\"fbaf469f-9b57-4056-8a23-b41b401a6262\").textContent = \"BokehJS is loading...\";\n",
       "    },\n",
       "    function(Bokeh) {\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-0.12.4.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.4.min.css\");\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.4.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.4.min.css\");\n",
       "    }\n",
       "  ];\n",
       "\n",
       "  function run_inline_js() {\n",
       "    \n",
       "    if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "      for (var i = 0; i < inline_js.length; i++) {\n",
       "        inline_js[i](window.Bokeh);\n",
       "      }if (force === true) {\n",
       "        display_loaded();\n",
       "      }} else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(run_inline_js, 100);\n",
       "    } else if (!window._bokeh_failed_load) {\n",
       "      console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "      window._bokeh_failed_load = true;\n",
       "    } else if (force !== true) {\n",
       "      var cell = $(document.getElementById(\"fbaf469f-9b57-4056-8a23-b41b401a6262\")).parents('.cell').data().cell;\n",
       "      cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "    }\n",
       "\n",
       "  }\n",
       "\n",
       "  if (window._bokeh_is_loading === 0) {\n",
       "    console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "    run_inline_js();\n",
       "  } else {\n",
       "    load_libs(js_urls, function() {\n",
       "      console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "      run_inline_js();\n",
       "    });\n",
       "  }\n",
       "}(this));"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <div class=\"bk-plotdiv\" id=\"29fbfe08-f942-46f2-9543-b0548f239fa6\"></div>\n",
       "    </div>\n",
       "<script type=\"text/javascript\">\n",
       "  \n",
       "  (function(global) {\n",
       "    function now() {\n",
       "      return new Date();\n",
       "    }\n",
       "  \n",
       "    var force = false;\n",
       "  \n",
       "    if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "      window._bokeh_onload_callbacks = [];\n",
       "      window._bokeh_is_loading = undefined;\n",
       "    }\n",
       "  \n",
       "  \n",
       "    \n",
       "    if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "      window._bokeh_timeout = Date.now() + 0;\n",
       "      window._bokeh_failed_load = false;\n",
       "    }\n",
       "  \n",
       "    var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "       \"<div style='background-color: #fdd'>\\n\"+\n",
       "       \"<p>\\n\"+\n",
       "       \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "       \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "       \"</p>\\n\"+\n",
       "       \"<ul>\\n\"+\n",
       "       \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "       \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "       \"</ul>\\n\"+\n",
       "       \"<code>\\n\"+\n",
       "       \"from bokeh.resources import INLINE\\n\"+\n",
       "       \"output_notebook(resources=INLINE)\\n\"+\n",
       "       \"</code>\\n\"+\n",
       "       \"</div>\"}};\n",
       "  \n",
       "    function display_loaded() {\n",
       "      if (window.Bokeh !== undefined) {\n",
       "        document.getElementById(\"29fbfe08-f942-46f2-9543-b0548f239fa6\").textContent = \"BokehJS successfully loaded.\";\n",
       "      } else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(display_loaded, 100)\n",
       "      }\n",
       "    }\n",
       "  \n",
       "    function run_callbacks() {\n",
       "      window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "      delete window._bokeh_onload_callbacks\n",
       "      console.info(\"Bokeh: all callbacks have finished\");\n",
       "    }\n",
       "  \n",
       "    function load_libs(js_urls, callback) {\n",
       "      window._bokeh_onload_callbacks.push(callback);\n",
       "      if (window._bokeh_is_loading > 0) {\n",
       "        console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "        return null;\n",
       "      }\n",
       "      if (js_urls == null || js_urls.length === 0) {\n",
       "        run_callbacks();\n",
       "        return null;\n",
       "      }\n",
       "      console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "      window._bokeh_is_loading = js_urls.length;\n",
       "      for (var i = 0; i < js_urls.length; i++) {\n",
       "        var url = js_urls[i];\n",
       "        var s = document.createElement('script');\n",
       "        s.src = url;\n",
       "        s.async = false;\n",
       "        s.onreadystatechange = s.onload = function() {\n",
       "          window._bokeh_is_loading--;\n",
       "          if (window._bokeh_is_loading === 0) {\n",
       "            console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "            run_callbacks()\n",
       "          }\n",
       "        };\n",
       "        s.onerror = function() {\n",
       "          console.warn(\"failed to load library \" + url);\n",
       "        };\n",
       "        console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      }\n",
       "    };var element = document.getElementById(\"29fbfe08-f942-46f2-9543-b0548f239fa6\");\n",
       "    if (element == null) {\n",
       "      console.log(\"Bokeh: ERROR: autoload.js configured with elementid '29fbfe08-f942-46f2-9543-b0548f239fa6' but no matching script tag was found. \")\n",
       "      return false;\n",
       "    }\n",
       "  \n",
       "    var js_urls = [];\n",
       "  \n",
       "    var inline_js = [\n",
       "      function(Bokeh) {\n",
       "        (function() {\n",
       "          var fn = function() {\n",
       "            var docs_json = {\"cf74eadd-323c-49ca-ad88-f3ccd451e610\":{\"roots\":{\"references\":[{\"attributes\":{\"plot\":null,\"text\":\"\"},\"id\":\"603a740f-314a-4c80-b678-a3774328862a\",\"type\":\"Title\"},{\"attributes\":{},\"id\":\"c836b661-497d-4edd-b766-514566c45150\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"callback\":null},\"id\":\"749c7139-7876-4419-9bef-6301d64ae837\",\"type\":\"DataRange1d\"},{\"attributes\":{\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"03f1ec69-182c-4523-9f66-398a6a465dcd\",\"type\":\"BasicTicker\"}},\"id\":\"3068f119-7751-4964-acf4-9a01c7d39c2a\",\"type\":\"Grid\"},{\"attributes\":{\"formatter\":{\"id\":\"c836b661-497d-4edd-b766-514566c45150\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"3893d6dc-14a0-4501-9ae4-14a29166f3ee\",\"type\":\"BasicTicker\"}},\"id\":\"b187b6ab-1ace-44bf-a422-f962f0e55f81\",\"type\":\"LinearAxis\"},{\"attributes\":{},\"id\":\"3893d6dc-14a0-4501-9ae4-14a29166f3ee\",\"type\":\"BasicTicker\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_scroll\":\"auto\",\"active_tap\":\"auto\",\"tools\":[{\"id\":\"a4431bc8-4c58-43a7-b5d9-7440bea9e3c5\",\"type\":\"PanTool\"},{\"id\":\"88133fdb-294c-45d3-b49a-db3fb4faaa14\",\"type\":\"WheelZoomTool\"},{\"id\":\"1d14a8c8-3da8-4b29-9242-af934e4dec3c\",\"type\":\"BoxZoomTool\"},{\"id\":\"b9cb0348-92b8-4431-9b19-ff79ef643f58\",\"type\":\"SaveTool\"},{\"id\":\"88ea8a5a-092b-494a-8d1e-3d97f8a23534\",\"type\":\"ResetTool\"},{\"id\":\"201a7447-2f45-42e1-b62f-9c743e879dea\",\"type\":\"HelpTool\"}]},\"id\":\"3db2a9db-158c-4472-ba3c-cfe73229e725\",\"type\":\"Toolbar\"},{\"attributes\":{\"formatter\":{\"id\":\"7645ecc6-c7c2-4b79-b7f4-0b5f2a5dd8d2\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"03f1ec69-182c-4523-9f66-398a6a465dcd\",\"type\":\"BasicTicker\"}},\"id\":\"faddb565-a989-4a52-98ef-0ba152037147\",\"type\":\"LinearAxis\"},{\"attributes\":{\"callback\":null},\"id\":\"52ef120c-a022-4817-8d96-40dead445f1e\",\"type\":\"DataRange1d\"},{\"attributes\":{},\"id\":\"a5d7bdb9-42f0-4728-b50e-7ff3f0041b71\",\"type\":\"ToolEvents\"},{\"attributes\":{},\"id\":\"03f1ec69-182c-4523-9f66-398a6a465dcd\",\"type\":\"BasicTicker\"},{\"attributes\":{\"line_color\":{\"value\":\"red\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"551e0aef-1b78-45c5-aecc-df9a5d56ae75\",\"type\":\"Line\"},{\"attributes\":{\"data_source\":{\"id\":\"bd972496-0c61-4198-ad50-4c7f8fa2cab7\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"551e0aef-1b78-45c5-aecc-df9a5d56ae75\",\"type\":\"Line\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"234090c1-490f-4a78-9cd2-161ed6679116\",\"type\":\"Line\"},\"selection_glyph\":null},\"id\":\"cb1cd9f4-7e82-486a-82cf-133a141a6bb4\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"below\":[{\"id\":\"faddb565-a989-4a52-98ef-0ba152037147\",\"type\":\"LinearAxis\"}],\"left\":[{\"id\":\"b187b6ab-1ace-44bf-a422-f962f0e55f81\",\"type\":\"LinearAxis\"}],\"renderers\":[{\"id\":\"faddb565-a989-4a52-98ef-0ba152037147\",\"type\":\"LinearAxis\"},{\"id\":\"3068f119-7751-4964-acf4-9a01c7d39c2a\",\"type\":\"Grid\"},{\"id\":\"b187b6ab-1ace-44bf-a422-f962f0e55f81\",\"type\":\"LinearAxis\"},{\"id\":\"35838a14-439f-4cec-8951-12669704dc2c\",\"type\":\"Grid\"},{\"id\":\"8105a2d5-f35e-43c0-944a-ca16d66cca11\",\"type\":\"BoxAnnotation\"},{\"id\":\"a41c665c-1861-4516-ab74-cd6b3645e376\",\"type\":\"GlyphRenderer\"},{\"id\":\"cb1cd9f4-7e82-486a-82cf-133a141a6bb4\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"603a740f-314a-4c80-b678-a3774328862a\",\"type\":\"Title\"},\"tool_events\":{\"id\":\"a5d7bdb9-42f0-4728-b50e-7ff3f0041b71\",\"type\":\"ToolEvents\"},\"toolbar\":{\"id\":\"3db2a9db-158c-4472-ba3c-cfe73229e725\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"749c7139-7876-4419-9bef-6301d64ae837\",\"type\":\"DataRange1d\"},\"y_range\":{\"id\":\"52ef120c-a022-4817-8d96-40dead445f1e\",\"type\":\"DataRange1d\"}},\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"dimension\":1,\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"3893d6dc-14a0-4501-9ae4-14a29166f3ee\",\"type\":\"BasicTicker\"}},\"id\":\"35838a14-439f-4cec-8951-12669704dc2c\",\"type\":\"Grid\"},{\"attributes\":{\"bottom_units\":\"screen\",\"fill_alpha\":{\"value\":0.5},\"fill_color\":{\"value\":\"lightgrey\"},\"left_units\":\"screen\",\"level\":\"overlay\",\"line_alpha\":{\"value\":1.0},\"line_color\":{\"value\":\"black\"},\"line_dash\":[4,4],\"line_width\":{\"value\":2},\"plot\":null,\"render_mode\":\"css\",\"right_units\":\"screen\",\"top_units\":\"screen\"},\"id\":\"8105a2d5-f35e-43c0-944a-ca16d66cca11\",\"type\":\"BoxAnnotation\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":{\"__ndarray__\":\"4CyTKTIrnD8OzR9bui/gP9ERem8SW+g/8PeBSw0T1z/oNO/ChOS8P/AXGhHqNOs/4DmR+j5q1j/N0JeNjSDmPyZJH/Ctn+Q/ojQGqv/d1T8oN2jZXv7FP93fR8cFO+0/PqicMvY12D9u0CsnxOXRPwk1LGu1d+w/jPdGsPRxyj9AfmAjKNDSP9YhpvuqS+A/AoaNIPFl1T/gLG9jAoPIP6a3st1mGec/2svi93dB0j/vyUT9E1bmP7IxHXOy/uc/xbXEMpUA6T/TyxHTQ1nnP2FWy4/G2u8/cNEi5A2gzT+my8MfGB/YP2P+VofnbeQ/M6Wsbewh4j9HeZFmqXnsP5uT1u4vnec/xwImJyNg6z/9gT+owCfrPx5fBgskUNE/GBCOVsp5vD80UcsWeH3fP7zMsQO2e9k/88m4nBOZ4T/As5wcl1bLP6hRptlBwdc/Nm3f39Ph1z9QU18m+tOjPxTpaRRPTcg/07amEO+07D+0anisZ6zrP5pm9itz4eE/kJbuExTKsT/fZY3rZsnnP5HAscF0Y+c/vxYgTuzZ7j8YSsu3QhDvPybEUcZgUOg/p6kP78sV7T8IyBmOJEG+P3ANm0oa0dg/sDmJkTf1xj/ZeiTSIHPmPxZFj/sBpu4/dH1DPSHZyj+2O9HAiRLZP9mtPSljPO0/q3XjQcaj5D9zdG3KttjiP5DEIzlgbaw/JAT6ma6iyj88k3LVUmrIP2Lao2mlTdw/doUukak74T8ghRNKD5vYP8zx2kWaK+0/kP2mqJJLrT95i7fUokPlP7CMQyWgvMM/Ik7pXsuU3j/ZmUbBAOTlPwxSB25Xwuc/ZN4WPoIQ2z96X1sKOtPRPxf50Qg2k+g/2ChQa3cY1D8lldo3R/3iPx4EJdmJYeI/YMxIaoZQoz9wGx4gOCHrP/S+EqNdTtw/fC+KZFZFxT+9Wm+oICnrP0D3C8XvDqE/qlxng2Zu0j8s6YDB2GncP+W6+6PH0uU/Jr6QKGsF3D9WidMSttLhPwKtDZz0pN4/b3aSZi9s4z+4Xqor2ircP/B3fPzWK7g/ZKENJFx41T8=\",\"dtype\":\"float64\",\"shape\":[100]},\"y\":{\"__ndarray__\":\"YMw3a8MPzT/s3okGgMnnP64Pk98Zjuw//RpBpzO24T/SkIhjOdzhP5clA/kK5uQ/Fm/hPCP/1z95/u8yc5fmP3o6NybY/tA/1CjCjwDAxj9uULWtZtPZP4SRijc7b+Q/uvg6NSIg5D921fN5xw7qPwikTfZ4LOw/cTnkHSoR6z8RlwjOsFPrP7zZOy3ZF8Q/v6fCUSQ+6z/bWDvEy5jjP+joWY9oku0/DFsf6PbxxD/BagzeGzHlP44DXNRV++4/NH1Kr8FLxD/cbjXLsR/rP8hGL8RQgug/M7NIVJMN4D8gzCDbPiKyPxhUsPeYg7M/XMJXlF6N3j8+8AZjJejtP/CkGgftMbE/E8lFg0885T+kaWr9MPfhPxuH6QGce+Y/OJkzyvw9wD9qaIDd/GvTP+tw9nwKzuY/2/XLaCTL7j/Zyem8ubfvPwhUD166u7g/7u+C+EWe4j8Q8v8CzvriPxxlVLdGtdE/6CLahvYlvz/OEuyNv8vrP8ym9nclnMU/Y5bASMic6D9YKTkKnTazPyeJrA9tUOs/KvJgSAlT7j8vqslpvfbrP8oSrDCQnu0/HsF1/xHl3D/CAPwRxJ3uPybF3gM0zNc/s0VdqDH17D8/RGxagzruP9Syr4q3Zck/GKwlsGCv1j/gi94cAl6tPxXJD4VD+eM/CNaMCjk/zz/EdtybQmrEP6juAj7Os9I/BpplnTf03z9jrnYT5zziP9i9qP29i9c/swrGbSvX4D/WjJYz7BjWP0TZr/WljN4/QJqPe38cmT/uVbtpzsTsPzYugC5L0tU//FWMJCN1xD9TdmBSFojhP8h65cTiS+s/8Msvtk1toz8wkdTkuGS+P1J2VNHq2tk/hQ0kbpIJ6z96AWthWZjhP6QmnWiZuOc//ahwwgsy7D+glDdw9ra3P0Kk6nipo+A/3zsxeoD/5z8Ue06KZaXKP+zUmBE8/tk/dm/aQrii4j+/HDvXS5HnPwAKy4fifec/hicxRoC77T9O3nWCRUjbPzirBuNUrdo/5uB2fGH10j8AADgswe3WPj8e5+80Tuo/ZcT2ShC+6T8=\",\"dtype\":\"float64\",\"shape\":[100]}}},\"id\":\"d2abdf16-faac-4bce-9770-1f27754e9052\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"fill_color\":{\"value\":\"#1f77b4\"},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"a38d5631-f6db-4fba-b82c-4e6ef853921b\",\"type\":\"Circle\"},{\"attributes\":{\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"201a7447-2f45-42e1-b62f-9c743e879dea\",\"type\":\"HelpTool\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"y\"],\"data\":{\"x\":{\"__ndarray__\":\"YVbLj8ba7z+/FiBO7NnuP7IxHXOy/uc/wLOcHJdWyz8IyBmOJEG+P2DMSGqGUKM/4CyTKTIrnD+Q/aaokkutP7heqivaKtw/m5PW7i+d5z9wGx4gOCHrP9O2phDvtOw/FkWP+wGm7j9hVsuPxtrvPw==\",\"dtype\":\"float64\",\"shape\":[14]},\"y\":{\"__ndarray__\":\"yEYvxFCC6D8q8mBICVPuP44DXNRV++4/2cnpvLm37z/CAPwRxJ3uP/2ocMILMuw/YMw3a8MPzT9Amo97fxyZPwAAOCzB7dY+8KQaB+0xsT+glDdw9ra3P+gi2ob2Jb8/1LKvirdlyT/IRi/EUILoPw==\",\"dtype\":\"float64\",\"shape\":[14]}}},\"id\":\"bd972496-0c61-4198-ad50-4c7f8fa2cab7\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"88ea8a5a-092b-494a-8d1e-3d97f8a23534\",\"type\":\"ResetTool\"},{\"attributes\":{},\"id\":\"7645ecc6-c7c2-4b79-b7f4-0b5f2a5dd8d2\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"overlay\":{\"id\":\"8105a2d5-f35e-43c0-944a-ca16d66cca11\",\"type\":\"BoxAnnotation\"},\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"1d14a8c8-3da8-4b29-9242-af934e4dec3c\",\"type\":\"BoxZoomTool\"},{\"attributes\":{\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"b9cb0348-92b8-4431-9b19-ff79ef643f58\",\"type\":\"SaveTool\"},{\"attributes\":{\"fill_alpha\":{\"value\":0.1},\"fill_color\":{\"value\":\"#1f77b4\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"323a04c9-1875-4bbf-a9d9-c5e86249383d\",\"type\":\"Circle\"},{\"attributes\":{\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"88133fdb-294c-45d3-b49a-db3fb4faaa14\",\"type\":\"WheelZoomTool\"},{\"attributes\":{\"plot\":{\"id\":\"6afebb37-8500-423c-ab49-710cbd2500f7\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"a4431bc8-4c58-43a7-b5d9-7440bea9e3c5\",\"type\":\"PanTool\"},{\"attributes\":{\"data_source\":{\"id\":\"d2abdf16-faac-4bce-9770-1f27754e9052\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"a38d5631-f6db-4fba-b82c-4e6ef853921b\",\"type\":\"Circle\"},\"hover_glyph\":null,\"nonselection_glyph\":{\"id\":\"323a04c9-1875-4bbf-a9d9-c5e86249383d\",\"type\":\"Circle\"},\"selection_glyph\":null},\"id\":\"a41c665c-1861-4516-ab74-cd6b3645e376\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x\":{\"field\":\"x\"},\"y\":{\"field\":\"y\"}},\"id\":\"234090c1-490f-4a78-9cd2-161ed6679116\",\"type\":\"Line\"}],\"root_ids\":[\"6afebb37-8500-423c-ab49-710cbd2500f7\"]},\"title\":\"Bokeh Application\",\"version\":\"0.12.4\"}};\n",
       "            var render_items = [{\"docid\":\"cf74eadd-323c-49ca-ad88-f3ccd451e610\",\"elementid\":\"29fbfe08-f942-46f2-9543-b0548f239fa6\",\"modelid\":\"6afebb37-8500-423c-ab49-710cbd2500f7\"}];\n",
       "            \n",
       "            Bokeh.embed.embed_items(docs_json, render_items);\n",
       "          };\n",
       "          if (document.readyState != \"loading\") fn();\n",
       "          else document.addEventListener(\"DOMContentLoaded\", fn);\n",
       "        })();\n",
       "      },\n",
       "      function(Bokeh) {\n",
       "      }\n",
       "    ];\n",
       "  \n",
       "    function run_inline_js() {\n",
       "      \n",
       "      if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "        for (var i = 0; i < inline_js.length; i++) {\n",
       "          inline_js[i](window.Bokeh);\n",
       "        }if (force === true) {\n",
       "          display_loaded();\n",
       "        }} else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(run_inline_js, 100);\n",
       "      } else if (!window._bokeh_failed_load) {\n",
       "        console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "        window._bokeh_failed_load = true;\n",
       "      } else if (force !== true) {\n",
       "        var cell = $(document.getElementById(\"29fbfe08-f942-46f2-9543-b0548f239fa6\")).parents('.cell').data().cell;\n",
       "        cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "      }\n",
       "  \n",
       "    }\n",
       "  \n",
       "    if (window._bokeh_is_loading === 0) {\n",
       "      console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "      run_inline_js();\n",
       "    } else {\n",
       "      load_libs(js_urls, function() {\n",
       "        console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "        run_inline_js();\n",
       "      });\n",
       "    }\n",
       "  }(this));\n",
       "</script>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "output_notebook()\n",
    "\n",
    "plot = figure()\n",
    "plot.scatter(x=points[:, 0], y=points[:, 1])\n",
    "plot.line(x=hull[:, 0], y=hull[:, 1], color='red')\n",
    "\n",
    "show(plot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}