I am trying to create an outline from a collection of points. I was doing research and I found in my Real Time Collision and Detection book, as well as Wikipedia of a solution called Convex Hull. I specifically picked this implementation: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
However, I am not getting results that match the points(Green) vs the Hull(yellow)
![Implementation](https://i.sstatic.net/nhNs2.png)
I have the point is defined as:
[Serializable]
public struct Point : IComparable<Point>, IEquatable<Point>
{
public int X;
public int Y;
public static int Cross(Point o, Point a, Point b)
{
return (a.X - o.X) * (b.Y - o.Y) - (a.Y - o.Y) * (b.X - o.X);
}
}
Here is the implementation of the algorithm:
public static List<Point> ConvexHull(List<Point> points)
{
if (points == null || points.Count <= 3) {
return points;
}
var size = points.Count;
var k = 0;
var hull = new Point[2 * size];
points.Sort();
//build lower hull
for (int i = 0; i < size; ++i) {
while (k >= 2 && Point.Cross(hull[k - 2], hull[k - 1], points[i]) <= 0) {
k--;
}
hull[k++] = points[i];
}
//build upper hull
for (int i = size - 1, t = k + 1; i > 0; --i) {
while (k >= t && Point.Cross(hull[k - 2], hull[k - 1], points[i - 1]) <= 0) {
k--;
}
hull[k++] = points[i - 1];
}
var result = new List<Point>(hull);
if (k > 1) {
result.Resize(k - 1);// remove non-hull vertices after k; remove k - 1 which is a duplicate
}
return result;
}