Pachner moves on 2+1 dimensional foliated Delaunay triangulations. More...

#include <expected>
#include "Formatters.hpp"
#include "Manifold.hpp"
#include "Move_tracker.hpp"

Include dependency graph for Ergodic_moves_3.hpp:

This graph shows which files directly or indirectly include this file:

Typedefs
using	ergodic_moves::Cell_container = std::vector< Cell_handle >

using	ergodic_moves::Cell_handle = Cell_handle_t< 3 >

using	ergodic_moves::Delaunay = Delaunay_t< 3 >

using	ergodic_moves::Edge_container = std::vector< Edge_handle >

using	ergodic_moves::Edge_handle = Edge_handle_t< 3 >

using	ergodic_moves::Expected = std::expected< Manifold, std::string >

using	ergodic_moves::Manifold = manifolds::Manifold_3

using	ergodic_moves::Vertex_container = std::vector< Vertex_handle >

using	ergodic_moves::Vertex_handle = Vertex_handle_t< 3 >

Functions
auto	ergodic_moves::bistellar_flip (Delaunay triangulation, Edge_handle edge, Vertex_handle top, Vertex_handle bottom) -> std::optional< Delaunay >
	Perform a bistellar flip on triangulation via the given edge.

auto	ergodic_moves::check_move (Manifold const &t_before, Manifold const &t_after, move_tracker::move_type const &t_move) -> bool
	Check move correctness.

auto	ergodic_moves::do_23_move (Manifold &t_manifold) -> Expected
	Perform a (2,3) move.

auto	ergodic_moves::do_26_move (Manifold &t_manifold) -> Expected
	Perform a (2,6) move.

auto	ergodic_moves::do_32_move (Manifold &t_manifold) -> Expected
	Perform a (3,2) move.

auto	ergodic_moves::do_44_move (Manifold const &t_manifold) -> Expected
	Perform a (4,4) move.

auto	ergodic_moves::do_62_move (Manifold &t_manifold) -> Expected
	Perform a (6,2) move.

auto	ergodic_moves::find_adjacent_31_cell (Cell_handle const &t_cell) -> std::optional< int >
	Find a (2,6) move location.

auto	ergodic_moves::find_bistellar_flip_location (Delaunay const &triangulation, Edge_handle const &t_edge_candidate) -> std::optional< Cell_container >
	Find a bistellar flip location.

auto	ergodic_moves::find_pivot_edge (Delaunay const &triangulation, Edge_container const &edges) -> std::optional< Edge_handle >

auto	ergodic_moves::get_incident_cells (Delaunay const &triangulation, Edge_handle const edge) -> std::optional< Cell_container >
	Return a container of cells incident to an edge.

auto	ergodic_moves::get_vertices (Cell_container const &cells)
	Return a container of all vertices in a container of cells.

auto	ergodic_moves::incident_cells_from_edge (Delaunay_t< 3 > const &triangulation, Edge_handle const &edge) -> std::optional< Cell_container >
	Find all cells incident to the edge.

auto	ergodic_moves::is_62_movable (Manifold const &manifold, Vertex_handle const &candidate) -> bool
	Find a (6,2) move location.

auto	ergodic_moves::null_move (Manifold const &t_manifold) noexcept -> Expected
	Perform a null move.

auto	ergodic_moves::try_23_move (Manifold &t_manifold, Cell_handle const &to_be_moved) -> bool
	Perform a TriangulationDataStructure_3::flip on a facet.

auto	ergodic_moves::try_32_move (Manifold &t_manifold, Edge_handle const &to_be_moved) -> bool
	Perform a TriangulationDataStructure_3::flip on an edge.

Detailed Description

Pachner moves on 2+1 dimensional foliated Delaunay triangulations.

Author: Adam Getchell

Pachner moves operate on the level of the Manifold_3. The helper functions for the moves operate on the level of the Delaunay_Triangulation_3. C++23 support is required for std::expected.

Definition in file Ergodic_moves_3.hpp.

Typedef Documentation

◆ Cell_container

using ergodic_moves::Cell_container = typedef std::vector<Cell_handle>

Definition at line 29 of file Ergodic_moves_3.hpp.

◆ Cell_handle

using ergodic_moves::Cell_handle = typedef Cell_handle_t<3>

Definition at line 28 of file Ergodic_moves_3.hpp.

◆ Delaunay

using ergodic_moves::Delaunay = typedef Delaunay_t<3>

Definition at line 34 of file Ergodic_moves_3.hpp.

◆ Edge_container

using ergodic_moves::Edge_container = typedef std::vector<Edge_handle>

Definition at line 31 of file Ergodic_moves_3.hpp.

◆ Edge_handle

