The code refactoring done in PR #7 to the gift wrapping algorithm for creating a convex hull is incorrect. The previous code properly implemented the gift wrapping algorithm and correctly generated a valid convex hull. The refactored code does not properly implement the gift wrapping algorithm. To demonstrate the error of the refactored code, consider this set of vertices to define a polygon:
var vertices = [
Vector2(-10, 20),
Vector2(-10, 0),
Vector2(0, -30),
Vector2(10, 0),
Vector2(10, 10),
];
final shape = PolygonShape()..set(vertices);
The correct convex hull output from this set of vertices from the gift wrapping algorithm is (and was from the old code):
Vector2(10, 0),
Vector2(10, 10),
Vector2(-10, 20),
Vector2(-10, 0),
Vector2(0, -30),
But the output from the new refactored code is an invalid polygon that crosses over itself:
Vector2(10, 0),
Vector2(-10, 0),
Vector2(0, -30),
Vector2(10, 10),
Vector2(-10, 20),
The incorrect refactored code is in forge2d-0.7.2 > lib > src > collision > shapes > polygon_shape.dart beginning at line 90:
final hull = <Vector2>[rightMostPoint];
for (final point1 in points) {
var currentPoint = hull.last;
for (final point2 in points) {
if (currentPoint == hull.last) {
currentPoint = point2;
continue;
}
final r = currentPoint.clone()..sub(point1);
final v = point2.clone()..sub(point1);
final c = r.cross(v);
if (c < 0.0) {
currentPoint = point2;
}
// Collinearity check
if (c == 0.0 && v.length2 > r.length2) {
currentPoint = point2;
}
}
if (!hull.contains(currentPoint)) {
hull.add(currentPoint);
}
}
Not only is this code incorrect, but it also changes the complexity of the gift wrapping algorithm from O(nh) where n is the number of vertices and h is the number of vertices on the hull, to O(nn).
I'd like to offer this fix for consideration as a correct implementation of the gift wrapping algorithm:
final hull = <Vector2>[rightMostPoint];
var pointOnHull = rightMostPoint;
do {
// Set first point in the set as the initial candidate for the
// next point on the convex hull.
var endPoint = points[0];
// Test the candidate point against all points in the set to find
// the next convex hull point.
for (final point in points) {
// If the candidate point is current last point on the convex
// hull update the candidate point to the current point and continue
// checking against the remaining points.
if (endPoint == pointOnHull) {
endPoint = point;
continue;
}
// Use the cross product of the vectors from the current convex hull
// point to the candidate point and the current test point to see if
// the test point is changes the winding to CW. Update the candidate
// point when the winding changes.
final r = endPoint.clone()..sub(pointOnHull);
final v = point.clone()..sub(pointOnHull);
final c = r.cross(v);
if (c < 0.0) {
endPoint = point;
}
// Collinearity check
if (c == 0.0 && v.length2 > r.length2) {
endPoint = point;
}
}
// Set the end point candidate as the new current convex hull point.
pointOnHull = endPoint;
if (!hull.contains(pointOnHull)) {
hull.add(pointOnHull);
}
} while (pointOnHull != hull.first);
bug
![[Feature Request] Box2d Lights](https://avatars.githubusercontent.com/u/20211760?v=4)
2 Nov 25, 2022
1 Oct 15, 2021
24 Jan 2, 2023
1 Jul 26, 2022
3 Jul 16, 2022
44 Oct 31, 2022
7 Jun 11, 2022
26 Aug 9, 2022
46 Dec 27, 2022
754 Dec 27, 2022
25 Nov 11, 2022
3 Feb 23, 2022
35 Dec 14, 2022
7 Nov 1, 2022
2 Jan 28, 2022
103 Nov 29, 2022
460 Jan 9, 2023
1 Apr 15, 2022