/* Created by Andrew Woolston on February 2, 2011 for use on http://www.afome.com/ * feel free to use this code for any purpose, but please let me know if you do end * up using the code. I'd love to see where my efforts are being utilized =) Enjoy! */ public List createHullFromPoints(List pointList) { double largestX = double.MinValue; int largestXIndex = 0; double smallestX = double.MaxValue; int smallestXIndex = 0; double largestY = double.MinValue; int largestYIndex = 0; double smallestY = double.MaxValue; int smallestYIndex = 0; for (int i = 0; i < pointList.Count; i++) { if (pointList[i].X < smallestX) { smallestX = pointList[i].X; smallestXIndex = i; } if (pointList[i].X > largestX) { largestX = pointList[i].X; largestXIndex = i; } if (pointList[i].Y < smallestY) { smallestY = pointList[i].Y; smallestYIndex = i; } if (pointList[i].Y > largestY) { largestY = pointList[i].Y; largestYIndex = i; } } List outsidePoints = new List(); outsidePoints.Add(pointList[smallestXIndex]); outsidePoints.Add(pointList[smallestYIndex]); outsidePoints.Add(pointList[largestXIndex]); outsidePoints.Add(pointList[largestYIndex]); AddPointsOutside(pointList[smallestXIndex], pointList[smallestYIndex], outsidePoints.Count - 3, pointList, outsidePoints); AddPointsOutside(pointList[smallestYIndex], pointList[largestXIndex], outsidePoints.Count - 2, pointList, outsidePoints); AddPointsOutside(pointList[largestXIndex], pointList[largestYIndex], outsidePoints.Count - 1, pointList, outsidePoints); AddPointsOutside(pointList[largestYIndex], pointList[smallestXIndex], outsidePoints.Count, pointList, outsidePoints); return outsidePoints; } public int AddPointsOutside(PointF p1, PointF p2, int InsertIndex, List pointList, List outsidePoints) { double largestDistance = 0; int largestDistanceIndex = -1; if (p1.X < p2.X && p1.Y > p2.Y) // Up-right { for (int i = 0; i < pointList.Count; i++) { if (pointList[i].X < p2.X && pointList[i].Y < p1.Y) { double distance = distanceFromPointToSegment(pointList[i], p1, p2); if (distance > largestDistance) { largestDistance = distance; largestDistanceIndex = i; } } } } if (p1.X < p2.X && p1.Y < p2.Y) // Down-right { for (int i = 0; i < pointList.Count; i++) { if (pointList[i].X > p1.X && pointList[i].Y < p2.Y) { double distance = distanceFromPointToSegment(pointList[i], p1, p2); if (distance > largestDistance) { largestDistance = distance; largestDistanceIndex = i; } } } } if (p1.X > p2.X && p1.Y < p2.Y) // Down-left { for (int i = 0; i < pointList.Count; i++) { if (pointList[i].X > p2.X && pointList[i].Y > p1.Y) { double distance = distanceFromPointToSegment(pointList[i], p1, p2); if (distance > largestDistance) { largestDistance = distance; largestDistanceIndex = i; } } } } if (p1.X > p2.X && p1.Y > p2.Y) // Up-Left { for (int i = 0; i < pointList.Count; i++) { if (pointList[i].X < p1.X && pointList[i].Y > p2.Y) { double distance = distanceFromPointToSegment(pointList[i], p1, p2); if (distance > largestDistance) { largestDistance = distance; largestDistanceIndex = i; } } } } if (largestDistanceIndex == -1) return 0; else { outsidePoints.Insert(InsertIndex, pointList[largestDistanceIndex]); int added = 1 + AddPointsOutside(p1, pointList[largestDistanceIndex], InsertIndex, pointList, outsidePoints); return added + AddPointsOutside(pointList[largestDistanceIndex], p2, InsertIndex + added, pointList, outsidePoints); } } //p0 is the point, p1 and p2 define the segment public double distanceFromPointToSegment(PointF p0, PointF p1, PointF p2) { double numerator = (p2.X - p1.X) * (p1.Y - p0.Y) - (p1.X - p0.X) * (p2.Y - p1.Y); // exclude the absolute value so we know which side of the line it's on double denominator = Math.Pow(p2.X - p1.X, 2d) + Math.Pow(p2.Y - p1.Y, 2d); // exclude the sqrt function - we don't care about actual distances, just which one is furthest. return numerator / denominator; }