DPoint3dOps.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------------------+
|
|   Supplied under applicable software license agreement.
|
|   Copyright (c) 2018 Bentley Systems, Incorporated. All rights reserved.
|
+---------------------------------------------------------------------------------------*/
#pragma once
BEGIN_BENTLEY_GEOMETRY_NAMESPACE
// To be included from GeomApi.h !!!
template <typename T>
struct VectorOps
{
public:
static GEOMDLLIMPEXP void Copy (bvector<T> *dest, bvector<T> const *source);

static GEOMDLLIMPEXP void Copy (bvector<T> *dest, T const *source, size_t count);


static GEOMDLLIMPEXP size_t Append (bvector<T> *dest, T const *source, size_t count);


static GEOMDLLIMPEXP size_t Append (bvector<T> *dest, bvector<T> const *source);


static GEOMDLLIMPEXP size_t Size (bvector<T> *dest);


static GEOMDLLIMPEXP size_t Append (bvector<T> *dest, T const &data);


static GEOMDLLIMPEXP void AppendDisconnect (bvector<T> *dest);

static GEOMDLLIMPEXP bool Set (bvector<T> *dest, T const &data, size_t index);

static GEOMDLLIMPEXP bool Get (bvector<T> *dest, T &data, size_t index);

static GEOMDLLIMPEXP void AppendInterpolated (bvector<T> &dest, T const &first, T const &last, size_t count, bool includeFirst = true);

static GEOMDLLIMPEXP void InterpolateAll (bvector<T> &dest, bvector <T> const &dataA, double f, bvector <T> const &dataB);

static GEOMDLLIMPEXP T * MallocAndCopy (bvector<T> &source);

static GEOMDLLIMPEXP void Compress (bvector<T> &data, double tolerance);

static GEOMDLLIMPEXP void CompressCyclic (bvector<T> &data, double tolerance);

static GEOMDLLIMPEXP void Compress (bvector<T> const &source, bvector<T> &dest, double tolerance);


public:
static GEOMDLLIMPEXP void Reverse (bvector<T>& xyz);

public: static double GEOMDLLIMPEXP LargestCoordinate (bvector<T> const &data);

public: static double GEOMDLLIMPEXP LargestCoordinate (T const *data, size_t count);

public: static double GEOMDLLIMPEXP Tolerance (bvector<T> const &data, double absTol, double relTol);

public: static double GEOMDLLIMPEXP Tolerance (T const *data, size_t count, double absTol, double relTol);

public: static bool GEOMDLLIMPEXP Equal (bvector<T> const &dataA, bvector<T> const &dataB);

public: static bool GEOMDLLIMPEXP Equal (T const *dataA, size_t countA, T const *dataB, size_t countB);

public: static bool GEOMDLLIMPEXP FindNotAlmostEqualAtOrAfter (bvector<T>const &data, T const &baseValue, size_t i0, size_t &i1, T &value);
public: static bool GEOMDLLIMPEXP FindNotAlmostEqualBefore (bvector<T>const &data, T const &baseValue, size_t i0, size_t &i1, T &value);

public: static bool GEOMDLLIMPEXP AlmostEqual (T const &valueA, T const &valueB);



public: static bool GEOMDLLIMPEXP AlmostEqual (T const &valueA, T const &valueB, double tolerance);

public: static bool GEOMDLLIMPEXP AlmostEqual
(
T const *valueA,
size_t numA,
T const *valueB,
size_t numB,
double tolerance);


public: static size_t GEOMDLLIMPEXP MostDistantIndex (bvector<T>const &data, T const &baseValue);
public: static size_t GEOMDLLIMPEXP MostDistantIndex (T const *data, size_t n, T const &baseValue);

};

struct DPoint2dOps : VectorOps <DPoint2d>
{
private: DPoint2dOps (){};
public:


static GEOMDLLIMPEXP void AppendXY (bvector<DPoint2d> *dest, double x, double y);

static GEOMDLLIMPEXP void AppendXY (bvector<DPoint2d> &dest, bvector<DPoint3d> const &source);

public:
static GEOMDLLIMPEXP size_t Cluster
(
bvector<DPoint2d> const &xyzIn,
bvector<DPoint2d> *xyzOut,
bvector<size_t>&oldIndexToPackedIndex,
double absTol = -1.0,
double relTol = -1.0
);

public:
static GEOMDLLIMPEXP void Multiply
(
bvector<DPoint2d> *xyz,
TransformCR transform
);

public:
static bool LexicalXExtrema (int &iMin, int &iMax, DPoint2dCP points, int nPoint);
public:
static bool LexicalYExtrema (int &iMin, int &iMax, DPoint2dCP points, int nPoint);
};

