{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "def qhull(pts):\n",
    " maxx = max(pts, key=lambda pt: pt[0])\n",
    " minx = min(pts, key=lambda pt: pt[0])\n",
    " hull_up = handle_line(pts, (minx, maxx))\n",
    " hull_down = handle_line(pts, (maxx, minx))\n",
    " return hull_up + hull_down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def handle_line(pts, line):\n",
    " left = [p for p in pts if leftOf(p, line)]\n",
    " if len(left) == 0: return []\n",
    " pivot = max(left, key=lambda pt: distanceToLine(pt, line))\n",
    " \n",
    " l = handle_line(left, (line[0], pivot))\n",
    " r = handle_line(left, (pivot, line[1]))\n",
    " hull= [line[0]] + l + [pivot] + r + [line[1]]\n",
    " return hull\n",
    "\n",
    "def distanceToLine(pt, (f, t)):\n",
    " return np.linalg.norm(cross(t - f, f - pt)) / np.linalg.norm(t - f)\n",
    "def leftOf(pt, (f, t)):\n",
    " return dot(ortho(t - f), (pt - f)) < -0.00000001\n",
    "def ortho(v):\n",
    " return np.array([-v[1], v[0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "pts = np.array([[24,10],[27,1],[35,1],[38,4],[34,9],[44,8],[50,19],[44,25],[24,25],[30,18],[24,10],[27,1]])\n",
    "pts[:,1]\n",
    "plt.figure()\n",
    "plt.scatter(pts[:,0],pts[:,1])\n",
    "plt.show()\n",
    "plt.figure()\n",
    "plt.scatter([1,2,3],[1,3,4])\n",
    "plt.show()\n",
    "#print(qhull(pts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}