# Creating outline from a collection of points following the concavity

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;
}

• The yellow line looks like a correct convex hull, so I'm not sure what the problem here is. Naturally, since the green shape contains a concavity, that won't be included in the convex hull (which is, by definition, convex). If you want an outline that follows concavities, then you will need to remove the "...using convex hull" from your question, otherwise you have contradictory requirements. Mar 9, 2021 at 1:21
• Thanks @DMGregory, updated Mar 9, 2021 at 1:35
• Do your shapes ever contain... 1) interior points not on the perimeter 2) holes 3) multiple disjoint parts? If the answer to all three is no, the solutions get much simpler. If any of the above can come up, then we need some additional topological information about how the points connect to their adjacent points. Mar 9, 2021 at 1:38
• The answer is no to all three questions Mar 9, 2021 at 2:16
• Then this problem reduces to simply sorting your points clockwise or counterclockwise around your shape, and connecting them with lines in that order. Mar 9, 2021 at 2:20