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 |
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 |
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 |
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 |
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 |
Free forum by Nabble | Edit this page |