struct DVec3dOps : VectorOps <DVec3d>
{
private: DVec3dOps (){};
public:


static GEOMDLLIMPEXP void AppendXYZ (bvector<DVec3d> *dest, double x, double y, double z = 0.0);


public:
static GEOMDLLIMPEXP size_t Cluster
(
bvector<DVec3d> const &xyzIn,
bvector<DVec3d> *xyzOut,
bvector<size_t>&oldIndexToPackedIndex,
double absTol = -1.0,
double relTol = -1.0
);

public: static bool GEOMDLLIMPEXP MinMaxAngle (bvector<DVec3d> const &dataA, bvector<DVec3d> const &dataB,
            double &minAngle, size_t &minIndex,
            double &maxAngle, size_t &maxIndex
            );
};
struct DVec2dOps : VectorOps <DVec2d>
{
private: DVec2dOps (){};
public:


static GEOMDLLIMPEXP void AppendXY (bvector<DVec2d> *dest, double x, double y);
};
struct DoubleOps : VectorOps <double>
{
public:

private: DoubleOps ();
public:
static GEOMDLLIMPEXP double Min (double a1, double a2);
static GEOMDLLIMPEXP double Min (double a1, double a2, double a3);
static GEOMDLLIMPEXP double Min (double a1, double a2, double a3, double a4);

static GEOMDLLIMPEXP double MinAbs (double a1, double a2);
static GEOMDLLIMPEXP double MinAbs (double a1, double a2, double a3);
static GEOMDLLIMPEXP double MinAbs (double a1, double a2, double a3, double a4);


static GEOMDLLIMPEXP double Max (double a1, double a2);
static GEOMDLLIMPEXP double Max (double a1, double a2, double a3);
static GEOMDLLIMPEXP double Max (double a1, double a2, double a3, double a4);

static GEOMDLLIMPEXP double MaxAbs (double a1, double a2);
static GEOMDLLIMPEXP double MaxAbs (double a1, double a2, double a3);
static GEOMDLLIMPEXP double MaxAbs (double a1, double a2, double a3, double a4);

static GEOMDLLIMPEXP double MaxAbs (double a1, double a2, double a3, double a4, double a5, double a6);

static GEOMDLLIMPEXP void UpdateMax (double &evolvingMax, double testValue);

static GEOMDLLIMPEXP bool WithinTolerance (double a1, double a2, double abstol);

static GEOMDLLIMPEXP double SnapZero (double a, double abstol);

static GEOMDLLIMPEXP int TolerancedSign (double a, double abstol);

static GEOMDLLIMPEXP bool WithinTolerance (double a1, double a2, double abstol, double reltol);
static GEOMDLLIMPEXP double ComputeTolerance (double maxSize, double abstol, double reltol);

static GEOMDLLIMPEXP double Max (bvector <double> &values);
static GEOMDLLIMPEXP double Min (bvector <double> &values);
static GEOMDLLIMPEXP double MaxAbs (bvector <double> &values);
static GEOMDLLIMPEXP double MinAbs (bvector <double> &values);

static GEOMDLLIMPEXP double Max (double const *values, size_t n);
static GEOMDLLIMPEXP double Min (double const *values, size_t n);
static GEOMDLLIMPEXP double MaxAbs (double const *values, size_t n);
static GEOMDLLIMPEXP double MinAbs (double const *values, size_t n);

static GEOMDLLIMPEXP void ScaleArray (double *values, size_t n, double a);
static GEOMDLLIMPEXP void ScaleArray (bvector <double> &values, double a);
static GEOMDLLIMPEXP double ClampFraction (double s);

static GEOMDLLIMPEXP void ClampDirectedFractionInterval (double &t0, double &t1);

static GEOMDLLIMPEXP double Clamp (double x, double a, double b);
static GEOMDLLIMPEXP bool IsExact01 (double a0, double a1);

static GEOMDLLIMPEXP bool IsIn01 (double x);
static GEOMDLLIMPEXP bool IsAlmostIn01 (double x);

static GEOMDLLIMPEXP bool IsIn01OrExtension (double x, bool extend0, bool extend1);

static GEOMDLLIMPEXP bool IsIn01 (double x, double y);

static GEOMDLLIMPEXP bool IsIn01 (DPoint2dCR xy);

static GEOMDLLIMPEXP bool IsIn01 (DPoint3dCR xyz);

static GEOMDLLIMPEXP double Hypotenuse (double a, double b);
static GEOMDLLIMPEXP double Hypotenuse (double a, double b, double c);
static GEOMDLLIMPEXP double Hypotenuse (double a, double b, double c, double d);

static GEOMDLLIMPEXP double DeterminantXYXY (double x0, double y0, double x1, double y1);
static GEOMDLLIMPEXP bool SafeDivideParameter (double &result, double numerator, double denominator, double defaultResult = 0.0);

static GEOMDLLIMPEXP bool ChooseSafeDivideParameter
(
double &result,
double numerator0,
double denominator0,
double numerator1,
double denominator1,
double defaultResult = 0.0
);


static GEOMDLLIMPEXP ValidatedDouble ValidatedDivideDistance(double a, double b, double defaultResult = 0.0);

static GEOMDLLIMPEXP ValidatedDouble ValidatedDivideDistanceSquared (double a, double b, double defaultResult = 0.0);


static GEOMDLLIMPEXP ValidatedDVec2d ValidatedDivideAndDifferentiate
(
double f,   
double df,  
double g,   
double dg   
);


static GEOMDLLIMPEXP ValidatedDouble ValidatedDivideParameter (double a, double b, double defaultResult = 0.0);

static GEOMDLLIMPEXP ValidatedDouble ValidatedDivide (double a, double b, double defaultResult = 0.0, double minRelativeDivisor = 1.0e-15);



static GEOMDLLIMPEXP bool SafeDivideDistanceSquared (double &result, double numerator, double denominator, double defaultResult = 0.0);

static GEOMDLLIMPEXP bool SafeDivide (double &result, double numerator, double denominator, double defaultResult = 0.0, double smallFraction = 1.0e-15);

static GEOMDLLIMPEXP bool LinearTransform (double a0, double a1, double b0, double b1, double &c, double &d);
static GEOMDLLIMPEXP bool UpperBound (double const *pData, size_t n, double searchValue, size_t &index);
static GEOMDLLIMPEXP bool LowerBound (double const *pData, size_t n, double searchValue, size_t &index);
static GEOMDLLIMPEXP bool BoundingValues (double const *pData, size_t n, double searchValue, size_t &lowerIndex, double &lowerBound, double &upperBound);
static GEOMDLLIMPEXP bool BoundingValues (bvector<double>const &data, double searchValue,  size_t &lowerIndex, double &lowerBound, double &upperBound);
static GEOMDLLIMPEXP bool BoundingValues (size_t n, double searchValue, size_t &lowerIndex, double &lowerBound, double &upperBound);
static GEOMDLLIMPEXP void Sort (double *data, size_t count, bool ascending = true);
static GEOMDLLIMPEXP void Sort (bvector<double> &data, bool ascending = true);
static GEOMDLLIMPEXP void SortTail (bvector<double> &data, size_t i0, bool ascending = true);

static GEOMDLLIMPEXP double Interpolate (double dataA, double fraction, double dataB);
static GEOMDLLIMPEXP ValidatedDouble InverseInterpolate (double dataA, double value, double dataB);
static GEOMDLLIMPEXP void Swap (double &dataA, double &dataB);

static GEOMDLLIMPEXP void UpdateMinMax (double x, double f, double &xMin, double &fMin, double &xMax, double &fMax);

static GEOMDLLIMPEXP double Magnitude (double a, double b, double c);
static GEOMDLLIMPEXP double Magnitude (double a, double b);
static GEOMDLLIMPEXP bool AlmostEqualFraction (double a, double b);

static GEOMDLLIMPEXP int TolerancedComparison (double a, double b);

static GEOMDLLIMPEXP bool ClearlyIncreasingFraction (double a, double b);

static GEOMDLLIMPEXP bool ClearlyIncreasing (double a, double b, double tol);

static GEOMDLLIMPEXP double Sum (double *data, int n);
static GEOMDLLIMPEXP double Sum (bvector<double> const &data);
static GEOMDLLIMPEXP double SumAbs (double *data, int n);
static GEOMDLLIMPEXP double SumAbs (bvector<double> const &data);

static GEOMDLLIMPEXP double PreciseSum (double *data, size_t n);
static GEOMDLLIMPEXP double PreciseSum (double a, double b, double c);

static GEOMDLLIMPEXP bool Normalize (bvector<double> &data, double a0, double a1);

static GEOMDLLIMPEXP void CopyToIndex (bvector<double> const &source, bvector<size_t> const &index, bvector<double> &dest);
static GEOMDLLIMPEXP void CopyFromIndex (bvector<double> const &source, bvector<size_t> const &index, bvector<double> &dest);
static GEOMDLLIMPEXP void SetZeros (bvector<double> &dest);
static GEOMDLLIMPEXP void SetSequential (bvector<double> &dest, double a0 = 0.0, double delta = 1.0);
static GEOMDLLIMPEXP double MaxAbsDiff (bvector<double> const &x, bvector<double> const &y);
static GEOMDLLIMPEXP void ApplyFunction (bvector<double> const &x, double (*f)(double), bvector <double> &fOfx);

static GEOMDLLIMPEXP void MovingAverages
(
bvector<double> &dest,              
bvector<double> const &source,      
size_t blockSize,                   
size_t numSkip0 = 0,                    
size_t numSkip1 = 0                     
);

static GEOMDLLIMPEXP void MovingAverages
(
bvector<double> &dest,   
double value0,          
double value1,          
size_t numOut,          
size_t blockSize,       
size_t numCopy0 = 1,    
size_t numCopy1 = 1     
);

static GEOMDLLIMPEXP void ChebyshevPoints
(
    bvector<double> &dest,   
    size_t numChebyshev,          
    bool addLimitPoints,      
    size_t numCopyLeft = 1,     
    size_t numCopyRight = 1     
    );
static GEOMDLLIMPEXP void LinearMapInPlace (bvector<double> &data, double a, double b);
static GEOMDLLIMPEXP void MinusOnePlus1LinearMapInPlace (bvector<double> &data, double aMinus, double aPlus);
static GEOMDLLIMPEXP void LinearMapFrontBackToInterval(bvector<double> &data, double a0, double a1);

static GEOMDLLIMPEXP double ChebyshevPoint (size_t i, size_t n);
public: static GEOMDLLIMPEXP double SmallCoordinateRelTol ();
};


struct DPoint3dOps : VectorOps <DPoint3d>
{
private:
    DPoint3dOps (); // No instances.
public:


static GEOMDLLIMPEXP void AppendXYZ (bvector<DPoint3d> *dest, double x, double y, double z = 0.0);

static GEOMDLLIMPEXP void AppendXY0 (bvector<DPoint3d> &dest, bvector<DPoint2d> const &source);

public:
static GEOMDLLIMPEXP size_t Cluster
(
bvector<DPoint3d> const &xyzIn,
bvector<DPoint3d> *xyzOut,
bvector<size_t>&oldIndexToPackedIndex,
double absTol = -1.0,
double relTol = -1.0
);



public:
static GEOMDLLIMPEXP void Multiply
(
bvector<DPoint3d> *xyz,
TransformCR transform
);


public: static bool GEOMDLLIMPEXP MinMaxDistance (bvector<DPoint3d> const &xyzA, bvector<DPoint3d> const &xyzB,
            double &minDistance, size_t &minIndex,
            double &maxDistance, size_t &maxIndex
            );


public: static bool GEOMDLLIMPEXP ClosestPoint (bvector<DPoint3d> const &xyz, DPoint3dCR spacePoint, size_t &closestIndex, double &minDist);

public: static bool GEOMDLLIMPEXP MaxDistanceFromUnboundedRay (bvector<DPoint3d> const &xyz, DRay3dCR ray, size_t &index, double &maxDistance);



public: static bool GEOMDLLIMPEXP ClosestPointXY (bvector<DPoint3d> const &xyz, DMatrix4dCP worldToLocal, DPoint3dCR spacePoint, size_t &closestIndex, double &minDist);


public:
static GEOMDLLIMPEXP DRange3d Range (bvector<DPoint3d> const *pXYZIn);

public:
static GEOMDLLIMPEXP DRange3d Range (bvector<DPoint3d> const *pXYZIn, TransformCR worldToLocal);

public: static GEOMDLLIMPEXP DRange1d ProjectedParameterRange (bvector <DPoint3d> const &points, DRay3dCR ray);


static GEOMDLLIMPEXP double LargestXYCoordinate (DPoint3dCP points, size_t n);

static GEOMDLLIMPEXP size_t CountDisconnects (bvector<DPoint3d> &points);


static GEOMDLLIMPEXP bool PrincipalAxes (bvector<DPoint3d> const &points, DVec3dR centroid, RotMatrixR axes, DVec3dR moments);

static GEOMDLLIMPEXP bool PrincipalAxes (bvector<DPoint3d> const &points, TransformR localToWorld, TransformR worldToLocal, DVec3dR moments);

static GEOMDLLIMPEXP bool PrincipalAxes (
        bvector<DPoint3d> const &pointsA,
        bvector<DPoint3d> const &pointsB,
        TransformR localToWorld, TransformR worldToLocal, DVec3dR moments);

static GEOMDLLIMPEXP bool PrincipalAxes (bvector<DPoint4d> const &points, DVec3dR centroid, RotMatrixR axes, DVec3dR moments);


static GEOMDLLIMPEXP bool PrincipalAxes (bvector<DPoint3d> const &pointsA, bvector<DPoint3d> const &pointsB, DVec3dR centroid, RotMatrixR axes, DVec3dR moments);

static GEOMDLLIMPEXP bool    PrincipalExtents (bvector<DPoint3d> const &points, TransformR originWithExtentVectors);


static GEOMDLLIMPEXP bool    PrincipalExtents (bvector<DPoint3d> const &points, TransformR originWithExtentVectors, TransformR localToWorld, TransformR worldToLocal);




static GEOMDLLIMPEXP DMatrix4d MomentSums (DPoint3dCR origin, bvector<DPoint3d> const &points);

};
struct PolylineOps
{
private:
    PolylineOps (); // No instances.

public: static GEOMDLLIMPEXP void SetPolylinePolylineHeapTrigger (size_t mn);

public: static GEOMDLLIMPEXP double SegmentFractionToPolylineFraction (size_t segmentIndex, size_t numSegment, double segmentFraction);

public: static GEOMDLLIMPEXP bool PolylineFractionToSegmentData
(
size_t numVertex,
double fraction,
size_t &segmentIndex,
size_t &numSegment,
double &segmentFraction,
bool &isExtrapolated
);

public: static GEOMDLLIMPEXP bool PolylineFractionsOnSameSegment
(
double f0,
double f1,
size_t numVertex
);

public: static GEOMDLLIMPEXP double Length (bvector<DPoint3d> const &xyz, bool addClosure = false);
public: static GEOMDLLIMPEXP double Length (bvector< bvector<DPoint3d> > const &xyz, bool addClosure = false);
public: static GEOMDLLIMPEXP double Length (RotMatrixCP worldToLocal, bvector<DPoint3d> const &xyz, bool addClosure = false);

public: static GEOMDLLIMPEXP UsageSums SumSegmentLengths (bvector<DPoint3d> const &xyz);

public: static GEOMDLLIMPEXP double Length (DPoint3dCP xyz, double const *weight, ptrdiff_t step, size_t n, bool addClosure = false);



// return  the total of (absolute) angles at vertices of polyline with step index.  Optionally add closure edge.   Weights optional.
public: static GEOMDLLIMPEXP double SumAbsoluteAngles (DPoint3dCP xyz, double const *weight, ptrdiff_t step, size_t count, bool addClosure, double minEdgeLength = 0.0);

public: static GEOMDLLIMPEXP bool ClosestPoint
        (
        bvector<DPoint3d> const &xyz,
        bool addClosurePoint,
        DPoint3dCR spacePoint,
        double &fraction,
        DPoint3dR curvePoint
        );

public: static GEOMDLLIMPEXP bool ClosestPoint
        (
        bvector<DPoint3d> const &xyz,
        bool addClosurePoint,
        DPoint3dCR spacePoint,
        double &fraction,
        DPoint3dR curvePoint,
        size_t &edgeIndex,
        size_t &numEdge,
        double &edgeFraction,
        bool extend0,
        bool extend1
        );

public: static GEOMDLLIMPEXP bool ClosestPointXY
        (
        bvector<DPoint3d> const &xyz,
        bool addClosurePoint,
        DPoint3dCR spacePoint,
        DMatrix4dCP worldToLocal,
        double &globalFraction,
        DPoint3dR curvePoint,
        size_t &edgeIndex,
        size_t &numEdge,
        double &edgeFraction,
        double &xyDistance
        );

public: static GEOMDLLIMPEXP bool ClosestPointXY
        (
        bvector<DPoint3d> const &xyz,
        bool addClosurePoint,
        DPoint3dCR spacePoint,
        DMatrix4dCP worldToLocal,
        double &globalFraction,
        DPoint3dR curvePoint,
        size_t &edgeIndex,
        size_t &numEdge,
        double &edgeFraction,
        double &xyDistance,
        bool extend0,
        bool extend1
        );


public: static bool GEOMDLLIMPEXP AddCloseApproaches
(
bvector<DPoint3d> const &xyzA,
bvector<DPoint3d> const &xyzB,
bvector< CurveLocationDetail> &locationA,
bvector< CurveLocationDetail> &locationB,
double maxDistance = DBL_MAX
);

public: static bool GEOMDLLIMPEXP AddCloseApproaches
(
bvector<DPoint3d> const &xyzA,
bvector<double> const *paramA,
bvector<DPoint3d> const &xyzB,
bvector<double> const *paramB,
bvector< CurveLocationDetail> &locationA,
bvector< CurveLocationDetail> &locationB,
double    maxDist
);

public: static bool GEOMDLLIMPEXP CollectIntersectionsAndCloseApproachesXY
(
bvector<DPoint3d> const &xyzA,
bvector<double> const *paramA,
bvector<DPoint3d> const &xyzB,
bvector<double> const *paramB,
bvector< CurveLocationDetail> &locationA,
bvector< CurveLocationDetail> &locationB,
double    maxDist
);

public: static bool GEOMDLLIMPEXP ClosestApproach
(
bvector<DPoint3d> const &xyzA,
bvector<DPoint3d> const &xyzB,
CurveLocationDetailR locationA,
CurveLocationDetailR locationB
);

public: static GEOMDLLIMPEXP void CollectZPairsForOrderedXPoints (
bvector<DPoint3d>const &pointA,
bvector<DPoint3d> const &pointB,
bvector<CurveLocationDetailPair> &pairs
);



public: static GEOMDLLIMPEXP bool IsSelfIntersectingXY (bvector<DPoint3d> const &xyz, bool addClosure = false);
public: static GEOMDLLIMPEXP bool IsSelfIntersectingXY (DPoint3d *points, size_t n, bool addClosure = false);
public: static GEOMDLLIMPEXP bool IsRectangle (DPoint3dCP points, size_t n,
    TransformR localToWorld,
    TransformR worldToLocal,
    bool requireClosurePoint = true
    );

public: static GEOMDLLIMPEXP bool Are4EdgesPerpendicular (DPoint3dCP points);

public: static GEOMDLLIMPEXP bool IsRectangle (bvector<DPoint3d> const &points,
    TransformR localToWorld,
    TransformR worldToLocal,
    bool requireClosurePoint = true);

public: static GEOMDLLIMPEXP double SegmentLength (bvector<DPoint3d> const &points, size_t index);
public: static GEOMDLLIMPEXP double SegmentLength (RotMatrixCP worldToLocal, bvector<DPoint3d> const &points, size_t index);

public: static GEOMDLLIMPEXP DPoint3d SegmentFractionToPoint (bvector<DPoint3d> const &points, size_t index, double segmentFraction);
public: static GEOMDLLIMPEXP ValidatedDRay3d PolylineFractionToRay (bvector<DPoint3d> const &points, double polylineFraction);

public: static GEOMDLLIMPEXP bool FractionAtSignedDistanceFromFraction
(
bvector<DPoint3d> const &xyz,
double startFraction,
double signedDistance,
double &endFraction,
size_t &endSegmentIndex,
double &segmentFraction,
double &actualDistance
);

public: static GEOMDLLIMPEXP bool FractionAtSignedDistanceFromFraction
(
RotMatrixCP worldToLocal,
bvector<DPoint3d> const &xyz,
double startFraction,
double signedDistance,
double &endFraction,
size_t &endSegmentIndex,
double &segmentFraction,
double &actualDistance
);

public: static GEOMDLLIMPEXP double SignedDistanceBetweenFractions
(
bvector <DPoint3d> const & points,
double fraction0,
double fraction1
);

public: static GEOMDLLIMPEXP double SignedDistanceBetweenFractions
(
RotMatrixCP worldTolocal,
bvector <DPoint3d> const & points,
double fraction0,
double fraction1
);

public: static GEOMDLLIMPEXP bool FractionToFrenetFrame
(
bvector <DPoint3d> const & points,
double f,
TransformR frame
);

public: static GEOMDLLIMPEXP void CopyBetweenFractions
(
bvector <DPoint3d> const &points,
bvector<DPoint3d> &dest,
double fractionA,
double fractionB
);

public: static void CopyBetweenFractions
(
bvector <DPoint3d> const &points,
bvector<CurveLocationDetail> &dest,
double fractionA,
double fractionB
);
public: static GEOMDLLIMPEXP bool WireCentroid
(
bvector <DPoint3d> const &points,
double &length,
DPoint3dR centroid,
double fraction0 = 0.0,
double fraction1 = 1.0
);

public: static GEOMDLLIMPEXP DRange1d ProjectedParameterRange (bvector <DPoint3d> const &points, DRay3dCR ray, double fraction0, double fraction1);

public: static GEOMDLLIMPEXP void AddContinuationStartPoint (bvector<DPoint3d>&points, DPoint3dCR xyz, bool forceIncludeThisPoint);

public: static GEOMDLLIMPEXP bool AddStrokes
(
bvector <DPoint3d> const &points,
bvector <DPoint3d> & strokes, 
IFacetOptionsCR options,
bool includeStartPoint = true,
double startFraction = 0.0,
double endFraction = 1.0
);
public: static GEOMDLLIMPEXP bool AddStrokes
(
bvector <DPoint3d> const &points,
DPoint3dDoubleUVCurveArrays &strokes, 
IFacetOptionsCR options,
double startFraction = 0.0,
double endFraction = 1.0,
ICurvePrimitiveCP curve = nullptr
);


public: static GEOMDLLIMPEXP size_t GetStrokeCount
(
bvector <DPoint3d> const &points,
IFacetOptionsCR options,
double startFraction = 0.0,
double endFraction = 1.0
);

public: static GEOMDLLIMPEXP void CompressColinearPoints (bvector<DPoint3d> &points, double absTol, bool eliminateOverdraw, bool closed);


static GEOMDLLIMPEXP bool OffsetLineStringXY
(
bvector<DPoint3d> &out,        
bvector<DPoint3d> const &in,  
double offsetDistance,        
bool periodic = false,        
double maxMiterRadians = 1.58 
);

static GEOMDLLIMPEXP bool OffsetLineString
(
bvector<DPoint3d> &out,        
bvector<DPoint3d> const &in,  
double offsetDistance,        
DVec3dCR planeNormal,         
bool periodic = false,        
double maxMiterRadians = 1.58 
);

static GEOMDLLIMPEXP void GreedyTriangulationBetweenLinestrings
(
bvector<DPoint3d> const & linestringA,   
bvector<DPoint3d> const &linestringB,    
bvector<DTriangle3d> &triangles,         
bvector<int> *oneBasedABIndex = nullptr  
);

static GEOMDLLIMPEXP void AppendToChains (bvector<bvector<DPoint3d>> &chains, DSegment3dCR segment);

static GEOMDLLIMPEXP void AddPointIfDistinctFromBack (bvector<DPoint3d> &points, DPoint3d xyz);
static GEOMDLLIMPEXP void EnforceClosure(bvector<DPoint3d> &points);
static GEOMDLLIMPEXP void PackAlmostEqualAfter (bvector<DPoint3d> &points, size_t initialCount);
static GEOMDLLIMPEXP void CompressByChordError (bvector<DPoint3d>& result, bvector<DPoint3d> const& source, double chordTolerance);
};



