Creating the smallest possible rectangle around 2D AutoCAD geometry using .NET

There was a follow-up comment on this previous post, requesting that it also create a rectangular boundary around selected geometry. This is a much simpler problem to solve that dealing with a minimum enclosing circle, so I was happy enough to oblige. 🙂

Rather than duplicate code from the previous implement, I went ahead and generalised it to contain a core set of functions that get called from different commands: MEC in the existing case where circular boundaries are required and MER for the new case of a rectangular polyline boundary.

I've also adjusted the prompts and code to be more general – including renaming the system variable to ENCLOSINGBOUNDARYBUFFER, although I only tested via the fallback USERI1 variable – and it all seems to work as expected.

Here's the updated C# code:

using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Runtime;
using Autodesk.AutoCAD.Geometry;
using System.Collections.Generic;
using System.Linq;
using System;
 
namespace MinimumEnclosingBoundary
{
  public class Commands
  {
    [CommandMethod("MER", CommandFlags.UsePickSet)]
    public void MinimumEnclosingRectangle()
    {
      MinimumEnclosingBoundary(false);
    }
 
    [CommandMethod("MEC", CommandFlags.UsePickSet)]
    public void MinimumEnclosingCircle()
    {
      MinimumEnclosingBoundary();
    }
 
    public void MinimumEnclosingBoundary(
      bool circularBoundary = true
    )
    {
      Document doc =
          Application.DocumentManager.MdiActiveDocument;
      Database db = doc.Database;
      Editor ed = doc.Editor;
 
      // Ask user to select entities
 
      PromptSelectionOptions pso =
        new PromptSelectionOptions();
      pso.MessageForAdding = "\nSelect objects to enclose: ";
     

; pso.AllowDuplicates = false;
      pso.AllowSubSelections = true;
      pso.RejectObjectsFromNonCurrentSpace = true;
      pso.RejectObjectsOnLockedLayers = false;
 
      PromptSelectionResult psr = ed.GetSelection(pso);
      if (psr.Status != PromptStatus.OK)
        return;
 
      bool oneBoundPerEnt = false;
 
      if (psr.Value.Count > 1)
      {
        PromptKeywordOptions pko =
          new PromptKeywordOptions(
            "\nMultiple objects selected: create " +
            "individual boundaries around each one?"
          );
        pko.AllowNone = true;
        pko.Keywords.Add("Yes");
        pko.Keywords.Add("No");
        pko.Keywords.Default = "No";
 
        PromptResult pkr = ed.GetKeywords(pko);
        if (pkr.Status != PromptStatus.OK)
          return;
 
        oneBoundPerEnt = (pkr.StringResult == "Yes");
      }
 
      // There may be a SysVar defining the buffer
      // to add to our radius
 
      double buffer = 0.0;
      try
      {
        object bufvar =
          Application.GetSystemVariable(
            "ENCLOSINGBOUNDARYBUFFER"
          );
        if (bufvar != null)
        {
          short bufval = (s

hort)bufvar;
          buffer = bufval / 100.0;
        }
      }
      catch
      {
        object bufvar =
          Application.GetSystemVariable("USERI1");
        if (bufvar != null)
        {
          short bufval = (short)bufvar;
          buffer = bufval / 100.0;
        }
      }
 
      // Get the current UCS
 
      CoordinateSystem3d ucs =
        ed.CurrentUserCoordinateSystem.CoordinateSystem3d;
 
      // Collect points on the component entities
 
      Point3dCollection pts = new Point3dCollection();
 
      Transaction tr =
        db.TransactionManager.StartTransaction();
      using (tr)
      {
        BlockTableRecord btr =
          (BlockTableRecord)tr.GetObject(
            db.CurrentSpaceId,
            OpenMode.ForWrite
          );
 
        for (int i = 0; i < psr.Value.Count; i++)
        {
          Entity ent =
            (Entity)tr.GetObject(
              psr.Value[i].ObjectId,
              OpenMode.ForRead
            );
 
          // Collect the points for each selected entity
 
          Point3dCollection entPts = CollectPoints(tr, ent);
          foreach (Point3d pt in entPts)
          {
   

0;        /*
             * Create a DBPoint, for testing purposes
             * 
            DBPoint dbp = new DBPoint(pt);
            btr.AppendEntity(dbp);
            tr.AddNewlyCreatedDBObject(dbp, true);
             */
 
            pts.Add(pt);
          }
 
          // Create a boundary for each entity (if so chosen) or
          // just once after collecting all the points
 
          if (oneBoundPerEnt || i == psr.Value.Count - 1)
          {
            try
            {
              Entity bnd =
                (circularBoundary ?
                  CircleFromPoints(pts, ucs, buffer) :
                  RectangleFromPoints(pts, ucs, buffer)
                );
              btr.AppendEntity(bnd);
              tr.AddNewlyCreatedDBObject(bnd, true);
            }
            catch
            {
              ed.WriteMessage(
                "\nUnable to calculate enclosing boundary."
              );
            }
 
            pts.Clear();
          }
        }
 
        tr.Commit();
      }
    }
 
