Untitled

using System;
using System.Collections.Generic;
using System.Linq;
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;

public class LargestInscribedRect
{
    // Provided Convex Hull Function (Assume it's implemented elsewhere)
    public static List<Point2d> ComputeHull(List<Point2d> points, double concavity = 0.0, double scaleFactor = 2)
    {
        // Implementation of Concave Hull
        // Assume this function is defined elsewhere and works correctly.
        // Replace this with your actual implementation
        // Placeholder: just return a simple rectangle for now
        if (points.Count < 3) return points;
        double minX = points.Min(p => p.X);
        double minY = points.Min(p => p.Y);
        double maxX = points.Max(p => p.X);
        double maxY = points.Max(p => p.Y);
        return new List<Point2d>
        {
            new Point2d(minX, minY),
            new Point2d(maxX, minY),
            new Point2d(maxX, maxY),
            new Point2d(minX, maxY)
        };
    }

    public static Polyline GetLargestRectangleInsidePolyline(Polyline polyline)
    {
        // 1. Preprocessing: Convex Hull
        List<Point2d> polylinePoints = new List<Point2d>();
        for (int i = 0; i < polyline.NumberOfVertices; i++)
        {
            polylinePoints.Add(polyline.GetPoint2dAt(i));
        }
        List<Point2d> hullPoints = ComputeHull(polylinePoints);

        // 2. Rotating Calipers
        Polyline largestRectangle = RotatingCalipers(hullPoints);

        // 3. Clipping to Original Polygon
        Polyline clippedRectangle = ClipRectangleToPolygon(largestRectangle, polyline);

        return clippedRectangle;
    }

    private static Polyline RotatingCalipers(List<Point2d> hullPoints)
    {
        if (hullPoints.Count < 3)
        {
            // Handle cases where the hull has fewer than 3 points (e.g., a point or a line segment)
            if (hullPoints.Count == 2)
            {
                Polyline linePolyline = new Polyline();
                linePolyline.AddVertexAt(0, hullPoints[0], 0, 0, 0);
                linePolyline.AddVertexAt(1, hullPoints[1], 0, 0, 0);
                return linePolyline;
            }
            else
            {
                return null; // Or handle as appropriate for your application
            }
        }

        double minX = hullPoints.Min(p => p.X);
        double minY = hullPoints.Min(p => p.Y);
        double maxX = hullPoints.Max(p => p.X);
        double maxY = hullPoints.Max(p => p.Y);

        Point2d p1 = new Point2d(minX, minY);
        Point2d p2 = new Point2d(maxX, minY);
        Point2d p3 = new Point2d(maxX, maxY);
        Point2d p4 = new Point2d(minX, maxY);

        Polyline maxRect = new Polyline();
        maxRect.AddVertexAt(0, p1, 0, 0, 0);
        maxRect.AddVertexAt(1, p2, 0, 0, 0);
        maxRect.AddVertexAt(2, p3, 0, 0, 0);
        maxRect.AddVertexAt(3, p4, 0, 0, 0);
        maxRect.Closed = true;

        double maxArea = (maxX - minX) * (maxY - minY);

        double angleIncrement = 0.01; // Adjust for finer/coarser rotation
        for (double angle = 0; angle < Math.PI / 2; angle += angleIncrement)
        {
            List<Point2d> rotatedHull = hullPoints.Select(p => RotatePoint(p, angle, new Point2d((minX + maxX) / 2, (minY + maxY) / 2))).ToList();

            minX = rotatedHull.Min(p => p.X);
            minY = rotatedHull.Min(p => p.Y);
            maxX = rotatedHull.Max(p => p.X);
            maxY = rotatedHull.Max(p => p.Y);

            Point2d rotatedP1 = new Point2d(minX, minY);
            Point2d rotatedP2 = new Point2d(maxX, minY);
            Point2d rotatedP3 = new Point2d(maxX, maxY);
            Point2d rotatedP4 = new Point2d(minX, maxY);

            // Rotate the points back to the original coordinate system
            p1 = RotatePoint(rotatedP1, -angle, new Point2d((minX + maxX) / 2, (minY + maxY) / 2));
            p2 = RotatePoint(rotatedP2, -angle, new Point2d((minX + maxX) / 2, (minY + maxY) / 2));
            p3 = RotatePoint(rotatedP3, -angle, new Point2d((minX + maxX) / 2, (minY + maxY) / 2));
            p4 = RotatePoint(rotatedP4, -angle, new Point2d((minX + maxX) / 2, (minY + maxY) / 2));

            double area = (maxX - minX) * (maxY - minY);

            if (area > maxArea)
            {
                maxArea = area;
                maxRect.SetPointAt(0, p1);
                maxRect.SetPointAt(1, p2);
                maxRect.SetPointAt(2, p3);
                maxRect.SetPointAt(3, p4);
            }
        }

        return maxRect;
    }

    // Helper function to rotate a point around a center
    private static Point2d RotatePoint(Point2d point, double angle, Point2d center)
    {
        double x = center.X + (point.X - center.X) * Math.Cos(angle) - (point.Y - center.Y) * Math.Sin(angle);
        double y = center.Y + (point.X - center.X) * Math.Sin(angle) + (point.Y - center.Y) * Math.Cos(angle);
        return new Point2d(x, y);
    }

    private static Polyline ClipRectangleToPolygon(Polyline rectangle, Polyline polygon)
    {
        // Create Regions from the rectangle and polygon
        Region rectangleRegion = CreateRegionFromPolyline(rectangle);
        Region polygonRegion = CreateRegionFromPolyline(polygon);

        if (rectangleRegion == null || polygonRegion == null)
        {
            // Handle cases where regions could not be created
            return ShrinkRectangleToFit(rectangle, polygon);
        }

        // Perform intersection
        Region clonedRegion = (Region)rectangleRegion.Clone();
        clonedRegion.IntersectWith(polygonRegion);

        // Extract the resulting polyline (if any)
        DBObjectCollection curves = new DBObjectCollection();
        clonedRegion.Explode(curves);

        Polyline clippedRectangle = null;
        foreach (DBObject curve in curves)
        {
            if (curve is Polyline)
            {
                clippedRectangle = (Polyline)curve;
                break;
            }
        }

        if (clippedRectangle != null)
        {
            return clippedRectangle;
        }
        else
        {
            // No intersection found or could not extract polyline, shrink the rectangle until it fits inside
            return ShrinkRectangleToFit(rectangle, polygon);
        }
    }

    // Helper function to create a Region from a Polyline
    private static Region CreateRegionFromPolyline(Polyline polyline)
    {
        if (polyline == null || polyline.Closed == false) return null;

        DBObjectCollection dbObjs = new DBObjectCollection();
        dbObjs.Add(polyline.Clone() as Polyline); // Clone to avoid modifying the original polyline
        DBObjectCollection regions = Region.CreateFromCurves(dbObjs);

        if (regions.Count > 0)
        {
            return regions[0] as Region;
        }

        return null;
    }

    // Function to shrink the rectangle until it fits inside the polygon
    private static Polyline ShrinkRectangleToFit(Polyline rectangle, Polyline polygon)
    {
        double scaleFactor = 0.95; // Shrink by 5% each iteration
        int maxIterations = 20; // Prevent infinite loop
        int iteration = 0;

        while (!IsRectangleInsidePolygon(rectangle, polygon) && iteration < maxIterations)
        {
            rectangle = ScaleRectangle(rectangle, scaleFactor);
            iteration++;
        }

        return rectangle;
    }

    // Helper function to check if a rectangle is fully inside a polygon
    private static bool IsRectangleInsidePolygon(Polyline rectangle, Polyline polygon)
    {
        for (int i = 0; i < rectangle.NumberOfVertices; i++)
        {
            Point2d point = rectangle.GetPoint2dAt(i);
            if (!IsPointInsidePolygon(point, polygon))
            {
                return false;
            }
        }
        return true;
    }

    // Helper function to check if a point is inside a polygon using ray casting
    private static bool IsPointInsidePolygon(Point2d point, Polyline polygon)
    {
        int i, j;
        bool c = false;
        for (i = 0, j = polygon.NumberOfVertices - 1; i < polygon.NumberOfVertices; j = i++)
        {
            Point2d pi = polygon.GetPoint2dAt(i);
            Point2d pj = polygon.GetPoint2dAt(j);
            if (((pi.Y > point.Y) != (pj.Y > point.Y)) &&
                (point.X < (pj.X - pi.X) * (point.Y - pi.Y) / (pj.Y - pi.Y) + pi.X))
            {
                c = !c;
            }
        }
        return c;
    }

    // Helper function to scale a rectangle from its center
    private static Polyline ScaleRectangle(Polyline rectangle, double scaleFactor)
    {
        // Calculate the center of the rectangle
        Point2d center = CalculateRectangleCenter(rectangle);

        // Scale each vertex from the center
        Polyline scaledRectangle = new Polyline();
        for (int i = 0; i < rectangle.NumberOfVertices; i++)
        {
            Point2d vertex = rectangle.GetPoint2dAt(i);
            Point2d scaledVertex = new Point2d(
                center.X + (vertex.X - center.X) * scaleFactor,
                center.Y + (vertex.Y - center.Y) * scaleFactor
            );
            scaledRectangle.AddVertexAt(i, scaledVertex, 0, 0, 0);
        }
        scaledRectangle.Closed = true;
        return scaledRectangle;
    }

    // Helper function to calculate the center of a rectangle
    private static Point2d CalculateRectangleCenter(Polyline rectangle)
    {
        double centerX = 0;
        double centerY = 0;
        for (int i = 0; i < rectangle.NumberOfVertices; i++)
        {
            Point2d vertex = rectangle.GetPoint2dAt(i);
            centerX += vertex.X;
            centerY += vertex.Y;
        }
        return new Point2d(centerX / rectangle.NumberOfVertices, centerY / rectangle.NumberOfVertices);
    }

    [CommandMethod("FindLargestRectangle")]
    public void FindLargestRectangleCommand()
    {
        Document doc = Application.DocumentManager.MdiActiveDocument;
        Editor ed = doc.Editor;

        PromptEntityOptions peo = new PromptEntityOptions("\nSelect a polyline: ");
        peo.SetRejectMessage("\nInvalid selection. Please select a polyline.");
        peo.AddAllowedClass(typeof(Polyline), true);

        PromptEntityResult per = ed.GetEntity(peo);

        if (per.Status != PromptStatus.OK)
        {
            ed.WriteMessage("\nNo polyline selected.");
            return;
        }

        using (Transaction tr = doc.TransactionManager.StartTransaction())
        {
            Polyline polyline = tr.GetObject(per.ObjectId, OpenMode.ForRead) as Polyline;

            if (polyline != null)
            {
                Polyline largestRect = LargestInscribedRect.GetLargestRectangleInsidePolyline(polyline);

                if (largestRect != null)
                {
                    // Add the resulting rectangle to the drawing
                    BlockTable bt = tr.GetObject(doc.Database.BlockTableId, OpenMode.ForRead) as BlockTable;
                    BlockTableRecord btr = tr.GetObject(bt[BlockTableRecord.ModelSpace], OpenMode.ForWrite) as BlockTableRecord;
                    btr.AppendEntity(largestRect);
                    tr.AddNewlyCreatedDBObject(largestRect, true);
                    tr.Commit();
                }
                else
                {
                    ed.WriteMessage("\nCould not find a valid rectangle.");
                }
            }
            else
            {
                ed.WriteMessage("\nSelected object is not a polyline.");
            }
        }
    }
}