The Quickhull algorithm for computing the convex hull in two dimensions may be summarized as follows:
Initialization:
Start with the entire set of points.
Identify the points with the minimum and maximum x-coordinates (or y-coordinates if there are ties).
Use the line formed by these two points to divide the set into two subsets: points above and below the line.
Recursive Steps:
Find the point farthest from the dividing line (maximum distance).
This point forms a triangle with the two initial points.
Points inside this triangle cannot be part of the convex hull and are ignored.
Recursively apply the same process to the two new line segments formed by the triangle's sides.
Continue until no more points remain.
Result:
The selected points constitute the convex hull.
/// Convex hull used for polygon collision
class b2Hull {
constructor() {
this.points = Vec2.MakeArray(b2_maxPolygonVertices); //array of b2Vec2
this.count = 0;
}
// quickhull recursion
static b2RecurseHull(/*b2Vec2*/ p1, /*b2Vec2*/ p2, /*b2Vec2**/ ps, /*int32*/ count) {
let hull = new b2Hull();
hull.count = 0;
if (count == 0) {
return hull;
}
// create an edge vector pointing from p1 to p2
let e = Vec2.Subtract(p2, p1);
e.normalize();
// discard points left of e and find point furthest to the right of e
let rightPoints = Vec2.MakeArray(b2_maxPolygonVertices);
let rightCount = 0;
let bestIndex = 0;
let bestDistance = b2Cross(Vec2.Subtract(ps[bestIndex], p1), e);
if (bestDistance > 0.0) {
rightPoints[rightCount++].copy(ps[bestIndex]);
}
for (let i = 1; i < count; i++) {
let distance = b2Cross(Vec2.Subtract(ps[i], p1), e);
if (distance > bestDistance) {
bestIndex = i;
bestDistance = distance;
}
if (distance > 0.0) {
rightPoints[rightCount++].copy(ps[i]);
}
}
if (bestDistance < 2.0 b2_linearSlop) {
return hull;
}
let bestPoint = ps[bestIndex]; //b2Vec2
// compute hull to the right of p1-bestPoint
let hull1 = b2Hull.b2RecurseHull(p1, bestPoint, rightPoints, rightCount);
// compute hull to the right of bestPoint-p2
let hull2 = b2Hull.b2RecurseHull(bestPoint, p2, rightPoints, rightCount);
// stich together hulls
for (let i = 0; i < hull1.count; i++) {
hull.points[hull.count++].copy(hull1.points[i]);
}
hull.points[hull.count++] = bestPoint;
for (let i = 0; i < hull2.count; i++) {
hull.points[hull.count++].copy(hull2.points[i]);
}
b2Assert(hull.count < b2_maxPolygonVertices);
return hull;
}
/// Compute the convex hull of a set of points. Returns an empty hull if it fails.
/// Some failure cases:
/// - all points very close together
/// - all points on a line
/// - less than 3 points
/// - more than b2_maxPolygonVertices points
// quickhull algorithm
// - merges vertices based on b2_linearSlop
// - removes collinear points using b2_linearSlop
// - returns an empty hull if it fails
b2ComputeHull(points, count) {
let hull = this;
hull.count = 0;
if (count < 3 || count > b2_maxPolygonVertices) {
// check your data
return hull;
}
count = Math.min(count, b2_maxPolygonVertices);
let aabb = new b2AABB(new Vec2(b2_maxFloat, b2_maxFloat), new Vec2(-b2_maxFloat, -b2_maxFloat)); //b2AABB
// Perform aggressive point welding. First point always remains.
// Also compute the bounding box for later.
let ps = Vec2.MakeArray(b2_maxPolygonVertices);
let n = 0;
const tolSqr = 16.0 b2_linearSlop b2_linearSlop;
for (let i = 0; i < count; i++) {
aabb.lowerBound = b2Min(aabb.lowerBound, points[i]);
aabb.upperBound = b2Max(aabb.upperBound, points[i]);
let vi = points[i];
let unique = true;
for (let j = 0; j < i; j++) {
let vj = points[j];
let distSqr = Vec2.DistanceSquared(vi, vj);
if (distSqr < tolSqr) {
unique = false;
break;
}
}
if (unique) {
ps[n++].copy(vi) ;
}
}
if (n < 3) {
// all points very close together, check your data and check your scale
return hull;
}
// Find an extreme point as the first point on the hull
let c = aabb.getCenter();
let i1 = 0;
let dsq1 = Vec2.DistanceSquared(c, ps[i1]);
for (let i = 1; i < n; i++) {
let dsq = Vec2.DistanceSquared(c, ps[i]);
if (dsq > dsq1) {
i1 = i;
dsq1 = dsq;
}
}
// remove p1 from working set
let p1 = ps[i1];
ps[i1] = ps[n - 1];
n = n - 1;
let i2 = 0;
let dsq2 = Vec2.DistanceSquared(p1, ps[i2]);
for (let i = 1; i < n; i++) {
let dsq = Vec2.DistanceSquared(p1, ps[i]);
if (dsq > dsq2) {
i2 = i;
dsq2 = dsq;
}
}
// remove p2 from working set
let p2 = ps[i2];
ps[i2] = ps[n - 1];
n = n - 1;
// split the points into points that are left and right of the line p1-p2.
let rightPoints = Vec2.MakeArray(b2_maxPolygonVertices - 2);
let rightCount = 0;
let leftPoints = Vec2.MakeArray(b2_maxPolygonVertices - 2);
let leftCount = 0;
let e = Vec2.Subtract(p2, p1);
e.normalize();
for (let i = 0; i < n; i++) {
let d = b2Cross(Vec2.Subtract(ps[i], p1), e);
// slop used here to skip points that are very close to the line p1-p2
if (d >= 2.0 b2_linearSlop) {
rightPoints[rightCount++].copy(ps[i]);
}
else if (d <= -2.0 b2_linearSlop) {
leftPoints[leftCount++].copy(ps[i]);
}
}
// compute hulls on right and left
let hull1 = b2Hull.b2RecurseHull(p1, p2, rightPoints, rightCount);
let hull2 = b2Hull.b2RecurseHull(p2, p1, leftPoints, leftCount);
if (hull1.count == 0 && hull2.count == 0) {
// all points collinear
return hull;
}
// stitch hulls together, preserving CCW winding order
hull.points[hull.count++].copy(p1);
for (let i = 0; i < hull1.count; i++) {
hull.points[hull.count++].copy(hull1.points[i]);
}
hull.points[hull.count++].copy(p2);
for (let i = 0; i < hull2.count; i++) {
hull.points[hull.count++].copy(hull2.points[i]);
}
b2Assert(hull.count <= b2_maxPolygonVertices);
// merge collinear
let searching = true;
while (searching && hull.count > 2) {
searching = false;
for (let i = 0; i < hull.count; ++i) {
let i1 = i;
let i2 = (i + 1) % hull.count;
let i3 = (i + 2) % hull.count;
let p1 = hull.points[i1];
let p2 = hull.points[i2];
let p3 = hull.points[i3];
let e = Vec2.Subtract(p3, p1);
e.normalize();
let v = Vec2.Subtract(p2, p1);
let distance = b2Cross(Vec2.Subtract(p2, p1), e);
if (distance <= 2.0 b2_linearSlop) {
// remove midpoint from hull
for (let j = i2; j < hull.count - 1; j++) {
hull.points[j] = hull.points[j + 1];
}
hull.count -= 1;
// continue searching for collinear points
searching = true;
break;
}
}
}
if (hull.count < 3) {
// all points collinear, shouldn't be reached since this was validated above
hull.count = 0;
}
return hull;
};
};
Comments