ConvexHull2D Namespace Reference

Functions
template<typename VectorType , typename Allocator >
void	ComputeConvexHull (const TArray< VectorType, Allocator > &Points, TArray< int32, Allocator > &OutIndices)
FVector::FReal	ComputeDeterminant (const FVector &A, const FVector &B, const FVector &C)
bool	ComparePoints (const FVector &A, const FVector &B)
template<typename Allocator >
void	ComputeConvexHullLegacy (const TArray< FVector, Allocator > &Points, TArray< int32, Allocator > &OutIndices)
FVector2D::FReal	ComputeDeterminant2D (const FVector2D &A, const FVector2D &B, const FVector2D &C)
template<typename Allocator >
void	ComputeConvexHullLegacy2 (const TArray< FVector2D, Allocator > &Points, TArray< int32, Allocator > &OutIndices)

Function Documentation

ComparePoints()

bool ConvexHull2D::ComparePoints ( const FVector & A, const FVector & B )

inline

Returns true if 'a' is more lower-left than 'b'.

Definition at line 104 of file ConvexHull2d.h.

ComputeConvexHull()

template<typename VectorType , typename Allocator >

void ConvexHull2D::ComputeConvexHull	(	const TArray< VectorType, Allocator > &	Points,
		TArray< int32, Allocator > &	OutIndices )

Andrew's monotone chain convex hull algorithm for 2-dimensional points. O(N log N).

Not the fastest algorithm out there, but definitely the simplest one to understand.

1 - Sort O(N log N) 2 - Scan sorted vertex from left to right to compute lower hull O(N) 3 - Scan sorted vertex from right to left to compute upper hull. O(N)

If this is slow for some reason, O(N log H) also exists where H is the number of outputted hull vertices which is normally a lot lower than N and helps reduce the overall complexity.

Definition at line 24 of file ConvexHull2d.h.

ComputeConvexHullLegacy()

template<typename Allocator >

void ConvexHull2D::ComputeConvexHullLegacy	(	const TArray< FVector, Allocator > &	Points,
		TArray< int32, Allocator > &	OutIndices )

Calculates convex hull on xy-plane of points on 'Points' and stores the indices of the resulting hull in 'OutIndices'. This code was fixed to work with duplicated vertices and precision issues.

Should be replaced by ComputeConvexHull and tested properly. Keep for backward compatibility until then.

Definition at line 136 of file ConvexHull2d.h.

ComputeConvexHullLegacy2()

template<typename Allocator >

void ConvexHull2D::ComputeConvexHullLegacy2	(	const TArray< FVector2D, Allocator > &	Points,
		TArray< int32, Allocator > &	OutIndices )

Alternate simple implementation that was found to work correctly for points that are very close together (inside the 0-1 range).

Should be replaced by ComputeConvexHull and tested properly. Keep for backward compatibility until then.

Definition at line 265 of file ConvexHull2d.h.

ComputeDeterminant()

FVector::FReal ConvexHull2D::ComputeDeterminant ( const FVector & A, const FVector & B, const FVector & C )

inline

Returns <0 if C is left of A-B

Definition at line 93 of file ConvexHull2d.h.

ComputeDeterminant2D()

FVector2D::FReal ConvexHull2D::ComputeDeterminant2D ( const FVector2D & A, const FVector2D & B, const FVector2D & C )

inline

Returns <0 if C is left of A-B

Definition at line 249 of file ConvexHull2d.h.