enum class PlanePolygonSSICode
{
Unknown = 0,
Transverse = 1,
Coincident = 2
};

struct PolygonOps
{
private:
    PolygonOps (); // No instances.

public: static GEOMDLLIMPEXP DVec3d AreaNormal (bvector<DPoint3d> const &xyz);


public: static GEOMDLLIMPEXP DVec3d AreaNormal (bvector<DPoint3d> const &xyz, size_t n);


public: static GEOMDLLIMPEXP bool IsConvex (bvector<DPoint3d> const &xyz);


public:
static GEOMDLLIMPEXP bool FixupAndTriangulateLoopsXY
(
bvector<int>        *pIndices,
bvector<int>        *pExteriorLoopIndices,
bvector<DPoint3d>   *pXYZOut,
bvector<DPoint3d>   *pXYZIn,
double                  xyTolerance,
int                     maxPerFace,
bool                    signedOneBasedIndices,
bool                    addVerticesAtCrossings
);

public:
static GEOMDLLIMPEXP bool FixupAndTriangulateProjectedLoops
(
bvector<int>*       pIndices,
bvector<int>*       pExteriorLoopIndices,
bvector<DPoint3d>*  pXYZOut,
TransformCR             localToWorld,
TransformCR             worldToLocal,
bvector<DPoint3d>   *pXYZIn,
double                  xyTolerance,
bool                    bSignedOneBasedIndices
);

public:
static GEOMDLLIMPEXP bool FixupAndTriangulateSpaceLoops
(
bvector<int>*       pIndices,
bvector<int>*       pExteriorLoopIndices,
bvector<DPoint3d>*  pXYZOut,
TransformR              localToWorld,
TransformR              worldToLocal,
bvector<DPoint3d>*  pXYZIn,
double                  xyTolerance,
bool                    bSignedOneBasedIndices
);


public:
static GEOMDLLIMPEXP bool CoordinateFrame
(
bvector<DPoint3d>   *pXYZIn,
TransformR              localToWorld,
TransformR              worldToLocal
);

public:
static GEOMDLLIMPEXP bool CoordinateFrame
(
DPoint3dCP       pXYZIn,
size_t          numXYZ,
TransformR      localToWorld,
TransformR      worldToLocal
);

public:
static GEOMDLLIMPEXP bool CoordinateFrame
(
DPoint3dCP       pXYZIn,
size_t          numXYZ,
TransformR              localToWorld,
TransformR              worldToLocal,
enum LocalCoordinateSelect selector
);



public:
static GEOMDLLIMPEXP bool  ReorientTriangulationIndices
(
bvector<int>    &indices,
bool                *pbReversed,
bool                bSignedOneBasedIndices
);

public: static GEOMDLLIMPEXP double AreaXY (bvector<DPoint3d> const &xyz);
public: static GEOMDLLIMPEXP double AreaXY (DPoint3dCP pXYZ, size_t numXYZ);

public: static GEOMDLLIMPEXP double Area (bvector<DPoint2d> const &xy);
public: static GEOMDLLIMPEXP double Area (DPoint2dCP pXY, size_t numXY);

public: static GEOMDLLIMPEXP bool CentroidNormalAndArea (bvector<DPoint3d> const &xyz, DPoint3dR centroid, DVec3dR normal, double &area);
public: static GEOMDLLIMPEXP bool CentroidNormalAndArea (DPoint3dCP pXYZ, size_t numXYZ, DPoint3dR centroid, DVec3dR normal, double &area);

public: static GEOMDLLIMPEXP bool CentroidAndArea (bvector<DPoint2d> &points, DPoint2dR centroid, double &area);

public: static GEOMDLLIMPEXP bool SecondAreaMomentProducts (bvector<DPoint3d> const &xyz, DPoint3dCR origin, DMatrix4dR products);

public: static GEOMDLLIMPEXP bool PickTriangleFromStart
    (
    DPoint3dCP pXYZ,
    size_t numXYZ,
    DRay3dCR ray,
    DPoint3dR xyz,
    DPoint3dR triangleFractions,
    double &rayFraction,
    size_t &edgeBaseIndex
    );


public: static GEOMDLLIMPEXP bool PickTriangleFromStart
    (
    DPoint2dCP xyPoints, size_t n, DPoint2dCR xy,
    size_t &edgeBaseIndex,
    DPoint3dR uvw, DPoint3dR duvwdX, DPoint3dCR duvwdY
    );

public: static GEOMDLLIMPEXP PlanePolygonSSICode PlaneIntersectionPoints
(
bvector<DPoint3d> const &points,
DPlane3dCR plane,
double touchTolerance,
bvector<CurveLocationDetail> &trueCrossings,
bvector<CurveLocationDetail> *touchData,
DRange1d &altitudeLimits
);
    
};



