Triangulated Surface Mesh Shortest Paths

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Triangulated Surface Mesh Shortest Paths

Tong
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<<"add source points for one polyline finished"<<std::endl;
        shortest_paths.source_points_begin();
       
        //calculate the shortest path bewteen two points
        for(j = 0;j<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<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.
Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Sebastien Loriot (GeometryFactory)
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
> 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


Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Tong
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) <[hidden email]>:
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
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



Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Tong
I would like to know is there an iterator to access S(3) so that we can calculate the shortest path between S(3) and the target point t.

2017-06-16 16:54 GMT+02:00 TONG FU <[hidden email]>:
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) <[hidden email]>:
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
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




Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Sebastien Loriot (GeometryFactory)
In reply to this post by Tong
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)
> <[hidden email] <mailto:[hidden email]>>:
>
>     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>
>         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>
>
>
>


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


Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Tong
Yes. exactly!

2017-06-16 17:14 GMT+02:00 Sebastien Loriot (GeometryFactory) <[hidden email]>:
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)
<[hidden email] <mailto:[hidden email]>>:


    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>
        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>





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



Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

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)
> <[hidden email] <mailto:[hidden email]>>:
>
>     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)
>         <[hidden email] <mailto:[hidden email]>
>         <mailto:[hidden email] <mailto:[hidden email]>>>:
>
>
>             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


Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Tong
Thank you for your explanation!

2017-06-19 10:11 GMT+02:00 Sebastien Loriot (GeometryFactory) <[hidden email]>:
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)
<[hidden email] <mailto:[hidden email]>>:

    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)
        <[hidden email] <mailto:[hidden email]>
        <mailto:[hidden email] <mailto:[hidden email]>>>:



            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



Reply | Threaded
Open this post in threaded view
|

Re: Triangulated Surface Mesh Shortest Paths

Julia Fischer


On 20 June 2017 at 16:24, TONG FU <[hidden email]> wrote:
Thank you for your explanation!

2017-06-19 10:11 GMT+02:00 Sebastien Loriot (GeometryFactory) <[hidden email]>:
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)
<[hidden email] <mailto:[hidden email]>>:

    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)
        <[hidden email] <mailto:[hidden email]>
        <mailto:[hidden email] <mailto:[hidden email]>>>:



            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





signature.txt (103K) Download Attachment