Skip to content

Instantly share code, notes, and snippets.

@douglasg14b
Last active March 12, 2018 22:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save douglasg14b/98023ded67c61369709e5b82b8ffba46 to your computer and use it in GitHub Desktop.
Save douglasg14b/98023ded67c61369709e5b82b8ffba46 to your computer and use it in GitHub Desktop.
Minimum Bounding Box example I made for receipt parser
using Emgu.CV.Structure;
using ReceiptParser.Models;
using ReceiptParser.Extensions;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ReceiptParser
{
public static class MinimumBoundingBox
{
public static List<Point> Calculate(List<Point> hullPoints)
{
RotatedRectangle minBox = null;
double minAngle = 0d;
for (int i = 0; i < hullPoints.Count; i++)
{
int nextIndex = i + 1;
Point current = hullPoints[i];
Point next = hullPoints[nextIndex % hullPoints.Count];
SegmentF segment = new SegmentF(current, next);
double top = double.MinValue;
double bottom = double.MaxValue;
double left = double.MaxValue;
double right = double.MinValue;
//get angle of segment to x axis
double angle = AngleToXAxis(segment);
foreach(PointF point in hullPoints)
{
PointF rotatedPoint = RotateToXAxis(point, 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);
}
RotatedRectangle box = new RotatedRectangle(new PointF((float)left, (float)bottom), new PointF((float)right, (float)top), angle);
if(minBox == null || minBox.Area > box.Area)
{
minBox = box;
minAngle = angle;
}
}
List<PointF> minBoxRect = minBox.Points;
List<Point> minBoxPoints = new List<Point>();
for(int i = 0; i < 4; i++)
{
minBoxPoints.Add(Point.Round(RotateToXAxis(minBoxRect[i], -minAngle)));
}
return minBoxPoints;
}
/// <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(SegmentF segment)
{
PointF delta = segment.A.Subtract(segment.B);
return -Math.Atan(delta.Y / 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 PointF RotateToXAxis(PointF 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 PointF((float)newX, (float)newY);
}
}
}
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ReceiptParser.Extensions
{
public static class PointExtension
{
public static PointF Subtract(this PointF p1, PointF p2)
{
return new PointF(p1.X - p2.X, p1.Y - p2.Y);
}
}
}
using ReceiptParser.Extensions;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ReceiptParser.Models
{
public class RotatedRectangle
{
/// <summary>
///
/// </summary>
/// <param name="a">Bottom Left</param>
/// <param name="b">Top Right</param>
public RotatedRectangle(PointF a, PointF b, double angle)
{
Location = a;
Size = new Size(Point.Round(b.Subtract(a)));
}
public PointF Location { get; private set; }
public Size Size { get; private set; }
public double Angle { get; private set; }
public List<PointF> Points
{
get
{
return new List<PointF>() {
new PointF(Location.X, Location.Y),
new PointF(Location.X + Size.Width, Location.Y),
new PointF(Location.X + Size.Width, Location.Y + Size.Height),
new PointF(Location.X, Location.Y + Size.Height)
};
}
}
public int Area
{
get
{
return Size.Width * Size.Height;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment