1
\$\begingroup\$

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

Implementation

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;
        }
\$\endgroup\$
7
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory
    Commented Mar 9, 2021 at 1:21
  • \$\begingroup\$ Thanks @DMGregory, updated \$\endgroup\$ Commented Mar 9, 2021 at 1:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory
    Commented Mar 9, 2021 at 1:38
  • \$\begingroup\$ The answer is no to all three questions \$\endgroup\$ Commented Mar 9, 2021 at 2:16
  • \$\begingroup\$ Then this problem reduces to simply sorting your points clockwise or counterclockwise around your shape, and connecting them with lines in that order. \$\endgroup\$
    – DMGregory
    Commented Mar 9, 2021 at 2:20

0

You must log in to answer this question.

Browse other questions tagged .