Hugging Face's logo

AbdulElahGwaith
/
FreeCAD

Arabic
English
freecad
Model card Files
xet
 Community
FreeCAD / src /Mod /Mesh /App /WildMagic4 /Wm4ContBox2.cpp
AbdulElahGwaith's picture
AbdulElahGwaith
Upload folder using huggingface_hub
985c397 verified
Raw History Blame Contribute Delete
17.1 kB
// SPDX-License-Identifier: BSL-1.0
// Geometric Tools, LLC
// Copyright (c) 1998-2010
// Distributed under the Boost Software License, Version 1.0.
// http://www.boost.org/LICENSE_1_0.txt
// http://www.geometrictools.com/License/Boost/LICENSE_1_0.txt
//
// File Version: 4.10.0 (2009/11/18)
#include "Wm4FoundationPCH.h"
#include "Wm4ContBox2.h"
#include "Wm4ApprGaussPointsFit2.h"
#include "Wm4ConvexHull2.h"
namespace Wm4
{
//----------------------------------------------------------------------------
template <class Real>
Box2<Real> ContAlignedBox (int iQuantity, const Vector2<Real>* akPoint)
{
Vector2<Real> kMin, kMax;
Vector2<Real>::ComputeExtremes(iQuantity,akPoint,kMin,kMax);
Box2<Real> kBox;
kBox.Center = ((Real)0.5)*(kMin + kMax);
kBox.Axis[0] = Vector2<Real>::UNIT_X;
kBox.Axis[1] = Vector2<Real>::UNIT_Y;
Vector2<Real> kHalfDiagonal = ((Real)0.5)*(kMax - kMin);
for (int i = 0; i < 2; i++)
{
kBox.Extent[i] = kHalfDiagonal[i];
}
return kBox;
}
//----------------------------------------------------------------------------
template <class Real>
Box2<Real> ContOrientedBox (int iQuantity, const Vector2<Real>* akPoint)
{
Box2<Real> kBox = GaussPointsFit2<Real>(iQuantity,akPoint);
// Let C be the box center and let U0 and U1 be the box axes. Each
// input point is of the form X = C + y0*U0 + y1*U1. The following code
// computes min(y0), max(y0), min(y1), max(y1), min(y2), and max(y2).
// The box center is then adjusted to be
// C' = C + 0.5*(min(y0)+max(y0))*U0 + 0.5*(min(y1)+max(y1))*U1
Vector2<Real> kDiff = akPoint[0] - kBox.Center;
Vector2<Real> kMin(kDiff.Dot(kBox.Axis[0]),kDiff.Dot(kBox.Axis[1]));
Vector2<Real> kMax = kMin;
for (int i = 1; i < iQuantity; i++)
{
kDiff = akPoint[i] - kBox.Center;
for (int j = 0; j < 2; j++)
{
Real fDot = kDiff.Dot(kBox.Axis[j]);
if (fDot < kMin[j])
{
kMin[j] = fDot;
}
else if (fDot > kMax[j])
{
kMax[j] = fDot;
}
}
}
kBox.Center +=
(((Real)0.5)*(kMin[0]+kMax[0]))*kBox.Axis[0] +
(((Real)0.5)*(kMin[1]+kMax[1]))*kBox.Axis[1];
kBox.Extent[0] = ((Real)0.5)*(kMax[0] - kMin[0]);
kBox.Extent[1] = ((Real)0.5)*(kMax[1] - kMin[1]);
return kBox;
}
//----------------------------------------------------------------------------
template <class Real>
static void UpdateBox (const Vector2<Real>& rkLPoint,
const Vector2<Real>& rkRPoint, const Vector2<Real>& rkBPoint,
const Vector2<Real>& rkTPoint, const Vector2<Real>& rkU,
const Vector2<Real>& rkV, Real& rfMinAreaDiv4, Box2<Real>& rkBox)
{
Vector2<Real> kRLDiff = rkRPoint - rkLPoint;
Vector2<Real> kTBDiff = rkTPoint - rkBPoint;
Real fExtent0 = ((Real)0.5)*(rkU.Dot(kRLDiff));
Real fExtent1 = ((Real)0.5)*(rkV.Dot(kTBDiff));
Real fAreaDiv4 = fExtent0*fExtent1;
if (fAreaDiv4 < rfMinAreaDiv4)
{
rfMinAreaDiv4 = fAreaDiv4;
rkBox.Axis[0] = rkU;
rkBox.Axis[1] = rkV;
rkBox.Extent[0] = fExtent0;
rkBox.Extent[1] = fExtent1;
Vector2<Real> kLBDiff = rkLPoint - rkBPoint;
rkBox.Center = rkLPoint + rkU*fExtent0 +
rkV*(fExtent1 - rkV.Dot(kLBDiff));
}
}
//----------------------------------------------------------------------------
template <class Real>
Box2<Real> ContMinBox (int iQuantity, const Vector2<Real>* akPoint,
Real fEpsilon, Query::Type eQueryType, bool bIsConvexPolygon)
{
Box2<Real> kBox;
// get the convex hull of the points
Vector2<Real>* akHPoint = nullptr;
if (bIsConvexPolygon)
{
akHPoint = (Vector2<Real>*)akPoint;
}
else
{
ConvexHull2<Real> kHull(iQuantity,(Vector2<Real>*)akPoint,fEpsilon,
false,eQueryType);
int iHDim = kHull.GetDimension();
int iHQuantity = kHull.GetSimplexQuantity();
const int* aiHIndex = kHull.GetIndices();
if (iHDim == 0)
{
kBox.Center = akPoint[0];
kBox.Axis[0] = Vector2<Real>::UNIT_X;
kBox.Axis[1] = Vector2<Real>::UNIT_Y;
kBox.Extent[0] = (Real)0.0;
kBox.Extent[1] = (Real)0.0;
return kBox;
}
if (iHDim == 1)
{
ConvexHull1<Real>* pkHull1 = kHull.GetConvexHull1();
aiHIndex = pkHull1->GetIndices();
kBox.Center = ((Real)0.5)*(akPoint[aiHIndex[0]] +
akPoint[aiHIndex[1]]);
Vector2<Real> kDiff = akPoint[aiHIndex[1]] - akPoint[aiHIndex[0]];
kBox.Extent[0] = ((Real)0.5)*kDiff.Normalize();
kBox.Extent[1] = (Real)0.0;
kBox.Axis[0] = kDiff;
kBox.Axis[1] = -kBox.Axis[0].Perp();
WM4_DELETE pkHull1;
return kBox;
}
iQuantity = iHQuantity;
akHPoint = WM4_NEW Vector2<Real>[iQuantity];
for (int i = 0; i < iQuantity; i++)
{
akHPoint[i] = akPoint[aiHIndex[i]];
}
}
// The input points are V[0] through V[N-1] and are assumed to be the
// vertices of a convex polygon that are counterclockwise ordered. The
// input points must not contain three consecutive collinear points.
// Unit-length edge directions of convex polygon. These could be
// precomputed and passed to this routine if the application requires it.
int iQuantityM1 = iQuantity -1;
Vector2<Real>* akEdge = WM4_NEW Vector2<Real>[iQuantity];
bool* abVisited = WM4_NEW bool[iQuantity];
int i;
for (i = 0; i < iQuantityM1; i++)
{
akEdge[i] = akHPoint[i+1] - akHPoint[i];
akEdge[i].Normalize();
abVisited[i] = false;
}
akEdge[iQuantityM1] = akHPoint[0] - akHPoint[iQuantityM1];
akEdge[iQuantityM1].Normalize();
abVisited[iQuantityM1] = false;
// Find the smallest axis-aligned box containing the points. Keep track
// of the extremum indices, L (left), R (right), B (bottom), and T (top)
// so that the following constraints are met:
// V[L].X() <= V[i].X() for all i and V[(L+1)%N].X() > V[L].X()
// V[R].X() >= V[i].X() for all i and V[(R+1)%N].X() < V[R].X()
// V[B].Y() <= V[i].Y() for all i and V[(B+1)%N].Y() > V[B].Y()
// V[T].Y() >= V[i].Y() for all i and V[(T+1)%N].Y() < V[T].Y()
Real fXMin = akHPoint[0].X(), fXMax = fXMin;
Real fYMin = akHPoint[0].Y(), fYMax = fYMin;
int iLIndex = 0, iRIndex = 0, iBIndex = 0, iTIndex = 0;
for (i = 1; i < iQuantity; i++)
{
if (akHPoint[i].X() <= fXMin)
{
fXMin = akHPoint[i].X();
iLIndex = i;
}
if (akHPoint[i].X() >= fXMax)
{
fXMax = akHPoint[i].X();
iRIndex = i;
}
if (akHPoint[i].Y() <= fYMin)
{
fYMin = akHPoint[i].Y();
iBIndex = i;
}
if (akHPoint[i].Y() >= fYMax)
{
fYMax = akHPoint[i].Y();
iTIndex = i;
}
}
// wrap-around tests to ensure the constraints mentioned above
if (iLIndex == iQuantityM1)
{
if (akHPoint[0].X() <= fXMin)
{
fXMin = akHPoint[0].X();
iLIndex = 0;
}
}
if (iRIndex == iQuantityM1)
{
if (akHPoint[0].X() >= fXMax)
{
fXMax = akHPoint[0].X();
iRIndex = 0;
}
}
if (iBIndex == iQuantityM1)
{
if (akHPoint[0].Y() <= fYMin)
{
fYMin = akHPoint[0].Y();
iBIndex = 0;
}
}
if (iTIndex == iQuantityM1)
{
if (akHPoint[0].Y() >= fYMax)
{
fYMax = akHPoint[0].Y();
iTIndex = 0;
}
}
// dimensions of axis-aligned box (extents store width and height for now)
kBox.Center.X() = ((Real)0.5)*(fXMin + fXMax);
kBox.Center.Y() = ((Real)0.5)*(fYMin + fYMax);
kBox.Axis[0] = Vector2<Real>::UNIT_X;
kBox.Axis[1] = Vector2<Real>::UNIT_Y;
kBox.Extent[0] = ((Real)0.5)*(fXMax - fXMin);
kBox.Extent[1] = ((Real)0.5)*(fYMax - fYMin);
Real fMinAreaDiv4 = kBox.Extent[0]*kBox.Extent[1];
// rotating calipers algorithm
enum { F_NONE, F_LEFT, F_RIGHT, F_BOTTOM, F_TOP };
Vector2<Real> kU = Vector2<Real>::UNIT_X, kV = Vector2<Real>::UNIT_Y;
bool bDone = false;
while (!bDone)
{
// determine edge that forms smallest angle with current box edges
int iFlag = F_NONE;
Real fMaxDot = (Real)0.0;
Real fDot = kU.Dot(akEdge[iBIndex]);
if (fDot > fMaxDot)
{
fMaxDot = fDot;
iFlag = F_BOTTOM;
}
fDot = kV.Dot(akEdge[iRIndex]);
if (fDot > fMaxDot)
{
fMaxDot = fDot;
iFlag = F_RIGHT;
}
fDot = -kU.Dot(akEdge[iTIndex]);
if (fDot > fMaxDot)
{
fMaxDot = fDot;
iFlag = F_TOP;
}
fDot = -kV.Dot(akEdge[iLIndex]);
if (fDot > fMaxDot)
{
fMaxDot = fDot;
iFlag = F_LEFT;
}
switch (iFlag)
{
case F_BOTTOM:
if (abVisited[iBIndex])
{
bDone = true;
}
else
{
// compute box axes with E[B] as an edge
kU = akEdge[iBIndex];
kV = -kU.Perp();
UpdateBox(akHPoint[iLIndex],akHPoint[iRIndex],
akHPoint[iBIndex],akHPoint[iTIndex],kU,kV,fMinAreaDiv4,
kBox);
// mark edge visited and rotate the calipers
abVisited[iBIndex] = true;
if (++iBIndex == iQuantity)
{
iBIndex = 0;
}
}
break;
case F_RIGHT:
if (abVisited[iRIndex])
{
bDone = true;
}
else
{
// compute dimensions of box with E[R] as an edge
kV = akEdge[iRIndex];
kU = kV.Perp();
UpdateBox(akHPoint[iLIndex],akHPoint[iRIndex],
akHPoint[iBIndex],akHPoint[iTIndex],kU,kV,fMinAreaDiv4,
kBox);
// mark edge visited and rotate the calipers
abVisited[iRIndex] = true;
if (++iRIndex == iQuantity)
{
iRIndex = 0;
}
}
break;
case F_TOP:
if (abVisited[iTIndex])
{
bDone = true;
}
else
{
// compute dimensions of box with E[T] as an edge
kU = -akEdge[iTIndex];
kV = -kU.Perp();
UpdateBox(akHPoint[iLIndex],akHPoint[iRIndex],
akHPoint[iBIndex],akHPoint[iTIndex],kU,kV,fMinAreaDiv4,
kBox);
// mark edge visited and rotate the calipers
abVisited[iTIndex] = true;
if (++iTIndex == iQuantity)
{
iTIndex = 0;
}
}
break;
case F_LEFT:
if (abVisited[iLIndex])
{
bDone = true;
}
else
{
// compute dimensions of box with E[L] as an edge
kV = -akEdge[iLIndex];
kU = kV.Perp();
UpdateBox(akHPoint[iLIndex],akHPoint[iRIndex],
akHPoint[iBIndex],akHPoint[iTIndex],kU,kV,fMinAreaDiv4,
kBox);
// mark edge visited and rotate the calipers
abVisited[iLIndex] = true;
if (++iLIndex == iQuantity)
{
iLIndex = 0;
}
}
break;
case F_NONE:
// polygon is a rectangle
bDone = true;
break;
}
}
WM4_DELETE[] abVisited;
WM4_DELETE[] akEdge;
if (!bIsConvexPolygon)
{
WM4_DELETE[] akHPoint;
}
return kBox;
}
//----------------------------------------------------------------------------
template <class Real>
bool InBox (const Vector2<Real>& rkPoint, const Box2<Real>& rkBox)
{
Vector2<Real> kDiff = rkPoint - rkBox.Center;
for (int i = 0; i < 2; i++)
{
Real fCoeff = kDiff.Dot(rkBox.Axis[i]);
if (Math<Real>::FAbs(fCoeff) > rkBox.Extent[i])
{
return false;
}
}
return true;
}
//----------------------------------------------------------------------------
template <class Real>
Box2<Real> MergeBoxes (const Box2<Real>& rkBox0, const Box2<Real>& rkBox1)
{
// construct a box that contains the input boxes
Box2<Real> kBox;
// The first guess at the box center. This value will be updated later
// after the input box vertices are projected onto axes determined by an
// average of box axes.
kBox.Center = ((Real)0.5)*(rkBox0.Center + rkBox1.Center);
// The merged box axes are the averages of the input box axes. The
// axes of the second box are negated, if necessary, so they form acute
// angles with the axes of the first box.
if (rkBox0.Axis[0].Dot(rkBox1.Axis[0]) >= (Real)0.0)
{
kBox.Axis[0] = ((Real)0.5)*(rkBox0.Axis[0] + rkBox1.Axis[0]);
kBox.Axis[0].Normalize();
}
else
{
kBox.Axis[0] = ((Real)0.5)*(rkBox0.Axis[0] - rkBox1.Axis[0]);
kBox.Axis[0].Normalize();
}
kBox.Axis[1] = -kBox.Axis[0].Perp();
// Project the input box vertices onto the merged-box axes. Each axis
// D[i] containing the current center C has a minimum projected value
// pmin[i] and a maximum projected value pmax[i]. The corresponding end
// points on the axes are C+pmin[i]*D[i] and C+pmax[i]*D[i]. The point C
// is not necessarily the midpoint for any of the intervals. The actual
// box center will be adjusted from C to a point C' that is the midpoint
// of each interval,
// C' = C + sum_{i=0}^1 0.5*(pmin[i]+pmax[i])*D[i]
// The box extents are
// e[i] = 0.5*(pmax[i]-pmin[i])
int i, j;
Real fDot;
Vector2<Real> akVertex[4], kDiff;
Vector2<Real> kMin = Vector2<Real>::ZERO;
Vector2<Real> kMax = Vector2<Real>::ZERO;
rkBox0.ComputeVertices(akVertex);
for (i = 0; i < 4; i++)
{
kDiff = akVertex[i] - kBox.Center;
for (j = 0; j < 2; j++)
{
fDot = kDiff.Dot(kBox.Axis[j]);
if (fDot > kMax[j])
{
kMax[j] = fDot;
}
else if ( fDot < kMin[j] )
{
kMin[j] = fDot;
}
}
}
rkBox1.ComputeVertices(akVertex);
for (i = 0; i < 4; i++)
{
kDiff = akVertex[i] - kBox.Center;
for (j = 0; j < 2; j++)
{
fDot = kDiff.Dot(kBox.Axis[j]);
if (fDot > kMax[j])
{
kMax[j] = fDot;
}
else if (fDot < kMin[j])
{
kMin[j] = fDot;
}
}
}
// [kMin,kMax] is the axis-aligned box in the coordinate system of the
// merged box axes. Update the current box center to be the center of
// the new box. Compute the extents based on the new center.
for (j = 0; j < 2; j++)
{
kBox.Center += kBox.Axis[j]*(((Real)0.5)*(kMax[j]+kMin[j]));
kBox.Extent[j] = ((Real)0.5)*(kMax[j]-kMin[j]);
}
return kBox;
}
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
template WM4_FOUNDATION_ITEM
Box2<float> ContAlignedBox<float> (int, const Vector2<float>*);
template WM4_FOUNDATION_ITEM
Box2<float> ContOrientedBox<float> (int, const Vector2<float>*);
template WM4_FOUNDATION_ITEM
Box2<float> ContMinBox<float> (int, const Vector2<float>*, float,
Query::Type, bool);
template WM4_FOUNDATION_ITEM
bool InBox<float> (const Vector2<float>&, const Box2<float>&);
template WM4_FOUNDATION_ITEM
Box2<float> MergeBoxes<float> (const Box2<float>&, const Box2<float>&);
template WM4_FOUNDATION_ITEM
Box2<double> ContAlignedBox<double> (int, const Vector2<double>*);
template WM4_FOUNDATION_ITEM
Box2<double> ContOrientedBox<double> (int, const Vector2<double>*);
template WM4_FOUNDATION_ITEM
Box2<double> ContMinBox<double> (int, const Vector2<double>*, double,
Query::Type, bool);
template WM4_FOUNDATION_ITEM
bool InBox<double> (const Vector2<double>&, const Box2<double>&);
template WM4_FOUNDATION_ITEM
Box2<double> MergeBoxes<double> (const Box2<double>&, const Box2<double>&);
//----------------------------------------------------------------------------
}