.. _half_edge:

The half-edge data structure
============================

The half-edge data structure (HDS), also doubly-connected edge list
(`DCEL <https://en.wikipedia.org/wiki/Doubly_connected_edge_list>`_),
is a data structure constructed to represent graphs, discrete surfaces and polytopes.
In particular it encodes all the structural and combinatorial information of a given graph or surface.
These information are stored in instances of vertices, edges and faces.
As the name suggests the edges play a special role.
Every combinatorial edge is represented by two directed half-edges, each pointing at one of the incident vertices.
Furthermore, each of the half-edges belongs to a unique face (or `None` if the edge is a boundary edge)
which allows simple and efficient ways to handle and modify surfaces.
Not all half-edge instances must be topological surfaces but since this is often desired and also needed for visualization
in Blender this can be verified within this package, as explained in the section `Validating a surface`_.
Anyhow, by abuse of terminology, the main class of the half-edge package, and often instances of it, are called surfaces.

.. contents:: Table of contents
   :local:
   :backlinks: none


The very basics and a simple half-edge surface
----------------------------------------------

We start by initializing an instance of the :py:class:`ddg.datastructures.halfedge.surface.Surface` class that can be accessed
using

.. doctest::

    >>> import ddg
    >>> s = ddg.halfedge.Surface()
    
The instance `s` is a surface with no edges, vertices or faces given yet.
Using the class methods :py:meth:`~ddg.datastructures.halfedge.surface.Surface.add_face` and :py:meth:`~ddg.datastructures.halfedge.surface.Surface.glue` allows a simple extension
of the surface `s`. New vertices and edges are automatically initialized and linked to the surface.

.. doctest::

    >>> f0 = s.add_face(3)
    >>> f1 = s.add_face(5)
    >>> s.glue(f0.edge, f1.edge)

The above results in a purely combinatoric surface with 2 faces, 14 edges and 6 vertices.

.. image:: simple_surface.png
    :width: 500px
    :align: center

Faces, edges and vertices are represented as classes stored in `s.faces`, `s.edges` and `s.verts`.
The objects themself posses different attributes, depending on the cell type:


    - faces:
        - edge
        - index
    - edges:
        - opp
        - nex
        - pre
        - head
        - tail
        - face
        - index
    - vertices:
        - edge
        - index

For a face `f` the attribute `f.edge` points to a random half-edge belonging to the face and for a vertex `v` the attribute
`v.edge` points to a random half-edge that points to the vertex.

Taking a closer look at the half-edges of a surface one sees, that the union of all half-edges consists of disjoint oriented loops
of half-edges. For every edge `e` the attributes `e.pre` and `e.nex` allow iteration though these loops.
The "inner" of such a loop either consists of a face of `s` or is empty. This is represented by each edge attribute `e.face` that either
returns the face that is enclosed by the corresponding edge loop or returns None if the edge is a boundary edge.

Eventually half-edges are still representing the connection between two vertices, two oppositely oriented half-edges
representing one combinatorial edge. The attribute `e.opp` allows switching between two such half-edges connecting the
vertices `v1 = e.head` and `v2 = e.opp.head`.


The surface generator
---------------------
There are various ways to create surfaces using the half-edge datastructure.
Next to the :py:mod:`~ddg.datastructures.halfedge.surface_generator` that we will explain in the following one can use

    * conversion from file
      for the conversion of obj (:ref:`obj_to_halfedge`, :ref:`to_obj`) or json (:py:mod:`~ddg.datastructures.halfedge.io`) files to halfedge surfaces
    * the :py:mod:`~ddg.datastructures.indexedfaceset` package
      with its conversion function :py:func:`~ddg.datastructures.indexedfaceset.utils.indexed_face_set_to_surface`

The :py:mod:`~ddg.datastructures.halfedge.surface_generator` is a module of the half-edge package for simple construction of common surfaces.
It also includes a convex hull algorithm that generates a half-edge surface from a given list of 3-dimensional coordinates.

We can simply create platonic solids:

