CGAL users discussion list

[TONG FU <>]

Thank you for your explanation!

2017-06-19 10:11 GMT+02:00 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>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss