Revit中实现GH Scan凸包算法

             
public static IEnumerable<XYZ> ConvexHull(IEnumerable<XYZ> points)
        {
            if (points.Count() < 3)
            {
                return points;
            }
            var inputPoints = new List<XYZ>(points);
            var llt = FindLowestThenLeftPoint(inputPoints);
            var res = new List<XYZ>();

            inputPoints = inputPoints.OrderBy(x => (x - llt).Normalize().AngleTo(XYZ.BasisX)).ToList();

            var stack = inputPoints.ToArray();

            var lowPtr = 1;
            var upPtr = 2;

            while (upPtr != stack.Length)
            {
                var p1 = stack[lowPtr];
                var p2 = stack[lowPtr - 1];

                var candidate = stack[upPtr];

                var left = ToLeft(p2, p1, candidate);
                if (left > 0)
                {
                    stack[++lowPtr] = stack[upPtr++];
                }
                else
                {
                    lowPtr--;
                }
            }
            return stack.ToList().Take(lowPtr + 1);
        }

      
private static XYZ FindLowestThenLeftPoint(IEnumerable<XYZ> points)
        {
            var res = points.FirstOrDefault();

            var enumerator = points.GetEnumerator();
            while (enumerator.MoveNext())
            {
                var temp = enumerator.Current as XYZ;
                if (temp.Y < res.Y)
                {
                    res = temp;
                }
                else if (temp.Y == res.Y)
                {
                    res = temp.X < res.X ? temp : res;
                }
            }
            return res;
        }



public static int ToLeft(XYZ p1, XYZ p2, XYZ p3, double eps = 1e-4)
        {
            var area = p1.X * p2.Y - p1.Y * p2.X
                    + p2.X * p3.Y - p2.Y * p3.X
                    + p3.X * p1.Y - p3.Y * p1.X;
            if (Math.Abs(area) < eps)
            {
                return 0;
            }

            return area > 0 ? 1 : -1;
        }

效果如下：