struct UnionFind
{
static bool GEOMDLLIMPEXP IsValidClusterIndex (bvector <size_t> &clusterData, size_t index);

static size_t GEOMDLLIMPEXP NewClusterIndex (bvector<size_t> &clusterData);

static size_t GEOMDLLIMPEXP AddClusters (bvector<size_t> &clusterData, size_t numAdd);

static size_t GEOMDLLIMPEXP MergeClusters (bvector<size_t> &clusterData, size_t index0, size_t index1);

static size_t GEOMDLLIMPEXP FindClusterRoot (bvector<size_t> &clusterData, size_t start);

};



template <typename T>
struct DoubleEndedQueue
{

private:
bvector<T> m_entries;
// The dequeue entries are in indices i0 <= i < i1, considered cyclically.
size_t      m_i0;   // Always 0 <= m_i0 < m_entries.size ();
size_t      m_i1;   // Always m_i0 <= m_i1 <= m_i0 + m_entries.size ();
T m_defaultValue;

size_t CyclicPhysicalIndex (size_t i)  const
    {
    if (i < m_entries.size ())
        return i;
    else
        return i % m_entries.size ();
    }


public:
void Clear (){m_i0 = m_i1 = 0;}
DoubleEndedQueue (T defaultValue)
    :
    m_entries(10),
    m_defaultValue (defaultValue)
    {
    Clear ();
    }
bool IsEmpty () const {return m_i1 <= m_i0;}
void MakeRoomForInsertion ()
    {
    size_t n0 = m_i1 - m_i0;
    size_t n1 = m_entries.size ();
    if (n0 < n1)
        return;
    // (and strictly, n0==n1 -- the > case cannot happen)
    // the array is packed with entries a..b c..d organized physically as [c..d a..b]
    // Copy all entries of the physical aray to the back, so its contents are [c..d a..b c..d a..b]
    m_entries.reserve (2 * n0);
    for (size_t i = 0; i < n0; i++)
        m_entries.push_back (m_entries[i]);
    // m_i0 already points at the first a
    // m_i1 = m_i0 + n0 is already correct, but now with no wraparound happening.
    // so there is nothing more to do!!!
    }
size_t Size () const { return m_i1 - m_i0;}
void AddRight (T value)
    {
    MakeRoomForInsertion ();
    m_entries[CyclicPhysicalIndex (m_i1)] = value;
    m_i1++;
//     if (s_printHullSteps)
//         printf ("   PushLeft  %3d\n", (int)value);
    }
void AddLeft (T value)
    {
    MakeRoomForInsertion ();
//     if (s_printHullSteps)
//         printf ("   PushLeft  %3d\n", (int)value);
    if (m_i0 == 0)
        {
        size_t n = m_entries.size ();
        m_i0 += n;
        m_i1 += n;
        }
    m_i0--;
    m_entries[m_i0] = value;
    }
T GetRight () const
    {
    if (IsEmpty ())
        return m_defaultValue;
    return m_entries[CyclicPhysicalIndex(m_i1)];
    }

T GetLeft () const
    {
    if (IsEmpty ())
        return m_defaultValue;
    return m_entries[m_i0];
    }

T GetCyclicFromLeft (ptrdiff_t k) const
    {
    size_t n = m_i1 - m_i0;
    if (n == 0)
        return m_defaultValue;
    if (k < 0)
        k = n - ((-k) % n);
    if (k >= (ptrdiff_t)n)
        k = (k % n);
    if ((ptrdiff_t)m_i0 + k >= (ptrdiff_t)m_i1)
        return m_defaultValue;
    size_t i = m_i0 + k;
    return m_entries[CyclicPhysicalIndex(i)];
    }

T GetFromRight (size_t k) const
    {
    if (IsEmpty ())
        return m_defaultValue;
    if (m_i0 + k >= m_i1)
        return m_defaultValue;
    size_t i = m_i1 - 1     - k;
    return m_entries[CyclicPhysicalIndex(i)];
    }

T GetFromLeft (size_t k) const
    {
    if (IsEmpty ())
        return m_defaultValue;
    size_t i = m_i0 + k;
    if (i < m_i1)
        return m_entries[CyclicPhysicalIndex(i)];
    return m_defaultValue;
    }

void PopRight ()
    {
    if (!IsEmpty ())
        {
//         if (s_printHullSteps)
//             printf ("   PopRight %3d\n", (int)GetRight ());
        if (m_i1 > m_i0)
            m_i1--;
        }
    }

void PopLeft ()
    {
    if (!IsEmpty ())
        {
//         if (s_printHullSteps)
//             printf ("   PopLeft  %3d\n", (int)GetLeft ());
        m_i0++;
        if (m_i0 >= m_entries.size ())
            {
            m_i0 = 0;
            m_i1 -= m_entries.size ();
            }
        }
    }
bool operator == (DoubleEndedQueue<T> const &other) const
    {
    size_t n = Size ();
    if (n != other.Size ())
        return false;
    for (size_t i = 0; i < n; i++)
        if (GetFromLeft (i) != other.GetFromLeft (i))
            return false;
    return true;
    }
};

