Computes the intersection between a set of halfspaces. More...

#include <geogram/voronoi/generic_RVD_cell.h>

Classes
class	Corner
	A Corner corresponds to a vertex seen from a triangle. More...

struct	Triangle
	Represents a vertex of this ConvexCell in dual form. More...

class	Vertex
	Represents a facet of this ConvexCell in dual form. More...

Public Types
enum	TriangleStatus { TRI_IS_FREE = 0 , TRI_IS_CONFLICT = 1 , TRI_IS_USED = 2 }
	Represents the current state of a triangle. More...

Public Member Functions
	ConvexCell (coord_index_t dim)
	ConvexCell constructor.

void	copy (const ConvexCell &rhs)
	Copies a ConvexCell.

coord_index_t	dimension () const
	Gets the dimension of this ConvexCell.

void	clear ()
	Clears this ConvexCell.

void	set_symbolic_is_surface (bool x)
	Specifies that symbolic information is relative to surfacic mesh (rather than volumetric mesh).

void	initialize_from_mesh_tetrahedron (const Mesh *mesh, index_t t, bool symbolic, const GEO::Attribute< double > &vertex_weight)
	Assigns a mesh tetrahedron to this ConvexCell.

void	initialize_from_surface_mesh (Mesh *mesh, bool symbolic)
	Copies a Mesh into a ConvexCell.

void	convert_to_mesh (Mesh *mesh, bool copy_symbolic_info=false)
	Copies a ConvexCell into a Mesh.

template<index_t DIM>
signed_index_t	clip_by_plane (const Mesh mesh, const Delaunay delaunay, index_t i, index_t j, bool exact, bool symbolic)
	Clips this ConvexCell with a plane.

index_t	max_t () const
	Gets the maximum valid triangle index plus one.

index_t	nb_t () const
	Gets the number of used triangles.

index_t	max_v () const
	Gets the maximum valid vertex index plus one.

bool	triangle_is_free (index_t t) const
	Tests whether a given triangle is free.

bool	triangle_is_valid (index_t t) const
	Tests whether a given triangle is valid.

bool	triangle_is_used (index_t t) const
	Tests whether a given triangle is used.

bool	triangle_is_conflict (index_t t) const
	Tests whether a given triangle belongs to the conflict zone.

index_t	triangle_vertex (index_t t, index_t iv) const
	Gets the index of a triangle vertex.

index_t	triangle_adjacent (index_t t, index_t e) const
	Gets the index of a triangle adjacent to another one.

void	set_triangle_vertex (index_t t, index_t iv, index_t v)
	Sets a vertex of a triangle.

void	set_triangle_adjacent (index_t t, index_t e, index_t t2)
	Sets a triangle adjacency.

index_t	find_triangle_vertex (index_t t, index_t v) const
	Finds the local index of a triangle vertex.

index_t	triangle_adjacent_index (index_t t1, index_t t2) const
	Finds the edge along which two triangles are adjacent.

signed_index_t	vertex_triangle (index_t v) const
	Gets one of the triangles incident to a vertex.

void	set_vertex_triangle (index_t v, index_t t)
	Stores in a vertex the index of one the triangles incident to it.

const GEOGen::Vertex &	triangle_dual (index_t t) const
	Gets the dual vertex that corresponds to a triangle.

GEOGen::Vertex &	triangle_dual (index_t t)
	Gets the dual vertex that corresponds to a triangle.

signed_index_t	cell_id () const
	Gets the id of this ConvexCell.

void	set_cell_id (signed_index_t i)
	Sets the id of this ConvexCell.

signed_index_t	triangle_id (index_t t) const
	Gets the id of a triangle.

void	set_triangle_id (index_t t, signed_index_t id)
	Sets the id of a triangle.

signed_index_t	vertex_id (index_t v) const
	Gets the id of a vertex.

void	set_vertex_id (index_t v, signed_index_t id)
	Sets the id of a vertex.

void	move_to_next_around_vertex (Corner &c) const
	Replaces a corner by the next corner obtained by turing around the vertex.

void	init_v_to_t ()
	Updates the cache that stores for each vertex a triangle incident to it.

index_t	create_triangle ()
	Creates a new uninitialized triangle.

index_t	create_triangle (index_t v0, index_t v1, index_t v2)
	Creates a new triangle with specified vertices.

index_t	create_triangle (index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
	Creates a new triangles with specified vertices and adjacent triangles.

void	set_triangle (index_t t, index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
	Sets the vertices and adjacent triangles of a triangle.

index_t	create_triangle (const double *p, double w, index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
	Creates a new triangles with specified vertices, adjacent triangles and geometric location at the dual vertex.

index_t	create_triangle_copy (const double *p, index_t v0, index_t v1, index_t v2, index_t t0, index_t t1, index_t t2)
	Creates a new triangles with specified vertices, adjacent triangles and geometric location at the dual vertex.

index_t	create_vertex ()
	Creates a new vertex.

template<index_t DIM>
index_t	triangulate_hole (const Delaunay *delaunay, index_t i, index_t j, bool symbolic, index_t t1, index_t t1ebord, index_t v_in)
	Triangulates the conflict zone.

template<index_t DIM>
void	get_conflict_list (const Mesh mesh, const Delaunay delaunay, index_t i, index_t j, bool exact, index_t &conflict_begin, index_t &conflict_end)
	Determines the conflict zone.

template<index_t DIM>
index_t	find_furthest_point_linear_scan (const Delaunay *delaunay, index_t i, index_t j) const
	Finds the index of the vertex furthest away on the negative side of a bisector.

template<index_t DIM>
void	propagate_conflict_list (const Mesh mesh, const Delaunay delaunay, index_t first_t, index_t i, index_t j, bool exact, index_t &conflict_begin, index_t &conflict_end)
	Computes the conflict list by propagation from a conflict triangle.

template<index_t DIM>
Sign	side (const Mesh mesh, const Delaunay delaunay, const GEOGen::Vertex &v, index_t i, index_t j, bool exact) const
	Tests on which side a vertex is relative to a bisector.

Sign	side_exact (const Mesh mesh, const Delaunay delaunay, const GEOGen::Vertex &v, const double pi, const double pj, coord_index_t dim, bool symbolic_is_surface=false) const
	Tests on which side a vertex is relative to a bisector using exact predicates.

bool	find_triangle_on_border (index_t conflict_begin, index_t conflict_end, index_t &t, index_t &e) const
	Gets a triangle and an edge on the internal border of the conflict zone.

index_t	next_triangle (index_t t) const
	Gets the successor of a triangle.

void	set_next_triangle (index_t t, index_t t2)
	Sets the successor of a triangle.

void	mark_as_free (index_t t)
	Specify that a triangle is free.

void	mark_as_conflict (index_t t)
	Specify that a triangle belongs to the conflict zone.

void	mark_as_used (index_t t)
	Specify that a triangle is used.

void	append_triangle_to_conflict_list (index_t t, index_t &conflict_begin, index_t &conflict_end)
	Appends a triangle to the conflict list.

void	merge_into_free_list (index_t list_begin, index_t list_end)
	Merges a list of triangles into the free list.

void	grow ()
	Allocates a new triangle.

std::ostream &	show_stats (std::ostream &os) const
	Displays the number of free,used,conflict triangles.

Static Public Member Functions
template<index_t DIM>
static double	signed_bisector_distance (const Delaunay delaunay, index_t i, index_t j, const double q)
	Evaluates the equation of a bisector at a given point.

static index_t	global_facet_id (const Mesh *mesh, index_t t, index_t lf)
	Computes a unique global facet id from a mesh tetrahedron and local facet index.

Static Public Attributes
static constexpr index_t	NO_TRIANGLE = index_t(-1)

static constexpr index_t	NO_VERTEX = index_t(-1)

static constexpr index_t	END_OF_LIST = index_t(-1)

Detailed Description

Computes the intersection between a set of halfspaces.

Note: This is an internal implementation class used by GEO::RestrictedVoronoiDiagram. It is not meant to be used directly by client code.

Definition at line 69 of file generic_RVD_cell.h.

Member Enumeration Documentation

◆ TriangleStatus

enum GEOGen::ConvexCell::TriangleStatus

Represents the current state of a triangle.

Definition at line 83 of file generic_RVD_cell.h.

Constructor & Destructor Documentation

◆ ConvexCell()

GEOGen::ConvexCell::ConvexCell ( coord_index_t dim )

inline

ConvexCell constructor.

Parameters

[in] dim dimension of the ConvexCell, e.g. 3 for 3d

Definition at line 173 of file generic_RVD_cell.h.

Member Function Documentation

◆ append_triangle_to_conflict_list()

void GEOGen::ConvexCell::append_triangle_to_conflict_list	(	index_t	t,
		index_t &	conflict_begin,
		index_t &	conflict_end
	)

inline

Appends a triangle to the conflict list.

The triangle is marked as conflict and linked to the conflict list.

Parameters

[in]	t	the triangle
[in,out]	conflict_begin	first triangle in the conflict list
[in,out]	conflict_end	one position past the last triangle in the conflict list

Definition at line 1306 of file generic_RVD_cell.h.

◆ cell_id()

signed_index_t GEOGen::ConvexCell::cell_id ( ) const

inline

Gets the id of this ConvexCell.

The id can be used to maintain the correspondence with a tetrahedron in the Mesh.

Returns: the id of this ConvexCell. Can be a negative number.

Definition at line 575 of file generic_RVD_cell.h.

◆ clear()

void GEOGen::ConvexCell::clear ( )

inline

Clears this ConvexCell.

Definition at line 201 of file generic_RVD_cell.h.

◆ clip_by_plane()

template<index_t DIM>

signed_index_t GEOGen::ConvexCell::clip_by_plane	(	const Mesh *	mesh,
		const Delaunay *	delaunay,
		index_t	i,
		index_t	j,
		bool	exact,
		bool	symbolic
	)

inline

Clips this ConvexCell with a plane.

The plane is specified as a bisector in a Delaunay triangulation.

Parameters

[in]	mesh	input mesh, used by exact predicates
[in]	delaunay	the Delaunay triangulation
[in]	i	index of the first extremity of the bisector
[in]	j	index of the second extremity of the bisector
[in]	exact	if true, uses exact predicates (implies symbolic)
[in]	symbolic	if true, computes symbolic information

Returns: the index of the newly created vertex that corresponds to the dual of the new face or -1 if the input cell was completely on the negative side (removed everything)

Template Parameters

DIM	dimension (specified as a template parameter for efficiency reasons).

Precondition: DIM == dimension()

Definition at line 282 of file generic_RVD_cell.h.

◆ convert_to_mesh()

void GEOGen::ConvexCell::convert_to_mesh	(	Mesh *	mesh,
		bool	copy_symbolic_info = `false`
	)

Copies a ConvexCell into a Mesh.

On exit, the output mesh is a surfacic mesh with the boundary of the convex cell.

Parameters

[out]	mesh	a pointer to the target mesh
[in]	copy_symbolic_info	if true, symbolic information is copied. An attribute "id" is attached to the facets. The value of id[f] is either 1 + the index of the Voronoi vertex that generated with `i` the bisector that created the facet, or -1-g if the facet was an original facet of mesh `mesh`, where g is the index of the original facet in `mesh`.

◆ copy()

void GEOGen::ConvexCell::copy ( const ConvexCell & rhs )

Copies a ConvexCell.

The allocated vertices are shared with rhs, thus rhs should not be deleted before this ConvexCell.

Parameters

[in] rhs a const reference to the ConvexCell to be copied.

◆ create_triangle() [1/4]

index_t GEOGen::ConvexCell::create_triangle ( )

inline

Creates a new uninitialized triangle.

The created triangle is marked as used.

Returns: The index of the new triangle.

Definition at line 720 of file generic_RVD_cell.h.

◆ create_triangle() [2/4]

index_t GEOGen::ConvexCell::create_triangle	(	const double *	p,
		double	w,
		index_t	v0,
		index_t	v1,
		index_t	v2,
		index_t	t0,
		index_t	t1,
		index_t	t2
	)

inline

Creates a new triangles with specified vertices, adjacent triangles and geometric location at the dual vertex.

The vertex is shared with caller. The created triangle is marked as used.

Parameters

[in]	p	geometric location at the dual vertex, shared with caller. Caller remains responsible for memory management.
[in]	w	the weight associated with point `p`
[in]	v0	index of first vertex
[in]	v1	index of second vertex
[in]	v2	index of third vertex
[in]	t0	index of adjacent triangle opposite to `v0`
[in]	t1	index of adjacent triangle opposite to `v1`
[in]	t2	index of adjacent triangle opposite to `v2`

Returns: the index of the new triangle

Definition at line 816 of file generic_RVD_cell.h.

◆ create_triangle() [3/4]

index_t GEOGen::ConvexCell::create_triangle	(	index_t	v0,
		index_t	v1,
		index_t	v2
	)

inline

Creates a new triangle with specified vertices.

The created triangle is marked as used. Adjacent triangles are left uninitialized.

Parameters

[in]	v0	index of first vertex
[in]	v1	index of second vertex
[in]	v2	index of third vertex

Returns: the index of the new triangle

Definition at line 740 of file generic_RVD_cell.h.

◆ create_triangle() [4/4]

index_t GEOGen::ConvexCell::create_triangle	(	index_t	v0,
		index_t	v1,
		index_t	v2,
		index_t	t0,
		index_t	t1,
		index_t	t2
	)

inline

Creates a new triangles with specified vertices and adjacent triangles.

The created triangle is marked as used.

Parameters

[in]	v0	index of first vertex
[in]	v1	index of second vertex
[in]	v2	index of third vertex
[in]	t0	index of adjacent triangle opposite to `v0`
[in]	t1	index of adjacent triangle opposite to `v1`
[in]	t2	index of adjacent triangle opposite to `v2`

Returns: the index of the new triangle

Definition at line 760 of file generic_RVD_cell.h.

◆ create_triangle_copy()

index_t GEOGen::ConvexCell::create_triangle_copy	(	const double *	p,
		index_t	v0,
		index_t	v1,
		index_t	v2,
		index_t	t0,
		index_t	t1,
		index_t	t2
	)

inline

Creates a new triangles with specified vertices, adjacent triangles and geometric location at the dual vertex.

The vertex is copied into local storage. The created triangle is marked as used.

Parameters

[in]	p	geometric location at the dual vertex. Vertex is copied into local storage.
[in]	v0	index of first vertex
[in]	v1	index of second vertex
[in]	v2	index of third vertex
[in]	t0	index of adjacent triangle opposite to `v0`
[in]	t1	index of adjacent triangle opposite to `v1`
[in]	t2	index of adjacent triangle opposite to `v2`

Returns: the index of the new triangle

Definition at line 844 of file generic_RVD_cell.h.

◆ create_vertex()

index_t GEOGen::ConvexCell::create_vertex ( )

inline

Creates a new vertex.

Returns: the index of the new vertex

Definition at line 862 of file generic_RVD_cell.h.

◆ dimension()

coord_index_t GEOGen::ConvexCell::dimension ( ) const

inline

Gets the dimension of this ConvexCell.

Returns: the dimension of this ConvexCell, e.g. 3 for 3d

Definition at line 194 of file generic_RVD_cell.h.

◆ find_furthest_point_linear_scan()

template<index_t DIM>

index_t GEOGen::ConvexCell::find_furthest_point_linear_scan	(	const Delaunay *	delaunay,
		index_t	i,
		index_t	j
	)		const

inline

Finds the index of the vertex furthest away on the negative side of a bisector.

Parameters

[in]	delaunay	the Delaunay triangulation
[in]	i	index of the first extremity of the bisector in `delaunay`
[in]	j	index of the second extremity of the bisector in `delaunay`

Returns: the index of the vertex furthest away on j's side, or -1 if all the vertices are on i's side.

Definition at line 1044 of file generic_RVD_cell.h.

◆ find_triangle_on_border()

bool GEOGen::ConvexCell::find_triangle_on_border	(	index_t	conflict_begin,
		index_t	conflict_end,
		index_t &	t,
		index_t &	e
	)		const

inline

Gets a triangle and an edge on the internal border of the conflict zone.

The returned triangle touches the conflict zone from inside.

Parameters

[in]	conflict_begin	first triangle of the conflict zone
[in]	conflict_end	one element past the last triangle of the conflict zone
[out]	t	a triangle in the conflict zone adjacent to the border of the conflict zone.
[out]	e	the edge along which `t` is adjacent to the border of the conflict zone.

Returns: true if a triangle on the border was found, false otherwise.

Definition at line 1226 of file generic_RVD_cell.h.

◆ find_triangle_vertex()

index_t GEOGen::ConvexCell::find_triangle_vertex	(	index_t	t,
		index_t	v
	)		const

inline

Finds the local index of a triangle vertex.

Parameters

[in]	t	the triangle
[in]	v	global vertex index

Returns: local vertex index (0,1 or 2) of v in t

Precondition: t is incident to v

Definition at line 469 of file generic_RVD_cell.h.

◆ get_conflict_list()

template<index_t DIM>

void GEOGen::ConvexCell::get_conflict_list	(	const Mesh *	mesh,
		const Delaunay *	delaunay,
		index_t	i,
		index_t	j,
		bool	exact,
		index_t &	conflict_begin,
		index_t &	conflict_end
	)

inline

Determines the conflict zone.

The conflict zone corresponds to the set of triangles that have their dual vertices on the negative side of a bisector.

Parameters

[in]	mesh	the input mesh
[in]	delaunay	the Delaunay triangulation
[in]	i	index of the first extremity of the bisector in `delaunay`
[in]	j	index of the second extremity of the bisector in `delaunay`
[in]	exact	if true, exact predicates are used
[out]	conflict_begin	index of the first triangle in conflict list
[out]	conflict_end	one position past index of the last triangle in conflict list

Definition at line 980 of file generic_RVD_cell.h.

◆ global_facet_id()

static index_t GEOGen::ConvexCell::global_facet_id	(	const Mesh *	mesh,
		index_t	t,
		index_t	lf
	)

inlinestatic

Computes a unique global facet id from a mesh tetrahedron and local facet index.

If a facet is shared by two tetrahedra t1 and t2, its global index determined from t1 and from t2 is the same.

Parameters

[in]	mesh	the mesh
[in]	t	the index of the tetrahedron
[in]	lf	the local facet index (0,1,2 or 3) in tetrahedron `t`

Returns: an index that uniquely identifies the facet in the tetrahedron

Definition at line 1367 of file generic_RVD_cell.h.

◆ grow()

void GEOGen::ConvexCell::grow ( )

inline

Allocates a new triangle.

This function is called whenever a triangle needs to be created and the free list is empty.

Definition at line 1344 of file generic_RVD_cell.h.

◆ init_v_to_t()

void GEOGen::ConvexCell::init_v_to_t ( )

inline

Updates the cache that stores for each vertex a triangle incident to it.

Definition at line 701 of file generic_RVD_cell.h.

◆ initialize_from_mesh_tetrahedron()

void GEOGen::ConvexCell::initialize_from_mesh_tetrahedron	(	const Mesh *	mesh,
		index_t	t,
		bool	symbolic,
		const GEO::Attribute< double > &	vertex_weight
	)

Assigns a mesh tetrahedron to this ConvexCell.

The tetrahedron from the initial mesh is converted into the internal geometric/symbolic representation.

Parameters

[in]	mesh	the mesh from which the tetrahedron is copied
[in]	t	the index of the tetrahedron in `mesh`
[in]	symbolic	if true, symbolic information is copied
[in]	vertex_weight	if bound, an attribute that gives the weight of each vertex in `mesh`.

◆ initialize_from_surface_mesh()

void GEOGen::ConvexCell::initialize_from_surface_mesh	(	Mesh *	mesh,
		bool	symbolic
	)

Copies a Mesh into a ConvexCell.

The surface mesh in mesh represents the boundary of the ConvexCell.

Parameters

[in]	mesh	a pointer to the input Mesh
[in]	symbolic	if true, symbolic information is copied

◆ mark_as_conflict()

void GEOGen::ConvexCell::mark_as_conflict ( index_t t )

inline

Specify that a triangle belongs to the conflict zone.

Definition at line 1282 of file generic_RVD_cell.h.

◆ mark_as_free()

void GEOGen::ConvexCell::mark_as_free ( index_t t )

inline

Specify that a triangle is free.

A free triangle can be reused by subsequent triangle creations.

Definition at line 1273 of file generic_RVD_cell.h.

◆ mark_as_used()

void GEOGen::ConvexCell::mark_as_used ( index_t t )

inline

Specify that a triangle is used.

Definition at line 1291 of file generic_RVD_cell.h.

◆ max_t()

index_t GEOGen::ConvexCell::max_t ( ) const

inline

Gets the maximum valid triangle index plus one.

May be greater than nb_t() if this ConvexCell has some free (unused) triangles.

Definition at line 339 of file generic_RVD_cell.h.

◆ max_v()

index_t GEOGen::ConvexCell::max_v ( ) const

inline

Gets the maximum valid vertex index plus one.

Definition at line 359 of file generic_RVD_cell.h.

◆ merge_into_free_list()

void GEOGen::ConvexCell::merge_into_free_list	(	index_t	list_begin,
		index_t	list_end
	)

inline

Merges a list of triangles into the free list.

Parameters

[in]	list_begin	first triangle in the list to be freed
[in]	list_end	one position past the last triangle of the list to be freed

Definition at line 1324 of file generic_RVD_cell.h.

◆ move_to_next_around_vertex()

void GEOGen::ConvexCell::move_to_next_around_vertex ( Corner & c ) const

inline

Replaces a corner by the next corner obtained by turing around the vertex.

Parameters

[in,out] c the corner

Definition at line 690 of file generic_RVD_cell.h.

◆ nb_t()

index_t GEOGen::ConvexCell::nb_t ( ) const

inline

Gets the number of used triangles.

Definition at line 346 of file generic_RVD_cell.h.

◆ next_triangle()

index_t GEOGen::ConvexCell::next_triangle ( index_t t ) const

inline

Gets the successor of a triangle.

Triangles are linked, for instance to represent the conflict zone.

Definition at line 1249 of file generic_RVD_cell.h.

◆ propagate_conflict_list()

template<index_t DIM>

void GEOGen::ConvexCell::propagate_conflict_list	(	const Mesh *	mesh,
		const Delaunay *	delaunay,
		index_t	first_t,
		index_t	i,
		index_t	j,
		bool	exact,
		index_t &	conflict_begin,
		index_t &	conflict_end
	)

inline

Computes the conflict list by propagation from a conflict triangle.

Parameters

[in]	mesh	the input mesh
[in]	delaunay	the Delaunay triangulation
[in]	first_t	a triangle in the conflict zone
[in]	i	index of the first extremity of the bisector in `delaunay`
[in]	j	index of the second extremity of the bisector in `delaunay`
[in]	exact	if true, exact predicates are used
[out]	conflict_begin	index of the first triangle in conflict list
[out]	conflict_end	one position past index of the last triangle in conflict list

Definition at line 1105 of file generic_RVD_cell.h.

◆ set_cell_id()

void GEOGen::ConvexCell::set_cell_id ( signed_index_t i )

inline

Sets the id of this ConvexCell.

The id can be used to maintain the correspondence with a tetrahedron in the Mesh.

Parameters

[in] i the id of this ConvexCell. Can be a negative number.

Definition at line 586 of file generic_RVD_cell.h.

◆ set_next_triangle()

void GEOGen::ConvexCell::set_next_triangle	(	index_t	t,
		index_t	t2
	)

inline

Sets the successor of a triangle.

Triangles are linked, for instance to represent the conflict zone.

Parameters

[in]	t	index of the triangle
[in]	t2	index of the successor

Definition at line 1262 of file generic_RVD_cell.h.

◆ set_symbolic_is_surface()

void GEOGen::ConvexCell::set_symbolic_is_surface ( bool x )

inline

Specifies that symbolic information is relative to surfacic mesh (rather than volumetric mesh).

Affects the behavior of side_exact().

Parameters

[in] x true if symbolic information is relative to surfacic mesh (triangles), false if symbolic information is relative to volumetric mesh (tetrahedra).

Definition at line 217 of file generic_RVD_cell.h.

◆ set_triangle()

void GEOGen::ConvexCell::set_triangle	(	index_t	t,
		index_t	v0,
		index_t	v1,
		index_t	v2,
		index_t	t0,
		index_t	t1,
		index_t	t2
	)

inline

Sets the vertices and adjacent triangles of a triangle.

Parameters

[in]	t	index of the triangle
[in]	v0	index of first vertex
[in]	v1	index of second vertex
[in]	v2	index of third vertex
[in]	t0	index of adjacent triangle opposite to `v0`
[in]	t1	index of adjacent triangle opposite to `v1`
[in]	t2	index of adjacent triangle opposite to `v2`

Definition at line 784 of file generic_RVD_cell.h.

◆ set_triangle_adjacent()

void GEOGen::ConvexCell::set_triangle_adjacent	(	index_t	t,
		index_t	e,
		index_t	t2
	)

inline

Sets a triangle adjacency.

Parameters

[in]	t	the triangle index
[in]	e	local edge index (0,1 or 2)
[in]	t2	global triangle index

Definition at line 452 of file generic_RVD_cell.h.

◆ set_triangle_id()

void GEOGen::ConvexCell::set_triangle_id	(	index_t	t,
		signed_index_t	id
	)

inline

Sets the id of a triangle.

Each triangle of a ConvexCell has an id, that can be used to maintain the correspondence with a vertex in the Mesh.

Definition at line 606 of file generic_RVD_cell.h.

◆ set_triangle_vertex()

void GEOGen::ConvexCell::set_triangle_vertex	(	index_t	t,
		index_t	iv,
		index_t	v
	)

inline

Sets a vertex of a triangle.

Parameters

[in]	t	the triangle index
[in]	iv	local vertex index (0,1 or 2) in `t`
[in]	v	global vertex index

Definition at line 438 of file generic_RVD_cell.h.

◆ set_vertex_id()

void GEOGen::ConvexCell::set_vertex_id	(	index_t	v,
		signed_index_t	id
	)

inline

Sets the id of a vertex.

Each vertex of a ConvexCell has an id, that can be used to maintain the correspondence with a facet in the Mesh.

Definition at line 627 of file generic_RVD_cell.h.

◆ set_vertex_triangle()

void GEOGen::ConvexCell::set_vertex_triangle	(	index_t	v,
		index_t	t
	)

inline

Stores in a vertex the index of one the triangles incident to it.

Parameters

[in]	v	index of the vertex
[in]	t	index of one of the triangles incident to `v`

Definition at line 534 of file generic_RVD_cell.h.

◆ show_stats()

std::ostream & GEOGen::ConvexCell::show_stats ( std::ostream & os ) const

Displays the number of free,used,conflict triangles.

For debugging purposes.

◆ side()

template<index_t DIM>

Sign GEOGen::ConvexCell::side	(	const Mesh *	mesh,
		const Delaunay *	delaunay,
		const GEOGen::Vertex &	v,
		index_t	i,
		index_t	j,
		bool	exact
	)		const

inline

Tests on which side a vertex is relative to a bisector.

Parameters

[in]	mesh	the input mesh
[in]	delaunay	the Delaunay triangulation
[in]	v	the query vertex
[in]	i	index of the first extremity of the bisector in `delaunay`
[in]	j	index of the second extremity of the bisector in `delaunay`
[in]	exact	if true, exact predicates are used

Returns: POSITIVE if v is on vertex i's side, NEGATIVE otherwise. ZERO is never returned since globally coherent symbolic perturbations are used in exact mode.

Template Parameters

DIM	dimension, specified as a template parameter for efficiency considerations.

Definition at line 1165 of file generic_RVD_cell.h.

◆ side_exact()

Sign GEOGen::ConvexCell::side_exact	(	const Mesh *	mesh,
		const Delaunay *	delaunay,
		const GEOGen::Vertex &	v,
		const double *	pi,
		const double *	pj,
		coord_index_t	dim,
		bool	symbolic_is_surface = `false`
	)		const

Tests on which side a vertex is relative to a bisector using exact predicates.

Parameters

[in]	mesh	the input mesh
[in]	delaunay	the Delaunay triangulation
[in]	v	the query vertex
[in]	pi	first extremity of the bisector
[in]	pj	second extremity of the bisector
[in]	dim	dimension of the points
[in]	symbolic_is_surface	if true, then symbolic information is relative to a surface mesh (facets) rather than volumetric mesh (tetrahedra).

Returns: POSITIVE if v is on vertex i's side, NEGATIVE otherwise. ZERO is never returned since globally coherent symbolic perturbations are used in exact mode.

Note: Only dimension=3 is implemented for now

◆ signed_bisector_distance()

template<index_t DIM>

static double GEOGen::ConvexCell::signed_bisector_distance	(	const Delaunay *	delaunay,
		index_t	i,
		index_t	j,
		const double *	q
	)

inlinestatic

Evaluates the equation of a bisector at a given point.

Positive side corresponds to vertex i and negative side to vertex j.

Parameters

[in]	delaunay	the Delaunay triangulation
[in]	i	index of the first extremity of the bisector in `delaunay`
[in]	j	index of the second extremity of the bisector in `delaunay`
[in]	q	the query point

Definition at line 1075 of file generic_RVD_cell.h.

◆ triangle_adjacent()

index_t GEOGen::ConvexCell::triangle_adjacent	(	index_t	t,
		index_t	e
	)		const

inline

Gets the index of a triangle adjacent to another one.

Parameters

[in]	t	the triangle index
[in]	e	local edge index (0,1 or 2) in `t`

Returns: the index of the triangle adjacent to t on edge e

Definition at line 426 of file generic_RVD_cell.h.

◆ triangle_adjacent_index()

index_t GEOGen::ConvexCell::triangle_adjacent_index	(	index_t	t1,
		index_t	t2
	)		const

inline

Finds the edge along which two triangles are adjacent.

Parameters

[in]	t1	first triangle
[in]	t2	second triangle

Returns: the local edge index (0,1 or 2) in t1 along which t2 is adjacent to t1

Precondition: t1 and t2 are adjacent

Definition at line 492 of file generic_RVD_cell.h.

◆ triangle_dual() [1/2]

GEOGen::Vertex & GEOGen::ConvexCell::triangle_dual ( index_t t )

inline

Gets the dual vertex that corresponds to a triangle.

Each triangle corresponds to a vertex of the ConvexCell (combinatorics are stored in dual form).

Parameters

[in] t index of the triangle

Returns: a reference to the GEOGen::Vertex that corresponds to the triangle, with both geometrical and combinatorial representations

Definition at line 563 of file generic_RVD_cell.h.

◆ triangle_dual() [2/2]

const GEOGen::Vertex & GEOGen::ConvexCell::triangle_dual ( index_t t ) const

inline

Gets the dual vertex that corresponds to a triangle.

Each triangle corresponds to a vertex of the ConvexCell (combinatorics are stored in dual form).

Parameters

[in] t index of the triangle

Returns: a const reference to the GEOGen::Vertex that corresponds to the triangle, with both geometrical and combinatorial representations

Definition at line 549 of file generic_RVD_cell.h.

◆ triangle_id()

signed_index_t GEOGen::ConvexCell::triangle_id ( index_t t ) const

inline

Gets the id of a triangle.

Each triangle of a ConvexCell has an id, that can be used to maintain the correspondence with a vertex in the Mesh.

Returns: The id of triangle t.

Definition at line 596 of file generic_RVD_cell.h.

◆ triangle_is_conflict()

bool GEOGen::ConvexCell::triangle_is_conflict ( index_t t ) const

inline

Tests whether a given triangle belongs to the conflict zone.

Parameters

[in] t index of the triangle

Precondition: t < max_t()

Definition at line 401 of file generic_RVD_cell.h.

◆ triangle_is_free()

bool GEOGen::ConvexCell::triangle_is_free ( index_t t ) const

inline

Tests whether a given triangle is free.

Definition at line 366 of file generic_RVD_cell.h.

◆ triangle_is_used()

bool GEOGen::ConvexCell::triangle_is_used ( index_t t ) const

inline

Tests whether a given triangle is used.

Parameters

[in] t index of the triangle

Precondition: t < max_t()

Definition at line 389 of file generic_RVD_cell.h.

◆ triangle_is_valid()

bool GEOGen::ConvexCell::triangle_is_valid ( index_t t ) const

inline

Tests whether a given triangle is valid.

A "valid" triangle is a triangle from which we can query information (vertices, adjacent triangles, embedding), therefore it is a "used" or "conflict" triangle.

Parameters

[in] t index of the triangle

Precondition: t < max_t()

Definition at line 380 of file generic_RVD_cell.h.

◆ triangle_vertex()

index_t GEOGen::ConvexCell::triangle_vertex	(	index_t	t,
		index_t	iv
	)		const

inline

Gets the index of a triangle vertex.

Parameters

[in]	t	the triangle index
[in]	iv	local vertex index (0,1 or 2) in `t`

Returns: the index of triangle's iv th vertex

Precondition: t < max_t()

Definition at line 414 of file generic_RVD_cell.h.

◆ triangulate_hole()

template<index_t DIM>

index_t GEOGen::ConvexCell::triangulate_hole	(	const Delaunay *	delaunay,
		index_t	i,
		index_t	j,
		bool	symbolic,
		index_t	t1,
		index_t	t1ebord,
		index_t	v_in
	)

inline

Triangulates the conflict zone.

Creates the triangles radiating from new_v and attached to the border of the conflict zone, indicated by t and e.

Parameters

[in]	delaunay	the Delaunay triangulation
[in]	i	index of the first extremity of the bisector in `delaunay`.
[in]	j	index of the first extremity of the bisector in `delaunay`.
[in]	symbolic	if true, symbolic representation of the vertices is generated.
[in]	t1	a triangle adjacent to the border of the conflict zone from inside.
[in]	t1ebord	the edge along which t is adjacent to the border of the conflict zone.
[in]	v_in	index of the new vertex

Returns: one of the created triangles

Definition at line 887 of file generic_RVD_cell.h.

◆ vertex_id()

signed_index_t GEOGen::ConvexCell::vertex_id ( index_t v ) const

inline

Gets the id of a vertex.

Each vertex of a ConvexCell has an id, that can be used to maintain the correspondence with a facet in the Mesh.

Definition at line 616 of file generic_RVD_cell.h.

◆ vertex_triangle()

signed_index_t GEOGen::ConvexCell::vertex_triangle ( index_t v ) const

inline

Gets one of the triangles incident to a vertex.

The information is cached and reconstructed whenever the v_to_t_dirty_ flag is positioned.

Parameters

[in] v index of the vertex

Returns: the index of a triangle incident to v

Definition at line 519 of file generic_RVD_cell.h.

Member Data Documentation

◆ END_OF_LIST

constexpr index_t GEOGen::ConvexCell::END_OF_LIST = index_t(-1)

staticconstexpr

Definition at line 78 of file generic_RVD_cell.h.

◆ NO_TRIANGLE

constexpr index_t GEOGen::ConvexCell::NO_TRIANGLE = index_t(-1)

staticconstexpr

Definition at line 76 of file generic_RVD_cell.h.

◆ NO_VERTEX

constexpr index_t GEOGen::ConvexCell::NO_VERTEX = index_t(-1)

staticconstexpr

Definition at line 77 of file generic_RVD_cell.h.

The documentation for this class was generated from the following file:

geogram/voronoi/generic_RVD_cell.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Enumeration Documentation

◆ TriangleStatus

Constructor & Destructor Documentation

◆ ConvexCell()

Member Function Documentation

◆ append_triangle_to_conflict_list()

◆ cell_id()

◆ clear()

◆ clip_by_plane()

◆ convert_to_mesh()

◆ copy()

◆ create_triangle() [1/4]

◆ create_triangle() [2/4]

◆ create_triangle() [3/4]

◆ create_triangle() [4/4]

◆ create_triangle_copy()

◆ create_vertex()

◆ dimension()

◆ find_furthest_point_linear_scan()

◆ find_triangle_on_border()

◆ find_triangle_vertex()

◆ get_conflict_list()

◆ global_facet_id()

◆ grow()

◆ init_v_to_t()

◆ initialize_from_mesh_tetrahedron()

◆ initialize_from_surface_mesh()

◆ mark_as_conflict()

◆ mark_as_free()

◆ mark_as_used()

◆ max_t()

◆ max_v()

◆ merge_into_free_list()

◆ move_to_next_around_vertex()

◆ nb_t()

◆ next_triangle()

◆ propagate_conflict_list()

◆ set_cell_id()

◆ set_next_triangle()

◆ set_symbolic_is_surface()

◆ set_triangle()

◆ set_triangle_adjacent()

◆ set_triangle_id()

◆ set_triangle_vertex()

◆ set_vertex_id()

◆ set_vertex_triangle()

◆ show_stats()

◆ side()

◆ side_exact()

◆ signed_bisector_distance()

◆ triangle_adjacent()

◆ triangle_adjacent_index()

◆ triangle_dual() [1/2]

◆ triangle_dual() [2/2]

◆ triangle_id()

◆ triangle_is_conflict()

◆ triangle_is_free()

◆ triangle_is_used()

◆ triangle_is_valid()

◆ triangle_vertex()

◆ triangulate_hole()

◆ vertex_id()

◆ vertex_triangle()

Member Data Documentation

◆ END_OF_LIST

◆ NO_TRIANGLE

◆ NO_VERTEX