using ergodic_moves::Edge_handle = typedef Edge_handle_t<3>

Definition at line 30 of file Ergodic_moves_3.hpp.

◆ Expected

using ergodic_moves::Expected = typedef std::expected<Manifold, std::string>

Definition at line 27 of file Ergodic_moves_3.hpp.

◆ Manifold

using ergodic_moves::Manifold = typedef manifolds::Manifold_3

Definition at line 26 of file Ergodic_moves_3.hpp.

◆ Vertex_container

using ergodic_moves::Vertex_container = typedef std::vector<Vertex_handle>

Definition at line 33 of file Ergodic_moves_3.hpp.

◆ Vertex_handle

using ergodic_moves::Vertex_handle = typedef Vertex_handle_t<3>

Definition at line 32 of file Ergodic_moves_3.hpp.

Function Documentation

◆ bistellar_flip()

auto ergodic_moves::bistellar_flip	(	Delaunay	triangulation,
		Edge_handle	edge,
		Vertex_handle	top,
		Vertex_handle	bottom
	)		-> std::optional<Delaunay>

inline

Perform a bistellar flip on triangulation via the given edge.

Pass by value to avoid modifying the original triangulation in the event that the flip is unsuccessful.

Parameters

triangulation	The triangulation to flip
edge	The edge to pivot on
top	Top vertex of the cells being flipped
bottom	Bottom vertex of the cells being flipped

Returns: A flipped triangulation or nullopt

Definition at line 570 of file Ergodic_moves_3.hpp.

References ergodic_moves::bistellar_flip(), and ergodic_moves::get_incident_cells().

Referenced by ergodic_moves::bistellar_flip(), and ergodic_moves::do_44_move().

◆ check_move()

auto ergodic_moves::check_move	(	Manifold const &	t_before,
		Manifold const &	t_after,
		move_tracker::move_type const &	t_move
	)		-> bool

inline

Check move correctness.

Parameters

t_before	The manifold before the move
t_after	The manifold after the move
t_move	The type of move

Returns: True if the move correctly changed the triangulation

Definition at line 1080 of file Ergodic_moves_3.hpp.

References ergodic_moves::check_move().

Referenced by ergodic_moves::check_move().

◆ do_23_move()

auto ergodic_moves::do_23_move ( Manifold & t_manifold ) -> Expected

inline

Perform a (2,3) move.

A (2,3) move "flips" a timelike face into a timelike edge. This adds a (2,2) simplex and a timelike edge.

This function calls try_23_move on (2,2) simplices drawn from a randomly shuffled container until it succeeds or runs out of simplices.

If successful, the triangulation is no longer Delaunay.

Parameters

t_manifold The simplicial manifold

Returns: The Expected (2,3) moved manifold or an Unexpected

Definition at line 87 of file Ergodic_moves_3.hpp.

References ergodic_moves::do_23_move(), and ergodic_moves::try_23_move().

Referenced by ergodic_moves::do_23_move().

◆ do_26_move()

auto ergodic_moves::do_26_move ( Manifold & t_manifold ) -> Expected

inline

Perform a (2,6) move.

A (2,6) move inserts a vertex into the spacelike face between a (1,3) simplex on the bottom connected to a (3,1) simplex on top. This adds 2 (1,3) simplices and 2 (3,1) simplices. It adds 2 spacelike faces and 6 timelike faces. It also adds 2 timelike edges and 3 spacelike edges, as well as the vertex. This function calls find_adjacent_31_cell on (1,3) simplices drawn from a randomly shuffled container until it succeeds or runs out of simplices. If successful, the triangulation is no longer Delaunay.

Parameters

t_manifold The simplicial manifold

Returns: The Expected (2,6) moved manifold or an Unexpected

Definition at line 188 of file Ergodic_moves_3.hpp.

References ergodic_moves::do_26_move(), and ergodic_moves::find_adjacent_31_cell().

Referenced by ergodic_moves::do_26_move().

◆ do_32_move()

auto ergodic_moves::do_32_move ( Manifold & t_manifold ) -> Expected

inline

Perform a (3,2) move.

A (3,2) move "flips" a timelike edge into a timelike face. This removes a (2,2) simplex and the timelike edge. This function calls try_32_move on timelike edges drawn from a randomly shuffled container until it succeeds or runs out of edges. If successful, the triangulation is no longer Delaunay.

Parameters

t_manifold The simplicial manifold

Returns: The Expected (3,2) moved manifold or an Unexpected

Definition at line 129 of file Ergodic_moves_3.hpp.

References ergodic_moves::do_32_move(), and ergodic_moves::try_32_move().

Referenced by ergodic_moves::do_32_move().

◆ do_44_move()

