120 lines
3.7 KiB
C#
120 lines
3.7 KiB
C#
namespace CandyboxPlugin.Geometry
|
|
{
|
|
public class DefaultRectangle2Algorithm
|
|
{
|
|
public List<IntPoint> FindRectangle2(List<IntPoint> hullPoints)
|
|
{
|
|
//check if no bounding box available
|
|
if (hullPoints.Count <= 1)
|
|
return hullPoints;
|
|
|
|
Rectangle2d minBox = null;
|
|
var minAngle = 0d;
|
|
|
|
//foreach edge of the convex hull
|
|
for (var i = 0; i < hullPoints.Count; i++)
|
|
{
|
|
var nextIndex = i + 1;
|
|
|
|
var current = hullPoints[i];
|
|
var next = hullPoints[nextIndex % hullPoints.Count];
|
|
|
|
|
|
|
|
//min / max points
|
|
var top = double.MinValue;
|
|
var bottom = double.MaxValue;
|
|
var left = double.MaxValue;
|
|
var right = double.MinValue;
|
|
|
|
//get angle of segment to x axis
|
|
var angle = AngleToXAxis(current,next);
|
|
|
|
//rotate every point and get min and max values for each direction
|
|
foreach (var p in hullPoints)
|
|
{
|
|
var rotatedPoint = RotateToXAxis(p, angle);
|
|
|
|
top = Math.Max(top, rotatedPoint.Y);
|
|
bottom = Math.Min(bottom, rotatedPoint.Y);
|
|
|
|
left = Math.Min(left, rotatedPoint.X);
|
|
right = Math.Max(right, rotatedPoint.X);
|
|
}
|
|
|
|
//create axis aligned bounding box
|
|
var box = new Rectangle2d(new IntPoint((int)left, (int)bottom), new IntPoint((int)right, (int)top));
|
|
|
|
if (minBox == null || minBox.Area() > box.Area())
|
|
{
|
|
minBox = box;
|
|
minAngle = angle;
|
|
}
|
|
}
|
|
|
|
//rotate axis algined box back
|
|
var minimalBoundingBox = minBox.Points.Select(p => RotateToXAxis(p, -minAngle)).ToList();
|
|
return minimalBoundingBox;
|
|
}
|
|
/// <summary>
|
|
/// Calculates the angle to the X axis.
|
|
/// </summary>
|
|
/// <returns>The angle to the X axis.</returns>
|
|
/// <param name="s">The segment to get the angle from.</param>
|
|
static double AngleToXAxis(IntPoint a, IntPoint b)
|
|
{
|
|
var delta = a-b;
|
|
return -Math.Atan((float)delta.Y / (float)delta.X);
|
|
}
|
|
|
|
/// <summary>
|
|
/// Rotates vector by an angle to the x-Axis
|
|
/// </summary>
|
|
/// <returns>Rotated vector.</returns>
|
|
/// <param name="v">Vector to rotate.</param>
|
|
/// <param name="angle">Angle to trun by.</param>
|
|
static IntPoint RotateToXAxis(IntPoint v, double angle)
|
|
{
|
|
var newX = v.X * Math.Cos(angle) - v.Y * Math.Sin(angle);
|
|
var newY = v.X * Math.Sin(angle) + v.Y * Math.Cos(angle);
|
|
|
|
return new IntPoint((int)newX, (int)newY);
|
|
}
|
|
}
|
|
public class Rectangle2d
|
|
{
|
|
public IntPoint Location { get; set; }
|
|
|
|
public IntPoint Size { get; set; }
|
|
|
|
public Rectangle2d()
|
|
{
|
|
}
|
|
|
|
public Rectangle2d(IntPoint a, IntPoint c) : this()
|
|
{
|
|
Location = a;
|
|
Size = c - a;
|
|
}
|
|
|
|
public double Area()
|
|
{
|
|
return Size.X * Size.Y;
|
|
}
|
|
|
|
public IntPoint[] Points
|
|
{
|
|
get
|
|
{
|
|
return new[] {
|
|
new IntPoint (Location.X, Location.Y),
|
|
new IntPoint (Location.X + Size.X, Location.Y),
|
|
new IntPoint (Location.X + Size.X, Location.Y + Size.Y),
|
|
new IntPoint (Location.X, Location.Y + Size.Y)
|
|
};
|
|
}
|
|
}
|
|
|
|
|
|
}
|
|
} |