ConvexHull2D::ComputeConvexHull

Navigation

API > API/Runtime > API/Runtime/Core > API/Runtime/Core/Math

References

namespace ConvexHull2D  
{  
    template<typename VectorType, typename Allocator>  
    void ConvexHull2D::ComputeConvexHull  
    (  
        const TArray < VectorType, Allocator > & Points,  
        TArray < int32 , Allocator > & OutIndices  
    )  
}  
Copy full snippet

namespace ConvexHull2D {     template<typename VectorType, typename Allocator>     void ConvexHull2D::ComputeConvexHull     (         const TArray < VectorType, Allocator > & Points,         TArray < int32 , Allocator > & OutIndices     ) }

Remarks

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.