.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/geometry/convex_hull/plot_01_graham_scan.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_geometry_convex_hull_plot_01_graham_scan.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_geometry_convex_hull_plot_01_graham_scan.py:


Graham's scan: the convex hull by an angular sweep
========================================================

Graham's scan sorts the points by angle around the lowest point, then
sweeps through them, dropping any point that would make a clockwise
turn. The picture shows the angular order the sweep follows and the
hull it produces; the result is checked against scipy's Qhull-based
:func:`~mathematicskit.geometry.convex_hull`.

.. GENERATED FROM PYTHON SOURCE LINES 13-19

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.geometry import convex_hull, graham_scan
    from mathematicskit.geometry.visualizers.plots import plot_convex_hull








.. GENERATED FROM PYTHON SOURCE LINES 20-22

Random points, the Graham scan, and the Qhull check
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 22-32

.. code-block:: Python


    rng = np.random.default_rng(0)
    points = rng.uniform(-5, 5, size=(30, 2))

    graham_result = graham_scan(points)
    qhull_result = convex_hull(points)

    print(f"Graham: {sorted(int(v) for v in graham_result.vertices)}, area={graham_result.volume:.4f}")
    print(f"Qhull:  {sorted(int(v) for v in qhull_result.vertices)}, area={qhull_result.volume:.4f}")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Graham: [1, 4, 5, 6, 10, 13, 19, 24, 26], area=80.3141
    Qhull:  [1, 4, 5, 6, 10, 13, 19, 24, 26], area=80.3141




.. GENERATED FROM PYTHON SOURCE LINES 33-38

The angular order of the sweep
-----------------------------------------------------
Rays from the pivot (the lowest point) to every other point, shaded by
polar angle: the scan visits the points in this order and keeps only
left turns.

.. GENERATED FROM PYTHON SOURCE LINES 38-51

.. code-block:: Python


    pivot = points[int(np.lexsort((points[:, 0], points[:, 1]))[0])]
    angles = np.arctan2(points[:, 1] - pivot[1], points[:, 0] - pivot[0])

    fig, ax = plt.subplots(figsize=(6, 6))
    cmap = plt.get_cmap("viridis")
    for p, a in zip(points, angles):
        ax.plot([pivot[0], p[0]], [pivot[1], p[1]], color=cmap(a / np.pi), lw=0.6, alpha=0.7)
    plot_convex_hull(graham_result, ax=ax)
    ax.plot(*pivot, "*", color="k", ms=14, zorder=3, label="pivot")
    ax.legend(loc="upper left")
    ax.set_title("Graham scan: angular sweep around the lowest point")
    plt.show()



.. image-sg:: /api/gallery/geometry/convex_hull/images/sphx_glr_plot_01_graham_scan_001.png
   :alt: Graham scan: angular sweep around the lowest point
   :srcset: /api/gallery/geometry/convex_hull/images/sphx_glr_plot_01_graham_scan_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.027 seconds)


.. _sphx_glr_download_api_gallery_geometry_convex_hull_plot_01_graham_scan.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_graham_scan.ipynb <plot_01_graham_scan.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_graham_scan.py <plot_01_graham_scan.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_graham_scan.zip <plot_01_graham_scan.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_