Skip to main content
deleted 28 characters in body; edited title
Source Link

Creating outline from a collection of points using Convex hullfollowing the concavity

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 athis solution calledfor Convex Hull. I specifically picked this implementation: https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

However,Edit: I am not getting resultscan't find an algorithm that matchwill find the points(Green) vsconcavity of the region specified in green. The yellow line is the Hull(yellow) from the algorithm amove

Implementation

Creating outline from a collection of points using Convex hull

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

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

Implementation

Source Link

Creating outline from a collection of points using Convex hull

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

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