.. doctest::

    >>> import numpy as np
    >>> import ddg.datastructures.halfedge.surface_generator as gen

    >>> tetrahedron = gen.tetrahedron()
    >>> cube = gen.cube()
    >>> octahedron = gen.octahedron()
    >>> dodecahedron = gen.dodecahedron()
    >>> icosahedron = gen.icosahedron()

.. image:: platonic_solids.png
    :width: 800px
    :align: center

or any other polytope from given vertices

.. doctest::

    >>> conv = gen.convexhull_3d(np.random.random((8, 3)))

It also includes a generator function for an :py:func:`~ddg.datastructures.halfedge.surface_generator.icosphere`:

.. doctest::

    >>> icosphere = gen.icosphere(
    ...     subdivision_steps=1, radius=1, generate_coordinates=True
    ... )


and a :py:func:`~ddg.datastructures.halfedge.surface_generator.cylinder`

.. doctest::

    >>> cylinder = gen.cylinder(
    ...     resolution=20, fill_caps=True, generate_coordinates=True, co_attr="co"
    ... )

.. image:: icosphere_and_cylinder.png
    :scale: 10 %
    :align: center

These two are used for the Tubes-and-Spheres visualization of half-edge objects
(see :ref:`Visualization of halfedge objects <visualizing_halfedge>`).

Furthermore, the surface generator allows us to generate grids, which are planar meshes of faces with a fixed number
of vertices, as half-edge surfaces:

.. doctest::

   >>> quad_grid = gen.grid(4, 5)
   >>> triangle_grid = gen.triangle_grid(4, 5)

The :py:func:`~ddg.datastructures.halfedge.surface_generator.grid` function for quadrilateral grids has an extra
keyword where vertices can be specified. If vertices are given they are copied to a new surface, keeping their old
attributes. If they have a coordinate attribute `co` the coordinates stored in this attribute are used, other wise the
`generate_coordinate` keyword holds. Note that the given dimension must coincide with the number of vertices. 4
For more, see `Working with grids`_.

One can also create an arrow, useful for vector field visualization:

.. doctest::

   >>> arrow = gen.arrow(resolution=30)

.. image:: arrow.png
    :width: 220px
    :align: center

A disc or circle embedded in 3d Euclidean space can be created using

.. doctest::

    >>> disc = gen.disc(
    ...     circle_subdivisions=40,
    ...     generate_coordinates=True,
    ...     co_attr="co",
    ...     center=np.array([0, 0, 0]),
    ...     radius=3,
    ...     normal=np.array([0, 0, 1]),
    ... )
    >>> circle = gen.disc(
    ...     circle_subdivisions=40,
    ...     generate_coordinates=True,
    ...     co_attr="co",
    ...     fill_face=False,
    ...     center=np.array([0, 0, 0]),
    ...     radius=3,
    ...     normal=np.array([0, 0, 1]),
    ... )

.. image:: disc.png
    :scale: 15%
    :align: center


Accessing the surfaces' data
----------------------------
All the information about a half-edge surface is stored in its vertices edges and faces.
Information can be accessed using the :py:mod:`ddg.datastructures.halfedge.get` module.

We start with a cube:

.. doctest::

    >>> import ddg.datastructures.halfedge.surface_generator as gen
    >>> get = ddg.halfedge.get
    >>> cube = gen.cube()

The cells of the surface are stored in classes and we can easily find the number of cells where the
class name is extended by the memory address of the surface:

.. doctest::

    >>> cube.verts
    <class 'ddg.datastructures.halfedge._node.Verts...'>
    >>> cube.edges
    <class 'ddg.datastructures.halfedge._node.Edges...'>
    >>> cube.faces
    <class 'ddg.datastructures.halfedge._node.Faces...'>

    >>> len(cube.verts), len(cube.edges), len(cube.faces)
    (8, 24, 6)

These classes are not subscriptable but iterable:

.. doctest::

    >>> for v in cube.verts:
    ...     pass
    ...

Sometimes it is handy to just pick out a single cell:

.. doctest::

    >>> get.get_vertex(cube)
    Verts(index=0, edge=0, surface=...)
    >>> get.get_edge(cube)
    Edges(index=0, head=0, face=0, surface=...)
    >>> get.get_face(cube)
    Faces(index=0, edge=0, surface=...)

