Topic: Find duplicate points

[dann.boy.001]

Hello,

Does anybody can help me, with some sugestion, how on quickest
way to remove duplicate points from list or point3dcollection...

Best regards,
Danijel
 

[Kerry]

Danijel

My first thought :
declare a new Collection
  Iterate the original collection
    Test if each Point3D exists in the new collection using Autodesk.AutoCAD.Geometry.Point3dCollection.Contains(Point3d value)
    If not there , add the Point3D to the new Collection.


Depending on the tolerance you require for matching you may need to write your own equalsTesting method.

There will be a way to do it with LINQ too, I'm sure.

[dann.boy.001]

Danijel

My first thought :
declare a new Collection
  Iterate the original collection
    Test if each Point3D exists in the new collection using Autodesk.AutoCAD.Geometry.Point3dCollection.Contains(Point3d value)
    If not there , add the Point3D to the new Collection.


Depending on the tolerance you require for matching you may need to write your own equalsTesting method.

There will be a way to do it with LINQ too, I'm sure.

Thank you Kerry!

Your first sugestion is very good, for now it is enough.
It is very fast method, but unfortunately there is not posibility to specify tolerances.

When find more time, I will try to add tolerances...

Best regards,
Danijel

[kaefer]

There will be a way to do it with LINQ too, I'm sure.

It is very fast method, but unfortunately there is not posibility to specify tolerances.

When find more time, I will try to add tolerances...

Hi Danijel,

as Kerry said, of course there is, and with a tolerance too. Take a look at this page: http://msdn.microsoft.com/en-us/library/bb338049.aspx.

Proof of concept in F# follows; alas, how to get a hashcode for this I couldn't grok yet.

Code: [Select]

type MyEqualityComparer(eps) =
    interface System.Collections.Generic.IEqualityComparer<Point3d> with
        member me.Equals(a: Point3d, b: Point3d) =
            a.DistanceTo b < eps
        member me.GetHashCode(pt: Point3d) =
            0
    
let dupPts eps sset =
    let db = acApp.DocumentManager.MdiActiveDocument.Database
    use tr = db.TransactionManager.StartTransaction()

    let pts =
        new Point3dCollection[|
            for so in Seq.cast<SelectedObject> sset do
                let dbp = tr.GetObject(so.ObjectId, OpenMode.ForRead) :?> DBPoint
                yield dbp.Position |]

    let ptsDistinct =
        pts.OfType<Point3d>().Distinct<Point3d>(new MyEqualityComparer(eps))
    
    let res = pts.Count - Seq.length ptsDistinct
    tr.Commit()
    res
Function signature is epsilon: float -> sset: SelectionSet -> int; that means it returns the difference in length between the Point3dCollection and the IEnumerable which hold the distinct values.

Cheers

[dgorsman]

Sort the list by at least one coordinate first (all coordinates for extremely large sets), so as you compare against each point if the test point coordinate is less than (or greater, depending on the sort order) the main point coordinate you can stop searching since all the other points will never match.

[gile]

Hi,

You can try these extension methods


EDIT: corrected code, see below.

EDIT 2: little optimisation

Code: [Select]

        public static void RemoveDuplicate(this Point3dCollection pts)
        {
            pts.RemoveDuplicate(Tolerance.Global);
        }

        public static void RemoveDuplicate(this Point3dCollection pts, Tolerance tol)
        {
            List<Point3d> ptlst = new List<Point3d>();
            for (int i = 0; i < pts.Count; i++)
            {
                ptlst.Add(pts[i]);
            }
            ptlst.Sort((p1, p2) => p1.X.CompareTo(p2.X));
            for (int i = 0; i < ptlst.Count - 1; i++)
            {
                for (int j = i + 1; j < ptlst.Count;)
                {
                    if ((ptlst[j].X - ptlst[i].X) > tol.EqualPoint)
                        break;
                    if (ptlst[i].IsEqualTo(ptlst[j], tol))
                    {
                        pts.Remove(ptlst[j]);
                        ptlst.RemoveAt(j);
                    }
                    else
                        j++;
                }
            }
        }

[kaefer]

Code: [Select]

            ptlst.Sort((p1, p2) => p1.X.CompareTo(p2.X));
            for (int i = 0; i < ptlst.Count - 1; i++)
            {
                if (ptlst[i].IsEqualTo(ptlst[i + 1], tol))
                    pts.Remove(ptlst[i]);
            }
        }

pt1.IsEqualTo(pt2, new Tolerance(1.0, 1.0)) is equal to (pt1 - pt2).Length <= 1.0. That's good, it's circular as well.

Is it just me or can this fail when encountering more than 2 points that have the same X but different Y or Z?
E.g. ((0,0,0)(0,3,0)(0,1,0)) with Tolerance.EqualPoint = 1 may not flag (0,0,0) and (0,1,0) as equal.

[gile]

