CGAL users discussion list

[TroyMcLure <>]

yes, i've read the manual . The part part where it speaks about the topology
constraints. I liked when it speaks about "Optional Named Parameters" (i had
never seen such technique).
Anyway i've read the cgal code, and (even if i didn't understand everything)
, i think i understood the matter. The fact is that edge_collapse uses a
priority queue class from boost, it is  boost::relaxed_heap<>. As far as i
understood relaxed heap is a priority queue algorithm fast but NOT perfect.
It means that some items in the queue have wrong position (non many, but
some). I came to this conclusion cause i've did many automated tests on 
boost::relaxed_heap<>, and i've seen that it violates the priority order for
some item. And if u go to read the document of JAMES R. DRISCOLL, HAROLD N.
GABOW , "Relaxed Heaps: an alternative to fibonacci heaps with application
to parallel computation" , the inventor of relaxed heaps... In the abstract
it says: "A relaxed heap is a type of binomial queue that allows heap order
to be violated ". 
So this means that relaxed heaps are INTENTIONALLY not perfect (but fast).
So this means too that edges are putted in a priority queue (by  increasing
cost, or error), and this priority queue violates priority order a little
bit. 
I made a little change to a cgal header to make the priority queue works
without violations of priority (even if slower).

file: Modifiable_priority_queue.h

erase line 53: 
handle update ( value_type const& v, handle h ) { mHeap.update(v); return h
; }

replace it with this:
#ifndef EXACT_PRIORITY_QUEUE
  handle update ( value_type const& v, handle h ) { mHeap.update(v); return
h ; }
#else
 handle update ( value_type const& v, handle h ) { mHeap.remove(v);
mHeap.push(v);return h ; }
#endif

i tryied (not too long, cause now i have to go out) but works...

the output of the code above, is now ok:

C:\Users\TroyMcLure\Desktop\cgalRel22\build\Debug>esempio zampa2.off
Quitting, cause current cost (0.0100131) is greater then target cost(0.01)
Finished...
28588 edges removed.
751 final edges.
halfedges_with_a_greter_cost = 1502
halfedges_with_a_lower_cost = 0

//

now halfedges_with_a_lower_cost=0 ...

-- 
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/understanding-edge-collapse-tp3248855p3255235.html
Sent from the cgal-discuss mailing list archive at Nabble.com.