Skip to content

Instantly share code, notes, and snippets.

@teocomi
Last active December 12, 2018 09:55
Show Gist options
  • Save teocomi/9265e52f5c66fa4204c6416b6dd16d71 to your computer and use it in GitHub Desktop.
Save teocomi/9265e52f5c66fa4204c6416b6dd16d71 to your computer and use it in GitHub Desktop.
Calculates the convex hull from a given list of Revit points
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Autodesk.Revit.DB;
namespace Geometry
{
/ /// <summary>
/// Adapted from http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
/// </summary>
public static class ConvexHull
{
private static double cross(XYZ O, XYZ A, XYZ B)
{
return (A.X - O.X) * (B.Y - O.Y) - (A.Y - O.Y) * (B.X - O.X);
}
public static List<XYZ> CalcConvexHull(List<XYZ> points)
{
points.OrderBy(p => p.X).ThenBy(p => p.Y);
var lower = new List<XYZ>();
for (var i = 0; i < points.Count; i++)
{
while (lower.Count >= 2 && cross(lower[lower.Count - 2], lower[lower.Count - 1], points[i]) <= 0)
{
lower.RemoveAt(lower.Count - 1);
}
lower.Add(points[i]);
}
var upper = new List<XYZ>();
for (var i = points.Count - 1; i >= 0; i--)
{
while (upper.Count >= 2 && cross(upper[upper.Count - 2], upper[upper.Count - 1], points[i]) <= 0)
{
upper.RemoveAt(upper.Count - 1);
}
upper.Add(points[i]);
}
upper.RemoveAt(upper.Count - 1);
lower.RemoveAt(lower.Count - 1);
return lower.Concat(upper).ToList();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment