138 lines
2.8 KiB
C#
138 lines
2.8 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Drawing;
|
|
using System.Text;
|
|
|
|
namespace DevComponents.DotNetBar.Charts
|
|
{
|
|
// Monotone Chain Convex Hull.
|
|
// It takes O(NlogN) in sorting & O(N) in actual convex hull calc for N points.
|
|
|
|
public static class ConvexHull
|
|
{
|
|
#region GetConvexHull
|
|
|
|
public static Point[] GetConvexHull(Point[] points)
|
|
{
|
|
int n = points.Length;
|
|
|
|
Array.Sort(points, 0, n, new PointComparer());
|
|
|
|
Point[] ans = new Point[2 * n];
|
|
|
|
int k = 0;
|
|
int start = 0;
|
|
|
|
// Bottom hull
|
|
|
|
Point lpt = Point.Empty;
|
|
|
|
for (int i = 0; i < n; i++)
|
|
{
|
|
Point p = points[i];
|
|
|
|
if (PtCompare(p, lpt) == 0)
|
|
continue;
|
|
|
|
lpt = p;
|
|
|
|
while (k - start >= 2)
|
|
{
|
|
Point sp1 = PtSub(p, ans[k - 1]);
|
|
Point sp2 = PtSub(p, ans[k - 2]);
|
|
|
|
if (PtCross(sp1, sp2) <= 0)
|
|
break;
|
|
|
|
k--;
|
|
}
|
|
|
|
ans[k++] = p;
|
|
}
|
|
|
|
k--;
|
|
|
|
// Top hull
|
|
|
|
start = k;
|
|
lpt = Point.Empty;
|
|
|
|
for (int i = n - 1; i >= 0; i--)
|
|
{
|
|
Point p = points[i];
|
|
|
|
if (PtCompare(p, lpt) == 0)
|
|
continue;
|
|
|
|
lpt = p;
|
|
|
|
while (k - start >= 2)
|
|
{
|
|
Point sp1 = PtSub(p, ans[k - 1]);
|
|
Point sp2 = PtSub(p, ans[k - 2]);
|
|
|
|
if (PtCross(sp1, sp2) <= 0)
|
|
break;
|
|
|
|
k--;
|
|
}
|
|
|
|
ans[k++] = p;
|
|
}
|
|
|
|
k--;
|
|
|
|
Point[] hullPoints = new Point[k + 1];
|
|
Array.Copy(ans, hullPoints, k);
|
|
|
|
hullPoints[k] = hullPoints[0];
|
|
|
|
return (hullPoints);
|
|
}
|
|
|
|
#endregion
|
|
|
|
#region PointComparer
|
|
|
|
private class PointComparer : IComparer<Point>
|
|
{
|
|
public int Compare(Point pt1, Point pt2)
|
|
{
|
|
return (ConvexHull.PtCompare(pt1, pt2));
|
|
}
|
|
}
|
|
|
|
#endregion
|
|
|
|
#region PtCompare
|
|
|
|
private static int PtCompare(Point pt1, Point pt2)
|
|
{
|
|
if (pt1.X == pt2.X)
|
|
return (pt1.Y - pt2.Y);
|
|
|
|
return (pt1.X - pt2.X);
|
|
}
|
|
|
|
#endregion
|
|
|
|
#region PtCross
|
|
|
|
private static int PtCross(Point pt1, Point pt2)
|
|
{
|
|
return (pt1.X * pt2.Y - pt1.Y * pt2.X);
|
|
}
|
|
|
|
#endregion
|
|
|
|
#region PtSub
|
|
|
|
private static Point PtSub(Point pt1, Point pt2)
|
|
{
|
|
return (new Point(pt1.X - pt2.X, pt1.Y - pt2.Y));
|
|
}
|
|
|
|
#endregion
|
|
}
|
|
}
|