Functions in the :py:mod:`~ddg.datastructures.halfedge.get` module that are built to yield multiple
instances of cells will return generators. For example, the following two generators will yield the same edges:

.. doctest::

    >>> f = get.get_face(cube)
    >>> get.get_edges(f)
    <generator object get_edge_loop at 0x...>
    >>> get.get_edge_loop(f.edge)
    <generator object get_edge_loop at 0x...>

If only the number of instances are of interest one can either use the implemented functions
or work with list comprehensions:

.. doctest::

    >>> assert get.get_number_of_edges(f) == get.count_edges_in_loop(f.edge)
    >>> assert len([e for e in get.in_edges(v)]) == len([e for e in get.out_edges(v)])

Another handy accessory of this module is dealing with interior and boundary edges.
The functions :py:func:`~ddg.datastructures.halfedge.get.interior_vertices` and
:py:func:`~ddg.datastructures.halfedge.get.boundary_vertices` return generators that yield all the desired
vertices. Similar functions exist for edges:

.. doctest::

    >>> [e.face for e in get.boundary_edges(cube)]
    []
    >>> len([e.face for e in get.interior_edges(cube)])
    24

They use :py:func:`~ddg.datastructures.halfedge.get.is_boundary_vertex` and
:py:func:`~ddg.datastructures.halfedge.get.is_boundary_edge` which return a bool.


Modifying a surface
-------------------

A great part of working with half-edge sufaces is the modification of a given
surface.  These modification can for example include joining, attaching and
glueing or anything about separating, splitting and removing.  Next to the
:py:class:`~ddg.datastructures.halfedge.surface.Surface` methods
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.add_vertex`,
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.add_edge`,
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.add_face` and
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.glue`, the half-edge
package allows much simpler and more efficient ways.  The module
:py:mod:`ddg.datastructures.halfedge.modify` contains a variety of
functions to modify a given surface.

In the following we will give a variety of small code snippets and supply pictures of their effects on a given surface.
For the creation of the pictures coordinates where explicitly set for vertices, see the next section
`Adding attributes to vertices, edges and faces`_. Thus they only serve as a rough orientation, essentially all
surfaces in this section are purely combinatoric.

In order to apply various utility functions we always start with the simple surface from the beginning:

.. doctest::

    >>> from ddg.datastructures.halfedge.surface import Surface
    >>> import ddg.datastructures.halfedge.get as get
    >>> import ddg.datastructures.halfedge.modify as modify

    >>> s = ddg.halfedge.Surface()
    >>> f0 = s.add_face(3)
    >>> f1 = s.add_face(5)
    >>> s.glue(f0.edge, f1.edge)



Removing and adding faces:

.. doctest::

    >>> modify.remove_face(f1)

    >>> boundary = get.boundary_edges(s)

    >>> e = next(boundary)
    >>> while e.face is not None or e.opp.face is not None:
    ...     e = next(boundary)
    ...

    >>> f1 = modify.fill_hole(e)
    >>> f1
    Faces(index=1, edge=6, surface=...)

.. image:: modify_01_delete_face_and_fill_hole.png
    :scale: 20 %
    :align: center


.. note::

    When calling :py:func:`~ddg.datastructures.halfedge.modify.remove_face` the edge loop that corresponds to the
    input face is not deleted. Therefore after removing the face we can find edges of this loop and fill the hole of this
    edge loop with a face using :py:func:`~ddg.datastructures.halfedge.modify.fill_hole`.


Subdividing and joining faces by hand:

.. doctest::

    >>> edge = f1.edge.pre
    >>> e0, e1, v = modify.subdivide_edge(edge, 2)

    >>> new_edge = modify.split_face_at(f1, v[0], f1.edge.nex.head)
    >>> modify.join_neighbouring_faces(new_edge)


.. image:: modify_03_subdivide_edge_and_split_face.png
     :scale: 15 %
     :align: center


Stellar subdivision using :py:func:`~ddg.datastructures.halfedge.modify.stellar_subdivide`:

.. doctest::

    >>> v = modify.stellar_subdivide(f1)
    >>> v
    Verts(index=7, edge=11, surface=...)


.. image:: modify_02_subdivide.png
    :scale: 15 %
    :align: center


Deleting a vertex along with all its connecting edges and faces using :py:func:`~ddg.datastructures.halfedge.modify.remove_vertex`:

.. doctest::

    >>> v = get.get_vertex(s)
    >>> modify.remove_vertex(v)


.. image:: modify_06_remove_vertex.png
    :scale: 15 %
    :align: center


Extending polygons to 3-dimensional polytopes:

.. doctest::

    >>> import ddg
    >>> s = ddg.halfedge.Surface()
    >>> f0 = s.add_face(5)

    >>> v = modify.attach_pyramid(f0.edge.opp)


.. image:: modify_04_attach_pyramid.png
    :scale: 15 %
    :align: center

To extend a polygon to a 3-dimensional polytope we can for example use the functions
:py:func:`~ddg.datastructures.halfedge.modify.attach_pyramid` or
:py:func:`~ddg.datastructures.halfedge.modify.bridge_loops`:

.. doctest::

    >>> s = ddg.halfedge.Surface()
    >>> f0 = s.add_face(5)
    >>> f1 = s.add_face(5)

    >>> modify.bridge_loops(f0.edge, f1.edge)

.. image:: modify_05_bride_loops.png
    :scale: 20 %
    :align: center


The methods :py:meth:`~ddg.datastructures.halfedge.surface.Surface.add_vertex`
just adds a single isolated vertex. The function
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.add_edge` connects two
vertices with a "whole" edge:

.. doctest::

    >>> s = ddg.halfedge.Surface()
    >>> v1 = s.add_vertex()
    >>> v2 = s.add_vertex()
    >>> e = s.add_edge(v1, v2)
    >>> e.head is v2
    True
    >>> e.opp.head is v1
    True
    >>> s.validate_curve()

In contrast to the functions mentioned above, these functions will not preserve
the manifold property.


Adding attributes to vertices, edges and faces
----------------------------------------------
Adding attributes to vertices, edges and faces of surfaces is an essential part.
New attributes can be initialized using ``add_attribute`` of the ``_node`` class.
The most commonly used attribute is the ``"co"`` attribute for vertices that stores 3-dimensional coordinates of
the corresponding vertices of the surface.
It is possible to name the vertex attribute storing the coordinates differently.
Functions that depend on the coordinate attribute support a keyword argument ``co_attr="co"``.

Coordinates can be assigned to the vertices in the following way.:

.. doctest::

    >>> import ddg

    >>> s = ddg.halfedge.Surface()
    >>> f0 = s.add_face(3)
    >>> f1 = s.add_face(5)
    >>> s.glue(f0.edge, f1.edge)

    >>> co_attr = s.verts.add_attribute("co")

    >>> l = [
    ...     [0.5, 0, 0],
    ...     [0.7, 0.4, 0],
    ...     [0.5, 0.8, 0],
    ...     [0, 0.8, 0],
    ...     [-0.5, 0, 0],
    ...     [0, 0, 0],
    ... ]

    >>> for i, v in enumerate(s.verts):
    ...     v.co = l[i]
    ...     # Similarly one could assign the coordinates by
    ...     # co_attr[v] = l[i]
    ...

Similarly attributes can be assigned to edges and faces:

.. doctest::

    >>> s.edges.add_attribute("len")
    <ddg.datastructures.halfedge._node.NodeAttribute object at 0x...>
    >>> s.faces.add_attribute("is_triangle", False)
    <ddg.datastructures.halfedge._node.NodeAttribute object at 0x...>

After the initialization above all edges have a ``e.len`` attribute that is by default set to None and all faces have a
``f.is_triangle`` attribute that, by default, is set to ``False``.


Utilities for setting (common) attributes
-----------------------------------------
The module :py:mod:`~ddg.datastructures.halfedge.set` contains functions to compute and set useful attributes
of halfedge surfaces.
The most general example is setting an attribute computed by a custom function on the desired cells:
:py:func:`~ddg.datastructures.halfedge.set.set_attr_by_function`

.. doctest::

    >>> hds = gen.triangle_grid(2, 2)
    >>> def neighbouring_faces(face):
    ...     return len(
    ...         list(
    ...             [e for e in get.get_edge_loop(face.edge) if e.opp.face is not None]
    ...         )
    ...     )
    ...
    >>> attribute = ddg.halfedge.set.set_attr_by_function(
    ...     hds,
    ...     neighbouring_faces,
    ...     cell_type="faces",
    ...     attr_name="number_of_neighbouring_faces",
    ... )

.. image:: set_set_attribute_by_function.png
    :scale: 30%
    :align: center

More specific examples are given by :py:func:`~ddg.datastructures.halfedge.set.set_euclidean_length_attr`
that assigns the euclidean edge length to edges (also see `Modifying surfaces with coordinates`_),
or by :py:func:`~ddg.datastructures.halfedge.set.set_valency_attr`,
that assigns a valency attribute to either vertices or faces that stores the number of neighbouring cells of the same kind.
To get the same result as in the above example
one can use

.. doctest::

    >>> attribute = ddg.halfedge.set.set_valency_attr(
    ...     hds, cell_type="faces", attr_name="number_of_neighbouring_faces"
    ... )


An even more specific example is given by
:py:func:`~ddg.datastructures.halfedge.set.indicate_minimal_valency`, that can be used to identify the
corners of regular halfedge surface:

.. doctest::

    >>> grid = gen.grid(4, 4)
    >>> diag_grid1, diag_grid2 = ddg.halfedge.modify.diagonals(grid)

    >>> attr1 = ddg.halfedge.set.set_minimal_valency_attr(
    ...     grid, attr_name="is_corner_vertex", attr_values=[1, 0]
    ... )
    >>> attr2 = ddg.halfedge.set.set_minimal_valency_attr(
    ...     diag_grid1, attr_name="is_corner_vertex", attr_values=[1, 0]
    ... )
    >>> attr3 = ddg.halfedge.set.set_minimal_valency_attr(
    ...     diag_grid2, attr_name="is_corner_vertex", attr_values=[1, 0]
    ... )

    >>> len([v for v in grid.verts if attr1[v]])
    4

.. image:: minimal_valence_attr.png
    :width: 900px
    :align: center


A different utility that can be found in the module
allows simple bi-coloring of hds using :py:func:`~ddg.datastructures.halfedge.set.bicolor_vertices`,
:py:func:`~ddg.datastructures.halfedge.set.bicolor_edges` or
:py:func:`~ddg.datastructures.halfedge.set.bicolor_faces` for a bi-coloring of vertices, edges or
faces, respectively.:

.. doctest::

    >>> v0, v1 = ddg.halfedge.set.bicolor_vertices(
    ...     grid, color_attr="color", colors=["white", "black"]
    ... )
    >>> v0, v1 = ddg.halfedge.set.bicolor_vertices(
    ...     diag_grid1, color_attr="color", colors=["white", "black"]
    ... )
    >>> v0, v1 = ddg.halfedge.set.bicolor_vertices(
    ...     diag_grid2, color_attr="color", colors=["white", "black"]
    ... )

.. image:: bi_coloring_vertices.png
    :width: 800px
    :align: center


.. doctest::

    >>> e0, e1 = ddg.halfedge.set.bicolor_edges(
    ...     grid, color_attr="color", colors=["white", "black"]
    ... )
    >>> e0, e1 = ddg.halfedge.set.bicolor_edges(
    ...     diag_grid1, color_attr="color", colors=["white", "black"]
    ... )
    >>> e0, e1 = ddg.halfedge.set.bicolor_edges(
    ...     diag_grid2, color_attr="color", colors=["white", "black"]
    ... )


.. image:: bi_coloring_edges.png
    :width: 800px
    :align: center

.. doctest::

    >>> diag_grid_3 = ddg.halfedge.modify.diagonals(grid, boundary_face_incidence=3)[0]
    >>> f0, f1 = ddg.halfedge.set.bicolor_faces(
    ...     diag_grid_3, color_attr="color", colors=["white", "black"]
    ... )
    >>> f0, f1 = ddg.halfedge.set.bicolor_faces(
    ...     grid, color_attr="color", colors=["white", "black"]
    ... )
    >>> f0, f1 = ddg.halfedge.set.bicolor_faces(
    ...     diag_grid1, color_attr="color", colors=["white", "black"]
    ... )
    >>> cylinder = gen.cylinder(fill_caps=False)
    >>> f0, f1 = ddg.halfedge.set.bicolor_faces(
    ...     hds, color_attr="color", colors=["black", "white"]
    ... )



.. image:: bi_coloring_faces.png
    :width: 800px
    :align: center


Modifying surfaces with coordinates
-----------------------------------
In addition to the previously mentioned utilities there are more utility functions that work with surfaces that have
3-dimensional coordinates set on the vertices.
The function :py:func:`~ddg.datastructures.halfedge.set.set_euclidean_length_attr` computes the Euclidean length
of the edges:

.. doctest::

    >>> length_attr = ddg.halfedge.set.set_euclidean_length_attr(
    ...     grid, co_attr="co", attr_name="length"
    ... )
    >>> ddg.halfedge.get.get_edge(grid).length
    1.0

By default, the grid possesses 2-dimensional coordinates stored in a vertex attribute with the name `co`.


With :py:func:`~ddg.datastructures.halfedge.modify.join_colplanar_faces` we can numerically test
whether two adjacent faces are coplanar and if so we can join them:

.. doctest::

    >>> s = gen.convexhull_3d(
    ...     [
    ...         [1, 1, 1],
    ...         [1, -1, 1],
    ...         [1, 1, -1],
    ...         [1, -1, -1],
    ...         [1, 0, 1.5],
    ...         [1, 0, -1.5],
    ...         [1, -1.5, 0],
    ...         [1, 1.5, 0],
    ...         [-1, 1, 1],
    ...         [-1, -1, 1],
    ...         [-1, 1, -1],
    ...         [-1, -1, -1],
    ...     ],
    ...     False,
    ... )
    >>> len(s.faces)
    20
    >>> modify.join_coplanar_faces(s)
    >>> len(s.faces)
    14

In some cases it might be convenient to reverse the orientation of a surface which can be done using the function
:py:func:`~ddg.datastructures.halfedge.modify.reverse_orientation`.

.. note::
    The function :py:func:`~ddg.datastructures.halfedge.modify.reverse_orientation` reverses the orientation of
    all edges of a surface. It might be convenient to do this for single connected components but it does not make sense
    for single faces or edges.

The :py:func:`~ddg.datastructures.halfedge.modify.reverse_orientation` function can, for example, be used to
simplify the visualization process of a surface created by :py:func:`~ddg.datastructures.halfedge.modify.bridge_loops`:

.. doctest::

    >>> s = ddg.halfedge.Surface()
    >>> f0 = s.add_face(5)

    >>> co_attr = s.verts.add_attribute("co")

    >>> l = [[0.5, 0, 0], [0.7, 0.4, 0], [0.5, 0.8, 0], [0, 0.8, 0], [0, 0, 0]]

    >>> for k, v in enumerate(ddg.halfedge.get.get_vertices(f0)):
    ...     v.co = l[k]
    ...

    >>> ddg.halfedge.modify.reverse_orientation(s)

    >>> f1 = s.add_face(5)

    >>> for k, v in enumerate(ddg.halfedge.get.get_vertices(f1)):
    ...     l[k][2] += 1
    ...     v.co = l[k]
    ...

    >>> ddg.halfedge.modify.bridge_loops(f0.edge, f1.edge)

Working with grids
------------------

The :py:mod:`~ddg.datastructures.halfedge.surface_generator` contains a
:py:meth:`~ddg.datastructures.halfedge.surface_generator.grid` method that creates a grid of m times n quadrilaterals
and a :py:meth:`~ddg.datastructures.halfedge.surface_generator.triangle_grid` method that creates a grid of m times n
triangles.
Various functions to modify grids are located at :py:mod:`ddg.datastructures.halfedge.grid`.

Creating grids and bi-coloring a quadrilateral grid using :py:meth:`~ddg.datastructures.halfedge.set.bicolor_graph`:

.. doctest::

    >>> grid = gen.grid(6, 4)
    >>> triangle_grid = gen.triangle_grid(6, 4)

    >>> v0, v1 = ddg.halfedge.set.bicolor_vertices(grid)

    >>> v0[0].color, v1[0].color
    (0, 1)

.. image:: grids01.png
    :width: 900px
    :align: center

The module :py:mod:`ddg.datastructures.halfedge.grid` includes functions to modify grids.

Finding parallel lines of a quadrilateral grid using :py:meth:`~ddg.datastructures.halfedge.grid.get_coordinate_polylines`
and :py:meth:`~ddg.datastructures.halfedge.grid.get_coordinate_polyline`:

.. doctest::

    >>> x_lines, y_lines = ddg.halfedge.grid.get_coordinate_polylines(grid)
    >>> len(x_lines), len(y_lines)
    (5, 7)
    >>> x_line = ddg.halfedge.grid.get_coordinate_polyline(
    ...     ddg.halfedge.get.get_edge(grid)
    ... )
    >>> len(x_line)
    4

.. image:: grids03.png
    :width: 500px
    :align: center

Creating two grids of diagonal combinatoric to the given grid using
:py:func:`ddg.datastructures.halfedge.modify.diagonals`:

.. doctest::

    >>> diagonal_grid0, diagonal_grid1 = ddg.halfedge.modify.diagonals(
    ...     grid, boundary_face_incidence=4, append_single_edges=True
    ... )
    >>> diagonal_grid0  # doctest: +ELLIPSIS
    <ddg.datastructures.halfedge.surface.Surface object at 0x...>

    >>> grid0, grid1 = ddg.halfedge.modify.diagonals(
    ...     diagonal_grid0, boundary_face_incidence=4, append_single_edges=True
    ... )
    >>> grid0  # doctest: +ELLIPSIS
    <ddg.datastructures.halfedge.surface.Surface object at 0x...>

.. image:: grids02.png
    :scale: 20 %
    :align: center

The keyword argument ``append_single_edges`` decides whether to attach edges in
the corners of a diagonal grid (making it lose the manifold property). The
keyword argument ``boundary_face_incidence`` states how many vertices of
another color must be adjacent to a given boundary vertex in order to create a
face.

.. doctest::

    >>> diagonal_grid0, diagonal_grid1 = ddg.halfedge.modify.diagonals(
    ...     grid, boundary_face_incidence=3, append_single_edges=True
    ... )
    >>> diagonal_grid0, diagonal_grid1 = ddg.halfedge.modify.diagonals(
    ...     grid, boundary_face_incidence=4, append_single_edges=False
    ... )



.. image:: grids04.png
    :scale: 20 %
    :align: center






Validating a surface
--------------------

Especially when modifying a surface explicitly, for example when setting new
heads, predecessors and successors of edges, it makes sense to check from time
to time whether everything has been set correctly. For this, you can use the
methods :py:meth:`~ddg.datastructures.halfedge.surface.Surface.validate`,
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.validate_surface`,
:py:meth:`~ddg.datastructures.halfedge.surface.Surface.validate_curve` and
:py:meth:`~ddg.datastructures.halfedge.Surface.validate_graph`,
depending on what type of object you want to represent with your halfedge
object. Basically, `validate` just checks for consistence of `nex`, `opp` and
so on, while the others additionally check if the object is a 2d or 1d manifold
or has faces. See the api docs for details.

It is also a very handy tool to use in tests. It can be executed by:

.. doctest::

    >>> s.validate()
    >>> s.validate_surface()
    >>> s.validate_curve()
    Traceback (most recent call last):
    ...
    ddg.datastructures.halfedge.surface.SurfaceError: Object has faces.

If everything was set up fine the code will continue and otherwise it will
raise a SurfaceError.  It is also possible to check whether a given surface
consists of triangulated faces:

.. doctest::

    >>> get.is_triangulation(cube)
    False

There is also a function to check whether your object is connected:

.. doctest::

    >>> get.is_connected(cube)
    True

Visualization in Blender
------------------------

A guide on how to visualize halfedge objects in Blender can be found here:
:ref:`Visualizing halfedge objects <visualizing_halfedge>`.