MvvmScaffoldFrame48/MvvmScaffoldFrame48.DLL/ImageAlgorithm/BoundRectangleClass.cs

using MvvmScaffoldFrame48.Model.StorageModel.ImageAlgorithm;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace MvvmScaffoldFrame48.DLL.ImageAlgorithm
{
    public class BoundRectangleClass
    {
        /// <summary>
        /// 凸包点集合获取
        /// </summary>
        /// <param name="points">点集合</param>
        /// <returns>凸包点集合</returns>
        public List<Point> ConvexHull(List<Point> points)
        {
            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 BoundingRectangleMdoel RotatingCalipers(List<Point> hull)
        {
            BoundingRectangleMdoel result = null;
            int n = hull.Count;
            if (n == 1)
            {
                return result;
            }
            if (n == 2)
            {
                result = new BoundingRectangleMdoel
                {
                    points = hull,
                    CenterPoint = new Point() { X = (hull[1].X + hull[0].X)/2, Y = (hull[1].Y + hull[0].Y)/2 },
                    Width = 0,
                    Height = Distance(hull[0], hull[1]),
                    Angle = Math.Atan2(hull[1].Y - hull[0].Y, hull[1].X - hull[0].X)
                };
                return result;
            }

            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 centerX = (minX + maxX) / 2;
            int centerY = (minY + maxY) / 2;

            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)
            };

            result = new BoundingRectangleMdoel
            {
                points = rectangle,
                CenterPoint = RotatePoint(new Point() { X = centerX, Y = centerY }, angle),
                Width = width,
                Height = height,
                Angle = angle
            };

            return result;
        }

        /// <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);
        }
    }
}