Sorting an AutoCAD Point2dCollection or Point3dCollection using .NET

Thanks to Virupaksha Aithal, from DevTech India, for providing the technical response to an ADN member than inspired this post.

When working with the Point2d and Point3d objects from AutoCAD's .NET API it's common to use the in-built collection types, Point2dCollection and Point3dCollection. Neither of these objects provides the capability to sort their contents (and, in any case, sorting would mean different things to different people when it comes to containers of objects with multiple data entries).

So how can you sort one of these collections?

The answer is fairly straightforward: you convert them to a .NET array, sort them using standard .NET capabilities and then recreate an AutoCAD collection.

The below C# code does this for collections of both Point2d and Point3d objects.

using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.EditorInput;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;
using System.Collections.Generic;
using System;
 
namespace PointSort
{
  internal class sort2dByX : IComparer<Point2d>
  {
    public static bool IsZero(double a)
    {
      return Math.Abs(a) < Tolerance.Global.EqualPoint;
    }
 
    public static bool IsEqual(double a, double b)
    {
      return IsZero(b - a);
    }
 
    public int Compare(Point2d a, Point2d b)
    {
      if (IsEqual(a.X, b.X)) return 0; // ==
      if (a.X < b.X) return -1; // <
      return 1; // >
    }
  }
 
  internal class sort3dByX : IComparer<Point3d>
  {
    public static bool IsZero(double a)
    {
      return Math.Abs(a) < Tolerance.Global.EqualPoint;
    }
 
    public static bool IsEqual(double a, double b)
    {
      return IsZero(b - a);
    }
 
    public int Compare(Point3d a, Point3d b)
    {
      if (IsEqual(a.X, b.X)) return 0; // ==
      if (a.X < b.X) return -1; // <
      return 1; // >
    }
  }
 
  public class Commands
  {
    private double DeNormalize(double a, double max)
    {
      // Random numbers are from 0 to 1.0, so we
      // multiply it out to be within our range
      // (this will create a value from -max to max)
 
      return (2 * a - 1) * max;
    }
 
    public Point2d Random2dPoint(Random rnd, double max)
    {
      double x = rnd.NextDouble(),
            y = rnd.NextDouble();
 
      return new Point2d(
        DeNormalize(x, max),
        DeNormalize(y, max)
      );
    }
 
    public Point3d Random3dPoint(Random rnd, double max)
    {
      double x = rnd.NextDouble(),
            y = rnd.NextDouble(),
            z = rnd.NextDouble();
 
      return new Point3d(
        DeNormalize(x, max),
        DeNormalize(y, max),
        DeNormalize(z, max)
      );
    }
 
    public Point2dCollection Random2dPoints(int num, double max)
    {
      Point2dCollection pts = new Point2dCollection(num);
      Random rnd = new Random();
      for (int i = 0; i < num; i++)
      {
        pts.Add(Random2dPoint(rnd, max));
      }
      return pts;
    }
 
    public Point3dCollection Random3dPoints(int num, double max)
    {
      Point3dCollection pts = new Point3dCollection();
      Random rnd = new Random();
      for (int i = 0; i < num; i++)
      {
        pts.Add(Random3dPoint(rnd, max));
      }
      return pts;
    }
 
    public void PrintPoints(Editor ed, Point2dCollection pts)
    {
      foreach (Point2d pt in pts)
      {
        ed.WriteMessage("{0}\n", pt);
      }
    }
 
    public void PrintPoints(Editor ed, Point3dCollection pts)
    {
  

;    foreach (Point3d pt in pts)
      {
        ed.WriteMessage("{0}\n", pt);
      }
    }
 
    [CommandMethod("PTS")]
    public void PointSort()
    {
      Document doc =
          Application.DocumentManager.MdiActiveDocument;
      Editor ed = doc.Editor;
 
      Point2dCollection pts2d = Random2dPoints(20, 1000.0);
      Point2d[] raw = pts2d.ToArray();
      Array.Sort(raw, new sort2dByX());
      Point2dCollection sorted2d = new Point2dCollection(raw);
 
      ed.WriteMessage("\n2D points before sort:\n\n");
      PrintPoints(ed, pts2d);
      ed.WriteMessage("\n\n2D points after sort:\n\n");
      PrintPoints(ed, sorted2d);
 
      Point3dCollection pts3d = Random3dPoints(20, 1000.0);
      Point3d[] raw3d = new Point3d[pts3d.Count];
      pts3d.CopyTo(raw3d, 0);
      Array.Sort(raw3d, new sort3dByX());
      Point3dCollection sorted3d = new Point3dCollection(raw3d);
 
      ed.WriteMessage("\n3D points before sort:\n\n");
      PrintPoints(ed, pts3d);
      ed.WriteMessage("\n\n3D points after sort:\n\n");
      PrintPoints(ed, sorted3d);
    }
  }
}

