Convex Hull Algorithm Implementation in Revit

ConvertHullAlgorithm (Convex Hull Algorithm)

Reference

“Computational Geometry” - Introduction: An Example of Convex Hull

Preface

1. The basic logic and concept of the algorithm come from the book “Computational Geometry”. The demos of other chapters will also be implemented and debugged in Revit, hoping to find a suitable implementation direction for each algorithm in Revit.
2. All code is written in C# and debugged in Revit. Some interfaces and judgments utilize the Revit API. If you want to run the algorithm purely, you can modify those API parts to use common libraries.

Algorithm Logic

The algorithm is relatively simple. It primarily involves acquiring the outer boundary of a point set by comparing points with vectors to determine the boundary area.


1. The algorithm sorts all points in the set by their X value from small to large. After sorting, connecting the leftmost point and the rightmost point divides the entire set into two subsets: the upper subset and the lower subset.


2. If a boundary is found, it means the boundary points will enclose all points. Therefore, connecting boundary points pairwise will form the largest vectors, ensuring no other points lie to the right of the vector, which identifies them as boundary points.


3. Through the above steps, we can create a traversal to find the outermost vector and gradually advance towards the maximum value position, thereby outlining the boundary area.


4. After completing the upper subset traversal (advancing to the point with the maximum X value), continue traversing the subset clockwise. At this point, the entire array collection needs to be transposed from large to small, and the reference vector Dir modified to (TheRight - TheLeft).


5. Once the leftmost endpoint and the rightmost endpoint become the start and end points of each other, all boundary traversals are completed.

Code

1. Create a judgment for the directionality of two vectors. Initially, use the vector of the two starting points as the comparison vector. First, traverse the upper subset, which requires checking if the target vector is above or to the left of the secondary vector.

Vector cross product and Z-value judgment are used at the decision position. The principle is: calculating the normal vector allows determining the rotation direction of the vector according to the left-hand rule, thereby determining the positional relationship of the two vectors.


/// <summary>
   /// Compare the vector and if value locate right of original , return true , else false
   /// In the upper hull and lower hull , the vector dot angle will -90 ~ 0 
   /// </summary>
   /// <param name="original"></param>
   /// <param name="value"></param>
   /// <returns></returns>
   public bool IsRight(XYZ original, XYZ value)
   {
       //Dot Product
       var angleValue = original.CrossProduct(value);
       //90°
       if (angleValue.Z >= 0) return true;
       
       return false;
   }

2. Create the traversal function. Here is the pseudo-code from the book and the C# code explanation.

Algorithm CONVEXHULL(P)
Input: Planar point set P
Output: A list consisting of all vertices of CH(P) in clockwise order
1. Sort all points by x-coordinate to get sequence p1, …, pn
2. Add p1 and p2 to Lupper (p1 first)
3. for (i← 3 to n)
4. do Add pi to Lupper
5. while (Lupper has at least three points, and the last three points do not form a right turn)
6. do Remove the second to last vertex from Lupper
7. Add pn and pn-1 to Llower (pn first)
8. for (i← n-2 downto 1)
9. do Add pi to Llower
10. while (Llower has at least three points, and the last three points do not form a right turn)
11. do Remove the second to last vertex from Llower
12. Remove the first and last points from Llower
(To avoid duplicate vertices after connecting upper and lower hulls)
13. Append Llower to Lupper (denote the resulting list as L)
14. return(L)

• Define start point TheLeft, end point TheLast, and point set vertices.
• Determine if the vector of the collection relative to TheLeft lies to the right of fakeDir = TheLast - TheLeft. If the point is to the right of the vector, iterate the point Point data, replace fakeDir, and enter the next loop to check if it’s to the right of fakeDir.
• After the loop ends, add the rightmost point to the collection, thereby identifying all boundary points.

private List<XYZ> GetHullVertices(bool isUp = true)
    {
        var vertices = new List<XYZ>();
        vertices.AddRange(_vertices);
        if (!isUp)
        {
            vertices =  vertices.OrderByDescending(x=>x.X).ToList();
        }
        var theLeft = vertices.First();
        vertices.Remove(theLeft);
        var theLast = vertices.Last();
        var fakeDir = (theLast - theLeft).Normalize();
        var upHullVertices = new List<XYZ>(){theLeft};
        var fakeIndex = 1;
        while (true)
        {
            if (theLeft.IsAlmostEqualWithoutZ(theLast))
            {
                //upHullVertices.Add(theLast);
                break;
            }
            var fakePoint = XYZ.Zero;
            for (int i = 0; i < vertices.Count ; i++)
            {
                var point = vertices[i];
                var dir = (point - theLeft).Normalize();
                //if is dir right to fakeDir , replace value to dir and fakePoint
                if (IsRight(fakeDir, dir))
                {
                    fakeDir = dir;
                    fakePoint = point;
                }
            }
            //remove the theLeft point and replace theLeft to new Point;
            theLeft = fakePoint;
            if (vertices.Remove(theLeft))
            {
                upHullVertices.Add(theLeft);
                fakeDir = (theLast - theLeft).Normalize();
            }
            fakeIndex++;
        }

        return upHullVertices;
    }

Execution Results