CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

With the current implementation, there is no way to do it better than
inserting each polygon vertex independently, compute the tree, and do 
the query. It is clearly not the optimal solution as the algortihm is
meant to be used for this purpose.

One thing that might speed things up is to only consider a sub-part of
the mesh that should be containing the edge and only compute the tree
on this sub-part. The tricky part being to get the correct sub-part.

Sebastien.

On 06/16/2017 05:16 PM, TONG FU wrote:
> Yes. exactly!
>
> 2017-06-16 17:14 GMT+02:00 Sebastien Loriot (GeometryFactory)
> <
>  
> <mailto:>>:
>
>     Let me rephrase to see if I got your question right:
>     You have an ordered sequence of points on a triangle mesh
>     (defining a polyline) and you would like to get the polyline
>     "segments" on the surface mesh between each consecutive pair of points.
>
>     Am I right?
>
>     Sebastien.
>
>
>     On 06/16/2017 04:54 PM, TONG FU wrote:
>
>         Sorry for my language.
>            I have some polylines on a triangulate surface. I want to
>         find the
>         shortest path between each two point of these polylines. So I
>         use the
>         package  'triangulated surface mesh shortest path'. I set all
>         points on
>         a polyline as a set of source points S.  I have a target point
>         t. If I
>         want to find the shortest path between t and S(3), what should I do?
>
>
>
>         2017-06-16 16:32 GMT+02:00 Sebastien Loriot (GeometryFactory)
>         
> <
>  
> <mailto:>
>         
> <mailto:
>  
> <mailto:>>>:
>
>
>             Could you rephrase your question, because it is not clear to
>         me what you
>             want to know.
>
>             Thanks,
>
>             Sebastien.
>
>             On 06/16/2017 04:11 PM, Tong wrote:
>
>                 Hello,
>
>                 I'm now working on the calculation of shortest path
>         between two
>                 points. I
>                 have a sequence of the source points. Is it possible to
>                 calculate the
>                 shortest path between my target point and one of the source
>                 points (for
>                 example, the third point in this sequence)?
>
>                 Here is my solution. Since each time I remove a source
>         point,
>                 the sequence
>                 tree rebuilds. It takes to much time to get the resultat.
>                        face_iterator fit, fit_end;
>                         boost::tie(fit, fit_end) = faces(polyhedron);
>                         std::vector<face_descriptor> face_vector(fit,
>         fit_end);
>                         const std::size_t nb_source_points = n_vertices;
>                         Traits::Barycentric_coordinate face_location =
>         {{0.25,
>                 0.5, 0.25}};
>                         std::vector<Face_location>
>         faceLocations(nb_source_points,
>                 Face_location(face_descriptor(), face_location));
>                         for (j = 0; j < nb_source_points; ++j)
>                         {
>
>
>         
> faceLocations[j].first=face_vector[boost::lexical_cast<int>(face_id[j])];
>                         }
>                         std::cout<<"construct a shortest path query
>         object and
>                 add a range
>                 of source points..."<<std::endl;
>                         Surface_mesh_shortest_path
>         shortest_paths(polyhedron);
>
>         shortest_paths.add_source_points(faceLocations.begin(),
>                 faceLocations.end());
>                         std::cout&lt;&lt;&quot;add source points for one
>         polyline
>                 finished&quot;&lt;&lt;std::endl;
>                         shortest_paths.source_points_begin();
>
>                         //calculate the shortest path bewteen two points
>                         for(j = 0;j&lt;n_vertices-1;j++){
>
>
>         
> shortest_paths.remove_source_point(shortest_paths.source_points_begin());
>                             face_iterator face_it = faces(polyhedron).first;
>
>
>         std::advance(face_it,boost::lexical_cast&lt;int>(face_id[j]));
>                             // collect the sequence of simplicies
>         crossed by the
>                 shortest
>                 path
>                             Sequence_collector sequence_collector;
>
>
>         shortest_paths.shortest_path_sequence_to_source_points(*face_it,
>                 face_location, sequence_collector);
>                 }
>
>
>                 Thank you.
>
>
>
>                 --
>                 View this message in context:
>
>         
> http://cgal-discuss.949826.n4.nabble.com/Triangulated-Surface-Mesh-Shortest-Paths-tp4662769.html
>         
> <http://cgal-discuss.949826.n4.nabble.com/Triangulated-Surface-Mesh-Shortest-Paths-tp4662769.html>
>
>         
> <http://cgal-discuss.949826.n4.nabble.com/Triangulated-Surface-Mesh-Shortest-Paths-tp4662769.html
>         
> <http://cgal-discuss.949826.n4.nabble.com/Triangulated-Surface-Mesh-Shortest-Paths-tp4662769.html>>
>                 Sent from the cgal-discuss mailing list archive at
>         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
>         <https://sympa.inria.fr/sympa/info/cgal-discuss>
>             <https://sympa.inria.fr/sympa/info/cgal-discuss
>         <https://sympa.inria.fr/sympa/info/cgal-discuss>>
>
>
>
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://sympa.inria.fr/sympa/info/cgal-discuss
>     <https://sympa.inria.fr/sympa/info/cgal-discuss>