template <typename T>
struct MinimumValuePriorityQueue
    {
    struct Entry
        {
        double m_value;
        T m_data;
        Entry (T data, double value) : m_data (data), m_value (value) {}
        };
    private:
    bvector<Entry> m_heap;

    size_t Parent (size_t i)
        {
        if (i > 0)
            return (i - 1) / 2;
        return 0;       // root is its own parent !?!?!
        }
    size_t LeftChild (size_t i) { return 2 * i + 1; }
    size_t RightChild (size_t i) { return 2 * i + 2; }
    public: size_t Size () const { return m_heap.size ();}
    public:
    void Clear (){m_heap.clear ();}
    void Insert (T data, double value)
        {
        m_heap.push_back (Entry (data, value));
        size_t child = m_heap.size () - 1;
        while (child > 0)
            {
            size_t parent = Parent (child);
            if (m_heap[parent].m_value < m_heap[child].m_value)
                break;
            std::swap (m_heap[parent], m_heap[child]);
            child = parent;
            }
        }
    public:
    // ASSUME heap has data .. use IsEmpty () to pretest !!!
    double MinValue (){return m_heap.front ().m_value;}
    T MinData (){return m_heap.front ().m_data;}
    bool IsEmpty (){return m_heap.empty ();}


    bool RemoveMin (T &data, double &value)
        {
        size_t n = m_heap.size ();
        if (n == 0)
            return false;
        data = m_heap.front ().m_data;
        value = m_heap.front ().m_value;
        // fill the hole at the root with the very last array entry.
        m_heap.front () = m_heap.back ();
        m_heap.pop_back ();
        size_t parent = 0;
        // push the new value back down until the sort condition is again in effect.
        for (;;)
            {
            // swap with the smaller child and continue down ....
            size_t child = LeftChild (parent);
            if (child >= n)
                break;
            size_t rightChild = child + 1;
            if (rightChild < n && m_heap[rightChild].m_value < m_heap[child].m_value)
                child = rightChild;
            if (m_heap[child].m_value < m_heap[parent].m_value)
                {
                std::swap (m_heap[child], m_heap[parent]);
                parent = child;
                }
            else
                break;
            }
        return true;
        }

    bool RemoveMin ()
        {
        T data;
        double value;
        return removeMin (data, value);
        }
    bool Validate ()
        {
        size_t errors = 0;
        size_t n = m_heap.size ();
        for (size_t i = 0; i < n; i++)
            {
            size_t i1 = LeftChild (i);
            size_t i2 = RightChild (i);
            if (i1 < n && m_heap[i1].m_value < m_heap[i].m_value)
                errors++;
            if (i2 < n && m_heap[i2].m_value < m_heap[i].m_value)
                errors++;
            }
        return errors == 0;
        }
    };

