#include <Delaunay2.h>

Public Types
enum class	EResult { Success , NotComputed , EmptyInput , Collinear , MissingEdges , Unknown }

enum class	EFillMode { Solid , PositiveWinding , NonZeroWinding , NegativeWinding , OddWinding }

Public Member Functions
GEOMETRYCORE_API bool	Triangulate (TArrayView< const TVector2< double > > Vertices, TArrayView< const FIndex2i > Edges=TArrayView< const FIndex2i >())

GEOMETRYCORE_API bool	Triangulate (TArrayView< const TVector2< float > > Vertices, TArrayView< const FIndex2i > Edges=TArrayView< const FIndex2i >())

template<typename RealType >
bool	Triangulate (const TPolygon2< RealType > &Polygon, TArray< FIndex3i > *TrianglesOut=nullptr)

template<typename RealType >
bool	Triangulate (const TGeneralPolygon2< RealType > &GeneralPolygon, TArray< FIndex3i > TrianglesOut=nullptr, TArray< TVector2< RealType > > VerticesOut=nullptr, bool bFallbackToGeneralizedWinding=false)

GEOMETRYCORE_API bool	ConstrainEdges (TArrayView< const TVector2< double > > Vertices, TArrayView< const FIndex2i > Edges)

GEOMETRYCORE_API bool	ConstrainEdges (TArrayView< const TVector2< float > > Vertices, TArrayView< const FIndex2i > Edges)

GEOMETRYCORE_API bool	Update (TArrayView< const TVector2< double > > Vertices, int32 FirstNewIdx)

GEOMETRYCORE_API TArray< FIndex3i >	GetTriangles () const

GEOMETRYCORE_API void	GetTrianglesAndAdjacency (TArray< FIndex3i > &Triangles, TArray< FIndex3i > &Adjacency) const

TArray< FIndex3i >	GetFilledTriangles (TArrayView< const FIndex2i > Edges, EFillMode FillMode=EFillMode::PositiveWinding)

GEOMETRYCORE_API bool	GetFilledTriangles (TArray< FIndex3i > &TrianglesOut, TArrayView< const FIndex2i > Edges, EFillMode FillMode=EFillMode::PositiveWinding) const

GEOMETRYCORE_API bool	GetFilledTrianglesGeneralizedWinding (TArray< FIndex3i > &TrianglesOut, TArrayView< const TVector2< double > > Vertices, TArrayView< const FIndex2i > Edges, EFillMode FillMode=EFillMode::PositiveWinding) const

GEOMETRYCORE_API bool	GetFilledTrianglesGeneralizedWinding (TArray< FIndex3i > &TrianglesOut, TArrayView< const TVector2< float > > Vertices, TArrayView< const FIndex2i > Edges, EFillMode FillMode=EFillMode::PositiveWinding) const

GEOMETRYCORE_API bool	GetFilledTriangles (TArray< FIndex3i > &TrianglesOut, TArrayView< const FIndex2i > BoundaryEdges, TArrayView< const FIndex2i > HoleEdges) const

bool	IsConstrained () const

GEOMETRYCORE_API bool	IsDelaunay (TArrayView< const FVector2f > Vertices, TArrayView< const FIndex2i > SkipEdges=TArrayView< const FIndex2i >()) const

GEOMETRYCORE_API bool	IsDelaunay (TArrayView< const FVector2d > Vertices, TArrayView< const FIndex2i > SkipEdges=TArrayView< const FIndex2i >()) const

GEOMETRYCORE_API bool	HasEdges (TArrayView< const FIndex2i > Edges) const

GEOMETRYCORE_API void	FixDuplicatesOnEdge (FIndex2i &Edge)

GEOMETRYCORE_API bool	HasEdge (const FIndex2i &Edge, bool bRemapDuplicates)

GEOMETRYCORE_API bool	HasDuplicates () const

GEOMETRYCORE_API int32	RemapIfDuplicate (int32 Index) const