    private Point3dCollection CollectPoints(
      Transaction tr, Entity ent
    )
    {
      // The collection of points to populate and return
 
      Point3dCollection pts = new Point3dCollection();
 
      // We'll start by checking a block reference for
      // attributes, getting their bounds and adding
  

;    // them to the point list. We'll still explode
      // the BlockReference later, to gather points
      // from other geometry, it's just that approach
      // doesn't work for attributes (we only get the
      // AttributeDefinitions, which don't have bounds)
 
      BlockReference br = ent as BlockReference;
      if (br != null)
      {
        foreach (ObjectId arId in br.AttributeCollection)
        {
          DBObject obj = tr.GetObject(arId, OpenMode.ForRead);
          if (obj is AttributeReference)
          {
            AttributeReference ar = (AttributeReference)obj;
            ExtractBounds(ar, pts);
          }
        }
      }
 
      // If we have a curve - other than a polyline, which
      // we will want to explode - we'll get points along
      // its length
 
      Curve cur = ent as Curve;
      if (cur != null &&
          !(cur is Polyline ||
            cur is Polyline2d ||
            cur is Polyline3d))
      {
        // Two points are enough for a line, we'll go with
        // a higher number for other curves
 
        int segs = (ent is Line ? 2 : 20);
 
        double param = cur.EndParam - cur.StartParam;
        for (int i = 0; i < segs; i++)
   

     {
          try
          {
            Point3d pt =
              cur.GetPointAtParameter(
                cur.StartParam + (i * param / (segs - 1))
              );
            pts.Add(pt);
          }
          catch { }
        }
      }
      else if (ent is DBPoint)
      {
        // Points are easy
 
        pts.Add(((DBPoint)ent).Position);
      }
      else if (ent is DBText)
      {
        // For DBText we use the same approach as
        // for AttributeReferences
 
        ExtractBounds((DBText)ent, pts);
      }
      else if (ent is MText)
      {
        // MText is also easy - you get all four corners
        // returned by a function. That said, the points
        // are of the MText's box, so may well be different
        // from the bounds of the actual contents
 
        MText txt = (MText)ent;
        Point3dCollection pts2 = txt.GetBoundingPoints();
        foreach (Point3d pt in pts2)
        {
          pts.Add(pt);
        }
      }
      else if (ent is Face)
      {
        Face f = (Face)ent;
        try
        {
          for (short i = 0; i < 4; i++)
          {
            pts.Add(f.GetVertexAt(i));
          }
        }
        catch { }
      }
      else if (ent is Solid)
      {
        Solid sol = (Solid)ent;
        try
        {
          for (short i = 0; i < 4; i++)
          {
            pts.Add(sol.GetPointAt(i));
          }
        }
        catch { }
      }
      else
      {
        // Here's where we attempt to explode other types
        // of object
 
        DBObjectCollection oc = new DBObjectCollection();
        try
        {
          ent.Explode(oc);
          if (oc.Count > 0)
          {
            foreach (DBObject obj in oc)
            {
              Entity ent2 = obj as Entity;
              if (ent2 != null && ent2.Visible)
              {
                foreach (Point3d pt in CollectPoints(tr, ent2))
                {
                  pts.Add(pt);
                }
              }
              obj.Dispose();
            }
          }
        }
        catch { }
      }
      return pts;
    }
 
