Skip to content

Instantly share code, notes, and snippets.

@WetHat

WetHat/PY-2dConvexHull.ipynb

Last active April 15, 2024 14:22
Show Gist options
  • Save WetHat/d69ce0e94e337538e5b4c848501522aa to your computer and use it in GitHub Desktop.
Save WetHat/d69ce0e94e337538e5b4c848501522aa to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. WetHat revised this gist Oct 4, 2023. 1 changed file with 89 additions and 60 deletions.
    149 changes: 89 additions & 60 deletions PY-2dConvexHull.ipynb
    View file
    89 additions, 60 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  2. WetHat revised this gist Apr 3, 2020. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion PY-2dConvexHull.ipynb
    View file
    Original file line number Diff line number Diff line change
    @@ -1668,7 +1668,7 @@
    "name": "python",
    "nbconvert_exporter": "python",
    "pygments_lexer": "ipython3",
    "version": "3.6.9"
    "version": "3.8.1"
    },
    "toc": {
    "base_numbering": 1,
  3. WetHat revised this gist Dec 11, 2019. 1 changed file with 11 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions PY-2dConvexHull.ipynb
    View file
    11 additions, 11 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  4. WetHat revised this gist Dec 11, 2019. 1 changed file with 167 additions and 38 deletions.
    205 changes: 167 additions & 38 deletions PY-2dConvexHull.ipynb
    View file
    167 additions, 38 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  5. WetHat revised this gist Dec 8, 2019. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions PY-2dConvexHull.ipynb
    View file
    Original file line number Diff line number Diff line change
    @@ -17,7 +17,7 @@
    "* an implementation of the [QuickHull](https://en.wikipedia.org/wiki/Quickhull) subdivision algorithm for computing convex hulls of point clouds\n",
    "* a marching algorithm to add points to existing convex hulls one by one.\n",
    "\n",
    "**Note**: For production use it is recommended to use\n",
    "**Note**: For production code it is recommended to use\n",
    "[scipy.spatial.ConvexHull](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html) \n",
    "from the [scipy](https://www.scipy.org/) package."
    ]
    @@ -528,7 +528,7 @@
    "and use this class to iteratively build a polygon until $OS(e) = \\emptyset$\n",
    "for all edges of that polygon.\n",
    "\n",
    "The `OuterSector` shall be able to:\n",
    "The `OuterSector` implementation shall be able to:\n",
    "* classify points in a point cloud as _right_ or _left_ relative to an oriented section line\n",
    " (represented by a `PolygonEdge` instance).\n",
    "* compute the outermost point (apogee) for _right_ (outside) points. An apogee, by definition,\n",
  6. WetHat revised this gist Dec 8, 2019. 1 changed file with 5 additions and 5 deletions.
    10 changes: 5 additions & 5 deletions PY-2dConvexHull.ipynb
    View file
    Original file line number Diff line number Diff line change
    @@ -374,12 +374,12 @@
    "\\right\\}\n",
    "$$\n",
    "\n",
    "where $PG_m(P_n)$ represents a polygon with $m$ edges defined on point of the point cloud $P_n$.\n",
    "where $PG_m(P_n)$ represents a polygon with $m$ edges defined on points of the point cloud $P_n$.\n",
    "\n",
    "We will use this class to:\n",
    "* create a polygon from an ordered set of points.\n",
    "* Iterate over the vertices or edges of the polygon\n",
    "* Draw the polygon"
    "* draw the polygon"
    ]
    },
    {
    @@ -451,7 +451,7 @@
    "cell_type": "markdown",
    "metadata": {},
    "source": [
    "This polygon we can easily draw using its `draw` method:"
    "This polygon can easily be drawn using its `draw` method:"
    ]
    },
    {
    @@ -502,7 +502,7 @@
    "Computation of a convex hull requires some means to determine whether points are outside or inside of a\n",
    "convex hull. We already have a way to determine if point is left or right to the (unbounded) straight\n",
    "line of a edge by calculating its signed distance. With this we can subdivide a point cloud using\n",
    "the signed distance.\n",
    "the signed distance method of edges.\n",
    "\n",
    "We define a class which describes the subset of points $OS(e)$ with $OS(e) \\subset P_n$ where\n",
    "all points of $OS(e)$ are to the right of the polygon edge $e(\\vec{a},\\vec{b},)$:\n",
    @@ -518,7 +518,7 @@
    "where $e$ is a shorthand notation for the edge $e(\\vec{a},\\vec{b})$.\n",
    "\n",
    "With this, a convex hull $C_m(P_n)$ of the point cloud $P_n$ can be described as a\n",
    "polygon $PG_m(P_n)$ where there are no points of $P_n$ outside (to the _right_ of any of its edges):\n",
    "polygon $PG_m(P_n)$ where there are no points of $P_n$ outside (to the _right_) of any of its edges:\n",
    "\n",
    "$$\n",
    "C_m(P_n) = PG_m(P_n) \\Longleftrightarrow \\forall e \\in PG_m(P_n) \\;\\big|\\; OS(e) = \\emptyset\n",
  7. WetHat revised this gist Dec 8, 2019. 1 changed file with 70 additions and 22 deletions.
    92 changes: 70 additions & 22 deletions PY-2dConvexHull.ipynb
    View file
    70 additions, 22 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  8. WetHat revised this gist Dec 7, 2019. 1 changed file with 27 additions and 17 deletions.
    44 changes: 27 additions & 17 deletions PY-2dConvexHull.ipynb
    View file
    27 additions, 17 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  9. WetHat revised this gist Dec 7, 2019. 1 changed file with 60 additions and 75 deletions.
    135 changes: 60 additions & 75 deletions PY-2dConvexHull.ipynb
    View file
    60 additions, 75 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  10. WetHat revised this gist Dec 7, 2019. 1 changed file with 539 additions and 203 deletions.
    742 changes: 539 additions & 203 deletions PY-2dConvexHull.ipynb
    View file
    539 additions, 203 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
  11. WetHat revised this gist Dec 6, 2019. 2 changed files with 1181 additions and 1 deletion.
    1,181 changes: 1,181 additions & 0 deletions PY-2dConvexHull.ipynb
    View file
    1,181 additions, 0 deletions not shown because the diff is too large. Please use a local Git client to view these changes.
    1 change: 0 additions & 1 deletion test.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1 +0,0 @@
    s
  12. WetHat created this gist Dec 6, 2019.
    1 change: 1 addition & 0 deletions test.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1 @@
    s