auto ergodic_moves::do_44_move ( Manifold const & t_manifold ) -> Expected

inline

Perform a (4,4) move.

This is a bistellar flip pivoting the internal spacelike edge between the two spacelike faces. A (4,4) move flips an edge which has exactly 4 incident cells. In CDT specifically, the edge is spacelike and the 4 incident cells are a pair of (1,3) simplices and a pair of (3,1) simplices. It thus re-labels each of the 4 cells in the complex, but doesn't actually change the number of cells, vertices, or edges. This move has the effect of mixing up the simplices, thus possibly creating different potential moves in different locations.

This function calls is_44_movable() on a randomly shuffled container of edges until it succeeds or runs out of edges.

If successful, the triangulation remains Delaunay. (Other moves may change this, however.)

Parameters

t_manifold The simplicial manifold

Returns: The Expected (4,4) moved manifold or Unexpected

Todo:: Need to debug bistellar_flip_really()

Definition at line 991 of file Ergodic_moves_3.hpp.

References ergodic_moves::bistellar_flip(), ergodic_moves::do_44_move(), and ergodic_moves::find_bistellar_flip_location().

Referenced by ergodic_moves::do_44_move().

◆ do_62_move()

auto ergodic_moves::do_62_move ( Manifold & t_manifold ) -> Expected

inline

Perform a (6,2) move.

This function performs a (6,2) move on the given manifold. A (6,2) move removes a vertex which has 3 incident (3,1) simplices and 3 (1,3) simplices for a total of 6 incident simplices exactly. This converts the 3 (1,3) simplices into a single (1,3) simplex on the bottom and the 3 (3,1) simplices into a single (3,1) simplex on top. It thus removes 2 (1,3) simplices, 2 (3,1) simplices, 2 spacelike faces, 6 timelike faces, 3 spacelike edges, 2 timelike edges, and a single vertex.

This function calls is_62_movable() on a randomly shuffled container of vertices until it succeeds or runs out of vertices.

If successful, the triangulation remains Delaunay. (Other moves may change this, however.)

Parameters

t_manifold The simplicial manifold

Returns: The Expected (6,2) moved manifold or Unexpected

Definition at line 458 of file Ergodic_moves_3.hpp.

References ergodic_moves::do_62_move(), and ergodic_moves::is_62_movable().

Referenced by ergodic_moves::do_62_move().

◆ find_adjacent_31_cell()

auto ergodic_moves::find_adjacent_31_cell ( Cell_handle const & t_cell ) -> std::optional<int>

inline

Find a (2,6) move location.

This function checks to see if a (2,6) move is possible. Starting with a (1,3) simplex, it checks neighbors for a (3,1) simplex.

Parameters

t_cell The (1,3) simplex that is checked

Returns: The integer of the neighboring (3,1) simplex or nullopt

Definition at line 155 of file Ergodic_moves_3.hpp.

References ergodic_moves::find_adjacent_31_cell().

Referenced by ergodic_moves::do_26_move(), and ergodic_moves::find_adjacent_31_cell().

◆ find_bistellar_flip_location()

auto ergodic_moves::find_bistellar_flip_location	(	Delaunay const &	triangulation,
		Edge_handle const &	t_edge_candidate
	)		-> std::optional<Cell_container>

inline

Find a bistellar flip location.

This function checks to see if a bistellar flip is possible. Starting with an edge, it checks all incident cells. There must be 4 incident cells; 2 should be (3,1) simplices, 2 should be (1,3) simplices, and there should be no (2,2) simplices.

Parameters

triangulation	The simplicial manifold
t_edge_candidate	The edge to check

Returns: A container of incident cells if there are exactly 4 or nullopt

Definition at line 523 of file Ergodic_moves_3.hpp.

References ergodic_moves::find_bistellar_flip_location(), and ergodic_moves::incident_cells_from_edge().

Referenced by ergodic_moves::do_44_move(), and ergodic_moves::find_bistellar_flip_location().

◆ find_pivot_edge()

auto ergodic_moves::find_pivot_edge	(	Delaunay const &	triangulation,
		Edge_container const &	edges
	)		-> std::optional<Edge_handle>

inline

Returns: The center edge of a 4-cell complex

Definition at line 937 of file Ergodic_moves_3.hpp.

References ergodic_moves::find_pivot_edge().

Referenced by ergodic_moves::find_pivot_edge().

◆ get_incident_cells()

auto ergodic_moves::get_incident_cells	(	Delaunay const &	triangulation,
		Edge_handle const	edge
	)		-> std::optional<Cell_container>

inline

Return a container of cells incident to an edge.

Parameters

triangulation	The triangulation with the cells.
edge	The edge to find the incident cells of.

Returns: A container of cells incident to the edge or nullopt