    private void ExtractBounds(
      DBText txt, Point3dCollection pts
    )
    {
      // We have a special approach for DBText and
      // AttributeReference objects, as we want to get
      // all four corners of the bounding box, even
      // when the text or the containing block reference
      // is rotated
 
      if (txt.Bounds.HasValue && txt.Visible)
      {
        // Create a straight version of the text object
        // and copy across all the relevant properties
        // (stopped copying AlignmentPoint, as it would
        // sometimes cause an eNotApplicable error)
 
        // We'll create the text at the WCS origin
        // with no rotation, so it's easier to use its
        // extents
 
        DBText txt2 = new DBText();
        txt2.Normal = Vector3d.ZAxis;
        txt2.Position = Point3d.Origin;
 
        // Other properties are copied from the original
 
        txt2.TextString = txt.TextString;
        txt2.TextStyleId = txt.TextStyleId;
        txt2.LineWeight = txt.LineWeight;
        txt2.Thickness = txt2.Thickness;
        txt2.HorizontalMode = txt.HorizontalMode;
        txt2.VerticalMode = txt.VerticalMode;
        txt2.WidthFactor = txt.WidthFactor;
        txt2.Height = txt.Height;
        txt2.IsMirroredInX = txt2.IsMirroredInX;
        txt2.IsMirroredInY = txt2.IsMirroredInY;
        txt2.Oblique = txt.Oblique;
 
        // Get its bounds if it has them defined
        // (which it should, as the original did)
 
        if (txt2.Bounds.HasValue)
        {
          Point3d maxPt = txt2.Bounds.Value.MaxPoint;
 
          // Place all four corners of the bounding box
          // in an array
 
          Point2d[] bounds =
            new Point2d[] {
              Point2d.Origin,
              new Point2d(0.0, maxPt.Y),
              new Point2d(maxPt.X, maxPt.Y),
              new Point2d(maxPt.X, 0.0)
            };
 
          // We're going to get each point's WCS coordinates
          // using the plane the text is on
 
          Plane pl = new Plane(txt.Position, txt.Normal);
 
          // Rotate each point and add its WCS location to the
          // collection
 
          foreach (Point2d pt in bounds)
          {
            pts.Add(
              pl.EvaluatePoint(
                pt.RotateBy(txt.Rotation, Point2d.Origin)
              )
            );
          }
        }
      }
    }
 
    private Entity RectangleFromPoints(
      Point3dCollection pts, CoordinateSystem3d ucs, double buffer
    )
    {
      // Get the plane of the UCS
 
      Plane pl = new Plane(ucs.Origin, ucs.Zaxis);
 
      // We will project these (possibly 3D) points onto
      // the plane of the current UCS, as that's where
      // we will create our circle
 
      // Project the points onto it
 
      List<Point2d> pts2d = new List<Point2d>(pts.Count);
      for (int i = 0; i < pts.Count; i++)
      {
        pts2d.Add(pl.ParameterOf(pts[i]));
      }
 
      // Assuming we have some points in our list...
 
      if (pts.Count > 0)
      {
        // Set the initial min and max values from the first entry
 
        double minX = pts2d[0].X,
               maxX = minX,
               minY = pts2d[0].Y,
               maxY = minY;
 
        // Perform a single iteration to extract the min/max X and Y
 
        for (int i = 1; i < pts2d.Count; i++)
        {
          Point2d pt = pts2d[i];
          if (pt.X < minX) minX = pt.X;
          if (pt.X > maxX) maxX = pt.X;
          if (pt.Y < minY) minY = pt.Y;
          if (pt.Y > maxY) maxY = pt.Y;
        }
 
        // Our final buffer amount will be the percentage of the
        // smallest of the dimensions
 
        double buf =
          Math.Min(maxX - minX, maxY - minY) * buffer;
 
        // Apply the buffer to our point ordinates
 
        minX -= buf;
        minY -= buf;
        maxX += buf;
        maxY += buf;
 
        // Create the boundary points
 
        Point2d pt0 = new Point2d(minX, minY),
                pt1 = new Point2d(minX, maxY),
                pt2 = new Point2d(maxX, maxY),
                pt3 = new Point2d(maxX, minY);
 
        // Finally we create the polyline
 
        var p = new Polyline(4);
        p.Normal = pl.Normal;
        p.AddVertexAt(0, pt0, 0, 0, 0);
        p.AddVertexAt(1, pt1, 0, 0, 0);
        p.AddVertexAt(2, pt2, 0, 0, 0);
        p.AddVertexAt(3, pt3, 0, 0, 0);
        p.Closed = true;
 
        return p;
      }
      return null;
    }
 
