.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "tutorials/delaunay-triangulation.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

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

        :ref:`Go to the end <sphx_glr_download_tutorials_delaunay-triangulation.py>`
        to download the full example code.

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

.. _sphx_glr_tutorials_delaunay-triangulation.py:


.. _tutorials-delaunay-triangulation:

======================
Delaunay Triangulation
======================

This example demonstrates how to calculate the `Delaunay triangulation <https://en.wikipedia.org/wiki/Delaunay_triangulation>`_ of an input graph. We start by generating a set of points on a 2D grid using random ``numpy`` arrays and a graph with those vertex coordinates and no edges.

.. GENERATED FROM PYTHON SOURCE LINES 11-18

.. code-block:: Python


    import numpy as np
    from scipy.spatial import Delaunay
    import igraph as ig
    import matplotlib.pyplot as plt









.. GENERATED FROM PYTHON SOURCE LINES 19-21

We start by generating a random graph in the 2D unit cube, fixing the random
seed to ensure reproducibility.

.. GENERATED FROM PYTHON SOURCE LINES 21-27

.. code-block:: Python

    np.random.seed(0)
    x, y = np.random.rand(2, 30)
    g = ig.Graph(30)
    g.vs["x"] = x
    g.vs["y"] = y








.. GENERATED FROM PYTHON SOURCE LINES 28-31

Because we already set the `x` and `y` vertex attributes, we can use
:meth:`igraph.Graph.layout_auto` to wrap them into a :class:`igraph.Layout`
object.

.. GENERATED FROM PYTHON SOURCE LINES 31-33

.. code-block:: Python

    layout = g.layout_auto()








.. GENERATED FROM PYTHON SOURCE LINES 34-35

Now we can calculate the delaunay triangulation using `scipy`'s :class:`scipy:scipy.spatial.Delaunay` class:

.. GENERATED FROM PYTHON SOURCE LINES 35-37

.. code-block:: Python

    delaunay = Delaunay(layout.coords)








.. GENERATED FROM PYTHON SOURCE LINES 38-39

Given the triangulation, we can add the edges into the original graph:

.. GENERATED FROM PYTHON SOURCE LINES 39-46

.. code-block:: Python

    for tri in delaunay.simplices:
        g.add_edges([
            (tri[0], tri[1]),
            (tri[1], tri[2]),
            (tri[0], tri[2]),
        ])








.. GENERATED FROM PYTHON SOURCE LINES 47-50

Because adjacent triangles share an edge/side, the graph now contains some
edges more than once. It's useful to simplify the graph to get rid of those
multiedges, keeping each side only once:

.. GENERATED FROM PYTHON SOURCE LINES 50-52

.. code-block:: Python

    g.simplify()





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

 .. code-block:: none


    <igraph.Graph object at 0x715d627d3e50>



.. GENERATED FROM PYTHON SOURCE LINES 53-55

Finally, plotting the graph gives a good idea of what the triangulation looks
like:

.. GENERATED FROM PYTHON SOURCE LINES 55-66

.. code-block:: Python

    fig, ax = plt.subplots()
    ig.plot(
        g,
        layout=layout,
        target=ax,
        vertex_size=4,
        vertex_color="lightblue",
        edge_width=0.8
    )
    plt.show()




.. image-sg:: /tutorials/images/sphx_glr_delaunay-triangulation_001.png
   :alt: delaunay triangulation
   :srcset: /tutorials/images/sphx_glr_delaunay-triangulation_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 67-72

Alternative plotting style
--------------------------
We can use :doc:`matplotlib <matplotlib:index>` to plot the faces of the
triangles instead of the edges. First, we create a hue gradient for the
triangle faces:

.. GENERATED FROM PYTHON SOURCE LINES 72-74

.. code-block:: Python

    palette = ig.GradientPalette("midnightblue", "lightblue", 100)








.. GENERATED FROM PYTHON SOURCE LINES 75-78

Then we can "plot" the triangles using
:class:`matplotlib:matplotlib.patches.Polygon` and the graph using
:func:`igraph.plot() <igraph.drawing.plot>`:

.. GENERATED FROM PYTHON SOURCE LINES 78-100

.. code-block:: Python

    fig, ax = plt.subplots()
    for tri in delaunay.simplices:
        # get the points of the triangle
        tri_points = [delaunay.points[tri[i]] for i in range(3)]

        # calculate the vertical center of the triangle
        center = (tri_points[0][1] + tri_points[1][1] + tri_points[2][1]) / 3

        # draw triangle onto axes
        poly = plt.Polygon(tri_points, color=palette.get(int(center * 100)))
        ax.add_patch(poly)

    ig.plot(
        g,
        layout=layout,
        target=ax,
        vertex_size=0,
        edge_width=0.2,
        edge_color="white",
    )
    ax.set(xlim=(0, 1), ylim=(0, 1))
    plt.show()



.. image-sg:: /tutorials/images/sphx_glr_delaunay-triangulation_002.png
   :alt: delaunay triangulation
   :srcset: /tutorials/images/sphx_glr_delaunay-triangulation_002.png
   :class: sphx-glr-single-img






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

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


.. _sphx_glr_download_tutorials_delaunay-triangulation.py:

.. only:: html

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

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

      :download:`Download Jupyter notebook: delaunay-triangulation.ipynb <delaunay-triangulation.ipynb>`

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

      :download:`Download Python source code: delaunay-triangulation.py <delaunay-triangulation.py>`

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

      :download:`Download zipped: delaunay-triangulation.zip <delaunay-triangulation.zip>`


.. only:: html

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

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