Definition at line 540 of file Ergodic_moves_3.hpp.

References ergodic_moves::get_incident_cells().

Referenced by ergodic_moves::bistellar_flip(), and ergodic_moves::get_incident_cells().

◆ get_vertices()

auto ergodic_moves::get_vertices ( Cell_container const & cells )

inline

Return a container of all vertices in a container of cells.

Parameters

cells The cells to find the vertices of.

Returns: A container of vertices in the cells

Definition at line 960 of file Ergodic_moves_3.hpp.

References ergodic_moves::get_vertices().

Referenced by ergodic_moves::get_vertices().

◆ incident_cells_from_edge()

auto ergodic_moves::incident_cells_from_edge	(	Delaunay_t< 3 > const &	triangulation,
		Edge_handle const &	edge
	)		-> std::optional<Cell_container>

inline

Find all cells incident to the edge.

Parameters

triangulation	The Delaunay triangulation
edge	The edge

Returns: A container of cells incident to the edge or nullopt

See also: https://github.com/CGAL/cgal/blob/8430d04539179f25fb8e716f99e19d28589beeda/TDS_3/include/CGAL/Triangulation_data_structure_3.h#L2094

Definition at line 489 of file Ergodic_moves_3.hpp.

References ergodic_moves::incident_cells_from_edge().

Referenced by ergodic_moves::find_bistellar_flip_location(), and ergodic_moves::incident_cells_from_edge().

◆ is_62_movable()

auto ergodic_moves::is_62_movable	(	Manifold const &	manifold,
		Vertex_handle const &	candidate
	)		-> bool

inline

Find a (6,2) move location.

This function checks to see if a (6,2) move is possible. Starting with a vertex, it checks all incident cells. There must be 6 incident cells; 3 should be (3,1) simplices, 3 should be (1,3) simplices, and there should be no (2,2) simplices.

Parameters

manifold	The simplicial manifold
candidate	The vertex to check

Returns: True if (6,2) move is possible

Definition at line 338 of file Ergodic_moves_3.hpp.

References ergodic_moves::is_62_movable().

Referenced by ergodic_moves::do_62_move(), and ergodic_moves::is_62_movable().

◆ null_move()

auto ergodic_moves::null_move ( Manifold const & t_manifold ) -> Expected

inlinenoexcept

Perform a null move.

Parameters

t_manifold The simplicial manifold

Returns: The null-moved manifold

Definition at line 40 of file Ergodic_moves_3.hpp.

References ergodic_moves::null_move().

Referenced by ergodic_moves::null_move().

◆ try_23_move()

auto ergodic_moves::try_23_move	(	Manifold &	t_manifold,
		Cell_handle const &	to_be_moved
	)		-> bool

inline

Perform a TriangulationDataStructure_3::flip on a facet.

Parameters

t_manifold	The manifold containing the cell to flip
to_be_moved	The cell on which to try the move

Returns: True if move succeeded

See also: https://doc.cgal.org/latest/TDS_3/classTriangulationDataStructure__3.html#a2ad2941984c1eac5561665700bfd60b4

Definition at line 52 of file Ergodic_moves_3.hpp.

References ergodic_moves::try_23_move().

Referenced by ergodic_moves::do_23_move(), and ergodic_moves::try_23_move().

◆ try_32_move()

auto ergodic_moves::try_32_move	(	Manifold &	t_manifold,
		Edge_handle const &	to_be_moved
	)		-> bool

inline

Perform a TriangulationDataStructure_3::flip on an edge.

Parameters

t_manifold	The manifold containing the edge to flip
to_be_moved	The edge on which to try the move

Returns: True if move succeeded

See also: https://doc.cgal.org/latest/TDS_3/classTriangulationDataStructure__3.html#a5837d666e4198f707f862003c1ffa033

Definition at line 114 of file Ergodic_moves_3.hpp.

References ergodic_moves::try_32_move().

Referenced by ergodic_moves::do_32_move(), and ergodic_moves::try_32_move().

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ Cell_container

◆ Cell_handle

◆ Delaunay

◆ Edge_container

◆ Edge_handle

◆ Expected

◆ Manifold

◆ Vertex_container

◆ Vertex_handle

Function Documentation

◆ bistellar_flip()

◆ check_move()

◆ do_23_move()

◆ do_26_move()

◆ do_32_move()

◆ do_44_move()

◆ do_62_move()

◆ find_adjacent_31_cell()

◆ find_bistellar_flip_location()

◆ find_pivot_edge()

◆ get_incident_cells()

◆ get_vertices()

◆ incident_cells_from_edge()

◆ is_62_movable()

◆ null_move()

◆ try_23_move()

◆ try_32_move()