I am trying to create an outline from a collection of points. I found this solution for Convex Hull. I specifically picked this implementation: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
Edit: I can't find an algorithm that will find the concavity of the region specified in green. The yellow line is the Hull from the algorithm amove
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;
}