17#ifndef GRAHAM_SCAN_2D_CONVEX_HULL_H
18#define GRAHAM_SCAN_2D_CONVEX_HULL_H
65 if (originalPoints.
size()<=1)
67 for (
int i=0;i<originalPoints.
size();i++)
72 for (
int i=0;i<originalPoints.
size();i++)
76 btScalar projL = originalPoints[i].dot(axis0);
77 btScalar projR = originalPoints[0].dot(axis0);
80 originalPoints.
swap(0,i);
85 originalPoints[0].m_angle = -1e30f;
86 for (
int i=1;i<originalPoints.
size();i++)
88 btVector3 ar = originalPoints[i]-originalPoints[0];
91 if( ar1*ar1+ar0*ar0 < FLT_EPSILON )
93 originalPoints[i].m_angle = 0.0f;
106 for (i = 0; i<2; i++)
110 for (; i != originalPoints.
size(); i++)
112 bool isConvex =
false;
113 while (!isConvex&& hull.
size()>1) {
116 isConvex =
btCross(a-b,a-originalPoints[i]).
dot(normalAxis)> 0;
123 if( hull.
size() == 1 )
void GrahamScanConvexHull2D(btAlignedObjectArray< GrahamVector3 > &originalPoints, btAlignedObjectArray< GrahamVector3 > &hull, const btVector3 &normalAxis)
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
btScalar btAtan2Fast(btScalar y, btScalar x)
void btPlaneSpace1(const T &n, T &p, T &q)
btVector3 btCross(const btVector3 &v1, const btVector3 &v2)
Return the cross product of two vectors.
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
int size() const
return the number of elements in the array
void swap(int index0, int index1)
void push_back(const T &_Val)
void quickSortInternal(const L &CompareFunc, int lo, int hi)
btVector3 can be used to represent 3D points and vectors.
btScalar dot(const btVector3 &v) const
Return the dot product.
GrahamVector3(const btVector3 &org, int orgIndex)
bool operator()(const GrahamVector3 &a, const GrahamVector3 &b) const
btAngleCompareFunc(const btVector3 &anchor)