Topic: Find duplicate points

[pkohut]

And for reference a way in C++/ARX

Code: [Select]

bool operator < (const AcGePoint3d& pt1, const AcGePoint3d& pt2)
{
if (pt1.x == pt2.x)
{
if (pt1.y == pt2.y)
return (pt1.z < pt2.z);
else
return (pt1.y < pt2.y);
}
else
return (pt1.x < pt2.x);
}


Shorten that up...

Code: [Select]

bool operator < (const AcGePoint3d & pt1, const AcGePoint3d & pt2)
{
    AcGeVector3d pt = pt1 - pt2;
    return pt.x < 0.0 || pt.y < 0.0 || pt.z < 0.0;
}

[It's Alive!]

Nice trick Dan

Code: [Select]

            public int GetHashCode(Point3d pnt)
            {
                return (pnt.X.GetHashCode() ^ pnt.Y.GetHashCode() ^ pnt.Z.GetHashCode());
            }

I have the nagging suspicion that this kind of HashCode calculation doesn't quite work in our scenario; it will gladly let false negatives pass, when the delta is actually below the threshold but the coordinates are sufficiently different.

Also, returning a 32 bit int hash from a 64 bit double isn't going to guarantee unique values, let alone 192 bits worth of doubles. Worse yet XOR'ing the hash values reduces the uniqueness even further.
For example: 1 ^ 2 ^ 3 = 0

ps, also from the .Net docs

The default implementation of the GetHashCode method does not guarantee unique return values for different objects. Furthermore, the .NET Framework does not guarantee the default implementation of the GetHashCode method, and the value it returns will be the same between different versions of the .NET Framework. Consequently, the default implementation of this method must not be used as a unique object identifier for hashing purposes.

if you notice, that call is not using the double's value to get generate a hash, but calling the objects GetHashCode() method.

I.e

Code: [Select]

double x = 9.990;
Console.WriteLine(x.GetHashCode().ToString());
prints
126742170

and

Code: [Select]


double x = 1.0;
double y = 2.0;
double z = 3.0;
int hash = x.GetHashCode() ^ y.GetHashCode() ^ z.GetHashCode();
Console.WriteLine(hash.ToString());

1073217536

[It's Alive!]

Oh and classes using IEqualityComparer must override GetHashCode()

[pkohut]

if you notice, that call is not using the double's value to get generate a hash, but calling the objects GetHashCode() method.

Code: [Select]

double x = 1.0;
double y = 2.0;
double z = 3.0;
int hash = x.GetHashCode() ^ y.GetHashCode() ^ z.GetHashCode();
Console.WriteLine(hash.ToString());

Wouldn't matter. The object represents a double value of 64 bits and can't be packed into a 32 bit hash without data loss.

For the XOR part of the problem (not on a Windows box right now) what is the result of x = y = z = 10.0? How about x = 10, y = z = 0.0? I think they might be the same.

[It's Alive!]

if you notice, that call is not using the double's value to get generate a hash, but calling the objects GetHashCode() method.

Code: [Select]

double x = 1.0;
double y = 2.0;
double z = 3.0;
int hash = x.GetHashCode() ^ y.GetHashCode() ^ z.GetHashCode();
Console.WriteLine(hash.ToString());

Wouldn't matter. The object represents a double value of 64 bits and can't be packed into a 32 bit hash without data loss.

For the XOR part of the problem (not on a Windows box right now) what is the result of x = y = z = 10.0? How about x = 10, y = z = 0.0? I think they might be the same.

true that! what would you recomend?

[pkohut]

true that! what would you recomend?

Don't have one. Once looked at an interesting x, y, z encoding technique but never figured out how to get it to work with doubles (works best with whole numbers of limited size). Drawing a blank right now on the name a mathematician the technique is named after. Will post a link in a bit.

[kaefer]

For the XOR part of the problem (not on a Windows box right now) what is the result of x = y = z = 10.0? How about x = 10, y = z = 0.0? I think they might be the same.

Wouldn't matter. It's a false positive, the Equals() override will take care of that.

My concern are the cases where GetHashCode() return differing values, then Equals() won't be called, but would return true if it were.

true that! what would you recomend?

[fixo]

This might be a point of interest, take look
http://www.codewrecks.com/blog/index.php/2011/01/18/linq-distinct-with-lambda

Oleg

[pkohut]

true that! what would you recomend?

Not a recommendation, just providing some prior research into the problem prior to settling on using KD Trees.
Calculating a unique hash for a given 3D point is really about finding a 1D value that represents the point. The mathematician Giuseppe Peano, http://en.wikipedia.org/wiki/Giuseppe_Peano, figured out such a method and it is called Peano Coordinate encoding which has the properties of a nearest neighbor problem.

To encode a 2D point of say, x=1234 and y = 5678 the Peano encoded 1D value is 15263748, which can also be decoded back to the original value. When multiple 2D values are encoded and sorted then they will fall naturally into a nearest neighbor when traversed.

The internal storage of a 64 bit double complicates the implementation of Peano encoding for these types. It may not be practical to use?

[LE3]

Thanks Paul,

I have tried something similar in the past, also by using the isEqualTo() with AcGeTol and none works, excepts the one I posted earlier.

If I try with a small selection of points works, btw.

I did my testings with a 100,000 points and having the same amount of duplicates.

Shorten that up...

Code: [Select]

bool operator < (const AcGePoint3d & pt1, const AcGePoint3d & pt2)
{
    AcGeVector3d pt = pt1 - pt2;
    return pt.x < 0.0 || pt.y < 0.0 || pt.z < 0.0;
}

[Jeff H]

I saw this and reminded me of this thread and thought this might be a good collection to use for task
SortedSet<T>
- Does not add duplicates
- takes a IComparer in constructor

http://msdn.microsoft.com/en-us/library/dd395024.aspx