ConvexHull2.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
// Adapted from GteConvexHull2.h from GTEngine; see Private/ThirdParty/GTEngine/Mathematics/GteConvexHull2.h
 
#pragma once
 
#include "Containers/Array.h"
#include "Containers/ArrayView.h"
#include "CoreMinimal.h"
#include "IndexTypes.h"
#include "LineTypes.h"
#include "Math/UnrealMathSSE.h"
#include "Math/Vector2D.h"
#include "MathUtil.h"
#include "Misc/AssertionMacros.h"
#include "PlaneTypes.h"
#include "Polygon2.h"
#include "Templates/Function.h"
 
 
namespace UE {
namespace Geometry {
 
using namespace UE::Math;
 
 
template<typename RealType>
class TConvexHull2
{
public:
 
    GEOMETRYCORE_API bool SolveSimplePolygon(int32 NumPolygonPoints, TFunctionRef<TVector2<RealType>(int32)> GetPointFunc, bool bIsKnownCCW = false);
 
    GEOMETRYCORE_API bool Solve(int32 NumPoints, TFunctionRef<TVector2<RealType>(int32)> GetPointFunc, TFunctionRef<bool(int32)> FilterFunc = [](int32 Idx) {return true;});
 
    bool Solve(TArrayView<const TVector2<RealType>> Points, TFunctionRef<bool(int32)> FilterFunc)
    {
        return Solve(Points.Num(), [&Points](int32 Idx)
            {
                return Points[Idx];
            }, FilterFunc);
    }
 
    // default FilterFunc version of the above Solve(); workaround for clang bug https://bugs.llvm.org/show_bug.cgi?id=25333
    bool Solve(TArrayView<const TVector2<RealType>> Points)
    {
        return Solve(Points.Num(), [&Points](int32 Idx)
            {
                return Points[Idx];
            }, [](int32 Idx) {return true;});
    }
 
    bool IsSolutionAvailable() const
    {
        return Dimension == 2;
    }
 
    void Empty()
    {
        Dimension = 0;
        NumUniquePoints = 0;
        Hull.Empty();
    }
 
    inline int32 GetDimension() const
    {
        return Dimension;
    }
 
    inline int32 GetNumUniquePoints() const
    {
        return NumUniquePoints;
    }
 
    TArray<int32> const& GetPolygonIndices() const
    {
        ensure(IsSolutionAvailable());
        return Hull;
    }
 
    TLine2<RealType> GetLine(TArrayView<const TVector2<RealType>> Points) const
    {
        ensure(Dimension == 1);
        if (ensure(Hull.Num() > 1))
        {
            return TLine2<RealType>::FromPoints(Points[Hull[0]], Points[Hull[1]]);
        }
        return TLine2<RealType>(); // not enough points to compute a valid line, return default
    }
 
protected:
 
    // divide-and-conquer algorithm
    void GetHull(TFunctionRef<TVector2<RealType>(int32)> GetPointFunc, TArray<int32>& Merged, int32& IdxFirst, int32& IdxLast);
    void Merge(TFunctionRef<TVector2<RealType>(int32)> GetPointFunc, TArray<int32>& Merged, int32 j0, int32 j1, int32 j2, int32 j3, int32& i0, int32& i1);
    void GetTangent(TFunctionRef<TVector2<RealType>(int32)> GetPointFunc, TArray<int32>& Merged, int32 j0, int32 j1, int32 j2, int32 j3, int32& i0, int32& i1);
 
    int32 Dimension = 0;
    int32 NumUniquePoints = 0;
    TArray<int32> Hull;
};
 
typedef TConvexHull2<float> FConvexHull2f;
typedef TConvexHull2<double> FConvexHull2d;
 
 
 
} // end namespace UE::Geometry
} // end namespace UE