Author Topic: Find duplicate points  (Read 14139 times)

0 Members and 1 Guest are viewing this topic.

dann.boy.001

  • Guest
Find duplicate points
« on: January 25, 2011, 03:47:24 AM »
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

  • Mesozoic relic
  • Seagull
  • Posts: 11654
  • class keyThumper<T>:ILazy<T>
Re: Find duplicate points
« Reply #1 on: January 25, 2011, 04:58:01 AM »


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. :)
kdub, kdub_nz in other timelines.
Perfection is not optional.
Everything will work just as you expect it to, unless your expectations are incorrect.
Discipline: None at all.

dann.boy.001

  • Guest
Re: Find duplicate points
« Reply #2 on: January 25, 2011, 06:07:27 AM »


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

  • Guest
Re: Find duplicate points
« Reply #3 on: January 25, 2011, 09:21:47 AM »
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

  • Water Moccasin
  • Posts: 2437
Re: Find duplicate points
« Reply #4 on: January 25, 2011, 10:36:07 AM »
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.
If you are going to fly by the seat of your pants, expect friction burns.

try {GreatPower;}
   catch (notResponsible)
      {NextTime(PlanAhead);}
   finally
      {MasterBasics;}

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Find duplicate points
« Reply #5 on: January 25, 2011, 04:05:10 PM »
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++;
                }
            }
        }
« Last Edit: January 26, 2011, 03:04:49 AM by gile »
Speaking English as a French Frog

kaefer

  • Guest
Re: Find duplicate points
« Reply #6 on: January 25, 2011, 05:43:06 PM »
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

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Find duplicate points
« Reply #7 on: January 25, 2011, 05:49:11 PM »
Quote
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.
Speaking English as a French Frog

Jeff H

  • Needs a day job
  • Posts: 6150
Re: Find duplicate points
« Reply #8 on: January 25, 2011, 06:36:50 PM »
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

  • Bull Frog
  • Posts: 305
  • CAD Programmer
Re: Find duplicate points
« Reply #9 on: January 25, 2011, 07:02:10 PM »
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);
}


It's amazing what you can do when you don't know what you can't do.
CAD Programming Solutions

Jeff H

  • Needs a day job
  • Posts: 6150
Re: Find duplicate points
« Reply #10 on: January 25, 2011, 07:41:31 PM »
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");
                }

            }
           
        }
« Last Edit: January 25, 2011, 07:48:07 PM by Jeff H »

Jeff H

  • Needs a day job
  • Posts: 6150
Re: Find duplicate points
« Reply #11 on: January 25, 2011, 08:46:48 PM »
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

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Find duplicate points
« Reply #12 on: January 26, 2011, 03:45:14 AM »
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;
        }
Speaking English as a French Frog

Jeff H

  • Needs a day job
  • Posts: 6150
Re: Find duplicate points
« Reply #13 on: January 26, 2011, 04:09:37 AM »
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

  • Guest
Re: Find duplicate points
« Reply #14 on: January 26, 2011, 06:50:16 AM »
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.