CGAL users discussion list

[Monique Teillaud <>]

Hi,

You are using a lot of geometric computations (circumcenter, squared 
length...). This is quite expensive.
Especially since you are probably computing each circumcenter several 
times...

--
Monique Teillaud
http://www.inria.fr/sophia/members/Monique.Teillaud/
INRIA Sophia Antipolis - Méditerranée
Institut National de Recherche en Informatique et Automatique

Le 02/02/14 12:52, jiju peethambaran a écrit :
> Hi,
>
> I use a priority queue for ordering the boundary tetrahedra in Delaunay
> triangulation_3 for further operations. But after the priority queue
> construction, while doing the subsequent operations , the program found to
> show very poor performance. In fact, for a point set of size 25000, it took
> around 12-13 hours on a system with 32GB RAM and 2.3Ghz processor. My
> declaration of priority queue is as follows:
>
> struct Comparator
> {
>    bool operator()(const Cell_handle lhs, const Cell_handle rhs)
>    {
>           K::FT l1=FT();
>           K::FT l2=FT();
>           Tetrahedron_3 tetrahedron1=Tetrahedron_3(lhs->vertex(0)->point(),
>                                 
> lhs->vertex(1)->point(),lhs->vertex(2)->point(),lhs->vertex(3)->point());
>           Point_3 cc1=CGAL::circumcenter(tetrahedron1);
>           Segment_3 s1=Segment_3(cc1,lhs->vertex(0)->point());
>           Tetrahedron_3 tetrahedron2=Tetrahedron_3(rhs->vertex(0)->point(),
>                                 
> rhs->vertex(1)->point(),rhs->vertex(2)->point(),rhs->vertex(3)->point());
>           Point_3 cc2=CGAL::circumcenter(tetrahedron2);
>           Segment_3 s2=Segment_3(cc2,rhs->vertex(0)->point());
>           return s1.squared_length()<s2.squared_length();
>    }
> };
>
> priority_queue&lt;Cell_handle, vector&lt;Cell_handle>, Comparator> pq;
>
> In the while loop, apart from 1 pop(), 3 push() (maximum), I use a
> Cell_circulator for 3 edges of each tetrahedra that is being popped and a
> predicate that use a Cell_iterator that iterates through the incident cells
> of a vertex of the tetrahedron being popped. I came to know that, it takes
> log(pqsize) for pushing and popping elements to and from the priority queue.
> If that is the case, these operations may not be the major contributors to
> the overall time. So is it the other two predicates, along with the number
> of iteration which are degrading the performance of the algorithm?
>
> In struct comparator, I declare tetrahedron_3, Point_3, Segment_3 etc.. each
> time? Will this be a overhead especially in the case of circumcenter
> computation in each iteration, if so, is there any viable alternative for
> this?
>
> Any suggestions, comments are highly appreciated and valued. I'm really
> looking forward to the replies.
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Performance-issues-regarding-Delaunay-3-priority-queue-tp4658738.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.