GEOMETRYCORE_API TArray< TArray< FVector2d > >	GetVoronoiCells (TArrayView< const FVector2d > Vertices, bool bIncludeBoundary=false, FAxisAlignedBox2d ClipBounds=FAxisAlignedBox2d::Empty(), double ExpandBounds=0.0) const

GEOMETRYCORE_API TArray< TArray< FVector2f > >	GetVoronoiCells (TArrayView< const FVector2f > Vertices, bool bIncludeBoundary=false, FAxisAlignedBox2f ClipBounds=FAxisAlignedBox2f::Empty(), float ExpandBounds=0.0f) const

EResult	GetResult () const

bool	CanComputeVoronoiCells () const

Static Public Member Functions
template<typename RealType >
static TArray< TArray< TVector2< RealType > > >	ComputeVoronoiCells (TArrayView< const TVector2< RealType > > Sites, bool bIncludeBoundary=false, TAxisAlignedBox2< RealType > ClipBounds=FAxisAlignedBox2f::Empty(), RealType ExpandBounds=(RealType) 0)

Public Attributes
FRandomStream	RandomStream

bool	bKeepFastEdgeAdjacencyData = false

bool	bValidateEdges = true

bool	bAutomaticallyFixEdgesToDuplicateVertices = false

Protected Member Functions
bool	ValidateResult (TArrayView< const FIndex2i > Edges) const

Protected Attributes
TPimplPtr< FDelaunay2Connectivity >	Connectivity

bool	bIsConstrained = false

Member Enumeration Documentation

◆ EFillMode

enum class UE::Geometry::FDelaunay2::EFillMode

strong

Enumerator
Solid
PositiveWinding
NonZeroWinding
NegativeWinding
OddWinding

◆ EResult

enum class UE::Geometry::FDelaunay2::EResult

strong

Enumerator
Success
NotComputed
EmptyInput
Collinear
MissingEdges
Unknown

Member Function Documentation

◆ CanComputeVoronoiCells()

bool UE::Geometry::FDelaunay2::CanComputeVoronoiCells ( ) const

inline

Returns: Whether the triangulation result supports computing a Voronoi diagram – i.e., if it was triangulated, or a collinear input

◆ ComputeVoronoiCells()

template<typename RealType >

static TArray< TArray< TVector2< RealType > > > UE::Geometry::FDelaunay2::ComputeVoronoiCells	(	TArrayView< const TVector2< RealType > >	Sites,
		bool	bIncludeBoundary = `false`,
		TAxisAlignedBox2< RealType >	ClipBounds = `FAxisAlignedBox2f::Empty()`,
		RealType	ExpandBounds = `(RealType)0`
	)

inlinestatic

Compute Voronoi diagram cells

Parameters

Sites	Positions to use as the sites of the Voronoi diagram
bIncludeBoundary	If true, include the cells on the boundary of the diagram. These cells are conceptually infinite, but will be clipped to a bounding box.
ClipBounds	If non-empty, all Voronoi diagram cells will be clipped to this rectangle.
ExpandBounds	Amount to expand the clipping bounds beyond the Bounds argument (or the bounding box of non-boundary Voronoi cells, if Bounds was empty)

Returns: The cells of each Voronoi site, or an empty array if the Triangulation was not yet computed

◆ ConstrainEdges() [1/2]

bool UE::Geometry::FDelaunay2::ConstrainEdges	(	TArrayView< const TVector2< double > >	Vertices,
		TArrayView< const FIndex2i >	Edges
	)

Update an already-computed triangulation so the given edges are in the triangulation. Note: Assumes the edges do not intersect other constrained edges OR existing vertices in the triangulation

Returns: true if edges were successfully inserted. Note: Will not detect failure due to intersection of constrained edges unless member bValidateEdges == true.

◆ ConstrainEdges() [2/2]

bool UE::Geometry::FDelaunay2::ConstrainEdges	(	TArrayView< const TVector2< float > >	Vertices,
		TArrayView< const FIndex2i >	Edges
	)

◆ FixDuplicatesOnEdge()

void UE::Geometry::FDelaunay2::FixDuplicatesOnEdge ( FIndex2i & Edge )

◆ GetFilledTriangles() [1/3]

bool UE::Geometry::FDelaunay2::GetFilledTriangles	(	TArray< FIndex3i > &	TrianglesOut,
		TArrayView< const FIndex2i >	BoundaryEdges,
		TArrayView< const FIndex2i >	HoleEdges
	)		const

Get (by reference) the triangles that are inside the given edges, removing the outside-boundary triangles and the inside-hole triangles

Parameters

TrianglesOut	Will be filled with a subset of the triangulation that is 'inside' the given edges, as defined by the FillMode
BoundaryEdges	Constrained edges in the triangulation that define the boundary of the desired shape
HoleEdges	Constrained edges in the triangulation that define inner holes of the desired shape

Returns: true if any result was successfully computed (including an empty result). Currently only returns false if Triangulate() has not been called yet.

◆ GetFilledTriangles() [2/3]

bool UE::Geometry::FDelaunay2::GetFilledTriangles	(	TArray< FIndex3i > &	TrianglesOut,
		TArrayView< const FIndex2i >	Edges,
		EFillMode	FillMode = `EFillMode::PositiveWinding`
	)		const

Get (by reference) the triangles that are inside the given edges, removing the outer boundary triangles If a Winding-Number-based fill mode is used, assumes edges are oriented and tracks the winding number across edges

Parameters

TrianglesOut	Will be filled with a subset of the triangulation that is 'inside' the given edges, as defined by the FillMode
Edges	The array of edges that were already constrained in the triangulation (by a previous call to Triangulate or ConstrainEdges)
FillMode	Strategy to use to define which triangles to include in the output

Returns: true if the result was well defined and consistent; false otherwise. Solid fill mode always has a well defined result; Winding-number-based fills do not if the edges have open spans. Note the triangulation will still be filled by best-effort even if the function returns false.

◆ GetFilledTriangles() [3/3]

TArray< FIndex3i > UE::Geometry::FDelaunay2::GetFilledTriangles	(	TArrayView< const FIndex2i >	Edges,
		EFillMode	FillMode = `EFillMode::PositiveWinding`
	)

inline

Return the triangles that are inside the given edges, removing the outer boundary triangles If a Winding-Number-based fill mode is used, assumes edges are oriented and tracks the winding number across edges

Parameters

Edges	The array of edges that were already constrained in the triangulation (by a previous call to Triangulate or ConstrainEdges)
FillMode	Strategy to use to define which triangles to include in the output

Returns: A subset of the triangulation that is 'inside' the given edges, as defined by the FillMode

◆ GetFilledTrianglesGeneralizedWinding() [1/2]

bool UE::Geometry::FDelaunay2::GetFilledTrianglesGeneralizedWinding	(	TArray< FIndex3i > &	TrianglesOut,
		TArrayView< const TVector2< double > >	Vertices,
		TArrayView< const FIndex2i >	Edges,
		EFillMode	FillMode = `EFillMode::PositiveWinding`
	)		const

Get (by reference) the triangles that are inside the given edges, using a generalized winding number method to determine which triangles are inside Not valid for EFillMode::Solid, will fall back to the above GetFilledTriangles method in that case.

This method is for triangulations where the edges did not define a fully-closed shape, either by construction or due to un-resolved edge intersections in the input. Note that it is slower than the standard GetFilledTriangles, and is worse for closed polygons where all edges were successfully constrained.

Parameters

TrianglesOut	Will be filled with a subset of the triangulation that is 'inside' the given edges, as defined by the FillMode
Vertices	The array of vertices that were used in the triangulation (by the previous call to Triangulate)
Edges	The array of edges that were already constrained in the triangulation (by a previous call to Triangulate or ConstrainEdges)
FillMode	Strategy to use to define which triangles to include in the output

Returns: true if the result was well defined and consistent; false otherwise. Solid fill mode always has a well defined result; Winding-number-based fills do not if the edges have open spans. Note the triangulation will still be filled by best-effort even if the function returns false.

◆ GetFilledTrianglesGeneralizedWinding() [2/2]

bool UE::Geometry::FDelaunay2::GetFilledTrianglesGeneralizedWinding	(	TArray< FIndex3i > &	TrianglesOut,
		TArrayView< const TVector2< float > >	Vertices,
		TArrayView< const FIndex2i >	Edges,
		EFillMode	FillMode = `EFillMode::PositiveWinding`
	)		const

◆ GetResult()

EResult UE::Geometry::FDelaunay2::GetResult ( ) const

inline

Returns: Last triangulation result – either Success, NotComputed, or a reason for failure

◆ GetTriangles()

TArray< FIndex3i > UE::Geometry::FDelaunay2::GetTriangles ( ) const

◆ GetTrianglesAndAdjacency()

void UE::Geometry::FDelaunay2::GetTrianglesAndAdjacency	(	TArray< FIndex3i > &	Triangles,
		TArray< FIndex3i > &	Adjacency
	)		const

◆ GetVoronoiCells() [1/2]

TArray< TArray< FVector2d > > UE::Geometry::FDelaunay2::GetVoronoiCells	(	TArrayView< const FVector2d >	Vertices,
		bool	bIncludeBoundary = `false`,
		FAxisAlignedBox2d	ClipBounds = `FAxisAlignedBox2d::Empty()`,
		double	ExpandBounds = `0.0`
	)		const

Get Voronoi diagram cells as dual of the Delaunay triangulation. You must call Triangulate() before calling this.

Parameters

Vertices	Vertices of the Delaunay triangulation, to be used as the sites of the Voronoi diagram
bIncludeBoundary	If true, include the cells on the boundary of the diagram. These cells are conceptually infinite, but will be clipped to a bounding box.
ClipBounds	If non-empty, all Voronoi diagram cells will be clipped to this rectangle.
ExpandBounds	Amount to expand the clipping bounds beyond the Bounds argument (or the bounding box of non-boundary Voronoi cells, if Bounds was empty)

Returns: The cells of each Voronoi site, or an empty array if the Triangulation was not yet computed

◆ GetVoronoiCells() [2/2]

TArray< TArray< FVector2f > > UE::Geometry::FDelaunay2::GetVoronoiCells	(	TArrayView< const FVector2f >	Vertices,
		bool	bIncludeBoundary = `false`,
		FAxisAlignedBox2f	ClipBounds = `FAxisAlignedBox2f::Empty()`,
		float	ExpandBounds = `0.0f`
	)		const

◆ HasDuplicates()

bool UE::Geometry::FDelaunay2::HasDuplicates ( ) const

◆ HasEdge()

bool UE::Geometry::FDelaunay2::HasEdge	(	const FIndex2i &	Edge,
		bool	bRemapDuplicates
	)

◆ HasEdges()

bool UE::Geometry::FDelaunay2::HasEdges ( TArrayView< const FIndex2i > Edges ) const

◆ IsConstrained()

bool UE::Geometry::FDelaunay2::IsConstrained ( ) const

inline

◆ IsDelaunay() [1/2]

bool UE::Geometry::FDelaunay2::IsDelaunay	(	TArrayView< const FVector2d >	Vertices,
		TArrayView< const FIndex2i >	SkipEdges = `TArrayView<const FIndex2i>()`
	)		const

◆ IsDelaunay() [2/2]

bool UE::Geometry::FDelaunay2::IsDelaunay	(	TArrayView< const FVector2f >	Vertices,
		TArrayView< const FIndex2i >	SkipEdges = `TArrayView<const FIndex2i>()`
	)		const

◆ RemapIfDuplicate()

int32 UE::Geometry::FDelaunay2::RemapIfDuplicate ( int32 Index ) const

◆ Triangulate() [1/4]

template<typename RealType >

bool UE::Geometry::FDelaunay2::Triangulate	(	const TGeneralPolygon2< RealType > &	GeneralPolygon,
		TArray< FIndex3i > *	TrianglesOut = `nullptr`,
		TArray< TVector2< RealType > > *	VerticesOut = `nullptr`,
		bool	bFallbackToGeneralizedWinding = `false`
	)

inline

◆ Triangulate() [2/4]

template<typename RealType >

bool UE::Geometry::FDelaunay2::Triangulate	(	const TPolygon2< RealType > &	Polygon,
		TArray< FIndex3i > *	TrianglesOut = `nullptr`
	)

inline

◆ Triangulate() [3/4]

bool UE::Geometry::FDelaunay2::Triangulate	(	TArrayView< const TVector2< double > >	Vertices,
		TArrayView< const FIndex2i >	Edges = `TArrayView<const FIndex2i>()`
	)

Compute an (optionally constrained) Delaunay triangulation. Note this clears any previously-held triangulation data, and triangulates the passed-in vertices (and optional edges) from scratch

Returns: false if triangulation failed

◆ Triangulate() [4/4]

bool UE::Geometry::FDelaunay2::Triangulate	(	TArrayView< const TVector2< float > >	Vertices,
		TArrayView< const FIndex2i >	Edges = `TArrayView<const FIndex2i>()`
	)

◆ Update()

bool UE::Geometry::FDelaunay2::Update	(	TArrayView< const TVector2< double > >	Vertices,
		int32	FirstNewIdx
	)

◆ ValidateResult()

bool UE::Geometry::FDelaunay2::ValidateResult ( TArrayView< const FIndex2i > Edges ) const

inlineprotected

Member Data Documentation

◆ bAutomaticallyFixEdgesToDuplicateVertices

bool UE::Geometry::FDelaunay2::bAutomaticallyFixEdgesToDuplicateVertices = false

◆ bIsConstrained

bool UE::Geometry::FDelaunay2::bIsConstrained = false

protected

◆ bKeepFastEdgeAdjacencyData

bool UE::Geometry::FDelaunay2::bKeepFastEdgeAdjacencyData = false

◆ bValidateEdges

bool UE::Geometry::FDelaunay2::bValidateEdges = true

◆ Connectivity

TPimplPtr<FDelaunay2Connectivity> UE::Geometry::FDelaunay2::Connectivity

protected

◆ RandomStream

FRandomStream UE::Geometry::FDelaunay2::RandomStream

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

Engine/Source/Runtime/GeometryCore/Public/CompGeom/Delaunay2.h
Engine/Source/Runtime/GeometryCore/Private/CompGeom/Delaunay2.cpp

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Member Enumeration Documentation

◆ EFillMode

◆ EResult

Member Function Documentation

◆ CanComputeVoronoiCells()

◆ ComputeVoronoiCells()

◆ ConstrainEdges() [1/2]

◆ ConstrainEdges() [2/2]

◆ FixDuplicatesOnEdge()

◆ GetFilledTriangles() [1/3]

◆ GetFilledTriangles() [2/3]

◆ GetFilledTriangles() [3/3]

◆ GetFilledTrianglesGeneralizedWinding() [1/2]

◆ GetFilledTrianglesGeneralizedWinding() [2/2]

◆ GetResult()

◆ GetTriangles()

◆ GetTrianglesAndAdjacency()

◆ GetVoronoiCells() [1/2]

◆ GetVoronoiCells() [2/2]

◆ HasDuplicates()

◆ HasEdge()

◆ HasEdges()

◆ IsConstrained()

◆ IsDelaunay() [1/2]

◆ IsDelaunay() [2/2]

◆ RemapIfDuplicate()

◆ Triangulate() [1/4]

◆ Triangulate() [2/4]

◆ Triangulate() [3/4]

◆ Triangulate() [4/4]

◆ Update()

◆ ValidateResult()

Member Data Documentation

◆ bAutomaticallyFixEdgesToDuplicateVertices

◆ bIsConstrained

◆ bKeepFastEdgeAdjacencyData

◆ bValidateEdges

◆ Connectivity

◆ RandomStream