struct DPoint3dDoubleArrays
{
bvector<DPoint3d> m_xyz;
bvector<double>   m_f;

void AppendXF (DPoint3dCR xyz, double f);
void AppendXdeltaF (DPoint3dCR xyz, double deltaF);

bool SearchBracketPoints (double f, size_t &i0, double &f0, DPoint3dR xyz0, size_t &i1, double &f1, DPoint3dR xyz1) const;

DRange3d GetRange () const;

DRange3d GetRange (TransformCR transform) const;
void ReverseXF (bool reverseFAs01Fraction);
};

struct DPoint3dDoubleUVArrays : DPoint3dDoubleArrays
{
bvector<DPoint2d> m_uv;
bvector<DVec3d>   m_vectorU;
bvector<DVec3d>   m_vectorV;

void ReverseXFUV (bool reverseFAs01Fraction, bool negateVectorU, bool negateVectorV);

};

struct DPoint3dDoubleUVCurveArrays : DPoint3dDoubleUVArrays
{
bvector<ICurvePrimitive *>  m_curve;

void ReverseXFUVC (bool reverseFAs01Fraction, bool negateVectorU, bool negateVectorV);
void ReverseXFUVC (size_t index0, size_t index1, bool reverseFAs01Fraction, bool negateVectorU, bool negateVectorV);


void Add (DPoint3dCR xyz, double f, DVec3dCR vectorU, ICurvePrimitive* curve)
    {
    m_xyz.push_back (xyz);
    m_f.push_back (f);
    m_vectorU.push_back (vectorU);
    m_curve.push_back (curve);
    }
void Add (ValidatedDRay3d const &ray, double f, ICurvePrimitive* curve)
    {
    if (ray.IsValid ())
        {
        m_xyz.push_back (ray.Value ().origin);
        m_f.push_back (f);
        m_vectorU.push_back (ray.Value ().direction);
        m_curve.push_back (curve);
        }
    }

};

END_BENTLEY_GEOMETRY_NAMESPACE