.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/geometry/proximity/plot_01_closest_pair.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_proximity_plot_01_closest_pair.py>`
        to download the full example code.

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

.. _sphx_glr_api_gallery_geometry_proximity_plot_01_closest_pair.py:


Shamos and Hoey: the closest pair of points
=================================================

Finds the closest pair in random point sets by divide and conquer,
checks the answer with a k-d tree, and compares the running time with
the brute-force comparison of every pair.

.. GENERATED FROM PYTHON SOURCE LINES 11-19

.. code-block:: Python

    import time

    import matplotlib.pyplot as plt
    import numpy as np
    from scipy.spatial import cKDTree

    from mathematicskit.geometry import closest_pair








.. GENERATED FROM PYTHON SOURCE LINES 20-22

One point set
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 22-35

.. code-block:: Python


    rng = np.random.default_rng(0)
    points = rng.uniform(size=(400, 2))
    result = closest_pair(points)
    kd_distance = cKDTree(points).query(points, k=2)[0][:, 1].min()
    print(f"closest pair {result.indices}, distance {result.distance:.6f} (k-d tree: {kd_distance:.6f})")

    fig, ax = plt.subplots()
    ax.plot(*points.T, ".", color="0.5")
    ax.plot(*points[list(result.indices)].T, "o-", color="tab:red")
    ax.set_aspect("equal")
    ax.set_title("closest pair")




.. image-sg:: /api/gallery/geometry/proximity/images/sphx_glr_plot_01_closest_pair_001.png
   :alt: closest pair
   :srcset: /api/gallery/geometry/proximity/images/sphx_glr_plot_01_closest_pair_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    closest pair (205, 357), distance 0.002077 (k-d tree: 0.002077)

    Text(0.5, 1.0, 'closest pair')



.. GENERATED FROM PYTHON SOURCE LINES 36-38

Divide and conquer against brute force
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 38-56

.. code-block:: Python


    sizes = [100, 200, 400, 800]
    dc_times, brute_times = [], []
    for n in sizes:
        pts = rng.uniform(size=(n, 2))
        start = time.perf_counter()
        closest_pair(pts)
        dc_times.append(time.perf_counter() - start)
        start = time.perf_counter()
        best = min(np.hypot(*(pts[i] - pts[j])) for i in range(n) for j in range(i + 1, n))
        brute_times.append(time.perf_counter() - start)

    fig, ax = plt.subplots()
    ax.loglog(sizes, dc_times, "o-", label=r"divide and conquer, $O(n \log n)$")
    ax.loglog(sizes, brute_times, "s-", label=r"all pairs, $O(n^2)$")
    ax.set_xlabel("number of points")
    ax.set_ylabel("seconds")
    ax.legend()



.. image-sg:: /api/gallery/geometry/proximity/images/sphx_glr_plot_01_closest_pair_002.png
   :alt: plot 01 closest pair
   :srcset: /api/gallery/geometry/proximity/images/sphx_glr_plot_01_closest_pair_002.png
   :class: sphx-glr-single-img


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

 .. code-block:: none


    <matplotlib.legend.Legend object at 0x119db6a50>




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

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


.. _sphx_glr_download_api_gallery_geometry_proximity_plot_01_closest_pair.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_closest_pair.ipynb <plot_01_closest_pair.ipynb>`

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

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

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

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


.. only:: html

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

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