Hash function for the Plane_3 class

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Hash function for the Plane_3 class

houes
Hello. I have a bunch of Plane_3 objects in std::vector, However, there are
some duplicates among them. I need to eliminate the duplicates.

I thought of two methods:
(1) sort and unique using std. However this requires me to design a
comparator for Plane_3, anyone know what would be a good comparator for
Plane_3 like?
(2) add items into a hashset one by one. However, this requires me to design
a hash function for Plane_3, and I wonder what is a good hash function for
Plane_3.

Efficiency speaking, method (2) would be better, because it take O(n) time,
where n is the number of input Planes. Method (1) takes O(nlogn) due to
sorting.

Therefore, I would like to know what a good hashing function for Plane_3 is
like.

Thank you, guys.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Hash function for the Plane_3 class

Marc Glisse
On Thu, 26 Apr 2018, houes wrote:

> Hello. I have a bunch of Plane_3 objects in std::vector, However, there are
> some duplicates among them. I need to eliminate the duplicates.
>
> I thought of two methods:
> (1) sort and unique using std. However this requires me to design a
> comparator for Plane_3, anyone know what would be a good comparator for
> Plane_3 like?
> (2) add items into a hashset one by one. However, this requires me to design
> a hash function for Plane_3, and I wonder what is a good hash function for
> Plane_3.
>
> Efficiency speaking, method (2) would be better, because it take O(n) time,
> where n is the number of input Planes. Method (1) takes O(nlogn) due to
> sorting.
>
> Therefore, I would like to know what a good hashing function for Plane_3 is
> like.

Numerical issues make this problematic.
Are you using Epick or Epeck?
Are your duplicates copies originating from the same object, or are they
possibly created separately?

--
Marc Glisse

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Hash function for the Plane_3 class

houes
Marc,

Thanks for the reply. I am using Epick.

The planes are created separately. For example, a pentagon in a 3D plane has
5 vertices. I might use any 3 vertices of it to define a 3D plane. Such
planes should be identical. And if there are two such planes, I need to
remove them.

Thanks.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Hash function for the Plane_3 class

Marc Glisse
On Fri, 27 Apr 2018, houes wrote:

> Marc,
>
> Thanks for the reply. I am using Epick.
>
> The planes are created separately. For example, a pentagon in a 3D plane has
> 5 vertices. I might use any 3 vertices of it to define a 3D plane. Such
> planes should be identical. And if there are two such planes, I need to
> remove them.

Well, you are in trouble because of the 'i' in Epick. You constructed a
Plane_3, and even assuming that your points are exactly coplanar (not that
likely), that construction was not exact. Even using the same 3 points in
a different order might yield a slightly different plane.

If we assume that you were lucky and your Plane_3 are equivalent, you
could consider hashing or sorting based on the tuple (p.a()/p.d(),
p.b()/p.d(), p.c()/p.d()) (handle the case d=0 separately, or normalize
differently). Then if you don't play with the rounding mode and don't hit
any x87 weirdness, it may work.

Actually, operator== for PlaneC3 (the base of Plane_3) looks suspicious to
me, I don't see where it handles the fact that the representation is not
canonical (multiplying a, b, c and d by 2 keeps the same plane).

--
Marc Glisse

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Hash function for the Plane_3 class

houes
Marc,

Thank you. I see your point. Epeck might take too much for me, so I choose
Epick.

I used your method to define a comparator for Plane_3. Each plane(a,b,c,d)
is normalized like (a/d,b/d,c/d,1) and a Point_3 is defined by
(a/d,b/d,c/d), I then compared the squared_distance of this point to Origin,
the Plane_3 is smaller if this distance is smaller. Then I sort the array of
Plane_3 using this comparator.

I know this comparison is not accurate, since two plane with the same
to_origin_distance is not necessary the same. After the sorting, planes with
the same to_origin_distance will be grouped together, this including planes
that are not the same. However, in my case, the chance I get a group of
planes that have same to_origin_distance but are different to each other is
low. So after the unique operation, I eliminate quite a lot of identical
planes, although it does not guarantee to eliminate all duplicates.

After the unique operation, I run a brute force method to eliminate left
duplicates planes (basically two nested loops). This process is exact, but
with O(n*n) time complexity. However, I did it after the sorting/unique
which, in my case, greatly reduce n, saves me some time. By the way, I
provide my own Plane_3_equal() function with tolerance to std::unique and in
the later nested loop, so inexact construction is handled.

Demonstration:
input:     A B C A A B D     (A, B, C, D are distinct planes, A and C are of
same to_origin_distance)
sort  :     A A C A B B D
unique:   A C A B D
2loops:   A C B D

This is a workaround method for me. Thanks.



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss