search

CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
4.87k stars 1.38k forks source link

Incoherent computation of edge weight property maps #933

Closed afabri closed 8 years ago

afabri commented 8 years ago

In <CGAL/boost/graph/properties_Polyhedron_3.h> we produce the squared length as weight of an edge. For a shortest path algorithm it should be the sqrt of this entity, because for a graph which forms a triangle with one edge e1 of length 2 and two edges of length 1.1, with the squared distance as weight we will go the longer way from source(e) to target(e).

The weight computation in the property map for Surface_mesh and OpenMesh produce the sqrt, that is what we do is not even coherent.

In case we go for sqrt everywhere, the question is how to deal with the different kernels. Shall the weight property map systematically return sqrt(to_double(squared_distance(s,t))), or shall it use FT sqrt(FT), and hence only compile with an FT that provide a sqrt function. Or shall we exploit the Algebraic_structure_traits::Has_sqrt to select FT(sqrt(to_double(squared_distance(s,t))))?

sloriot commented 8 years ago

Please update your post, right now I don't get neither your point nor your question

afabri commented 8 years ago

I now systematically use CGAL::approximate_sqrt() for the edge property map. It is implemented in the branch PMP_Epec-GF

lrineau commented 8 years ago

I think that branch PMP_Epec-GF should be turned to a pull-request. Otherwise it is not visible to the release team, and will be forgotten.

sloriot commented 8 years ago

It is #957 I think.

lrineau commented 8 years ago

And also #871. That is complicated:

$ git lg cgal/master..cgal-dev/PMP_Epec-GF 
* 8a9e5eb - (cgal-dev/PMP_Epec-GF) The edge_weight must be the lenth, and not the squared length (3 weeks ago) <Andreas Fabri>
* a57f9a1 - (janetournois/PMP_Epec-GF, refs/pull/957/head) document that fairing is not exact (6 weeks ago) <Jane Tournois>
* a5d9bea - use CGAL::approximate_sqrt(x) to replace CGAL::sqrt(to_double(x)) (6 weeks ago) <Jane Tournois>
* 5534be2 - use compute__face_normals to avoid computing each face normal * its nb of vertices times (6 weeks ago) <Jane Tournois>
* 919a21a - use PMP::compute_vertex_normal instead of duplicate code (6 weeks ago) <Jane Tournois>
* 9100e3f - make a better use of geom_traits in compute_face_normal (6 weeks ago) <Jane Tournois>
* 9fbec4d - fix compilation (extra */ added in comments) (6 weeks ago) <Jane Tournois>
* 5f597a7 - Document where sqrt is done approximately (7 weeks ago) <Andreas Fabri>
* af4c5f0 - (afabri/PMP_Epec-GF, refs/pull/871/head) Use to_double to make it work with Epec (10 weeks ago) <Andreas Fabri>

871 (afabri/PMP_Epec-GF) is an ancestor of #957 (janetournois/PMP_Epec-GF), and the commit at the HEAD of cgal-dev/PMP_Epec-GF is not in any of them.

sloriot commented 8 years ago

I cherry-picked the missing commit in janetournois and removed the branches in cgal-dev and afabri.

871 is now closed and marked as replaced by #957

lrineau commented 8 years ago

Fixed by #957.