WindowsFormsTest/MinBoundRectangle/Program.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MinBoundRectangle
{
    internal class Program
    {
        static void Main(string[] args)
        {
            BlobMaxRectangle blobMaxRectangle = new BlobMaxRectangle();
            List<RowStartEndCol> InitPints = new List<RowStartEndCol>()
            {
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2201 , EndCol = 2201 },
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2203 , EndCol = 2224 },
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2226 , EndCol = 2226 },
            };
            blobMaxRectangle.ConvexHull(InitPints);
            List<RowStartEndCol> Rows = new List<RowStartEndCol>()
            {
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2201 , EndCol = 2201 },
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2203 , EndCol = 2224 },
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2226 , EndCol = 2226 },
                new RowStartEndCol(){ RowsCol = 2811  ,StartCol = 2232 , EndCol = 2232 },
                new RowStartEndCol(){ RowsCol = 2812  ,StartCol = 2196 , EndCol = 2235 },
                new RowStartEndCol(){ RowsCol = 2813  ,StartCol = 2189 , EndCol = 2243 },
                new RowStartEndCol(){ RowsCol = 2813  ,StartCol = 2245 , EndCol = 2245 },
                new RowStartEndCol(){ RowsCol = 2814  ,StartCol = 2186 , EndCol = 2250 },
                new RowStartEndCol(){ RowsCol = 2815  ,StartCol = 2180 , EndCol = 2258 },
                new RowStartEndCol(){ RowsCol = 2816  ,StartCol = 2179 , EndCol = 2261 },
                new RowStartEndCol(){ RowsCol = 2817  ,StartCol = 2175 , EndCol = 2266 },
                new RowStartEndCol(){ RowsCol = 2818  ,StartCol = 2174 , EndCol = 2269 },
                new RowStartEndCol(){ RowsCol = 2819  ,StartCol = 2172 , EndCol = 2273 },
                new RowStartEndCol(){ RowsCol = 2820  ,StartCol = 2170 , EndCol = 2275 },
                new RowStartEndCol(){ RowsCol = 2821  ,StartCol = 2170 , EndCol = 2280 },
                new RowStartEndCol(){ RowsCol = 2822  ,StartCol = 2170 , EndCol = 2283 },
                new RowStartEndCol(){ RowsCol = 2823  ,StartCol = 2169 , EndCol = 2285 },
                new RowStartEndCol(){ RowsCol = 2824  ,StartCol = 2168 , EndCol = 2287 },
                new RowStartEndCol(){ RowsCol = 2825  ,StartCol = 2168 , EndCol = 2291 },
                new RowStartEndCol(){ RowsCol = 2826  ,StartCol = 2168 , EndCol = 2293 }
            };
            for(int i = 0; i < 10; i++)
            {
                Stopwatch stopwatch = Stopwatch.StartNew();
                var Conveexs = blobMaxRectangle.ConvexHull(Rows);
                var MaxLength = blobMaxRectangle.RotatingCalipers(Conveexs);
                var MinMRectangle = blobMaxRectangle.CalculateMinimumBoundingRectangle(Conveexs);
                stopwatch.Stop();
                Console.WriteLine($"额外计算耗时：{stopwatch.Elapsed}");
                Console.WriteLine(MaxLength);
            }
        }
    }

    // 活动物体跟踪类
    public class RowStartEndCol
    {
        /// <summary>
        /// 当前有效区行数
        /// </summary>
        public long RowsCol { get; set; }
        /// <summary>
        /// 当前行有效区域起始列坐标
        /// </summary>
        public int StartCol { get; set; }
        /// <summary>
        /// 当前行有效区域结束列坐标
        /// </summary>
        public int EndCol { get; set; }
    }

    public class BlobMaxRectangle
    {
        /// <summary>
        /// 凸包点集合获取
        /// </summary>
        /// <param name="Rows"></param>
        /// <returns></returns>
        public List<Point> ConvexHull(List<RowStartEndCol> Rows)
        {
            List<Point> points = Rows.Select(o => new Point(o.StartCol, (int)o.RowsCol)).ToList();
            points.AddRange(Rows.Select(o => new Point(o.EndCol, (int)o.RowsCol)).ToList());
            points = points.OrderBy(o => o.X).ThenBy(o => o.Y).ToList();
            var lower = new List<Point>();
            foreach (var p in points)
            {
                while (lower.Count >= 2 && Cross(lower[lower.Count - 2], lower[lower.Count - 1], p) <= 0)
                    lower.RemoveAt(lower.Count - 1);
                lower.Add(p);
            }

            var upper = new List<Point>();
            for (int i = points.Count - 1; i >= 0; i--)
            {
                var p = points[i];
                while (upper.Count >= 2 && Cross(upper[upper.Count - 2], upper[upper.Count - 1], p) <= 0)
                    upper.RemoveAt(upper.Count - 1);
                upper.Add(p);
            }

            lower.RemoveAt(lower.Count - 1);
            upper.RemoveAt(upper.Count - 1);
            lower.AddRange(upper);
            return lower;
        }

        /// <summary>
        /// 凸包最长长度
        /// </summary>
        /// <param name="hull"></param>
        /// <returns></returns>
        public double RotatingCalipers(List<Point> hull)
        {
            int n = hull.Count;
            if (n == 1) return 0;
            if (n == 2) return Distance(hull[0], hull[1]);

            double maxDist = 0;
            int pointIndex1 = 0;
            int pointIndex2 = 0;

            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if(Distance(hull[i], hull[j]) > maxDist)
                    {
                        maxDist = Distance(hull[i], hull[j]);
                        pointIndex1 = i;
                        pointIndex2 = j;
                    }
                }
            }

            /* 计算最长长度的结果的宽度
            double angle = Math.Atan2(hull[pointIndex2].Y - hull[pointIndex1].Y, hull[pointIndex2].X - hull[pointIndex2].X);
            var rotatedPoints = hull.Select(p => RotatePoint(p, -angle)).ToList();
            // 找到包围盒
            int minX = rotatedPoints.Min(p => p.X);
            int maxX = rotatedPoints.Max(p => p.X);
            int minY = rotatedPoints.Min(p => p.Y);
            int maxY = rotatedPoints.Max(p => p.Y);

            int width = maxX - minX;
            int height = maxY - minY;

            // 构造矩形的四个顶点并旋转回原来的角度
            var rectangle = new List<Point>
            {
                 RotatePoint(new Point(minX, minY), angle),
                 RotatePoint(new Point(maxX, minY), angle),
                 RotatePoint(new Point(maxX, maxY), angle),
                 RotatePoint(new Point(minX, maxY), angle)
            };
            */

            return maxDist;
        }

        /// <summary>
        /// 计算凸包的最小外接矩形
        /// </summary>
        /// <param name="convexHull">凸包顶点列表（按逆时针顺序排列）</param>
        /// <returns>最小外接矩形的四个顶点</returns>
        public List<Point> CalculateMinimumBoundingRectangle(List<Point> convexHull)
        {
            if (convexHull == null || convexHull.Count < 3)
                return null;

            double minArea = double.MaxValue;
            List<Point> minRectangle = null;

            int n = convexHull.Count;

            // 遍历每一条边作为基准边
            for (int i = 0; i < n; i++)
            {
                Point edgeStart = convexHull[i];
                Point edgeEnd = convexHull[(i + 1) % n];

                // 计算当前边的角度
                double angle = Math.Atan2(edgeEnd.Y - edgeStart.Y, edgeEnd.X - edgeStart.X);

                // 将所有点绕原点旋转-angle角度，使当前边与x轴平行
                var rotatedPoints = convexHull.Select(p => RotatePoint(p, -angle)).ToList();

                // 找到包围盒
                int minX = rotatedPoints.Min(p => p.X);
                int maxX = rotatedPoints.Max(p => p.X);
                int minY = rotatedPoints.Min(p => p.Y);
                int maxY = rotatedPoints.Max(p => p.Y);

                // 计算面积
                double area = (maxX - minX) * (maxY - minY);

                // 如果面积更小，则更新最小矩形
                if (area < minArea)
                {
                    minArea = area;

                    // 构造矩形的四个顶点并旋转回原来的角度
                    var rectangle = new List<Point>
                    {
                         RotatePoint(new Point(minX, minY), angle),
                         RotatePoint(new Point(maxX, minY), angle),
                         RotatePoint(new Point(maxX, maxY), angle),
                         RotatePoint(new Point(minX, maxY), angle)
                    };

                    minRectangle = rectangle;
                }
            }

            return minRectangle;
        }

        /// <summary>
        /// 绕原点旋转点
        /// </summary>
        /// <param name="point">待旋转的点</param>
        /// <param name="angle">旋转角度（弧度）</param>
        /// <returns>旋转后的点</returns>
        private static Point RotatePoint(Point point, double angle)
        {
            double cos = Math.Cos(angle);
            double sin = Math.Sin(angle);

            return new Point(
                (int)(point.X * cos - point.Y * sin),
                (int)(point.X * sin + point.Y * cos)
            );
        }

        /// <summary>
        /// 计算点到线段的距离
        /// </summary>
        /// <param name="a">线段点1</param>
        /// <param name="b">线段点2</param>
        /// <param name="c">点三</param>
        /// <returns></returns>
        private double DistanceToLine(Point a, Point b, Point c)
        {
            double area = Math.Abs(Area2(a, b, c));
            double baseLength = Distance(a, b);
            return area / baseLength;
        }

        /// <summary>
        /// 计算向量叉积
        /// </summary>
        /// <param name="o"></param>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        private int Cross(Point o, Point a, Point b) =>
            (a.X - o.X) * (b.Y - o.Y) - (a.Y - o.Y) * (b.X - o.X);

        /// <summary>
        /// 计算三角形面积的两倍
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        private int Area2(Point a, Point b, Point c) =>
            (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);

        /// <summary>
        /// 计算两点间距离
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        private double Distance(Point a, Point b)
        {
            int dx = a.X - b.X;
            int dy = a.Y - b.Y;
            return Math.Sqrt(dx * dx + dy * dy);
        }
    }
}