CGAL users discussion list

[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/