Some notes on this implementation:

For the purposes of this example, we're assuming "sorting" means to sort on the X value of each point
- It should be obvious how to change the implementation to use different sort criteria
To test the sorting, we're populating the collections with a set of randomly-generated points
- We create 20 points in each collection, each with coordinates in the range of –1000 to 1000
- I've kept the number of points in each collection low, just to keep the post to a reasonable length and still be able to include the results
Converting to a .NET array is a little different for 2D and 3D collections
- Point2dCollection has the ToArray() method
- Point3dCollection has the CopyTo() method

Something I will say about the above code... It's code like
this that makes me yearn for a more dynamic environment (I'm writing this in "classic", statically-typed C#). There are several duplicate classes with basically the same implementation but taking different types: plenty of code that just feels redundant.

It would be interesting to rework this IronPython, to see what that it brings (or even to see if using the dynamic keyword would help – I should really install VS 2010 and give it a try). This is also exactly the kind of problem that F# excels at solving, so I'll expect I'll be giving that a try, too, before too long, just to see how much code can be ripped out.

Here are some sample results from running the PTS command:

Command: PTS 
2D points before sort:
 
(546.62044884014,333.683370302284)
(273.865409788613,671.008432130799)
(786.237089795171,-664.37283328938)
(-951.588503062533,-221.942868652727)
(-362.490728200642,-93.6347987007512)
(-938.590817124858,-889.46122764119)
(628.55356355596,-180.880018128492)
(485.986099339084,329.109809980313)
(525.820961001246,-659.813289372164)
(-902.095012321181,-931.107034874664)
(683.452251219867,931.710177069395)
(110.748492698534,-899.346025613763)
(47.6774876227963,-794.155224130561)
(-993.500254113926,438.08932389975)
(994.927220044158,-722.431948279232)
(198.020555636855,462.94129894252)
(-693.78015850381,-930.635690656787)
(-330.415913523369,497.267734025264)
(-855.102567866027,951.917634323201)
(520.609316192851,-779.07530860001)
 
 
2D points after sort:
 
(-993.500254113926,438.08932389975)
(-951.588503062533,-221.942868652727)
(-938.590817124858,-889.46122764119)
(-902.095012321181,-931.107034874664)
(-855.102567866027,951.917634323201)
(-693.78015850381,-930.635690656787)
(-362.490728200642,-93.6347987007512)
(-330.415913523369,497.267734025264)
(47.6774876227963,-794.155224130561)
(110.748492698534,-899.346025613763)
(198.020555636855,462.94129894252)
(273.865409788613,671.008432130799)
(485.986099339084,329.109809980313)
(520.609316192851,-779.07530860001)
(525.820961001246,-659.813289372164)
(546.62044884014,333.683370302284)
(628.55356355596,-180.880018128492)
(683.452251219867,931.710177069395)
(786.237089795171,-664.37283328938)
(994.927220044158,-722.431948279232)
 
3D points before sort:
 
(-282.271111981138,909.546242053409,285.631638618946)
(371.393521023632,762.584686168742,-119.380790330181)
(386.957248387373,-908.643945077734,648.815548815213)
(494.069362754966,93.28737999,323.425575775758)
(494.450510244095,586.600064107496,680.753123797827)
(489.99652056489,712.608007580325,660.061542717768)
(132.996848380657,-910.9989078301,-602.627639473708)
(564.335921576403,-454.319581135325,78.9875290724391)
(276.740193961533,837.884722202031,922.783010603293)
(-314.830172487921,370.544476141475,-925.548076594969)
(865.08049995875,-543.389787684842,101.277599624022)
(-267.499718473991,616.808070622761,558.13882665622)
(-782.131620581323,-289.302226756374,373.464381961834)
(832.297310155024,-629.765324122163,523.183570021383)
(614.174030541523,-112.834495079161,366.034026893803)
(-234.866094419205,43.4879246370345,265.665525228561)
(-255.009830582426,195.9628114458,-851.765022544081)
(374.128198891007,532.42736753655,-900.2289231402)
(-385.354406845455,153.392966442459,363.865823188734)
(-793.355890453493,-905.346672937901,924.69996396671)
 
 
3D points after sort:
 
(-793.355890453493,-905.346672937901,924.69996396671)
(-782.131620581323,-289.302226756374,373.464381961834)
(-385.354406845455,153.392966442459,363.865823188734)
(-314.830172487921,370.544476141475,-925.548076594969)
(-282.271111981138,909.546242053409,285.631638618946)
(-267.499718473991,616.808070622761,558.13882665622)
(-255.009830582426,195.9628114458,-851.765022544081)
(-234.866094419205,43.4879246370345,265.665525228561)
(132.996848380657,-910.9989078301,-602.627639473708)
(276.740193961533,837.884722202031,922.783010603293)
(371.393521023632,762.584686168742,-119.380790330181)
(374.128198891007,532.42736753655,-900.2289231402)
(386.957248387373,-908.643945077734,648.815548815213)
(489.99652056489,712.608007580325,660.061542717768)
(494.069362754966,93.28737999,323.425575775758)
(494.450510244095,586.600064107496,680.753123797827)
(564.335921576403,-454.319581135325,78.9875290724391)
(614.174030541523,-112.834495079161,366.034026893803)
(832.297310155024,-629.765324122163,523.183570021383)
(865.08049995875,-543.389787684842,101.277599624022)

Update

Thanks to Dan Smith for provide a refactored version of the code: if you use multiple inheritance – in the case of our "comparer" classes – and generics/LINQ – in the case of the point generation piece – then it's certainly possible to factor out the redundant code in good old C#. (You will have to target .NET Framework 3.5 or higher to get this to build.)

using Autodesk.AutoCAD.ApplicationServices;

using Autodesk.AutoCAD.EditorInput;

using Autodesk.AutoCAD.Geometry;

using Autodesk.AutoCAD.Runtime;

using System.Collections.Generic;

using System.Linq;

using System;

namespace PointSort

{

internal class sortByX

{

    protected static bool IsZero(double a)

    {

      return Math.Abs(a) < Tolerance.Global.EqualPoint;

    }

    protected static bool IsEqual(double a, double b)

    {

      return IsZero(b - a);

    }

    protected int Compare(double aX, double bX)

    {

      if (IsEqual(aX, bX)) return 0; // ==

      if (aX < bX) return -1; // <

      return 1; // >

    }

}

internal class sort2dByX : sortByX, IComparer<Point2d>

{

    public int Compare(Point2d a, Point2d b)

    {

      return base.Compare(a.X, b.X);

    }

}

internal class sort3dByX : sortByX, IComparer<Point3d>

{

    public int Compare(Point3d a, Point3d b)

    {

      return base.Compare(a.X, b.X);

    }

}

public class Commands

{

    private double DeNormalize(double a, double max)

    {

      // Random numbers are from 0 to 1.0, so we

      // multiply it out to be within our range

      // (this will create a value from -max to max)

      return (2 * a - 1) * max;

    }

    public Point2d Random2dPoint(Random rnd, double max)

    {

      double x = rnd.NextDouble(),

            y = rnd.NextDouble();

      return new Point2d(

        DeNormalize(x, max),

        DeNormalize(y, max)

      );

    }

    public Point3d Random3dPoint(Random rnd, double max)

    {

      double x = rnd.NextDouble(),

            y = rnd.NextDouble(),

            z = rnd.NextDouble();

      return new Point3d(

        DeNormalize(x, max),

        DeNormalize(y, max),

        DeNormalize(z, max)

      );

    }

    TPoint[] RandomPoints<TPoint>(

      int num, double max, Func<Random, double, TPoint> generator

    )

    {

      var pts = new TPoint[num];

      var rnd = new Random();

      for (int i = 0; i < num; i++)

      {

        pts[i] = generator(rnd, max);

      }

      return pts;

    }

    public Point2dCollection Random2dPoints(int num, double max)

    {

      var pts = RandomPoints<Point2d>(num, max, Random2dPoint);

      return new Point2dCollection(pts);

    }

    public Point3dCollection Random3dPoints(int num, double max)

    {

      var pts = RandomPoints<Point3d>(num, max, Random3dPoint);

      return new Point3dCollection(pts);

    }

    public void PrintPoints(Editor ed, Point2dCollection pts)

    {

      foreach (Point2d pt in pts)

      {

        ed.WriteMessage("{0}\n", pt);

      }

    }

    public void PrintPoints(Editor ed, Point3dCollection pts)

    {

      foreach (Point3d pt in pts)

      {

        ed.WriteMessage("{0}\n", pt);

      }

    }

    [CommandMethod("PTS")]

    public void PointSort()

    {

      Document doc =

          Application.DocumentManager.MdiActiveDocument;

      Editor ed = doc.Editor;

      Point2dCollection pts2d = Random2dPoints(20, 1000.0);

      Point2d[] raw = pts2d.ToArray();

      Array.Sort(raw, new sort2dByX());

      Point2dCollection sorted2d = new Point2dCollection(raw);

      ed.WriteMessage("\n2D points before sort:\n\n");

      PrintPoints(ed, pts2d);

      ed.WriteMessage("\n\n2D points after sort:\n\n");

      PrintPoints(ed, sorted2d);

      Point3dCollection pts3d = Random3dPoints(20, 1000.0);

      Point3d[] raw3d = new Point3d[pts3d.Count];

      pts3d.CopyTo(raw3d, 0);

      Array.Sort(raw3d, new sort3dByX());

      Point3dCollection sorted3d = new Point3dCollection(raw3d);


    ed.WriteMessage("\n3D points before sort:\n\n");

      PrintPoints(ed, pts3d);

      ed.WriteMessage("\n\n3D points after sort:\n\n");

      PrintPoints(ed, sorted3d);

    }

}

}

It's still more verbose than I'd like, given the relatively low complexity of the problem, so I'll still give IronPython and F# a go to see how they compare, when I get the chance.

Share on X
LinkedIn
WhatsApp
Email
Copy Link

10 responses to “Sorting an AutoCAD Point2dCollection or Point3dCollection using .NET”

J. Daniel Smith

January 14, 2011 at 7:17 pm

"... plenty of code that just feels redundant."

internal class sortByX
{
protected static bool IsZero(double a)
{
return Math.Abs(a) < Tolerance.Global.EqualPoint;
}

protected static bool IsEqual(double a, double b)
{
return IsZero(b - a);
}

protected int Compare(double aX, double bX)
{
if (IsEqual(aX, bX)) return 0; // ==
if (aX < bX) return -1; // <
return 1; // >
}
}

internal class sort2dByX : sortByX, IComparer<point2d>
{
public int Compare(Point2d a, Point2d b)
{
return base.Compare(a.X, b.X);
}
}

internal class sort3dByX : sortByX, IComparer<point3d>
{
public int Compare(Point3d a, Point3d b)
{
return base.Compare(a.X, b.X);
}
}

TPoint[] RandomPoints<tpoint>(int num, double max, Func<random, double,="" tpoint=""> generator)
{
var pts = new TPoint[num];
var rnd = new Random();

for (int i = 0; i < num; i++)
{
pts[i] = generator(rnd, max);
}

return pts;
}

public Point2dCollection Random2dPoints(int num, double max)
{
var pts = RandomPoints(num, max, Random2dPoint);
return new Point2dCollection(pts);
}

public Point3dCollection Random3dPoints(int num, double max)
{
var pts = RandomPoints(num, max, Random3dPoint);
return new Point3dCollection(pts);
}

Jeremy Tammik

January 14, 2011 at 8:37 pm

Hi Kean,

I did actually mention this to Viru as well, but here it is again:

The 2D and 3D point comparers that you present above compare only the X coordinate and simply ignore the Y and Z coordinates. The result is that all points are sorted along the X axis, but the Y and Z axes are ignored.

To make them work more reliably and span the entire 2D plane or 3D space, not just the X axis, I would suggest checking the Y and Z coordinates as well.

Here is an example for 3D points, represented by the Revit API XYZ class, and easily translated to Point2d and Point3d:

const double _eps = 1.0e-9;

public static bool IsZero( double a )
{
return _eps > Math.Abs( a );
}

public static bool IsEqual( double a, double b )
{
return IsZero( b - a );
}

public static int Compare( double a, double b )
{
return IsEqual( a, b ) ? 0 : ( a < b ? -1 : 1 );
}

public static int Compare( XYZ p, XYZ q )
{
int diff = Compare( p.X, q.X );
if( 0 == diff ) {
diff = Compare( p.Y, q.Y );
if( 0 == diff ) {
diff = Compare( p.Z, q.Z );
}
}
return diff;
}

Cheers, Jeremy.

Kean Walmsley

January 14, 2011 at 8:42 pm

Hi Jeremy,

Thanks, but the aim of the code really wasn't to provide a definitive point sorting algorithm. That strikes me as a task-specific issue, so I was quite happy to just show the code needed to sort by X.

Readers of the blog will certainly have other requirements which they can implement, should they need to.

Cheers,

Kean

Chris

January 14, 2011 at 9:21 pm

I'm not sure how this would look in C#, but its a good task for LINQ.

<commandmethod("linq")> _
Public Sub SortTest()

Dim doc As Document = Application.DocumentManager.MdiActiveDocument
Dim ed As Editor = doc.Editor

Dim X As New Point2dCollection
X.Add(New Point2d(0, 5))
X.Add(New Point2d(2, 6))
X.Add(New Point2d(-1, 8))
X.Add(New Point2d(20, 8))
X.Add(New Point2d(5, 2))

Dim Z = From a As Point2d In X Order By a.X Descending

Dim Y As New Point2dCollection(Z.ToArray)

For Each b In Y
ed.WriteMessage(b.X & "," & b.Y & vbNewLine)
Next

End Sub

It essentially makes the sort a two liner. What would probably be best is if there was a .Sort() function added to the Point2dCollection that took an instance of a IComparer.

Kean Walmsley

January 14, 2011 at 9:29 pm

Thanks, Chris.

I need to play around with LINQ some more... this is interesting.

Kean

Chris

January 14, 2011 at 10:38 pm

I just started using it a little while ago myself. Sometimes it can make things too hard to read, but in some cases it can save you a lot of code if you have to do sorting, complex filtering, or creating objects.

Heres a quick little example, it sorts the points, then creates a list of lines connecting them that could be added to a drawing.

Dim Z = (From a As Point2d In X Order By a.X Descending).ToList
Dim L1 = From a As Point2d In Z _
Select P1 = a, P2 = Z.Item(Z.IndexOf(a) + 1) _
Select New Line(New Point3d(P1.X, P1.Y, 0), New Point3d(P2.X, P2.Y, 0)) _
Take Z.Count - 1

Artvegas

May 4, 2012 at 10:26 pm

Good tip for making the output a little cleaner is to use a custom format string.

string format =
"+0000.0000;-0000.0000; 0000.0000";

ed.WriteMessage("
[{0}, {1}, {2}]",
pt.X.ToString(format),
pt.Y.ToString(format),
pt.Z.ToString(format)
);

The output will look like this:

[-1121.1351, -0775.8176, -1086.5035]
[-0877.2471, +0752.0913, +1150.9867]
[-0795.9096, +0163.4927, -0352.9859]
[-0789.7526, -0758.6186, +1242.8648]
[+0319.2778, +1057.0662, -0048.1380]
[+0320.2252, -1190.7591, -0264.5781]
[+0384.9640, -0852.7373, -1143.8729]
[+0697.8685, -0978.0293, +0922.0133]
[+0909.2203, -1181.4823, -0964.9591]
[+1146.2095, -0502.8926, +0835.8155]

Sorted using X coordinates of course 🙂

HTML might not do it justice. In AutoCAD the text is perfectly aligned.

For more info for custom numeric format strings refer to msdn:
msdn.microsoft.com/en-us/library/0c899ak8.aspx

Art

Ben

February 19, 2017 at 1:04 am

hi thx Kean. i generally avoid using autocad collections and stick to lists and ienumerables - is there any benefit of using point3dcollections over them?

1. Kean Walmsley
  
  February 20, 2017 at 6:22 am
  
  Some AutoCAD APIs need these collections, of course (in many cases they were introduced when generics weren't available to all .NET coders).
  
  It really depends on what you're going to end up doing with the data.
  
  Kean
  
Billy Klay

February 18, 2018 at 4:15 pm

Does seem like a lot of code for a simple sort. How about using a DataTable with the following Columns
Point3d (stores the object)
X (stores the X value)
Y (stores the Y value)
Z (stores the Z value)

Set X, Y and Z as a Key to ensure the combination is unique. Then sort the DataTable by which ever columns you so choose.