Is it just me or can this fail when encountering more than 2 points that have the same X but different Y or Z?
E.g. ((0,0,0)(0,3,0)(0,1,0)) with Tolerance.EqualPoint = 1 may not flag (0,0,0) and (0,1,0) as equal.

You're right thorsen, I was just thinking about this and correct the code in my previous post.

[Jeff H]

Since Point3d is a structure could you not just use the Equals method.

Have not tested but equals is overridden and sealed for point3d

[mohnston]

Since you are comparing doubles you *must* convert the value before comparing.
Even if you leave the data type as double you need to round or truncate or ?.

I stole recycled this from StackOverflow

Code: [Select]

internal static double DecimalDouble(double d, int NumberOfPlaces)
{
     double scale = Math.Pow(10, Math.Floor(Math.Log10(Math.Abs(d))) + 1);
     return scale * Math.Round(d / scale, NumberOfPlaces);
}


[Jeff H]

Since Pont3d is a structure Equals seems to work and should check for equality of fields rather than memory location.

This prints duplicate when pnt1 member function Equals passing in pnt2 is called.

Code: [Select]



[CommandMethod("TestDupslicate")]
        public void TestDupslicate()
        {
            Document doc = Application.DocumentManager.MdiActiveDocument;
            Database db = doc.Database;
            Editor ed = doc.Editor;

            Point3dCollection pntcoll = new Point3dCollection();

            Random rdn = new Random();
            for (int i = 0; i <= 10; i++)
            {
                Point3d pnt = new Point3d(rdn.Next(100) + .000001, rdn.Next(100) + .000000001, rdn.Next(100) + .000001);
                pntcoll.Add(pnt);
            }

            Point3d pnt1 = new Point3d(4.000001, 7000000001, 9.000000000000001);
            pntcoll.Add(pnt1);


            Point3d pnt2 = new Point3d(4.000001, 7000000001, 9.000000000000001);

            foreach (Point3d pnt in pntcoll)
            {
                if (pnt.Equals(pnt2))
                {
                   ed.WriteMessage("\nDuplicate");
                }
                else
                {
                    ed.WriteMessage("\nNon-Duplicate");
                }

            }
           
        }

[Jeff H]

That was not a good example .

I have not narrowed down the exact tolerence but

pnt1, pnt2 will print duplicates and pnt3 will print non-duplicate

Code: [Select]

[CommandMethod("TestDupslicate")]
        public void TestDupslicate()
        {
            Document doc = Application.DocumentManager.MdiActiveDocument;
            Database db = doc.Database;
            Editor ed = doc.Editor;

            Point3dCollection pntcoll = new Point3dCollection();


            Point3d pnt1 = new Point3d(4.000001, 7.000000001, 9.000000000000001);
            pntcoll.Add(pnt1);


            Point3d pnt2 = new Point3d(4.000001, 7.000000001, 9.00000000000001);
            pntcoll.Add(pnt2);

            Point3d pnt3 = new Point3d(4.000001, 7.000000001, 9.000000001);
            pntcoll.Add(pnt3);

            Point3d pnt4 = new Point3d(4.000001, 7.000000001, 9.0000000001);

            foreach (Point3d pnt in pntcoll)
            {
                if (pnt.Equals(pnt4))
                {
                    ed.WriteMessage("\nDuplicate");
                }
                else
                {
                    ed.WriteMessage("\nNon-Duplicate");
                }

            }
           
     
   
           
        }


[gile]

Hi,

I tryed to implement Kerry's algo defining an override extension method for Point3dCollection.Contains() to be used with a Tolerance.

From the tests I made with 100 random point.dwg (from here) it seems to be slower than the solution I posted Reply #5.

Code: [Select]

        public static void RemoveDuplicate2(this Point3dCollection pts, Tolerance tol)
        {
            Point3dCollection tmp = new Point3dCollection();
            for (int i = 0; i < pts.Count; )
            {
                if (tmp.Contains(pts[i], tol))
                    pts.RemoveAt(i);
                else
                {
                    tmp.Add(pts[i]);
                    i++;
                }
            }
        }

        public static bool Contains(this Point3dCollection pts, Point3d pt, Tolerance tol)
        {
            for (int i = 0; i < pts.Count; i++)
            {
                if (pt.IsEqualTo(pts[i], tol))
                    return true;
            }
            return false;
        }

[Jeff H]

Sorry dann.boy.001 ,

gile uses Point3d.IsEqualTo() which takes a tolerance as a parameter and does not create the uncertainty and extra work that my previous post does.

[kaefer]

Code: [Select]

internal static double DecimalDouble(double d, int NumberOfPlaces)
{
     double scale = Math.Pow(10, Math.Floor(Math.Log10(Math.Abs(d))) + 1);
     return scale * Math.Round(d / scale, NumberOfPlaces);
}


I thought I'd give it a try, but then I realized that log10(0.) gives an unholy value.