    private Entity CircleFromPoints(
      Point3dCollection pts, CoordinateSystem3d ucs, double buffer
    )
    {
      // Get the plane of the UCS
 
      Plane pl = new Plane(ucs.Origin, ucs.Zaxis);
 
      // We will project these (possibly 3D) points onto
      // the plane of the current UCS, as that's where
      // we will create our circle
 
      // Project the points onto it
 
      List<Point2d> pts2d = new List<Point2d>(pts.Count);
      for (int i = 0; i < pts.Count; i++)
      {
        pts2d.Add(pl.ParameterOf(pts[i]));
      }
 
      // Assuming we have some points in our list...
 
      if (pts.Count > 0)
      {
        // We need the center and radius of our circle
 
        Point2d center;
        double radius = 0;
 
        // Use our fast approximation algorithm to
        // calculate the center and radius of our
        // circle to within 1% (calling the function
        // with 100 iterations gives 10%, calling it
        // with 10K gives 1%)
 
        BadoiuClarksonIteration(
          pts2d, 10000, out center, out radius
        );
 
        // Get our center point in WCS (on the plane
        // of our UCS)
 
        Point3d cen3d = pl.EvaluatePoint(center);
 
        // Create the circle and add it to the drawing
 
        return new Circle(
          cen3d, ucs.Zaxis, radius * (1.0 + buffer)
        );
      }
      return null;
    }
 
    // Algorithm courtesy (and copyright of) Frank Nielsen
    // http://blog.informationgeometry.org/article.php?id=164
 
    public void BadoiuClarksonIteration(
      List<Point2d> set, int iter,
      out Point2d cen, out double rad
    )
    {
      // Choose any point of the set as the initial
      // circumcenter
 
      cen = set[0];
      rad = 0;
 
      for (int i = 0; i < iter; i++)
      {
        int winner = 0;
        double distmax = (cen - set[0]).Length;
 
        // Maximum distance point
 
        for (int j = 1; j < set.Count; j++)
        {
          double dist = (cen - set[j]).Length;
          if (dist > distmax)
          {
            winner = j;
            distmax = dist;
          }
        }
        rad = distmax;
 
        // Update
 
        cen =
          new Point2d(
            cen.X + (1.0 / (i + 1.0)) * (set[winner].X - cen.X),
            cen.Y + (1.0 / (i + 1.0)) * (set[winner].Y - cen.Y)
          );
      }
    }
  }
}
 
 

Here's the MER command in action, using a 15% boundary and choosing to create individual boundaries for each object:

16 responses to “Creating the smallest possible rectangle around 2D AutoCAD geometry using .NET”

Jeremy Tammik

November 5, 2012 at 6:17 pm

Hi Kean.

To find the bounding box in 2D, I should think that Graham's scan is significantly more efficient and above all precise, with no iteration required, than the algorithm you are using:

en.wikipedia.org/wiki/Graham_scan

Cheers, Jeremy.

Kean Walmsley

November 5, 2012 at 6:35 pm

Hi Jeremy,

Which algorithm do you mean: the one for the circular or rectangular boundaries?

As far as I can tell you need to sort the points as part of the Grahan scan algorithm, so it's not clear what I'd be gaining, performance-wise (I don't need the convex hull for the rectangular boundary - just the min and max in X and Y).

Please respond by email - I'll follow up with a comment to summarise the exchange (assuming there's something further of value).

Cheers,

Kean

Kean Walmsley

November 5, 2012 at 8:11 pm

