{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Implementation of the Graham Scan algorithm.\n", "\n", "Sources:\n", " \n", " - https://en.wikipedia.org/wiki/Graham_scan (Not 100% clear to me)\n", " - http://www.dcs.gla.ac.uk/~pat/52233/slides/Hull1x1.pdf" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "%matplotlib inline\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We want to sort a set of points in the upper half plane by the angle the point makes with the +ve x-axis.\n", "\n", "Thus (x1,y1) <= (x2,y2) if decided by:\n", "\n", " - x1 >= 0 and x2 < 0\n", " - x2 ==0 and x1 > 0\n", " - if x1, x2 == 0 then y1 <= y2\n", " - if x1, x2 > 0 then y1/x1 <= y2/x2\n", " - and if y1/x1 == y2/x2 then x1 <= x2\n", " - and finally if x1, x2 < 0 then iff (-x1,y1) >= (-x2,y2)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class UpperHalfPlanePoint:\n", " def __init__(self, x, y):\n", " self.x, self.y = x, y\n", " \n", " def __repr__(self):\n", " return \"UpperHalfPlanePoint({},{})\".format(self.x, self.y)\n", " \n", " def __le__(self, rhs):\n", " # Special case is that (0,0) is the \"smallest\", so effectively (infty, 0)\n", " if self.x == 0 and self.y == 0:\n", " return True\n", " if rhs.x == 0 and rhs.y == 0:\n", " return False\n", " if rhs.x < 0:\n", " if self.x < 0:\n", " return UpperHalfPlanePoint(-rhs.x, rhs.y) <= UpperHalfPlanePoint(-self.x, self.y)\n", " return True\n", " if rhs.x == 0:\n", " if self.x > 0:\n", " return True\n", " if self.x < 0:\n", " return False\n", " return self.y <= rhs.y\n", " # So now rhs.x > 0\n", " if self.x <= 0:\n", " return False\n", " #slope1 = self.y / self.x\n", " #slope2 = rhs.y / rhs.x\n", " #if slope1 < slope2:\n", " # return True\n", " #if slope1 > slope2:\n", " # return False\n", " if self.y * rhs.x < rhs.y * self.x:\n", " return True\n", " if self.y * rhs.x > rhs.y * self.x:\n", " return False\n", " return self.x <= rhs.x\n", " \n", " def __eq__(self, rhs):\n", " return self <= rhs and rhs <= self\n", " \n", " def __ge__(self, rhs):\n", " return rhs <= self\n", " \n", " def __lt__(self, rhs):\n", " return self <= rhs and not rhs <= self\n", " \n", " def __gt__(self, rhs):\n", " return rhs < self\n", " \n", " def __ne__(self, rhs):\n", " return not self <= rhs or not rhs <= self\n", " \n", "UpperHalfPlanePoint(0,1) <= UpperHalfPlanePoint(-1,-1)" ] }, { "cell_type": "code", "execution_count": 165, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from collections import namedtuple\n", "Point = namedtuple(\"Point\", [\"x\", \"y\"])\n", "\n", "def colinear(one, two, three):\n", " \"\"\"Considers the vectors from one--two and one--three. Returns:\n", " 0 to indicate colinear\n", " -ve to indicate three lies on the right of the half-plane from one to two.\n", " +ve shows on the left.\"\"\"\n", " return (two.x-one.x) * (three.y-one.y) - (two.y-one.y) * (three.x-one.x)\n", "\n", "def FindExtremePoints(points, leaveColinear = True):\n", " lowerLeft = points[0]\n", " for point in points:\n", " if point.y < lowerLeft.y or ( point.y == lowerLeft.y and point.x < lowerLeft.x ):\n", " lowerLeft = point\n", " inUHP = [ UpperHalfPlanePoint(pt.x - lowerLeft.x, pt.y - lowerLeft.y) for pt in points ]\n", " inUHP.sort()\n", " #print(points, \"-->\", lowerLeft)\n", " #print(inUHP)\n", " # Need to check for repeated points\n", " uniques = [inUHP[0]]\n", " index = 1\n", " for index in range(1, len(inUHP)):\n", " if inUHP[index] != inUHP[index - 1]:\n", " uniques.append(inUHP[index])\n", " inUHP = uniques\n", " if len(inUHP) <= 2:\n", " return [ Point(pt.x + lowerLeft.x, pt.y + lowerLeft.y) for pt in inUHP ]\n", " # Now implement the Graham Scan algorithm\n", " convexHull = [inUHP[0], inUHP[1], inUHP[2]]\n", " index = 3\n", " while True:\n", " #direction = ( (convexHull[-2].x - convexHull[-3].x) * (convexHull[-1].y - convexHull[-3].y)\n", " # - (convexHull[-2].y - convexHull[-3].y) * (convexHull[-1].x - convexHull[-3].x) )\n", " direction = colinear(convexHull[-3], convexHull[-2], convexHull[-1])\n", " if direction < 0 or (leaveColinear == False and direction == 0):\n", " # Right turn, so reject -2 point\n", " #print(convexHull[-3], convexHull[-2], convexHull[-1], \"Right\")\n", " del convexHull[-2]\n", " #newBack = convexHull.pop()\n", " #convexHull.pop()\n", " #convexHull.append(newBack)\n", " # If we delete colinears then possible to run out of points!\n", " if len(convexHull) < 3:\n", " if index == len(inUHP):\n", " break\n", " convexHull.append( inUHP[index] )\n", " index += 1\n", " else:\n", " #print(convexHull[-3], convexHull[-2], convexHull[-1], \"Left\")\n", " if index == len(inUHP):\n", " break\n", " convexHull.append( inUHP[index] )\n", " index += 1\n", "\n", " return [ Point(pt.x + lowerLeft.x, pt.y + lowerLeft.y) for pt in convexHull ]" ] }, { "cell_type": "code", "execution_count": 166, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[Point(x=0, y=0), Point(x=2, y=2)]\n", "[Point(x=0, y=0), Point(x=1, y=1), Point(x=2, y=2)]\n", "[Point(x=0, y=0), Point(x=2, y=2)]\n", "[Point(x=0, y=0), Point(x=1, y=1), Point(x=2, y=2), Point(x=3, y=3)]\n", "[Point(x=0, y=0), Point(x=3, y=3)]\n", "[Point(x=0, y=0), Point(x=1, y=1), Point(x=2, y=2), Point(x=3, y=3), Point(x=0, y=5)]\n", "[Point(x=0, y=0), Point(x=3, y=3), Point(x=0, y=5)]\n" ] } ], "source": [ "# So difficult corner cases!\n", "print(FindExtremePoints([Point(0,0), Point(2,2)]))\n", "print(FindExtremePoints([Point(0,0), Point(2,2), Point(1,1)]))\n", "print(FindExtremePoints([Point(0,0), Point(2,2), Point(1,1)], False))\n", "print(FindExtremePoints([Point(0,0), Point(2,2), Point(1,1), Point(3,3)]))\n", "print(FindExtremePoints([Point(0,0), Point(2,2), Point(1,1), Point(3,3)], False))\n", "print(FindExtremePoints([Point(0,0), Point(2,2), Point(1,1), Point(3,3), Point(0,5)]))\n", "print(FindExtremePoints([Point(0,0), Point(2,2), Point(1,1), Point(3,3), Point(0,5)], False))" ] }, { "cell_type": "code", "execution_count": 170, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[]" ] }, "execution_count": 170, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": [ "iVBORw0KGgoAAAANSUhEUgAAAXMAAAEACAYAAABBDJb9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n", "AAALEgAACxIB0t1+/AAAFmFJREFUeJzt3X2wXHV9x/H3h1xTEhEoQQMhtKFOUwNSGwyXiFJShREY\n", "nxBFQRBTtZ0xPEjiA9wohJkmQDsEHBNmVCBFeVIDONAikKq3YukEIlGQQFGmVJI0gQQbhUTkwrd/\n", "nBPYhJv7sHt2zzm//bxmdrLn3H347g358t3PnrM/RQRmZlZvu5VdgJmZtc7N3MwsAW7mZmYJcDM3\n", "M0uAm7mZWQLczM3MEjCiZi7pGkkbJT3UsG8fSSskPSbpbkl7t69MMzMbykgn82XAcTvtOw9YERFT\n", "gR/k22ZmVgKN9KQhSVOA2yPi0Hz7UeDoiNgoaT+gPyLe1K5Czcxs11rJzCdGxMb8+kZgYgH1mJlZ\n", "Ewr5ADSy8d7fC2BmVpKeFu67UdJ+EbFB0v7AU4PdSJKbvJlZEyJCI71tK838NuAM4NL8z+8VUVDd\n", "SFoQEQvKrqMdUn5t4NdXd13w+kY1CI/00MQbgXuBv5D0pKTZwCXAsZIeA96Zb5uZWQlGNJlHxCm7\n", "+NExBdZiZmZN8hmgresvu4A26i+7gDbrL7uANusvu4A26y+7gCoZ8XHmTT+BFCln5mZm7TDa3unJ\n", "3MwsAW7mZmYJcDM3M0uAm7mZWQLczM3MEuBmbmaWADdzM7MEuJmbmSXAzdzMLAFu5tZ11Lu0T5NX\n", "btLklZvUu7Sv7HrMiuDT+a2rqHdpH6tnL2RgfLajZytMXzY/7puzqNzKzHbk0/nNhrJ+xtyskT8G\n", "fBUGtsC6t84tuyyzVnkyt66iid9+hqd+/MfwLWBvYBvo+SB+9x/AGuDh/LIG2BDt/gditguj7Z2t\n", "rDRkVguSBBwNzGW3sWPRuRD/BeyfxSxvWnQxv1i4Ajgkv3ww/3OMpO2N3U3eKs2TuSVL0ljgI8C5\n", "wDjgcuA6Dl/yWdbPyKKVSasW7yovl/QG4GBeafLbr4/hlcbuJm9tMdre6WZuyZG0D/D3wJnAI8Bi\n", "4M6IeKmgx3eTt7ZzM7euJWkqcA5wKtkC41dExM87+Pxu8lYYN3PrKjvk4TAT+BpwZUT8b6mFNXCT\n", "t2a4mVtX2FUeHhFbSy1sFNzkbShu5pa0dufhVeAmb+BmbokqOw+vAjf57uJmbsmoQx5eBW7yaXIz\n", "t9pLIQ+vgrzJNzb37ZfdcJOvPDdzq61uyMOrwE2+HtzMrXach1eDm3y1uJlbLTgPrw83+XJ0vJlL\n", "Oh84DXgJeAiYHRHPN1uQpa0hD58L7I7z8Npyk2+vjjZzSVOAHwLTIuJ5Sd8G7oiIa5styNLkPLx7\n", "uMkXo9Nfgftb4AVgvKQXgfHAuhYf0xKS5+GfBU4hy8NPcB6etoh4CngK+FHj/kGa/En5n7uN5quG\n", "1bu0byTfetltiohZ/g64DNgG3BURp+/0c0/mXSbPw2eRHVroPNyGNKpJ/pDzjuHRL53Hi6/N7pzw\n", "sn+djlneCNwOHAVsAb4LLI+I65styOrLebgVadAmrz2PIsYI9gC+CMyBA1ZujrVH7Ftmre3Q6Zhl\n", "BnBvRGzOn/wW4Ejg+sYbSVrQsNkfEf0tPq9VyCB5+Hych1uLBotrNHnlJtYdNAGuARYCJ5dVXuEk\n", "zSJ7R9uUVpv5o8CXJY0Dfg8cA9y3840iYkGLz2MV5DzcOm7SqsVsPHQhA+cBW0Cnwv7vvRyOKLuy\n", "luVDbv/2bUkXjub+RWTmXwDOIDs08QHgUxHxQsPPHbMkxHm4le3lD0BjADa971n+8MzXIuLisusq\n", "mk8asrZwHm5VJGkysAr4cETcU3Y9RXIzt0L5+HCrOknHA18HDouIp8uupyij7Z27tbMYqy9JUyVd\n", "CTwOTCXLw4+JiDvcyK1KIuL7wHXAtyR1bU/r2hdur6bM30i6DfgJsBk4OCJm+4NNq7gv88rxil3J\n", "MYs5D7ckpJafOzO3EXMebqlJKT93Zm7Dch5uqerm/LyrXmw3cx5uXaQr83PHLIlzHm7dKIX83Jm5\n", "Aa/Kw9eQ5eF3OUaxblH3/NyZeZcbJA8/PiKOjYjvu5FbN+m2/Dz5F9gNBsnDN5Gt/jQ7Ih4suTyz\n", "MnVNfu5mXhPqXdqnySs3afLKTepd2gdZHi7pdLIvOLsS+BfgTyPigojYUGa9ZlUQEQPAR4FzJB1V\n", "dj3t5My8BtS7tI/VsxcyMD7bMWYt7PWBu3nmp2/GebjZsOqYn/sD0ARlX8h/xIQsQbkBuBHGHfE8\n", "2+7qdYxiNjKSLgamk51XUfnBxx+AJutesq8Rfx3wCOxz0bNu5GajknR+7mZeBxPuuhI+RjaVXwo9\n", "e2YrrpjZiKWenztmqbh8ZZ/lvG7q/uz5zakATFq1OMXVyM06oS75uTPzxEg6C/gEcGREPF9yOWZJ\n", "qEN+7maeEEkzgDuAt0XE42XXY5YKST1kiyf/a1XXD/UHoImQtDfwHeAzbuRmxUoxP/dkXkEv5+Sw\n", "PiLOKrses1RVOT/3ZJ6GM4EpwOdKrsMsaSl9f4sn84pxTm7WWVXNzz2Z15hzcrPOSyU/92ReEc7J\n", "zcpVtfzck3l9OSc3K1Hd83NP5hXgnNysGqqUn3syrxnn5GbVUef83JN5iZyTm1VTFfLzjk/mkvaW\n", "tFzSI5LWSJrZ6mN2EefkZhVUx/y85clc0rXAv0fENXne9NqI2NLwc0/mgxhtTq6L9G5gXr55WVwY\n", "d7WzvpSl/rtM/fV1ysv5+T5vfY5xS98KdPQbSzv6RVuS9gJWR8SfFVVQN8hz8geAL0TE8mFvn/3j\n", "vBUYl+/aBpzof6Sjl/rvMvXX12k65AuXsObaL2Zp6FHQsxWmL5vfiYbe6ZjlIOBpScskPSDpG5LG\n", "t/iYSctz8qvJPi0ftpHn5vHKP07y6/N2cVsbWuq/y9RfX2dtOelT8M/AqcDTMDAe1s+YW3JVg+op\n", "4P6HAWdGxP2SrgDOAy5ovJGkBQ2b/RHR3+Lz1tn2nPzUkuswsxE5nqylvQFo3wEjkmaRrQ3ZlFYn\n", "87XA2oi4P99eTtbcdxARCxou/S0+Z23lOfmXgZNHudDEZWRvl7fblu+z0Uv9d5n66+usSasW07MV\n", "+HS23bO1bUs2RkR/Y68c7f1bauYRsQF4UtLUfNcxwMOtPGaqWjmePM87TwRW5BdnoE1K/XeZ+uvr\n", "tLhvziKmL5vPASs3Ax3Ly5tRxNEsbwGuAsYCjwOzfTTLjnw8uVn9dbqXedm4CvI6nmb1V/Vm3uoH\n", "oDaMhpz8bW7kZtYutTizqa78vStm1imOWdrEOblZWhyzdC8fT25mHeNm3gbOyc2s05yZF8w5uZmV\n", "wZl5gZyTm6XLmXl3cU5uZqVwMy+Ic3IzK5Mz8wI4Jzezsjkzb5FzcrPu4Mw8Uepd2sf6GXPZ8+zd\n", "2XbtFl7YssvVlmxoXubMrHWOWZqg3qV9rJ69kHVjJvDbG1/LSz+ZxOFLvJpLExqWOTs2v9ya7zOz\n", "UXAzb8b6GXMZ2B2YDVwJL765sktJ1YCXOTMrgGOWpu0G3A1Mop1LSZmZjYQn82a8vJTU/tl2G5eS\n", "6gJe5sysAD6apUkvfwC6buYEDl9S2aWk6sAfgFodVP1oFjfzFqX++swsU/Vm7pjFzCwBbuZmZglw\n", "MzczS4CbuZlZAtzMzcwS4GZuZpYAN3MzswS4mZuZJcDN3MwsAW7mZmYJKKSZSxojabWk24t4PDMz\n", "G52iJvNzgDX4u2DNzErRcjOXNBk4AbgK8BdOmZmVoIjJ/HLg88BLBTyWmZk1oaWVhiS9B3gqIlZL\n", "mjXE7RY0bPZHRH8rz2tmlpq8h85q+v6tfJ+5pEXA6cAAsDuwJ3BzRHy84TZJf9936q/PzDJV/z7z\n", "whankHQ08LmIeG8rBdVN6q/PzDJVb+ZFH2fuo1nMzErgZeNalPrrM7NMt03mZmZWAjdzM7MEuJmb\n", "mSXAzdzMLAFu5mZmCXAzNzNLgJu5mVkC3MzNzBLgZm5mlgA3czOzBLiZm5klwM28SbpI79ZFunv7\n", "9bLrMbP2UO/SPk1euWn79bLr2RU38ybkzftW4Nh8161u6GbpUe/SPlbPXsi6IyYAsHr2wqo2dDfz\n", "5swDxjVsj8v3mVlK1s+Yy8BWIF9vZ2B8tq+C3MzNzHZl64qxcCjw+rIrGZabeXMuA7Y1bG/L95lZ\n", "AiTtK+kmfnfJ84y5nuyfd0DPVpi0anHZ9Q3GzbwJcWHcBZwIrMh3nZjvM7Oak3QS8BCwjoHn/oTD\n", "HpnPASs3c8DKzUxfNj/um7Oo7BoH45WGWpT66zPrFpL2BZYA04HZEXFvyfV4pSEzs9HYYRqHvyq7\n", "kTejp+wCzMzKstM0flIdm/h2nszNrCulMI038mRuZl0lpWm8kSdzM+saqU3jjTyZm1nyUp3GG3ky\n", "N7OkpTyNN/JkbmZJ6oZpvJEnczNLTrdM4408mZtZMrptGm/U0mQu6UBJP5L0sKRfSDq7qMLMzEaj\n", "G6fxRq3GLC8A50bEIcBMYI6kaa2XVX11WX3ErN22r7qVXzq+SMvL33AIi8im8XkRsW24+6WmpWYe\n", "ERsi4mf59WeBR4BJRRRWZXVafcSsnXZadetYOrzqVrdP440K+wBU0hSynGplUY9ZWetnzGVgPLAh\n", "267w6iNmbVbKqluexl+tkA9AJe0BLAfOySf0nX++oGGzPyL6i3jecgVwQn79VoiJZRZj1jXyaXwJ\n", "cAPZV9Um0cQlzQJmNXv/lpu5pNcANwPXRcT3BrtNRCxo9XkqZdKqxWw8dCED95G9w7wYNj4saetZ\n", "wLLB/odmlqjLgHfwynTetlW3Uj9SJR9y+7dvS7pwNPdv9WgWAVcDayLiilYeq07ivjmLmL5sPgf8\n", "dDMH/MlmDj9jPi9ufQ/w18ATkv5R0oFl12nWbjuturWCNq265Wx8eC2tNCTpHcCPgQfJcgeA8yPi\n", "zobbdNVKPJIOAs4CPgHcCVweEfeXWpRZTVVt9Z9OGm3v9LJxbSJpL+CTwDnAr4HFwG0R8WKphZnV\n", "xE7Z+JdSycZHys28YiT1kL0NnQe8HrgC5+pmu9TN03gjrwFaMRExEBHfjYiZwGlkufr/OFc3ezVn\n", "483zZF6CPFc/GzgD5+pmnsYH4cm8BiLivyPiXOAgYBWwXNI9kk6UNKbk8sw6ytN4MTyZV0Ceq38Q\n", "mItzdesSnsaH5sm8hvJc/TvO1a1beBovnifzinKubinyND5ynswT4VzdUuNpvL08mdeEc3WrK0/j\n", "zfFknqhd5OpPSLrUubpVlafxzvFkXmOD5OqLI2JVuVWZeRovgifzLjJIrn6zpB87V7cyeRovhyfz\n", "hDhXtzJ5Gi+WJ/Mu5lzdyuJpvHyezBPnXN3aydN4+3gytx04V7d28TReLZ7Mu4xzdWuVp/HO8GRu\n", "Q3Kubq3wNF5dnszNuboNy9N453kyt1Fzrm5D8TReD57M7VUacvV5wL44V+9KnsbL5cncWrY9Vwdm\n", "AqcDR+Ncvat4Gq8fT+Y2Is7Vu4On8erwZG5tsVOu/lOcqyfH03i9eTK3pjhXT4en8WryZG4d4Vw9\n", "DZ7G0+HJ3ArjXL0+PI1XnydzK80QufoHnKtXh6fxNLU8mUs6jiwvHQNcFRGX7vRzT+ZdaqdcfQLw\n", "FZyrl8bTeL10dDLPp60lwHHAwcApkqa18piWjp1y9Y+zY64+udzquoun8fS1GrP0Ar+KiCci4gXg\n", "JuD9rZdlKYnMvRHxIeBwYCzwoKTrJc1Q79I+TV65SZNXblLv0r6Sy629HX6fh17wD5JuAhYBJ0XE\n", "vIjYVnaN1gYR0fQF+BDwjYbt04Cv7nSbaOU5fEnzAuwFzGPMuN/A2wNuDRgIep4LDl/SV3Z9db1w\n", "+JI+ep4LiIDlARODPafdA4wruzZfRvl3Ocre2epk3t5DYSxZEbElIi5j4ooXswNgLgbeCQPjYf2M\n", "uWXXV1vrZ8xlYDxwJdAH3AKvWzYtPI0nr6fF+68DGo8pPhBYu/ONJC1o2OyPiP4Wn9dSoR7gZODD\n", "ZKmfYB0TJA8KxTgSWFl2ETYCkmYBs5p+gBbfBvQAjwNTyHLQnwHTWnmr4Et3XXaMBcIxi3+fvmz/\n", "uxxl7yzi0MTjeeXQxKsj4uKdfh7hQxNtCOpd2vdytDJp1eK4b86ikkuqNf8+0zDa3ukzQM3MKshn\n", "gJqZdSE3czOzBLiZm5klwM3czCwBbuZmZglwMzczS4CbuZlZAtzMzcwS4GZuZpYAN3MzswS4mZuZ\n", "JcDN3MwsAW7mZmYJcDM3M0uAm7mZWQLczM3MEuBmbmaWADdzM7MEuJmbmSXAzdzMLAFu5mZmCXAz\n", "NzNLgJu5mVkC3MzNzBLgZm5mlgA3czOzBLiZm5klwM3czCwBTTdzSf8k6RFJP5d0i6S9iizMzMxG\n", "rpXJ/G7gkIh4C/AYcH4xJdWLpFll19AuKb828Ouru9Rf32g13cwjYkVEvJRvrgQmF1NS7cwqu4A2\n", "mlV2AW02q+wC2mxW2QW02ayyC6iSojLzvwXuKOixzMxslHqG+qGkFcB+g/yoLyJuz28zH/hDRNzQ\n", "hvrMzGwEFBHN31n6BPBp4F0R8ftd3Kb5JzAz62IRoZHedsjJfCiSjgM+Dxy9q0Y+2mLMzKw5TU/m\n", "kn4JjAWeyXf9Z0R8pqjCzMxs5FqKWczMrBo6cgZoiicYSTpO0qOSfinpi2XXUyRJB0r6kaSHJf1C\n", "0tll19QOksZIWi3p9rJrKZqkvSUtz//drZE0s+yaiiLp/Py/zYck3SDpj8quqRWSrpG0UdJDDfv2\n", "kbRC0mOS7pa093CP06nT+ZM6wUjSGGAJcBxwMHCKpGnlVlWoF4BzI+IQYCYwJ7HXt905wBogxben\n", "XwHuiIhpwF8Cj5RcTyEkTSE76OKwiDgUGAN8tMyaCrCMrJc0Og9YERFTgR/k20PqSDNP8ASjXuBX\n", "EfFERLwA3AS8v+SaChMRGyLiZ/n1Z8kawaRyqyqWpMnACcBVQFIf0ufvfI+KiGsAImIgIraUXFZR\n", "fks2bIyX1AOMB9aVW1JrIuIe4Dc77X4fcG1+/VrgA8M9ThlftJXCCUYHAE82bK/N9yUnn4Smk/1P\n", "OCWXkx2N9dJwN6yhg4CnJS2T9ICkb0gaX3ZRRYiIZ4DLgF8D64H/i4h/K7eqtpgYERvz6xuBicPd\n", "obBmnuc7Dw1yeW/DbVI5wSjFt+WvImkPYDlwTj6hJ0HSe4CnImI1iU3luR7gMODKiDgMeI4RvE2v\n", "A0lvBD4LTCF7t7iHpI+VWlSbRXaUyrA9p+njzAd5wmOH+nl+gtEJwLuKes4SrQMObNg+kGw6T4ak\n", "1wA3A9dFxPfKrqdgRwLvk3QCsDuwp6RvRsTHS66rKGuBtRFxf769nESaOTADuDciNgNIuoXs7/P6\n", "Uqsq3kZJ+0XEBkn7A08Nd4dOHc2y/QSj9w91glGNrAL+XNIUSWOBjwC3lVxTYSQJuBpYExFXlF1P\n", "0SKiLyIOjIiDyD48+2FCjZyI2AA8KWlqvusY4OESSyrSo8BMSePy/06PIfsQOzW3AWfk188Ahh2o\n", "CpvMh/FVshOMVmS//3qfYBQRA5LOBO4i+zT96ohI4miB3NuB04AHJa3O950fEXeWWFM7pRibnQVc\n", "nw8bjwOzS66nEBHxc0nfJBuoXgIeAL5eblWtkXQjcDSwr6QngQuAS4DvSPok8ARw8rCP45OGzMzq\n", "z8vGmZklwM3czCwBbuZmZglwMzczS4CbuZlZAtzMzcwS4GZuZpYAN3MzswT8P5fiEWR3nv66AAAA\n", "AElFTkSuQmCC\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import random\n", "points = [Point(random.randrange(10), random.randrange(10)) for _ in range(15)]\n", "extpts = FindExtremePoints( points, False )\n", "fig, ax = plt.subplots()\n", "ax.scatter([pt.x for pt in points], [pt.y for pt in points], color = \"green\")\n", "ax.scatter([pt.x for pt in extpts], [pt.y for pt in extpts], color = \"blue\")\n", "for i in range(len(extpts)-1):\n", " ax.plot( [extpts[i].x, extpts[i+1].x], [extpts[i].y, extpts[i+1].y], color = \"black\" )\n", "ax.plot( [extpts[-1].x, extpts[0].x], [extpts[-1].y, extpts[0].y], color = \"black\" )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Application to 2D Linear Programming" ] }, { "cell_type": "code", "execution_count": 197, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[Point(x=0, y=0),\n", " Point(x=40.0, y=2.0),\n", " Point(x=340.0, y=97.0),\n", " Point(x=360.0, y=147.0),\n", " Point(x=370.0, y=177.0),\n", " Point(x=330.0, y=175.0),\n", " Point(x=30.0, y=80.0),\n", " Point(x=10.0, y=30.0)]" ] }, "execution_count": 197, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": [ "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEACAYAAABfxaZOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n", "AAALEgAACxIB0t1+/AAAHbtJREFUeJzt3XuYXXV97/H3Jwm3ECVAPIEkCJweaEkPSDQMfZTLWC4D\n", "arkdRBAQI7XtEVs9QS4ZqIHWIPA0UXvO2ONTIAVEFK1YaI/cxHjhlMRAwj0CR1IJIeEiVwNIwvf8\n", "8Vshm2H2zM7svfZae6/P63nmyZ6198z6ZmXnM2u+6/JVRGBmZtUwpugCzMysfRz6ZmYV4tA3M6sQ\n", "h76ZWYU49M3MKsShb2ZWIQ2FvqRdJP1Y0gOS7pf0V9nyHSTdKulhSbdImljzNXMkPSJphaTD8/oL\n", "mJlZ49TIefqSdgJ2iojlkiYAdwHHALOAZyLiUknnANtHxLmSpgPfAvYDpgK3AXtGxBt5/UXMzGxk\n", "De3pR8SaiFiePX4ZeIgU5kcBV2Yvu5L0gwDgaODaiHg9IlYCjwI9LazbzMxGYbN7+pJ2A2YAi4HJ\n", "EbE2e2otMDl7PAVYVfNlq0g/JMzMrECbFfpZa+efgc9FxEu1z0XqEw3XK/L9HszMCjau0RdK2oIU\n", "+FdHxA+yxWsl7RQRayTtDDyVLX8C2KXmy6dly2q/n38ImJmNQkSomS8e8QMQcBXwlUHLLwXOyR6f\n", "C1ycPZ4OLAe2BHYH/h/ZQeOar41G1t3uD+CComtwTa6pinW5poZrima+vtE9/Q8ApwD3SlqWLZsD\n", "XAxcJ+l0YCVwQlbRg5KuAx4E1gOfiaxaMzMrTkOhHxE/p37//9A6X3MRcNEo6zIzsxz4ity3W1R0\n", "AUNYVHQBQ1hUdAFDWFR0AUNYVHQBdSwquoAhLCq6gCEsKrqAVmvo4qxcVixFNHMwwsysgprNTu/p\n", "m5lViEPfzKxCHPpmZhXi0DczqxCHvplZhTj0zcwqxKFvZlYhDn0zswpx6JuZVYhD38ysQhz6ZmYV\n", "4tA3M2sh9Qz0a9riZzRt8TPqGegvup7BfMM1M7MWUc9AP8tmzWP9+LRg3DqYsfC8WHJGy24z7xuu\n", "mZkNoR173Eq2lTRF0nQeG3c2638KzANuhPXjYfXM2Xmse7QanpFrZtYp3rbHvXbveeoZYPAet6Qt\n", "gYnAdtnH5j7eDngdeAF4gRe+tm0aD/4AcCLwJ/n+RUfB7R0z6zqatvgZnth7R/gK8ENgCmz12Ou8\n", "tnQZbw3ucWwMbHh+NI8j4ndvrrdnoJ+7T5nHhl2BX8K4d5SuveM9fTPrGpIE7M/4D0+A/wvsDbwH\n", "OAi2XfUKry39PG8N7nWtnN8dS864SLufvCurJp3O5JXPM2XpglYGfis49M2s40naGTgVmAWMY+sn\n", "f8Jriw9nwx7pBePWwe8tvCSejX/PvZiV33oK+LtYtf+5sH/uq9tcDn0z60hZP/4jpKA/ALge+DRw\n", "Rzx7V6hnoJ/Vv0kHUdu7x90HnNOmdW029/TNrKNI2ocU9CcDK4ArgO9FxMuFFgZImgT8CphU2+tv\n", "8Trc0zez7iZpB+Ak4FPAfwKuBN4fEY8WWtjbHQr8JK/AbwWHvpmVkqSxwGGkvfo+4CagH7gtIjYU\n", "WdswNtZZWm7vmFmpSNoD+CTwCWAtqX1zbUQ8V2RdI8nOHHoCOCjP30Dc3jGzjidpAvBR0l79HwDf\n", "BD4UEfcVWtjm2Rt4pYQtp7dw6JtZIbI94wNIffpjgJ+Rrqb6tzL3xIfRB9xcdBEjceibWVtJmgac\n", "RmrhvA4sBOZExJoi62qBPuB/Fl3ESNzTN7PcSdoaOJrUvukBvkvq1S9p5RWxRZG0LbAGmBoRL+a8\n", "Lvf0zax8svbNe0lBfxKwjLRXf1xErCuythwcDNydd+C3gkPfzFpK0ruAU0hh/w7gn4D3RcTKAsvK\n", "W0f088Ghb2YtIGkccCQp6P8YuBH4PLAoIt4osrY26SNdIVx6Dn0zGzVJe5GC/lRgJalPPysiXiiy\n", "rnaStBuwA6l9VXoOfTPbLJK2Az5GOtVyV+Aq4I8j4qFCCytOH3BLp/xG49A3sxFJGgN8kLRX/xHg\n", "R8CXgJsiYn2RtZVAH+kOnx3Bp2yaWV1Z6+KT2ccLpLNvromIpwsrqkQkbQE8Dfx+RKxt0zrzH4wu\n", "6QpJayXdV7PsAkmrJC3LPo6seW6OpEckrZB0+GiLM7P2kzRe0imSfgQsBXYEjgP2jYivOvDfYn/g\n", "sXYFfis02t5ZSLrS7KqaZQEsiIgFtS+UNJ3U75sOTAVuk7Rnp/S7zKrozTGDqU9/PLAY+AZwQ0S8\n", "WmRtJdcxp2pu1FDoR8TPsl/zBhvqV4yjSXfEex1YKelR0hV4d462SDPLx9vGDKYdvH0iYlWhhXWO\n", "Uk/JGkpD7Z1h/KWkeyRdLmlitmwKUPuGWUXa4zezEpC0paTjJN0IPEi6q+WngT0j4iIHfmOyKVl/\n", "ANxRdC2bo5mzd/4B+Jvs8d8C84HT67x2yKPFki6o+XRRRCxqoh4zG0adMYMnlWHMYKdRz0A/2889\n", "l3U3b8U+p3wByG3+rqReoLdV32/UoR8RT218LOky0hV4kIYI7FLz0mnZsqG+xwWjXb+ZjayDxgx2\n", "DPUM9LNs1jzWnwGcDMtmzVPPAHkNXs92hhe9uX5pbjPfb9TtnawXuNGxwMYze24ATsx+hdwd2ANY\n", "MvoSzWxzSBor6QhJ3yEN6T6QNGZwt4g4v5sCXxeqTxfqluyjry0rXT1zNuu3Jt0otBfWj0/LOkRD\n", "e/qSriXdRW6SpMeBuUCvpH1JrZvHgD8HiIgHJV1H6hWuBz7TDbdONSu7OmMG/6LsYwZHKwv564Ft\n", "skUH6EIdG3OjDWfT3EG6l9z0/FfVYo2evXPSEIuvGOb1F5Fjj8vMki4ZMzhaZ7Ip8Mken0nep1BO\n", "WbqA1SvmEX8GjIFx69Iy9s91ta3i2zCYdZguHDPYWX7x2YsZu/XZ7PiPwRaLNzBl6YK8+vl5cOib\n", "dYguHjM4WvNJP/w27u2/ki3LWw8bXl3NU6f+YWpdd8Ye/ka+945ZiXX7mMFmZX39M7NP57ejny9p\n", "AfBSRDR1Fk0T628qOx36ZiUzzJjB67twzGBHye42upJ03OT+gmrwjFyzblDRMYOdpgd4GXig6EJG\n", "y6FvViCPGew4JwDf7eTWmkPfrAAeM9h5stbO8cCHiq6lGQ59szbxmMGO1/GtHXDom+XKYwa7Sse3\n", "dsBn75jlwmMGu0sZztqpqcVn75iVgaTxpLGCs4D3ANdmny/r9L1D647WDjj0zZriMYOV0RWtHXDo\n", "m42KxwxWR7ectbORQ9+sQZK2JB2MnUW658v1pDGDd3TDHqDV1TWtHXDom43IYwYrr2taO+DQNxuS\n", "xwwadF9rBxz6Zm+SNBY4jLRX3wfcRBozeFtEbCiyNitMV7V2wKFvVrkxg7ZZuqq1Aw59q6iKjxm0\n", "BnRjawcc+lYhHjNom6nrWjvg0LcK8JhBG6Wua+2AQ9+6VJ0xg6fgMYPWgG5t7YBD37rIMGMGj/OY\n", "QdtMXdnaAYe+dQGPGbQcdGVrB3xrZetQdcYMLsRjBq1JZbqN8lB8a2WrFI8ZtDbo2tYOOPStA3jM\n", "oLVZ17Z2wO0dK6k6YwYX4jGDlqOyt3bA7R3rMnXGDP4Pjxm0Nunq1g449K0EPGbQSqSrWzvg0LeC\n", "eMyglU03X5BVy6FvbeUxg1ZiXd/aAYe+tYHHDFqH6PrWDjj0LUceM2idoiqtHXDoW4t5zKB1qEq0\n", "dgDGNPIiSVdIWivpvpplO0i6VdLDkm6RNLHmuTmSHpG0QtLheRRu5SFprKQjJH0H+BVwIGnM4G4R\n", "cb4D3zpAJVo70ODFWZIOJP0UvCoi9s6WXQo8ExGXSjoH2D4izpU0HfgWsB8wFbgN2HPw/VB8cVbn\n", "qzNm8FqPGbRO0gkXZNVqNjsb2tOPiJ8Bg/8jH0X61Z3sz2Oyx0eT/uO/nt3l8FHSr07WBSRNkDRL\n", "0k+BO4BtSP9ZZkbE1x341oEq09qB5nr6kyNibfZ4LTA5ezwFuLPmdatIe/zWoTxm0LpcZVo70KID\n", "uRERkobbYJXYmN3GYwat21XprJ2Nmgn9tZJ2iog12QU3T2XLnwB2qXndtGzZ20i6oObTRRGxqIl6\n", "rAU8ZtCqQj0D/Uz6xtk8P28C+37hKKCU/XxJvUBvy75fo/+Psxth3TjoQO6zEXGJpHOBiYMO5Paw\n", "6UDufxkcGD6QWx7DjBm83mMGLW+6UH3Amdmn82Nu3Jz7OnsG+lk2ax7r+4HtYNw5MGPhebHkjIvy\n", "Xnezms3ORs/euRY4GJhE6t9/EfgX4Drg3aQj3ydExPPZ6/tJ/d/1wOci3v6P6NAvXp0xg1d6zKC1\n", "Sxb415NOCAB4BTg27+DX5G8+x1N3T4S/B24CDoWpi5+NVftPynO9rdCWWytHxEl1njq0zusvAkr/\n", "E7OK6owZ/DweM2jFOJNNgU/2+Eyg5aEvaXvSb7KzGDPpnfBnpPv8vbfVqyq1hk7ZtM4naa+sJfc4\n", "6cKpHwK7RsSpEXG7A9+6UXbh4OFZt+IxUsfifGac/0XGnQe8DxCMWwdTli4otNg28W0YupjHDFoH\n", "mE86Hbi2vTO/2W8q6fdIZ52dBjxNunDwjIj4TfaSm9UzEKyeORuAKUsXdEI/vxU8LrHLeMygdZpW\n", "HciVtC3p9MtPAXsB1wALI+LelhRaEm05kJsHh35r1RkzeI3HDFo3y848ez8p6I8Dfk567/9rt144\n", "6Bm5FeYxg1ZVkqaS7vn0SeANUtBPj4gni6yrEzj0O4zHDFpVSdqKdM+vWcAfkS4cPA1Y7J2cxjn0\n", "O4THDFpVSZrBpgsH7yW994/3hYOj49AvMY8ZtKqSNIk0cW0WMJF04WBPRDxWZF3dwAdyS6jOmMHv\n", "ecygdbPswsE+0nv/UOBfSe99XzhYwwdyu0SrxwwWcT8Ts9GQ9PukoP8E8B+k9s3pEfFCoYV1Ke/p\n", "F0jSWOAw0hu+j3QTkIXAbRGxYdTft6D7mZg1StI7Sfex/xSwO3A16Zx6Xzg4grZMzrLRU89Av6Yt\n", "fkbTFj+jnoF+SGMGJc0j3ajuS8BPgN0j4sSIuLmZwM/Uu5+JWWEkjZH0QUlXAb8m3cP+y8C7I+Js\n", "B357uL2To023bx0PvAxPLpunrSd9GtgW+CZpzOB9w38Xs84maVc2DeN5mdSnP9MXDhbDe/p5Wj1z\n", "dgr8k4HJ8Mb/gfGzdwSmRcTsHAN/Pqmls1FL7mdi1ihJ20j6uKRbgbtIx6k+CrwnIr7qwC+OQ78t\n", "7iUdl70Bxh/yu7wvD89698cCt2Yf7udb7pT0SPrfpNnYnwAuI+3kfDYi7vKpxsVzeydPU5YuYM2E\n", "eWx4Cjim5vat++e+6izkHfSWO0mT2XTh4Jakc+r3jYjHi6zLhuazd3KmHfe7iVenHMz2/b+t0u1b\n", "rbtJ2gL4MCnoDwa+Tzrz7Ofem8+X77JZcpLuAs6KiNuLrsWsWZL+KynoTwF+SQr67/rCwfbxxVkl\n", "Juk/A9OAnxZdi9lovWXMIOxMOkB1QEQ8UmhhNioO/Xx9FPi+h5dYp8kuHDyEFPRHko4PnU+TFw5a\n", "8Rz6+ToBOKvoIswa1cCYQetwDv2cuLVjnaLOmMGPdNuYQUsc+vlxa8dKq86Ywa/RxWMGLXHo58et\n", "HSsdjxk0h34O3NqxMvGYQavl0M+HWztWuJoxgx8H7sFjBg2Hfl7c2rFC1BkzuJ/HDNpGDv0Wc2vH\n", "2q3OmMHZeMygDcGh33pu7VhbDBoz+GvSOfUeM2jDcui3nls7lps6YwYPjYgHCy3MOoZvuNZCWWvn\n", "34Gp3tO3VpE0hnQny1mks3BuJx2UvSkiXi+yNms/33CtXNzasZbxmEHLg0O/tdzasaZI2oY09WwW\n", "MAP4Nmln4m6fU2+t4NBvEZ+1Y6OV3RJhP1Kf/qPAL0hjBv8lIl4tsjbrPg791nFrxzbLoDGDW5H6\n", "9B4zaLly6LeOWzs2okFjBg8CfgD8BR4zaG3SdOhLWgm8CGwAXo+IHkk7AN8BdgVWAidExPPNrqus\n", "3NqxkdQZM3iyxwxau41pwfcIoDciZkRET7bsXODWiNgT+FH2eTdza8feRtL2kv67pF8ANwGvksYM\n", "HhQRCx34VoRWhD7A4HNGjyLN0ST785gWraesTiDdudAqTtJYSYdLuhZ4DOgF/hrYNSLO81xZK1rT\n", "F2dJ+hXwAqm9842I+EdJz0XE9tnzAn6z8fOar+uKi7N8QZZB3TGD13rMoLVaGS7O+kBEPCnpXcCt\n", "klbUPhkRIambD1C5tVNRHjNonajp0N84cScinpZ0PdADrJW0U0SskbQz8NRQXyvpgppPF0XEombr\n", "KYDP2qkQjxm0dpPUS2oTtub7NdPekTQeGBsRL2V7PbcAF5Ju7/psRFwi6VxgYkScO+hrO76949ZO\n", "ddQZM3i1xwxauxXd3pkMXJ92fhgHXBMRt0haClwn6XSyUzabXE9ZubXTxTxm0LqR77LZBEl3AWdF\n", "xO1F12KtUzNm8CTgXtJe/fc9ZtDKoOg9/cryBVndpc6YwR6PGbRu49AfPbd2OpzHDFoVOfRHz2ft\n", "dKiaMYOnAo/jMYNWIQ79UXBrp/PUGTN4mMcMWtU49EfHrZ0OkI0ZPIgU9BvHDH4Zjxm0CnPoj45b\n", "OyU2xJjBhcAXImLIiwTNqsShv5nc2iknjxk0a4xDf/O5tVMSNWMGZwEfA5bgMYNmw3Lobz63dgpW\n", "Z8zgezxm0GxkDv3N0O7Wji5UH3Bm9un8mBs3t2O9ZeQxg2at4dswNEA9A/2snjmbF6/YBm6/P158\n", "ZP/c15kC/3pgm2zRK8CxVQv+QWMGHyadU/9dT52yqmo2O1s1OatrqWegn2Wz5vHE/jvy0tLx/PZr\n", "PeoZ6G/Dqs9kU+CTPT6zzmu7yjBjBg/0mEGz5jj0R7J65mzWjwfuAX4NbxyelllLecygWXu4p9+w\n", "+cDOtHGTzQcO4K3tnfntWnm71BkzeIbHDJrlw3v6I5mydAHj1gFPAhfCuHVpWc6y3v2xwK3ZR9f0\n", "8yVtK+k0SYtIQ2gmkMYMvi8iBhz4ZvnxgdwGaMYlc7nnwrnsdONzTFsxP5accVHRNXWaOmMGF+Ix\n", "g2abpdnsdOg3QNKRwJyIOKjoWjqNxwyatZaHqLRHH9AVrZV28JhBs/Jy6Demj3QFqA2jzpjB4z1m\n", "0Kw8HPojkPRuYEfg7qJrKaNszODHSb16jxk0KzmH/sj6gFs9Pm8Tjxk061wO/ZH1ATcUXUQZeMyg\n", "Wefz2TvDyPZonwb2iog1RddThDpjBv/JYwbNiuGzd/K1P/AfVQt8jxk0614O/eFV6lRNjxk0634O\n", "/eH1AXOKLiJPHjNoVi3u6dchaUfS3R7fFRGvFV1PK9UZM7gQjxk0Kz339PNzKPCTbgp8jxk0M4d+\n", "fV3Rz/eYQTOr5fbOELL2xyqgt1OHd3jMoFl3cnsnH38IvAY8WnQhm0PS9sCJpFMtdwauJI0Z7Mgf\n", "XGbWeg79ofUBN3dC+0PSWOAQ0l79kaSW1F+Tbh2xocjazKx8HPpDOwIYKLqI4XjMoJmNhnv6g0ga\n", "D6wFpkbEi0XXU0vStsDxpL366cA1wMKIuLfQwsysbdzTb72DSRcmlSLw64wZ/Hs8ZtDMRsGD0d+u\n", "badqqmegX9MWP6Npi59Rz0D/W56TpkqaA6wALgN+CUyPiD+JiO878M1sNHJr70g6AvgqMBa4LCIu\n", "GfR8Wds7DwGnRMRdua6nZ6CfZbPmsX58WjBuHezz9S9y91kr2DRm8HukXr3HDJoZUNL2TnZGyf8i\n", "XdX6BPALSTdExEN5rK8V1DPQz6+nfIEx203kvX9zBJBr6LN65mzWbwk8C9wJ62+G5VddCPwYjxk0\n", "s5zk1dPvAR6NiJUAkr4NHA2UMvQ37XVfA3wYlv/pl9QzELHkjIvqfk26/fAEYDvSmMDtBj0eatmm\n", "x9pqR1iffYtXgDnwrsufjzX/7ZDc/qJmVnl5hf5U0mSljVaR7k1fTqtnzk5tliuBPWH91+Ghe86X\n", "Prsz9QP8ncA64AXg+ezPwY+fA1YOWp7+3OeLf8r9n5vLhm2BgHGvwLsX/l27/spmVk15hX5D/WdJ\n", "F9R8uigiFuVSTcN+C7wKrAFtGcAj1A/0FyNifRMru0A9A79j9czZAExZumC43yzMrJok9QK9Lft+\n", "eRwflPRHwAURcUT2+RzgjdqDuWU6kDvkQdUZC89zCJtZ2TSbnXmF/jjSKYaHAKtJ92s/qfZAbplC\n", "H7Lg9163mZVcKUMfQNKRbDpl8/KI+PKg50sV+mZmnaC0oT/iih36Zmabrdns9BW5ZmYV4tA3M6sQ\n", "h76ZWYU49M3MKsShb2ZWIQ59M7MKceibmVWIQ9/MrEIc+mZmFeLQNzOrEIe+mVmFOPTNzCrEoW9m\n", "ViEOfTOzCnHom5lViEPfzKxCHPpmZhXi0DczqxCHvplZhTj0zcwqxKFvZlYhDn0zswpx6JuZVYhD\n", "38ysQhz6ZmYV4tA3M6sQh76ZWYU49M3MKsShb2ZWIQ59M7MKceibmVWIQ9/MrEIc+mZmFeLQNzOr\n", "EIe+mVmFjDr0JV0gaZWkZdnHkTXPzZH0iKQVkg5vTalmZtasZvb0A1gQETOyjx8CSJoOfAyYDhwB\n", "fF1Sx/xGIam36BoGc02NcU2NK2Ndrqk9mg1jDbHsaODaiHg9IlYCjwI9Ta6nnXqLLmAIvUUXMITe\n", "ogsYQm/RBQyht+gC6ugtuoAh9BZdwBB6iy6g1ZoN/b+UdI+kyyVNzJZNAVbVvGYVMLXJ9ZiZWQsM\n", "G/qSbpV03xAfRwH/AOwO7As8Ccwf5ltF60o2M7PRUkTzeSxpN+DGiNhb0rkAEXFx9txNwNyIWDzo\n", "a/yDwMxsFCJiqNZ6Q8aN9gsl7RwRT2afHgvclz2+AfiWpAWkts4ewJLBX99M0WZmNjqjDn3gEkn7\n", "klo3jwF/DhARD0q6DngQWA98Jlrx64SZmTWtJe0dMzPrDG0/f76sF3VJOiJb7yOSzmnnugfVsVLS\n", "vdm2WZIt2yE7qP6wpFtqzpTKq4YrJK2VdF/Nsro1tOvfrU5dhb6fJO0i6ceSHpB0v6S/ypYXtr2G\n", "qamwbSVpa0mLJS2X9KCkL2fLi9xO9WoqPKMkjc3WfWP2eeu2U0S09QOYC8weYvl0YDmwBbAb6fz+\n", "MW2qaWy2vt2y9S8H9mr3tslqeQzYYdCyS4Gzs8fnABfnXMOBwAzgvpFqaOe/W526Cn0/ATsB+2aP\n", "JwC/BPYqcnsNU1PR22p89uc44E7ggKLfV3VqKjyjgNnANcAN2ect205FXSlbtou6eoBHI2JlRLwO\n", "fDurpyiDt89RwJXZ4yuBY/JceUT8DHiuwRra9u9Wpy4o8P0UEWsiYnn2+GXgIdIJDIVtr2FqgmK3\n", "1brs4ZakHa3nKPh9VacmKHA7SZoGfAi4rKaOlm2nokK/bBd1TQUeL2jdgwVwm6Slkj6dLZscEWuz\n", "x2uByQXUVa+GMlyMV4r3k9KpyzOAxZRke9XUdGe2qLBtJWmMpOWk7fHjiHiAgrdTnZqg2PfUV4Cz\n", "gDdqlrVsO+US+uq8i7rKdDT7AxExAzgSOEPSgbVPRvqdrtB6G6ihnfWV4v0kaQLwz8DnIuKlt6y0\n", "oO2V1fS9rKaXKXhbRcQbEbEvMA04SNIHBz3f9u00RE29FLidJH0EeCoiljH0bxtNb6dmTtmsv8aI\n", "wxp5naTLgBuzT58Adql5elq2rB0Gr3sX3vrTs20iu/YhIp6WdD3pV7W1knaKiDWSdgaeKqC0ejUU\n", "+e9GRLy5LYp6P0naghT4V0fED7LFhW6vmpq+ubGmMmyrrI4XJP0b8D5K8r6qqWlmRCzauLyA7fR+\n", "4ChJHwK2Bt4p6WpauJ2KOHtn55pPB1/UdaKkLSXtTp2LunKyFNhD0m6StiTdJfSGNq37TZLGS3pH\n", "9nhb4HDS9rkBOC172WnAD4b+DrmqV0OR/26Fv58kCbgceDAivlrzVGHbq15NRW4rSZM2tkkkbQMc\n", "Biyj2O00ZE2Sdqp5WVu3U0T0R8QuEbE7cCJwe0ScSiu3Ux5Hnkc4Kn0VcC9wT1b45Jrn+kkHIlYA\n", "fW2u60jSWQ6PAnPavV2yGnYnHYlfDty/sQ5gB+A24GHgFmBiznVcC6wGfkc61jFruBra9e82RF2f\n", "Kvr9RDrb443s32xZ9nFEkdurTk1HFrmtgL2Bu7Oa7gXOGum9XWBNpcgo4GA2nb3Tsu3ki7PMzCqk\n", "Y4abmJlZ8xz6ZmYV4tA3M6sQh76ZWYU49M3MKsShb2ZWIQ59M7MKceibmVXI/wfR5ZqBFVn3PgAA\n", "AABJRU5ErkJggg==\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "data = [\n", "[10.0000, 30.0000],\n", "[20.0000, 50.0000],\n", "[300.0000, 95.0000],\n", "[40.0000, 2.0000] ]\n", "\n", "points = []\n", "for n in range(2**len(data)):\n", " t = [ (n>>i)&1 for i in range(len(data)) ]\n", " x = sum(ti * pair[0] for ti, pair in zip(t,data))\n", " y = sum(ti * pair[1] for ti, pair in zip(t,data))\n", " points.append(Point(x,y))\n", "\n", "extpts = [Point(0,0)]\n", "for (x,y) in data:\n", " pt = Point(x, y)\n", " points = extpts[:] + [Point(p.x + pt.x, p.y + pt.y) for p in extpts]\n", " extpts = FindExtremePoints( points, False )\n", " \n", "fig, ax = plt.subplots()\n", "ax.scatter([pt.x for pt in points], [pt.y for pt in points], color = \"green\")\n", "ax.scatter([pt.x for pt in extpts], [pt.y for pt in extpts], color = \"blue\")\n", "for i in range(len(extpts)-1):\n", " ax.plot( [extpts[i].x, extpts[i+1].x], [extpts[i].y, extpts[i+1].y], color = \"black\" )\n", "ax.plot( [extpts[-1].x, extpts[0].x], [extpts[-1].y, extpts[0].y], color = \"black\" )\n", "extpts" ] }, { "cell_type": "code", "execution_count": 200, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "([Point(x=0, y=0),\n", " Point(x=40.0, y=80.0),\n", " Point(x=50.0, y=380.0),\n", " Point(x=70.0, y=1380.0),\n", " Point(x=370.0, y=29880.0),\n", " Point(x=330.0, y=29800.0),\n", " Point(x=320.0, y=29500.0),\n", " Point(x=300.0, y=28500.0)],\n", " Point(x=50.0, y=3750.0))" ] }, "execution_count": 200, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": [ "iVBORw0KGgoAAAANSUhEUgAAAYoAAAEACAYAAACtVTGuAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n", "AAALEgAACxIB0t1+/AAAIABJREFUeJzt3XuclWXd7/HPF5CD5iEeyxOo9IglZUGomEfUVNRCTbdi\n", "aZpUFkVu01SsR6Ays7bH8lCpqagkW7amaR5zyqdSzEBRNMFHSlCxsDDTDPS3/7iuscWsYRiYw3XP\n", "zPf9eq3X3Ota617rNzfD+q3rrIjAzMxsVXqVDsDMzKrNicLMzFrkRGFmZi1yojAzsxY5UZiZWYuc\n", "KMzMrEWtShSS+kt6UNIcSfMknZ3Lp0haJGl2vh1Qc84kSfMlPSlpv5rykZLm5scurCnvJ+mGXP6A\n", "pK3a8xc1M7O106pEERH/BPaKiOHA+4G9JO0GBHBeRIzIt58DSBoGHAkMA8YAl0hSfrlLgfERMRQY\n", "KmlMLh8PLM3l5wPntM+vaGZmbdHqpqeIeDUf9gV6A3/N99XM0w8GpkfE8ohYCCwARknaDFg/Imbl\n", "510DHJKPxwJX5+OZwD6tjc3MzDpOqxOFpF6S5gBLgPsi4vH80ERJj0i6QtJGuWxzYFHN6YuALZop\n", "X5zLyT+fBYiIFcAySQPX9BcyM7P2tSY1ijdz09MgYA9Jo0nNSEOA4cDzwLkdEaSZmZXTZ01PiIhl\n", "km4DdoiIhsZySZcDt+a7i4HBNacNItUkFufjpuWN52wJPCepD7BhRLxU+96SvDCVmdlaiIjmugla\n", "ffJqb8DGwEb5eADwK1IfwqY1zzkJuD4fDwPmkPozhgBPA8qPPQiMIvVt3A6MyeUTgEvz8TjgJ83E\n", "Ea2JtzNvwJTSMXSVuByTY+oJcVU0pmjL+a2tUWwGXC2pF6m5alpE3CvpGknDSaOfngFOyBHNkzQD\n", "mAesACZEjjYnhKtywrk9Iu7I5VcA0yTNB5bmZGFmZoW1KlFExFzgg82Uf7KFc74FfKuZ8oeB7Zsp\n", "fx04ojXxmJlZ5/HM7LZrKB3AKjSUDqAZDaUDaEZD6QCa0VA6gGY0lA5gFRpKB9CMhtIBtDf9u0Wo\n", "+iRFtKVDxsysB2rrZ6drFGZm1iInCjMza5EThZmZtciJwszMWuREYWZmLXKiMDOzFjlRmJlZi5wo\n", "zMysRU4UZmbWIicKMzNrkROFmZm1yInCzMxa5ERhZmYtcqIwM7MWOVGYmVmLnCjMzKxFThRmZtai\n", "ViUKSf0lPShpjqR5ks7O5QMl3S3pKUl3Sdqo5pxJkuZLelLSfjXlIyXNzY9dWFPeT9INufwBSVu1\n", "5y9qZmZrp1WJIiL+CewVEcOB9wN7SdoNOB24OyK2Be7N95E0DDgSGAaMAS6R1LgN36XA+IgYCgyV\n", "NCaXjweW5vLzgXPa4xc0M7O2aXXTU0S8mg/7Ar2BvwJjgatz+dXAIfn4YGB6RCyPiIXAAmCUpM2A\n", "9SNiVn7eNTXn1L7WTGCfNf5tzMy6IIn9Je7Kt/1Lx9NUqxOFpF6S5gBLgPsi4nFgk4hYkp+yBNgk\n", "H28OLKo5fRGwRTPli3M5+eezABGxAlgmaeCa/TpmZmuvxAd2fp+bgH3z7aaqJYs+rX1iRLwJDJe0\n", "IXCnpL2aPB6Sor0DNDNrL/kD+OR899wI7mzy2E3AgFy0m8Shtc9Jz5NIX7L7NHPrveblV38LNhgA\n", "DwNfADYdkGNc6X1LanWiaBQRyyTdBowElkjaNCJeyM1KL+anLQYG15w2iFSTWJyPm5Y3nrMl8Jyk\n", "PsCGEfFS0/eXNKXmbkNENKzp72BmPc+qEgHoLmBruOi78IcB8P+AV4F+A+Cft0ovv0r9h/6bwIoW\n", "bm+0/vHLBsPzpI/PvYBN2+F31WhgdJtfqPH1IlZfCZC0MbAiIv4maQAp000F9id1QJ8j6XRgo4g4\n", "PXdmXw/sRGpSugfYJtc6HgS+BMwCbgMuiog7JE0Ato+Iz0saBxwSEeOaxBERIczM1pDEXcC+sBy4\n", "DvgLcPuLcN+b6Rl794ID3wnvA4YC6wJvNMCgQ2nyIR+t+eBsVUz6ILztp3DwZnBJb9gA4DWor8m0\n", "8X3a9NnZ2hrFZsDVknqRqlzTIuJeSbOBGZLGAwuBIwAiYp6kGcA80oWdUHNhJwBXkbL67RFxRy6/\n", "ApgmaT6wFFgpSZiZtc1jA+BG0piZF4FPAh9bAveNBf4I9+7HyjWO14BvR8Tf2juS/Fl6Srq9ciJc\n", "+xKraBKrglbVKKrCNQozWxOS3gYcDhwHfYfDZ9aD4/vACEB139xb6sNox5gGkbJVX+DoiPhje79H\n", "M+/Zps9OJwoz61byt/U9gONIw+9/RWrFuA1iNAW/uUv6GGku2UWk2sobnfS+ThRm1rM0981f0hDg\n", "2Hx7BfgxcF3NEP5ics3mAlIH8yci4sFOfv9O6aMwM6uElUcvvQLcsKc06UnSPK3pwGHA7PbqcG4r\n", "STuSes9/DYyIiL8XDmmNOVGYWVdzMrw0AHYjjarfsy+cFfDZQRHxeungGknqDZwKnAR8MSJmFA5p\n", "rTlRmFkXc9Pb4UTSsnM/B7YCeDHiM1VKEoOBafnuDhHxp5LxtJUThZl1CZL6AlOh37tg5utwUL/8\n", "0GvAuQVDW4mkI4DvA+cB3+2sDuuO5ERhZpUnaVvSJN7n4fXt4KARVGzegaT1SaOZdgUOioiHCofU\n", "bjzqycwqK6+rNB44G5gMXFqVTupakkaROqzvA06KiFcKh7QSj3oys25J0n8APwS2AUbnFasrJXdY\n", "TwImklagmFk4pA7hrVDNrHIk7QPMIS0NtFNFk8RWQANpJb+R3TVJgBOFmVWIpL6SvkPa1Gx8RJxc\n", "pSGvjSQdBTwE3ALsGxGLVnNKl+amJzOrBEnvIXVYPwt8ICL+UjikOpI2AC4GdgQOiIiHC4fUKVyj\n", "MLOilJwA3A/8gLTFQBWTxC6k5rB/kJqaekSSANcozKygvNfN5aRNy3aPiCcLh1Qnb6T2VeDzwOci\n", "4ubCIXU61yjMrAhJ+wKPAE8BH6pokhgC/JI0N+KDPTFJgBOFmXUySf0knUta3fWTEXFqRTusjybt\n", "xDkTGBMRzxUOqRg3PZlZp8nbJE8HniZ1WC8tHFIdSRsCl5B2N9o3IuYUDqk41yjMrMPlDusJpGac\n", "7wGHVTRJ7EZqDvsbaTG/Hp8kwDUKM+tgkt4JXAlsCuwaEU8VDqmOpHWAM4FPA5+JiJ8VDqlSWlWj\n", "kDRY0n2SHpf0mKQv5fIpkhZJmp1vB9ScM0nSfElPStqvpnykpLn5sQtryvtJuiGXP5BnPZpZFyZp\n", "DGlI6Vxgl4omif8kDc3dkbSxkJNEE61telpOWujqvcDOwBckbQcEcF5EjMi3n8Nb7ZBHAsOAMcAl\n", "eXEvSPvFjo+IocDQ/IcEaeGvpbn8fOCcdvj9zKwASf3zF8EfAh+PiEkR8a/ScdXKzWHHAg+Q+k0O\n", "jIgXCodVSa1KFBHxQmNbXV4V8Qlgi/xwcysSHgxMj4jlEbEQWACMkrQZsH5EzMrPu4a0+TnAWODq\n", "fDwT2GcNfxczqwBJ7yMtb7E5MDwiGspGVE/S24GfAF8B9omICyPizcJhVdYad2ZL2po0GuCBXDRR\n", "0iOSrpC0US7bHKhd+2QRKbE0LV/MvxPOFqSp+0TECmCZpIFrGp+ZlZG/oU8kLbV9HnBERLxUOKw6\n", "kvYkNYctAXaMiEcLh1R5a9SZLeltwI3AiRHxiqRLga/nh79B2mVqfPuGWBfDlJq7DVX8tmLW00ja\n", "BLgKGEiaPLegbET1cof1FOB4UvP37WUj6jiSRgOj2+v1Wp0o8kWeCVzbODsxIl6sefxy4NZ8dzEw\n", "uOb0QaSaxOJ83LS88ZwtgefylPkNm/s2EhFTWhuzmXU8SQeRluG4ApgaEcsLh1RH0lDSxkJ/JjWH\n", "LSkcUofKX6AbGu9LmtyW12vtqCeR/gjmRcQFNeWb1TztUNLIBkhL747LSwYPAYYCs3JH0cuSRuXX\n", "PAb4ac05x+bjw4F71/J3MrNOIGmApO+TJqcdGRFfq1qSyM1hxwO/IfWBfqS7J4mO0Noaxa7A0cCj\n", "kmbnsjOAoyQNJ41+egY4ASAi5kmaAcwDVpB2fmrcvnACqYo6ALg9Iu7I5VcA0yTNB5YC49ryi5lZ\n", "x5H0AdKS4HNJM6z/VjikOrmP84fAtlR0h7yuwntmm1mrSeoFnEj6ovhlUlN05T5EJO1FGlV5IzAp\n", "Iv5ZOKSivGe2mXWK3NR8FbABMCoi/qdsRPUk9SUNrDkaOD4i7iwcUrfgtZ7MbLUkjQVmA78l7RtR\n", "xSTxblJ825E6rJ0k2olrFGa2SpLWJQ17H0NayO/XhUOqkwfGfBr4Fmm9psuq2BzWlTlRmFmzJI0g\n", "dVg/TPqGvqxwSHXyDnk/ArYG9oiIJ8pG1D256cnMViKpl6RTgLuAb0bE0RVNEh8mzbB+GtjZSaLj\n", "uEZhZm+RtAVpvkF/YKeIeKZwSHUk9QPOIg2hPy4i7ikcUrfnGoWZASDpUOD3pM2FRlc0SWxHWmdu\n", "G1JzmJNEJ3CNwqyHk7QeaWn/fYBDIuK3hUOqkzusP0daW+4M4HJ3WHceJwqzHkzSDqQ1kH5L2rTn\n", "5cIh1ZH0DtLKDVsAu0XEHwqH1OO46cmsB5LUW9JpwO3AmRFxXEWTxP6kDusnSKvSOkkU4BqFWQ8j\n", "aTBpeYvewA4R8afCIdWR1B84m7RA6DER8YvCIfVorlGY9SCSDgd+B9wN7FXRJPFe4EHSVgUfcJIo\n", "zzUKsx4gbzp2EbA78NGa7YgrI3dYfwGYDJwG/Ngd1tXgRGHWzUnaidRh/StSh/UrhUOqk3fIuxJ4\n", "B7BLRMwvHJLVcNOTWTeVO6y/CvwMOCMixlc0SRxIWnBwDrCrk0T1uEZh1g1J2hK4FngDGBkRzxYO\n", "qY6kAcA5wMHAURHxy8Ih2Sq4RmHWzUg6ktRhfRvw4Yomie2BWcAmpBnWThIV5hqFWTchaQPge8DO\n", "wAER8XDhkOrkHfImAl8DTgGucYd19TlRmHUDknYmdVjfC3wwIv5ROKQ6kjYl7ZC3EWm116fLRmSt\n", "1aqmJ0mDJd0n6XFJj0n6Ui4fKOluSU9JukvSRjXnTJI0X9KTkvarKR8paW5+7MKa8n6SbsjlD0ja\n", "qj1/UbPuSFIfSWcCPwVOiYjPVjRJfJTUYT2LtEOek0QX0to+iuXASRHxXlK19gt5FcfTgbsjYlvS\n", "N5nTASQNA44EhpF2xrokj5EGuBQYHxFDgaGSxuTy8cDSXH4+qZPLzFZB0tZAA7AHqRZxU8l4miNp\n", "XUmXkOZw/K+IODMilpeOy9ZMqxJFRLwQEXPy8SukdVe2AMaS1q4n/zwkHx8MTI+I5RGxEFgAjMqb\n", "s69fM9nnmppzal9rJmklSzNrhqRPAA8BNwH7RcTiwiHVkTSc1Km+EWn+xn8XDsnW0hr3UeRvMSNI\n", "U+w3iYgl+aElpBEMAJuT1oxvtIiUWJbn40aLczn557MAEbFC0jJJAyPipTWN0ay7krQhcDEwkpQg\n", "ZhcOqU7usP7fwCRSS8S1hUOyNlqjRJGXAZgJnBgRf/93axJEREjq8NELkqbU3G2IiIaOfk+zKpC0\n", "K2luxB2kuRGvFg6pjqTNSS0D61HRHfJ6AkmjgdHt9XqtThSS1iEliWkRcXMuXiJp04h4ITcrvZjL\n", "F5MW9Go0iFSTWJyPm5Y3nrMl8JykPsCGzdUmImJKa2M26w7y/4f/Ak4APhsRtxQOqVmSDgEuI/VD\n", "nhURKwqH1GPlL9ANjfclTW7L67V21JNIG4fMi4gLah66BTg2Hx8L3FxTPk5SX0lDgKHArIh4AXhZ\n", "0qj8mseQRms0fa3DSZ3jZj2apHcB95MGkYyoYpKQtJ6kHwDnAR+LiKlOEt2LWjPXRdJupAXFHgUa\n", "T5hEGuo2g1QTWAgcERF/y+ecARwPrCA1Vd2Zy0eSxlIPAG6PiMahtv2AaaT+j6XAuNwRXhtHRIQw\n", "6+byF6mjSR++ZwEXRcSbZaOqJ+mDwPWkz4IvVnHzI2v7Z2erEkVVOFFYT5DnI10KvB/4eEQ8Ujik\n", "OrnD+pR8OzEiphcOyVrQ1s9Oz8w2qxBJe5Bq1reQdp97rXBIdSQNInVY9wV2jIg/Fg7JOpgXBTSr\n", "AEnrSPomcAMwISImVjRJHAY8DNwHjHaS6BlcozArTNI2pHWalpJWUl2ymlM6XR4afwFpyOXYiHiw\n", "bETWmVyjMCtEyaeA35LmRxxU0SSxI/B7oDdp5JWTRA/jGoVZAZLeDvwA2A7YKyIeKxxSHUm9gVOB\n", "k0gjmmYUDskKcY3CrJPlWbOPAM+TOoOrmCQGk+YyjSF1qjtJ9GBOFGadJE9A/TZp3sEJEXFiRPyz\n", "dFxNSTqC1GF9B7B3RPypcEhWmJuezDqBpG1JCeJ5Uof1i6s5pdNJWp+0HPiupP6ShwqHZBXhGoVZ\n", "B8od1p8Gfg1cSRoxVMUkMYq0sdAbpL0tnCTsLa5RmHUQSf8B/BDYhjTn4PHCIdXJHdaTSPtYT4iI\n", "mYVDsgpyjcKsA0jaB5hDWgNtp4omia1IK4zuRVq23EnCmuVEYdaOcof1d0i7N46PiJMj4vXScTUl\n", "6SjSDnm3APtGxKLVnGI9mJuezNqJpPeQOqyfBT4QEX8pHFIdSRuQdsjbCTggIh4uHJJ1Aa5RmLVR\n", "7rA+gbRvxA+AQyqaJHYhNYf9g9Rh7SRhreIahVkbSNoYuJy0J8vuEfFk4ZDq5B3yvgp8HvhczQ6V\n", "Zq3iGoXZWpK0H2mG9VPAhyqaJIaQNh3bjVSLcJKwNeZEYbaGJPWTdB5pe+BPRsSpFe2wPpq089yN\n", "wP4R8VzhkKyLctOT2RqQNAyYDjxNmmG9tHBIdfIOeReTthXeNyLmFA7JujjXKMxaIXdYTwB+CXwP\n", "OKyiSWI3Uof1MtJifk4S1matShSSrpS0RNLcmrIpkhZJmp1vB9Q8NknSfElP5nbcxvKRkubmxy6s\n", "Ke8n6YZc/kCeCGRWCZLeCdwKHA/sGhGXR8U2m8875H2D1Mw0MSImRMSrpeOy7qG1NYofk5YbrhXA\n", "eRExIt9+Dm9VzY8EhuVzLpHUuKn3paRJSEOBoZIaX3M8sDSXnw+cs9a/kVk7yn+jc4C5wC4R8VTh\n", "kOpI+k/S0NwdSc1htxYOybqZViWKiLgf+GszD6mZsoOB6RGxPCIWAguAUZI2A9aPiFn5edcAh+Tj\n", "saTN2gFmAvu0LnyzjiGpf671/hD4eERMioh/lY6rVm4OOxZ4gNRvcmBEvFA4LOuG2tpHMVHSI5Ku\n", "yB1oAJsDtcsBLAK2aKZ8cS4n/3wWICJWAMskDWxjbGZrRdL2pOUtNid9Q28oG1G9vEPeT4CvAPtE\n", "xIUR8WbhsKybasuop0uBr+fjbwDnkpqQOpSkKTV3G6r4n9i6ptxEOhH4L9IH8NVV64sAkLQnqUb+\n", "U+C4iHitcEhWMXkXxdHt9XprnShq19SXdDmpsw9STWFwzVMHkWoSi/Nx0/LGc7YEnsuzSDeMiJdW\n", "8b5T1jZms1WRtAlwFTCQNHluQdmI6klaB5hC6lQfHxG3l43Iqip/gW5ovC9pclteb62bnnKfQ6ND\n", "SZ19kFajHJdX0RwCDAVm5bbTlyWNyt/cjiF9I2o859h8fDhpr16zTiHpIFKH9cPAbhVNEkOB3wDD\n", "Sc1hThLWaVpVo5A0HdgT2FjSs8BkYLSk4aTRT88AJwBExDxJM4B5wArSZiiN1fcJpG9tA4DbI+KO\n", "XH4FME3SfGApMK4dfjezFkkaAHwX+AhwZET8qnBIdfKXqk+RRgJOBS6uYnOYdW/qSn9zkiIimhtp\n", "ZbZGJH2AtCT4o8DnI+JvhUOqkwd0/BDYFjiqipsfWdfQ1s9Oz8y2HkVSL0knAfcA3yYNfa1iktib\n", "tODgs1R0hzzrObzWk/UYuV/tKmADYFRE/E/ZiOpJ6ksaRXgMcHxN86xZMa5RWI8gaSwwG/gtad+I\n", "KiaJd5Pi2460Q56ThFWCaxTWrUlalzTHZwxpIb9fFw6pTu6w/jTwLeBM4DJ3WFuVOFFYtyVpBKnD\n", "+mHSkNJlhUOqk3fI+xEwBNgjIp4oHJJZHTc9WbeTO6xPAe4CvhkRR1c0SXyYNH/jaVKfiZOEVZJr\n", "FNatSNqCtMBkf2DHvDBlpUjqB5xFmi90XETcUzgksxa5RmHdhqRDgd+TNhcaXdEksR1ptddtSM1h\n", "ThJWea5RWJcnaT3gAmBv4OCIeKBwSHVyh/XnSAtpngFUbvMjs1VxorAuTdIOwHWkYaUjIuLlwiHV\n", "kfQO0jI1W5DWkvpD4ZDM1oibnqxLktRb0mnA7cCZEXFcRZPE/qQZ1k+QVqV1krAuxzUK63IkDSbt\n", "x9AL2CEi/lQ4pDqS+gNnk1ZDPjoiflE4JLO15hqFdSmSDgd+B9wN7F3RJPFe4EHSvizDnSSsq3ON\n", "wroESW8DLgJ2Bz5as/d6ZeQO6y+QluE/DfixO6ytO3CisMqTtBOpw/pXpA7rVwqHVCfvkHcl8E5g\n", "l4iYXzgks3bjpierrNxh/VXSNruTImJ8RZPEgaQFB+fgJGHdkGsUVkmStgSuBd4gdVg/WzikOnmH\n", "vHOAg0kbC/2ycEhmHcI1CqscSUeSOqxvAz5c0STxfuAhYBNSh7WThHVbrlFYZUjaAPgesDNwQEQ8\n", "XDikOpJ6AROBrwGnANe4w9q6u1bVKCRdKWmJpLk1ZQMl3S3pKUl3Sdqo5rFJkuZLelLSfjXlIyXN\n", "zY9dWFPeT9INufwBSVu11y9oXYOknUnt/K8DH6xoktiMNMHvKNLkuaudJKwnaG3T049JG7/UOh24\n", "OyK2Be7N95E0DDgSGJbPuSQPGwS4FBgfEUOBoZIaX3M8sDSXn09q97UeQFIfSWcCPwVOiYjPRsQ/\n", "SsfVlKSPkhYcnEXaIW9B4ZDMOk2rEkVE3A/8tUnxWNJyzuSfh+Tjg4HpEbE8r965ABiVv42tXzP+\n", "/Zqac2pfayawzxr+HtYFSdoaaAD2INUibioZT3MkrSvpElKT2BERcWZELC8dl1lnaktn9iYRsSQf\n", "LyF16gFsDiyqed4i0mJoTcsX53Lyz2cBImIFsEzSwDbEZhUn6ROkzuCbgP0iYnHhkOpIGk7qVN+I\n", "1GF9f+GQzIpol87siAhJndJWK2lKzd2GiGjojPe19iFpQ+BiYCQpQcwuHFKd3GF9Eqk59aSIuLZw\n", "SGZrRNJoYHR7vV5bEsUSSZtGxAu5WenFXL6YtMZNo0GkmsTifNy0vPGcLYHnJPUBNoyIl5p704iY\n", "0oaYrSBJu5LmRtwBjIyIVwuHVEfS5qRm0PWAnSLimcIhma2x/AW6ofG+pMlteb22ND3dAhybj48F\n", "bq4pHyepr6QhwFBgVkS8ALwsaVTu3D6G1IHZ9LUOJ3WOWzeRO6ynkvqfToyIz1c0SRxC6rD+b2AP\n", "JwmzpFU1CknTgT2BjSU9C5wJfBuYIWk8sBA4AiAi5kmaAcwDVgATaoYQTgCuAgYAt0fEHbn8CmCa\n", "pPnAUtJewtYNSHoXaZ2ml0nrND1fOKQ6eYe884B9gY9FxG8Kh2RWKepKw8AlRURo9c+00mpqjecC\n", "ZwEXRcSbZaOqJ+mDwPWkYa9frOLmR2Zt1dbPTs/MtnaXJ19eBmxPWoLjkcIh1ckd1qcAXwG+FBHT\n", "C4dkVllOFNauJO0BTCP1O+0QEa8VDqmOpEGkDuu+wI55vo+ZrYIXBbR2IWkdSd8EbiD1S02saJI4\n", "DHgYuA8Y7SRhtnquUVibSdqG1M7/F9LEtCWrOaXT5R3yLiCNLR8bEQ+Wjcis63CNwtaakk8BvyU1\n", "Nx1U0SSxI2nYa2/SyCsnCbM14BqFrRVJbwd+AGwH7BURjxUOqY6k3sCppFnWX4yIGYVDMuuSXKOw\n", "NZaXB3gEeJ7UGVzFJDGYNHFzDKlT3UnCbC05UVir5dn23yb1R5wQESdGxD9Lx9WUpCNIHdZ3AntH\n", "xJ8Kh2TWpbnpyVpF0rakBPE8qcP6xdWc0ukkrQ9cBOxK6i95qHBIZt2CaxTWotxh/Wng18CVpBFD\n", "VUwSo0g75L1B2tvCScKsnbhGYask6T+AHwHvAvaMiHmFQ6qTO6wnkfaxnhARMwuHZNbtuEZhzZK0\n", "DzAHeAYYVdEksRVpKeW9ScuWO0mYdQAnCluJpH6SvkPaqnZ8RJwcEa+XjqspSUeRdsi7hbSe1KLV\n", "nGJma8lNT/YWSe8hdVj/CfhARPylcEh1JG1A2iFvJ+CAiHi4cEhm3Z5rFNbYYX0CcD9p1ddDK5ok\n", "diE1h71K6rB2kjDrBK5R9HCS3gFcTtq+dveIeLJwSHXy9rhfAz5Pmr9x82pOMbN25BpFDyZpP9I3\n", "9D8AH6pokhgC/Io0N2KEk4RZ53Oi6IFyh/V5pC1oPxkRp1a0w/po0s5zM4H9I+K5wiGZ9Uhueuph\n", "JA0DpgNPk2ZYLy0cUp28Q97FwAhg34iYUzgksx6tzTUKSQslPSpptqRZuWygpLslPSXprvwfv/H5\n", "kyTNl/RkbvpoLB8paW5+7MK2xmUryx3WE4BfAt8DDqtoktiN1By2jLSYn5OEWWHt0fQUpJ3CRkTE\n", "TrnsdODuiNiWtILn6fDWt9kjgWGkVT0vkdS44felpHH7Q4Ghksa0Q2wGSHoncCtwPLBrRFweEVE4\n", "rJXkHfK+AdwITIyICRHxaum4zKz9+ijU5P5Y0p7E5J+H5OODgekRsTxvQbkAGCVpM2D9iJiVn3dN\n", "zTnWBjnhzgHmArtExFOFQ6oj6T9JQ3N3JDWH3Vo4JDOr0V41insk/U7SZ3LZJjU7nS0BNsnHmwO1\n", "M2gXAVs0U744l9taktQ/N+H9EPh4REyKiH+VjqtWbg47DniA1G9yYES8UDYqM2uqPTqzd42I5/N4\n", "/LslrTTEMiJCUrs1c0iaUnO3ISIa2uu1uwtJ25NmWD9BmmH918Ih1ck75F0GvBfYJyIeLRySWbeR\n", "Nxcb3V6v1+ZEERHP559/lnQTaWmFJZI2jYgXcrNS47LUi0kTuxoNItUkFufj2vLFq3i/KW2NubvK\n", "/T0Tgf8CvgJcXbW+CABJe5KaF28BjouI1wqHZNat5C/QDY33JU1uy+u1qelJ0rp5sxgkrQfsR2oL\n", "vwU4Nj8cn7qKAAAMKElEQVTtWKBxktQtwLi8U9oQYCgwKzc3vCxpVP6wO6bmHGsFSZsCtwOfIE2e\n", "u6pqSSJ3WH8L+Anw+YiY6CRhVn1trVFsAtyUBy71Aa6LiLsk/Q6YIWk8sBA4AiAi5kmaAcwDVpD2\n", "D2j8MJsAXAUMAG6PiDvaGFuPIekjpH0jLge+HhHLC4dUR9JQUnPYi6QO6yWrOcXMKkIV+9LZIkkR\n", "EU1HWPVYkgYA3wU+AhwTEfcXDqlOriF+CjgHmApcXLWajll319bPTs/M7qIkfYD0Df1R0jf0vxUO\n", "qY6kgaRRV9sCe0XEY4VDMrO14LWeuhhJvSSdBNwDfJs09PWtJKGp2lBTNVlTtW6xIAFJewOPAM8C\n", "OzlJmHVdrlF0IXkE2VXA+qTtSf/nrcemqg/wWeBM4GdAP9K+DZ0dY1/gG6QBCce7r8ms63Oi6CIk\n", "jSU141wGfDMiVgBoqgQcAPwf4Hlg/5gcjxSK8d2k5rDnSPM3/lwiDjNrX04UFSdpXeBc0tpYh0XE\n", "r996bKq2z49tCZwC3BaTO7+jOHdYfwb4FmkOx2XusDbrPpwoKkzSCNLSFg+ROqyXAWiqNgW+Tlo7\n", "6xvAD2JymSGxkjYmDc0dQtoh74kScZhZx3GiqCBJvYAvA6cBJ0bE9QCaqgHA/wZOJvVVvCcml1ue\n", "Q9K+wI9JE+jGVXHzIzNrOyeKipG0BWnF3f7AjhGxMPdDjCONcnoIGBWT4+mCMfYjNTMdCXwqIu4u\n", "FYuZdTwnigqRdCips/r7wNkRsUJTtQtwHtAbODoml51UJ2k7Uof1H0nNYX8pGY+ZdTzPzK6AvE7W\n", "BcDewCci4gFN1btINYgPAZOA62NyvFkwRgGfI/WJnAH8yB3WZl2DZ2Z3cZJ2AK4DfguMYArSVH0H\n", "GA+cDxwXk8vu9JaXkL+CtEfIbhHx5GpOMbNuxImiEEm9SUNaTwYmMoWZpAlzk0nblr4vJqcl3EuS\n", "tD+pw3oacHjVNj8ys47nRFGApMGk/Rh60Ycd+BrvI63Z1Dhhbk7nx8T+pKQFcC7ol8DZwOHA0RHx\n", "i86OycyqwYmik0k6HLgYuJBJ3EY/Lge2ItUuflZmwhz7AzeRlngHHt0dNngeXp5N6rBe2tkxmVl1\n", "OFF0krzB04XA7gzjWI7gY8DdpM7hy0pNmMtOBgbAa6R8NaM/fPVVOO1wd1ibmRNFJ5C0E3Ad/fg1\n", "X+Za+nEtaa7Eu0tOmMuxCe7cMFUobgD6AvcB73su4lQnCTNzouhIucP6dOBLHMz1jOBjpJVfd47J\n", "saBwbJuTVng9Dj62AZy6HOask5aN4jXSGlJmZp5H0VEkbQVMYxvWYxyiD28CX47J8auCMfUnrQ91\n", "HLAzcCNpKZDfQOxHTWd2BHeWiNHM2l9bPzsrlSgkjSFNPOsNXB4R5zR5vEskCknjeDvf5wgWsykD\n", "EWcA13XGhLlmRi/dBexESg5HAL8nJYebIsrOzzCzztFtJtzlZprvAx8GFgMPSbqlK61GKmkD1uMy\n", "DmB/dqA3vbkROLc9J8w1TQS13/xXHr30HHD1aFj/efj766TkMDwinm2vWMysZ6hMoiB9610QEQsB\n", "JP2E1ExSyURR9829v17hQ9zMnqxHH2bQm0ntPWGufhgru0kcGsGdaVTV/z0LnhiQRt++Dhy+Dvzk\n", "BThoZ49eMrO1VaVEsQVpf+VGi4BRhWJp0cof2Mth6LF7sT+96Mfj9OeTHTdh7o2T4Y30niwEZg+A\n", "Wy+XZiwFhsI3/gX7A18iTfLeGGCZk4SZtUWVEkVX+jBL8w4GzIbDdoaN3ujDve/7G0889hhwhqao\n", "D+naNt56N7m/tuXAOoDyUz4CDP0HcAIwBx4Zzco1Do9eMrM2q1KiWAwMrrk/mFSrWImkKTV3GyKi\n", "oWPDasE/3wVzR8Hcj8Obry6Ck38GrKi5vdHkfmsea6E89gVugjcHpGSh14ATI856MEd0p8ShePSS\n", "WY8maTQwut1eryqtEpL6AH8A9iH1xM4CjqrtzK7KqKdm+gpeg9RX0Env7URgZq3W3YbHHsC/h8de\n", "ERFnN3m8EokC/IFtZl1Ht0oUq1OlRGFm1lW09bOzV3sGY2Zm3Y8ThZmZtciJwszMWuREYWZmLXKi\n", "MDOzFjlRmJlZi5wozMysRU4UZmbWIicKMzNrkROFmZm1yInCzMxa5ERhZmYtcqIwM7MWOVGYmVmL\n", "nCjMzKxFThRmZtYiJwozM2uRE4WZmbXIicLMzFq01olC0hRJiyTNzrcDah6bJGm+pCcl7VdTPlLS\n", "3PzYhTXl/STdkMsfkLTV2v9KZmbWntpSowjgvIgYkW8/B5A0DDgSGAaMAS6R1Lip96XA+IgYCgyV\n", "NCaXjweW5vLzgXPaEFenkjS6dAzNqWJcjql1HFPrVTGuKsbUVm1telIzZQcD0yNieUQsBBYAoyRt\n", "BqwfEbPy864BDsnHY4Gr8/FMYJ82xtWZRpcOYBVGlw6gGaNLB9CM0aUDaMbo0gE0Y3TpAFZhdOkA\n", "mjG6dADtra2JYqKkRyRdIWmjXLY5sKjmOYuALZopX5zLyT+fBYiIFcAySQPbGJuZmbWDFhOFpLtz\n", "n0LT21hSM9IQYDjwPHBuJ8RrZmadLSLafAO2Bubm49OB02seuwMYBWwKPFFTfhRwac1zds7HfYA/\n", "r+J9wjfffPPNtzW/teUzvg9rSdJmEfF8vnsoMDcf3wJcL+k8UpPSUGBWRISklyWNAmYBxwAX1Zxz\n", "LPAAcDhwb3PvGRHN9YmYmVkHWutEAZwjaTgpWz0DnAAQEfMkzQDmASuACZGrA8AE4CpgAHB7RNyR\n", "y68ApkmaDywFxrUhLjMza0f692e4mZlZvS4xM3ttJvd1Ulxj8vvOl3RaZ753kzgWSno0X5tZuWxg\n", "HozwlKS7akaldVQMV0paImluTdkqY+iMf7dVxFT0b0nSYEn3SXpc0mOSvpTLS1+rVcVV7HpJ6i/p\n", "QUlzJM2TdHYuL3atWoip+GeUpN75vW/N99vvOrVHZ3ZH34DJwJebKR8GzAHWIXWoLwB6dVJMvfP7\n", "bZ3ffw6wXaHr8wwwsEnZd4BT8/FpwLc7OIbdgRHkQQ0txdBZ/26riKno3xJpUMfwfPw24A/AdhW4\n", "VquKq/T1Wjf/7EPqw9ytAtequZiKf0YBXwauA27J99vtOnWJGkXW2sl9O3VSPDsBCyJiYUQsB36S\n", "4yml6fWpncR4Nf+e3NghIuJ+4K+tjKFT/t1WERMU/FuKiBciYk4+fgV4gjToo/S1WlVcUPZ6vZoP\n", "+5K+nP2V8tequZig4HWSNAg4ELi8Jo52u05dKVGsyeS+zvDWJMEC791UAPdI+p2kz+SyTSJiST5e\n", "AmxSIK5VxVDy3w0q8rckaWtSjedBKnStauJ6IBcVu16SekmaQ7om90XE4xS+VquICcr+XZ0PfAV4\n", "s6as3a5TZRKF2m9yX2f1zldpFMCuETECOAD4gqTdax+MVN8sGm8rYuis+CrxtyTpbaTlak6MiL+v\n", "9KYFr1WO68Yc1ysUvl4R8WZEDAcGAXtI2qvJ451+rZqJaTQFr5OkjwAvRsRsmq/VtPk6tWV4bLuK\n", "iH1b8zxJlwO35ruLgcE1Dw/KZZ2h6XsPZuUs3Wkiz2eJiD9LuolUjVwiadOIeEFpna0XC4S2qhiK\n", "/btFxFvXodTfkqR1SEliWkTcnIuLX6uauK5tjKsK1yvHsUzSbcBIKnCtmsS0Q0Q0NJYXuE67AGMl\n", "HQj0BzaQNI12vE6VqVG0JP+SjZpO7hsnqa+kIeTJfZ0U1u9IK+BuLakvacXcWzrpvd8iaV1J6+fj\n", "9YD9SNencRIj+efNzb9Ch1pVDMX+3Ur/LUkSad7QvIi4oOahotdqVXGVvF6SNm5swpE0ANgXmE3B\n", "a7WqmCRtWvO0Tr1OEXFGRAyOiCGkOWi/iIhjaM/r1BG97x3Qm38N8CjwSP5lN6l57AxSZ8yTwP6d\n", "HNcBpNEhC4BJha7NENIIhjnAY41xAAOBe4CngLuAjTo4junAc8C/SH03n2ophs74d2smpuNL/y2R\n", "Rsi8mf+9ZufbmApcq+biOqDk9QK2B36fY3oU+Mrq/rYLxlSJzyhgT/496qndrpMn3JmZWYu6RNOT\n", "mZmV40RhZmYtcqIwM7MWOVGYmVmLnCjMzKxFThRmZtYiJwozM2uRE4WZmbXo/wNTJ48mZzcLZAAA\n", "AABJRU5ErkJggg==\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "data = [\n", "[10.0000, 30.0000],\n", "[20.0000, 50.0000],\n", "[300.0000, 95.0000],\n", "[40.0000, 2.0000] ]\n", "data = [ [pair[0], pair[0]*pair[1]] for pair in data ]\n", "extpts = [Point(0,0)]\n", "for (x,y) in data:\n", " pt = Point(x, y)\n", " points = extpts[:] + [Point(p.x + pt.x, p.y + pt.y) for p in extpts]\n", " extpts = FindExtremePoints( points, False )\n", "\n", "aim = [5000.0000, 75.0000]\n", "aim = [aim[0], aim[0] * aim[1]]\n", "scale = 100\n", "aim = Point(aim[0] / scale, aim[1] / scale)\n", "\n", "fig, ax = plt.subplots()\n", "ax.scatter([pt.x for pt in extpts], [pt.y for pt in extpts], color = \"blue\")\n", "for i in range(len(extpts)-1):\n", " ax.plot( [extpts[i].x, extpts[i+1].x], [extpts[i].y, extpts[i+1].y], color = \"black\" )\n", "ax.plot( [extpts[-1].x, extpts[0].x], [extpts[-1].y, extpts[0].y], color = \"black\" )\n", "ax.plot( [0, aim[0]], [0, aim[1]], color = \"green\" )\n", "extpts, aim" ] }, { "cell_type": "code", "execution_count": 208, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.6\n" ] } ], "source": [ "def IntersectSegmentVector(seg0, seg1, vec):\n", " \"\"\"Finds if the line segment from `seg0` to `seg1` intersects the\n", " half-line in the direction of `vec`. Returns the value of t>0 with\n", " vec / t in the line segment, or 0.\"\"\"\n", " det = (seg1.x - seg0.x) * vec.y - (seg1.y - seg0.y) * vec.x\n", " if det == 0:\n", " if vec.x * seg0.y == vec.y * seg0.x:\n", " if seg0.x == 0:\n", " if seg1.x == 0:\n", " return 0\n", " return vec.x / seg1.x\n", " if seg1.x == 0:\n", " return vec.x / seg0.x\n", " return min( vec.x / seg0.x, vec.x / seg1.x )\n", " return 0\n", " s = (vec.y * seg1.x - vec.x * seg1.y) / det\n", " if s < 0 or s > 1:\n", " return 0\n", " invt = ( (seg0.y - seg1.y) * seg1.x - (seg0.x - seg1.x) * seg1.y ) / det\n", " if invt <= 0:\n", " return 0\n", " return 1 / invt\n", "\n", "print( IntersectSegmentVector(Point(0.2,0.8), Point(1,1), Point(0.2,0.5)) )" ] }, { "cell_type": "code", "execution_count": 184, "metadata": { "collapsed": false }, "outputs": [], "source": [ "def FindMinScale(convexHull, vector):\n", " \"\"\"Input: convexHull is a list of extreme points of a convex set.\n", " Assumes convexHull[0] = Point(0,0) and ordering is counter-clockwise.\n", " Find the minimal t so that vector / t is in convexHull\n", " Returns 0 if t = infinity is the answer.\"\"\"\n", " if colinear(convexHull[0], convexHull[1], vector) < 0:\n", " return 0\n", " if colinear(convexHull[0], convexHull[-1], vector) > 0:\n", " return 0\n", " t = 0\n", " for i in range(len(convexHull)-1):\n", " tnew = IntersectSegmentVector( convexHull[i], convexHull[i+1], vector)\n", " if tnew != 0 and ( t == 0 or tnew < t ):\n", " t = tnew\n", " tnew = IntersectSegmentVector( convexHull[-1], convexHull[0], vector)\n", " if tnew != 0 and ( t == 0 or tnew < t ):\n", " t = tnew\n", " return t" ] }, { "cell_type": "code", "execution_count": 202, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "18.975332068311197" ] }, "execution_count": 202, "metadata": {}, "output_type": "execute_result" } ], "source": [ "aim = [5000.0000, 75.0000]\n", "aim = [aim[0], aim[0] * aim[1]]\n", "FindMinScale(extpts, Point(aim[0], aim[1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Hard Case" ] }, { "cell_type": "code", "execution_count": 210, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "([Point(x=0, y=0),\n", " Point(x=0.0001, y=0.008839830000000002),\n", " Point(x=100.0, y=8839.83999999),\n", " Point(x=99.9999, y=8839.83116016)],\n", " Point(x=100.0, y=8839.83))" ] }, "execution_count": 210, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": [ "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEACAYAAABGYoqtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\n", "AAALEgAACxIB0t1+/AAAGWhJREFUeJzt3X+QVeWd5/H3Z0UQRUMYM6DSUZLB0bYEASM/EtaeSFwm\n", "EzFblRWcGouJZHa3HFeyUzUbILUbqnZ1JrM1SbBmtTbGKJrVhDJZBmcopRE7Y1TSGn5GZMRxSehO\n", "dRswE5OUOlB+94/7dHNo+0LT93afc+79vKpucc5zftzvTdrzvc95zvO9igjMzMwG86/yDsDMzIrL\n", "ScLMzKpykjAzs6qcJMzMrConCTMzq8pJwszMqhpSkpD0TUm9kvZm2iZJapf0iqQtkiZmtq2WdEDS\n", "fknXZ9rnSNqbtq3LtI+T9J3Uvl3SxfX6gGZmNnxD7Uk8ACwe0LYKaI+IS4Gn0jqSWoGlQGs65h5J\n", "SsfcC6yIiOnAdEl951wBHEntXwW+PMzPY2ZmdTSkJBERzwC/GNC8BFifltcDn07LNwKPRsTRiDgI\n", "vArMlXQBcG5EdKb9Hsockz3Xd4HrTvNzmJnZCKhlTGJyRPSm5V5gclq+EOjK7NcFXDRIe3dqJ/17\n", "CCAijgG/lDSphtjMzKwO6jJwHZXaHq7vYWbWYMbUcGyvpCkR0ZNuJb2e2ruBlsx+U6n0ILrT8sD2\n", "vmM+CPxM0hjgfRHxxsA3lOREZGY2DBGhU+/1XrUkiU3AciqDzMuBjZn2RyR9hcptpOlAZ0SEpDcl\n", "zQU6gVuAuwecazvwGSoD4YMa7gctAklrI2Jt3nEMl+PPV5njL3Ps0BDxD/sL9pCShKRHgWuB8yUd\n", "Av4b8JfABkkrgIPATQARsU/SBmAfcAy4LY6Xmr0NeBAYD2yOiCdS+/3Aw5IOAEeAZcP9QGZmVj9D\n", "ShIRcXOVTYuq7H8XcNcg7T8Crhyk/R1SkjEzs+LwjOvR1ZF3ADXqyDuAGnXkHUCNOvIOoAYdeQdQ\n", "o468A8iLyvSjQ5KizGMSZmZ5qOXa6Z6EmZlV5SRhZmZVOUmYmVlVThJmZlaVk4SZmVXlJGFmZlU5\n", "SZiZWVVOEmZmVpWThJmZVeUkYWZmVTlJmJlZVU4SZmZWlZOEmVkVEmskDqfXmrzjyUMtv0xnZtaw\n", "UlK4M9N0pwQR7/2tnEbmUuFmZoOQOAz8Fmf9A5z/dej6FsCRCM7PObTTVsu10z0JM7NqPnwrLHkA\n", "dp0HXXkHkw8nCTOzATRDF3PD+PH8zlvwt5+D1+7r2/SVPOPKgweuzcwydI3+gjYOctZb73L//13H\n", "a/cdAY4AX2y28QjwmISZGQCaoYm0sJdWpvI8G+MH8W/zjqle/POlZmY10NX6PB/lDd7PB2jn9xop\n", "QdTKYxJm1rQ0S+P4ADv5OJfzAj8A/nXsKtHtlVHgJGFmTUmztYzZfIsA2vl3sTMeyzumInKSMLOm\n", "ot+TgOdYxDx28hK/4KrYGcfyjquonCTMrGnoKl3HlWzmHMawjdvjxfhfecdUdH66ycyaghbqcebx\n", "KV7iJ3RzZeyOX+Ud02ip5drpJGFmDU0zNYPLeI7f5hx+yP+Izvivecc02nJ9BFbSakkvSdor6RFJ\n", "4yRNktQu6RVJWyRNHLD/AUn7JV2faZ+TznFA0rpa4zIz0wLdz3Xs5h3e4vu0NGOCqFVNPQlJlwDb\n", "gMsj4h1J3wE2A1cAhyPiryR9AXh/RKyS1Ao8AnwEuAjYCkyPiJDUCdweEZ2SNgN3R8QTA97PPQkz\n", "OyXN0MV8mB1MYxLP8/V4Pv5D3jHlKc+exJvAUeBsSWOAs4GfAUuA9Wmf9cCn0/KNwKMRcTQiDgKv\n", "AnMlXQCcGxGdab+HMseYmQ1Zf1mNMxnLVmY0e4KoVU1PN0XEG5L+Gvgp8BbwZES0S5ocEb1pt15g\n", "clq+ENieOUUXlR7FUU6ssdid2s3MhqS/rMa1TGU7fxvPhL9o1kFNPQlJHwY+D1xCJQFMkPRH2X2i\n", "cj+rPKPjZlY67ymr4QRRN7XOk7gaeC4ijgBI+h4wH+iRNCUietKtpNfT/t1AS+b4qVR6EN1pOdve\n", "PdgbSlqbWe2IiI4aP4OZlZTLagxOUhvQVpdz1ThwPRP4P1QGot8GHgQ6gYuBIxHxZUmrgIkDBq6v\n", "4fjA9e+kgesfAnek4/8eD1yb2UlotpYxi28BsJM/jB2xIeeQCiu3X6aLiN2SHgJeBN4FdgBfB84F\n", "NkhaARwEbkr775O0AdgHHANui+NZ6jYqSWY8sHlggjAzgyplNXa4rMZI8WQ6MyuNTFmNM3mR/+Sy\n", "GkPjGddm1vBOKKvRxVWxJ/4575jKwknCzBqWy2rUzknCzBqSFuh+5nErr3GY15gVe6Lr1EfZQE4S\n", "ZtZQXFajvvwb12bWMFxWo1jckzCzQugvq9Hqshr15p6EmZWay2oUl3++1Mxy47IaxeckYWa50Gwt\n", "Y3Yqq7GVpS6rUUxOEmY2qlxWo1ycJMxs1JxQVmMbt7usRvH56SYzGxUuq5EfT6Yzs8JyWY38OUmY\n", "WSG5rEYxOEmYWaG4rEaxeDKdmRWGy2o0FvckzKwuXFajuNyTMLNc6Wrd4bIajcnzJMxs2FxWo/E5\n", "SZjZsLisRnNwkjCz05LKavyARSxwWY3G5yRhZkPmshrNx083mdmQuKxGeXkynZmNGJfVKD8nCTMb\n", "ES6r0RicJMysrlxWo7F4Mp2Z1Y3LaliWexJmBrisRiNzT8LMatJfVmOSy2rYiWpOEpImSnpM0suS\n", "9kmaK2mSpHZJr0jaImliZv/Vkg5I2i/p+kz7HEl707Z1tcZlZqemWRqn67WPj7OO/TxLF+NjV3Tk\n", "HZcVRz16EuuAzRFxOTAD2A+sAtoj4lLgqbSOpFZgKdAKLAbukdTXBboXWBER04HpkhbXITYzqyKV\n", "1fgNLVzKVpbG07Ewni7R/WcbFTWNSUh6H7AzIj40oH0/cG1E9EqaAnRExGWSVgPvRsSX035PAGuB\n", "nwDbUqJB0jKgLSL+44DzekzCrEb9ZTU+wgJ2sY83mBkvuqxGI8tzTGIa8HNJD0jaIek+SecAkyOi\n", "N+3TC0xOyxcC2eesu4CLBmnvTu1mVke6Stcxlbf5XeazjdtjS1zhBGEnU2vtpjHAbOD2iHhB0tdI\n", "t5b6RERIqlsXVtLazGpHhO+fmg2FFupxPpHKaux2WY1GJqkNaKvHuWpNEl1AV0S8kNYfA1YDPZKm\n", "RESPpAuA19P2bqAlc/zUdI7utJxt7x7sDSNibY0xmzWVVFbjWWYxge+7rEYzSF+eO/rWJX1puOeq\n", "6XZTRPQAhyRdmpoWAS8BjwPLU9tyYGNa3gQskzRW0jRgOtCZzvNmejJKwC2ZY8xsmLRA93Mdu3mH\n", "t+mgxQnCTlfNk+kkzQS+AYwF/gn4LHAGsAH4IHAQuCmi0rWVtAa4FTgGrIyIJ1P7HOBBYDyVp6Xu\n", "GOS9PHBtNgQuq2FZrt1kZv10je5kHmvo4dfsZ0Hsib15x2T5cpIws76yGntopcVlNSzLZTnMmlym\n", "rMZvu6yG1ZN/vtSsxDRL4/gAO/g4rbzAs8DC2FWi2wNWeE4SZiWVymp8C4CtLI0dsSHnkKwBOUmY\n", "lUx/WY1FmbIaOzxr2kaGk4RZiegqtXElT3IOZ7KNlfFi3J13TNbY/HSTWUlooTYxjxvYx085xEyX\n", "1bCh8iOwZg2sv6zGZCaw3WU17PQ5SZg1KM3Xfcznc7zGYV5jVuyJrlMfZXYiJwmzBpPKavyIafwW\n", "z/ONeD7+JO+YrLw8mc6sgega3UkbBzmTcWxlhhOE5ck9CbOCcFkNGynuSZiVnMtqWFF5noRZjlxW\n", "w4rOScIsJ5qtm5jNI4DLalhhOUmYjTKX1bAycZIwG0Uuq2Fl46ebzEaJy2pYXjyZzqzAXFbD8uYk\n", "YVZQLqthReAkYVYwLqthReLJdGYF4rIa1kjckzCrkwFlNR6PZ2JJ3jGZgXsSZrkbpKyGE4Q1BM+T\n", "MKuBy2pYo3OSMBsml9WwZuAkYXaa3lNW4+fMjp3xTt5xmY0EJwmz0+CyGtZs6jJwLekMSTslPZ7W\n", "J0lql/SKpC2SJmb2XS3pgKT9kq7PtM+RtDdtW1ePuMzqSQu1iU/wNG/Qw3NMcoKwZlCvp5tWAvuA\n", "vgG7VUB7RFwKPJXWkdQKLAVagcXAPZL6Hsu6F1gREdOB6ZIW1yk2s5popmZoqX7FLG7g+9wVfx8X\n", "u+6SNYuak4SkqcAngW8AfRf8JcD6tLwe6PuVrRuBRyPiaEQcBF4F5kq6ADg3IjrTfg9ljjHLjebr\n", "Pq5jN+/wNh20RGd8Me+YzEZTPcYkvgr8OXBepm1yRPSm5V5gclq+ENie2a8LuAg4mpb7dKd2s1z0\n", "l9WY77Ia1txqShKSPgW8HhE7JbUNtk9EhKS6PTcuaW1mtSMiOup1bjPoL6uxhh5+zVPMjN2xJ++Y\n", "zE5Huh631eNctfYkFgBLJH0SOAs4T9LDQK+kKRHRk24lvZ727wZaMsdPpdKD6E7L2fbuwd4wItbW\n", "GLPZoPrLalzrshpWbunLc0ffuqQvDfdcNY1JRMSaiGiJiGnAMmBbRNwCbAKWp92WAxvT8iZgmaSx\n", "kqYB04HOiOgB3pQ0Nw1k35I5xmzEuayG2eDqPU+i77bSXwIbJK0ADgI3AUTEPkkbqDwJdQy4LY5X\n", "GLwNeBAYD2yOiCfqHJvZe7ishtnJuQqsNS3N1k3MSmU1dvKHLqthjaqWa6dnXFvTcVkNs6FzkrCm\n", "4rIaZqfHt5usaWihNjGPG9jHTznETM+atmbh37g2OwnN1Awu41kmM4Ht3OVZ09ZsnCTMqtB83cd8\n", "PsdrHOY1ro498ZO8YzIbbU4SZgP0l9WY5rIaZv6Na7OMVFbjIGcyjqeY6QRhNnzuSVjD6C+r0eqy\n", "GmZZ7klY03NZDbOR4XkSVmouq2E2spwkrLQ0WzcxO5XV2MpSl9Uwqz8nCSsdl9UwGz1OElYqqazG\n", "E0xgrMtqmI08P91kpeGyGmbD48l01tBcVsOsNk4S1rBcVsOsdk4S1nBcVsOsfjyZzhqKy2qYFYd7\n", "ElYYqazGblr5oMtqmNWPexJWerpad7CAN5jEZJfVMCsOz5OwXLmshlmxOUlYblxWw6z4nCRs1KWy\n", "Gs+wiI+6rIZZsTlJ2KhyWQ2zcvHTTTZqtFAbmceNLqthNro8mc4KTTN0JZfxHFNcVsMsD04SVlj9\n", "ZTX+H0f4J+a4rIbZ6HOSsMJxWQ2z4shtMp2kFklPS3pJ0o8l3ZHaJ0lql/SKpC2SJmaOWS3pgKT9\n", "kq7PtM+RtDdtW1dLXJYvl9Uwaxw19SQkTQGmRMQuSROAHwGfBj4LHI6Iv5L0BeD9EbFKUivwCPAR\n", "4CJgKzA9IkJSJ3B7RHRK2gzcHRFPDHg/9yQKzGU1zIopt55ERPRExK60/GvgZSoX/yXA+rTbeiqJ\n", "A+BG4NGIOBoRB4FXgbmSLgDOjYjOtN9DmWOsBFxWw6wx1W2ehKRLgFnAD4HJEdGbNvUCk9PyhcD2\n", "zGFdVJLK0bTcpzu1W8G5rIZZY6tLkki3mr4LrIyIX0nHezXpVlLdLhqS1mZWOyKio17nttMzoKzG\n", "zbEjvp1zSGYGSGoD2upxrpqThKQzqSSIhyNiY2rulTQlInrSraTXU3s30JI5fCqVHkR3Ws62dw/2\n", "fhGxttaYrTYuq2FWbOnLc0ffuqQvDfdctT7dJOB+YF9EfC2zaROwPC0vBzZm2pdJGitpGjAd6IyI\n", "HuBNSXPTOW/JHGMFoqvUxlTe4jIWsI2VsSWucIIwa1y1Pt30MeAfgD1A34lWA53ABuCDwEHgpohK\n", "CQZJa4BbgWNUbk89mdrnAA8C44HNEXHHIO/np5tylCmrcYhDzHBZDbNy8GQ6G1Euq2FWbk4SNmJc\n", "VsOs/JwkrO40Q1P5EDv5EOeznW/Gc7Ei75jMbHj8G9dWV7pG/51rOcQ4zuIpZjpBmDUv9ySsn8tq\n", "mDUm9ySsZrpaf5rKakyhnUVOEGYG/vnSpjegrMZzwMdcVsPM+jhJNDGX1TCzU3GSaEIuq2FmQ+Uk\n", "0WR0ldq4kieYwFi2sTJejLvzjsnMistPNzURl9Uwa06eTGcn5bIaZs3NScKqclkNM3OSsPdwWQ0z\n", "6+PJdHYCl9Uws3pxT6KBDCir8XfxTNyQd0xmlj/3JGywshpOEGZWM8+TKDmX1TCzkeQkUWIuq2Fm\n", "I81JooRcVsPMRouTRMm4rIaZjSY/3VQiLqthZsPhyXQNzmU1zKwWThINTPP1v5nPv3dZDTMbLieJ\n", "BuSyGmZWL55M12BcVsPMisI9iQJxWQ0zGwnuSTQAl9UwsyLyPImcuayGmRVZoXoSkhZL2i/pgKQv\n", "5B3PSNMsfYbZ/IYWfpet3BxPx0fjaScIMyuOwoxJSDoD+EdgEdANvADcHBEvZ/ZpiDGJ/rIaH3FZ\n", "DTMbeY0yJnEN8GpEHIyIo8C3gRtzjqkuJNZIHJY4rPP/5j6m8haXsYBtrIwtcYUThJkVVZHGJC4C\n", "DmXWu4C5OcVSNxJrgDsBuPwG+IO/+xx7zvslu9+c4rIaZlZ0RUoSxbjvVX9/BsCcabDgIHx7FXT9\n", "xbEInCDMrPCKlCS6gZbMeguV3sQJJK3NrHZERMfIhlUnP94Ae86Go1fkHYmZNThJbUBbXc5VoIHr\n", "MVQGrq8DfgZ00gAD1yfcbjruixHclUc8ZtZ8arl2FqYnERHHJN0OPAmcAdyfTRBlFcFdqvxf82ep\n", "6StOEGZWFoXpSQxFGXsSZmZ5a5RHYM3MrGCcJMzMrConCTMzq8pJwszMqnKSMDOzqpwkzMysKicJ\n", "MzOryknCzMyqcpIwM7OqnCTMzKwqJwkzM6vKScLMzKpykjAzs6qcJMzMrConCTMzq8pJwszMqnKS\n", "MDOzqpwkzMysKicJMzOryknCzMyqcpIwM7OqnCTMzKwqJwkzM6vKScLMzKpykjAzs6qcJMzMrCon\n", "CTMzq8pJwszMqhp2kpD0PyW9LGm3pO9Jel9m22pJByTtl3R9pn2OpL1p27pM+zhJ30nt2yVdPPyP\n", "ZGZm9VJLT2ILcEVEzAReAVYDSGoFlgKtwGLgHklKx9wLrIiI6cB0SYtT+wrgSGr/KvDlGuIqLElt\n", "ecdQC8efrzLHX+bYofzx12LYSSIi2iPi3bT6Q2BqWr4ReDQijkbEQeBVYK6kC4BzI6Iz7fcQ8Om0\n", "vARYn5a/C1w33LgKri3vAGrUlncANWrLO4AateUdQA3a8g6gRm15B5CXeo1J3ApsTssXAl2ZbV3A\n", "RYO0d6d20r+HACLiGPBLSZPqFJuZmQ3TmJNtlNQOTBlk05qIeDzt80XgXyLikRGIz8zM8hQRw34B\n", "fww8C5yVaVsFrMqsPwHMpZJsXs603wzcm9lnXloeA/y8yvuFX3755Zdfp/8a7nX+pD2Jk0mDzn8O\n", "XBsRb2c2bQIekfQVKreRpgOdERGS3pQ0F+gEbgHuzhyzHNgOfAZ4arD3jAgN1m5mZiND6Rv66R8o\n", "HQDGAm+kpucj4ra0bQ2VcYpjwMqIeDK1zwEeBMYDmyPijtQ+DngYmAUcAZalQW8zM8vRsJOEmZk1\n", "vlLMuB7OxL2ikbQ4xXhA0hfyjudkJLVIelrSS5J+LKmvxzdJUrukVyRtkTQx71hPRtIZknZK6nvI\n", "ojTxS5oo6bH0d79P0tySxb86/f3slfRImjBb2PglfVNSr6S9mbaq8RbpulMl9rpdM0uRJDi9iXuF\n", "+0ySzgD+hkqMrcDNki7PN6qTOgr854i4ApgH/GmKdxXQHhGXUhk3WpVjjEOxEthHZeAOyhX/Oiq3\n", "ZC8HZgD7KUn8ki4B/gSYHRFXAmcAyyh2/A9Q+e8za9B4C3jdGSz2ul0zC3dBHcxpTty7JocQT+Ua\n", "4NWIOBgRR4FvU4m9kCKiJyJ2peVfAy9TeQghO+lxPccnQxaOpKnAJ4FvAH0PPJQi/vStb2FEfBMg\n", "Io5FxC8pSfzAm1S+aJwtaQxwNvAzChx/RDwD/GJAc7V4C3XdGSz2el4zS5EkBhjKxL2i6Z8smBQ1\n", "zvdI3wpnUflDmxwRvWlTLzA5p7CG4qtUnr57N9NWlvinAT+X9ICkHZLuk3QOJYk/It4A/hr4KZXk\n", "8M8R0U5J4s+oFm9Zrjt9arpmFiZJpHt/ewd53ZDZZygT94o4El/EmE5J0gQqZVJWRsSvstui8sRD\n", "IT+XpE8Br0fETo73Ik5Q5PipzBWaDdwTEbOB3zDg1kyR45f0YeDzwCVULkoTJP1Rdp8ixz+YIcRb\n", "yM9Sj2vmsOdJ1FtEfOJk2yX9MZXbB9m6Tt1AS2Z9amormoFxtnBiNi8cSWdSSRAPR8TG1NwraUpE\n", "9KRaXK/nF+FJLQCWSPokcBZwnqSHKU/8XUBXRLyQ1h+jck+5pyTxXw08FxFHACR9D5hPeeLvU+3v\n", "pRTXnXpdMwvTkzgZHZ+4d+MgE/eWSRoraRpp4l4eMZ7Ci1Sq3l4iaSyVgaNNOcdUlSQB9wP7IuJr\n", "mU19kx5J/24ceGwRRMSaiGiJiGlUBky3RcQtlCf+HuCQpEtT0yLgJeBxShA/lUH2eZLGp7+lRVQe\n", "IChL/H2q/b0U/rpT12tmLWU5RusFHAB+AuxMr3sy29ZQGXzZD/ybvGM9yWf4feAfU6yr847nFLF+\n", "jMq9/F2Z/80XA5OArVSeltgCTMw71iF8lmuBTWm5NPEDM4EXgN3A94D3lSz+/0Ilse2lMuh7ZpHj\n", "Bx6lMn7yL1TGDz97sniLdN0ZJPZb63nN9GQ6MzOrqhS3m8zMLB9OEmZmVpWThJmZVeUkYWZmVTlJ\n", "mJlZVU4SZmZWlZOEmZlV5SRhZmZV/X8tRLkc1DoypAAAAABJRU5ErkJggg==\n" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "aim = [100.0000, 88.3983]\n", "data = [\n", "[0.0001, 88.3983],\n", "[99.9999, 88.3984] ]\n", "\n", "#aim = [1000000, 883983]\n", "#data = [ [1, 883983], [999999, 883984] ]\n", "\n", "\n", "data = [ [pair[0], pair[0]*pair[1]] for pair in data ]\n", "extpts = [Point(0,0)]\n", "for (x,y) in data:\n", " pt = Point(x, y)\n", " points = extpts[:] + [Point(p.x + pt.x, p.y + pt.y) for p in extpts]\n", " extpts = FindExtremePoints( points, False )\n", "\n", "aim = [aim[0], aim[0] * aim[1]]\n", "scale = 1\n", "aim = Point(aim[0] / scale, aim[1] / scale)\n", "\n", "fig, ax = plt.subplots()\n", "ax.scatter([pt.x for pt in extpts], [pt.y for pt in extpts], color = \"blue\")\n", "for i in range(len(extpts)-1):\n", " ax.plot( [extpts[i].x, extpts[i+1].x], [extpts[i].y, extpts[i+1].y], color = \"black\" )\n", "ax.plot( [extpts[-1].x, extpts[0].x], [extpts[-1].y, extpts[0].y], color = \"black\" )\n", "ax.plot( [0, aim[0]], [0, aim[1]], color = \"green\" )\n", "extpts, aim" ] }, { "cell_type": "code", "execution_count": 211, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 211, "metadata": {}, "output_type": "execute_result" } ], "source": [ "FindMinScale(extpts, Point(aim[0], aim[1]))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Convert to integers\n", "\n", "My convex hull finding code will work with just integers, which preserves accuracy. So, if we can convert the input to integers, we have won, in some sense." ] }, { "cell_type": "code", "execution_count": 229, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[1200100, 504200, 751123]" ] }, "execution_count": 229, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def ScaleFloats(data):\n", " \"\"\"Pass a list of floating point numbers, as strings of the from \"12\" or \"5.2300\"\n", " but _not_ exponential format. Finds a power of 10 to multiply them all by so they\n", " become integers, and returns this list of integers.\"\"\"\n", " dataParts = [ x.split(\".\") for x in data ]\n", " scalePower = [len(x[1]) for x in dataParts if len(x) > 1]\n", " scalePower = max(scalePower) if len(scalePower) > 0 else 0\n", " newData = []\n", " for x in dataParts:\n", " b = x[1] if len(x) > 1 else \"\"\n", " b = b + \"0\"*(scalePower - len(b))\n", " newData.append( int(x[0] + b) )\n", " return newData\n", "\n", "ScaleFloats([\"12.00100\", \"5.042\", \"07.51123\"])" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x=list(range(10))\n", "x" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/plain": [ "[3, 5, 7, 9]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x[3::2]" ] }, { "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.4.3" } }, "nbformat": 4, "nbformat_minor": 0 }