Just to close this off... it turned out it didn't make sense to do a Graham scan, but the discussion did highlight that I'd left in a slightly lazy bit of code that used LINQ to iterate the list of points four times to get the min/max coordinates.

I've now switched back to a good old for loop to do that in a single pass.

Kean

Gaston Nunez

November 5, 2012 at 9:23 pm

Hi Kean:

Why not a Extents3d structure, add points to it and get the min/max points?, or I'm missing something?

Gaston Nunez

Kean Walmsley

November 5, 2012 at 9:46 pm

Hi Gaston,

Mainly because we're not actually interested in the 3D extents: the code projects points (which may or may not be 3D) onto the plane of the UCS, and then takes their 2D extents relative to that. I suppose we could have made something work via the Extents3d object (Extents2d doesn't offer the same capabilities) but it seemed better to do it this way.

Regards,

Kean

Anonymoose

November 12, 2012 at 5:39 am

"but the discussion did highlight that I'd left in a slightly lazy bit of code that used LINQ to iterate the list of points four times to get the min/max coordinates."

Actually, the LINQ Aggregate() method was designed to solve precisely that type of problem. And as a bonus, if you give it the result of calling AsParallel() on the input sequence, it will produce a result in about 1/3 the time that the good old sequential 'for' loop requires.

Kean Walmsley

November 12, 2012 at 11:50 am

Ah good. I suspected there was a better LINQ (or PLINQ) call for this.

Thanks, Tony.

Kean

Anonymoose

November 13, 2012 at 1:05 am

"And as a bonus, if you give it the result of calling AsParallel() on the input sequence, it will produce a result in about 1/3 the time that the good old sequential 'for' loop requires."

Oops, sorry if that was a bit presumptuous, but that performance gain assumes one has 4 or more CPU or cores that are not busy.

Lambros Kaliakatsos

June 28, 2013 at 1:43 pm

Hi Kean,

It's been a useful post and I've worked with the code for DBText.

I noticed that the ExtractBounds ignore the IsMirroredInX & IsMirroredInY properties.

Since these properties are already taken into consideration into the Bounds property, it's pretty easy to implement them with a couple of modifications:

private static void ExtractBounds(DBText txt, Point3dCollection pts)
{
...
txt2.IsMirroredInX = txt.IsMirroredInX;
txt2.IsMirroredInY = txt.IsMirroredInY;
...
Point3d maxPt = txt2.Bounds.Value.MaxPoint;
Point3d minPt = txt2.Bounds.Value.MinPoint;

Point2d[] bounds = new Point2d[] {new Point2d(minPt.X, minPt.Y),new Point2d(minPt.X, maxPt.Y),new maxPt.X, maxPt.Y),new Point2d(maxPt.X, minPt.Y)};
...
}

The rotation should still be based on Point.Origin.

Regards,

Lambros

Kean Walmsley

June 28, 2013 at 5:28 pm

Hi Lambros,

Interesting - thank you for the information.

Regards,

Kean

Lambros Kaliakatsos

July 2, 2013 at 9:16 pm

You're welcome Kean.

Thank you for all the valuable information you share in this blog.

- Lambros

Eric Van Dorpe

October 23, 2013 at 8:56 am

Hi Kean,

I found trough google this page. I would like to use this. But I forgot how to add it to my 2011 ACAD version. Can you tell me how?

Thx.

Kean Walmsley

October 23, 2013 at 9:09 am

Hi Eric,

You need to copy & paste the source code into Visual C# Express (or Visual Studio, if you have it), inside a Class Library project, then add a few project references (see here for more info) before building a .DLL you can NETLOAD into AutoCAD.

I hope this helps,

Kean

Alan Capuano

July 24, 2015 at 11:42 pm

Hi everyone,

Something similar could have been done with the Curve2d.BoundBlock Property, rigth?
Then you'd be able to get the min/max results, and would be able to draw the rectangle.

1. Kean Walmsley
  
  July 27, 2015 at 10:38 am
  
  It depends on what geometry you're working with, of course. But if you're working with the subset that implement that property, then yes.
  
  Kean
  
Thomas Longnecker

August 25, 2018 at 2:24 pm

Kean,

Once again I find myself indebted to you. Thank you!

Longnecker