Add information in Triangulation while inserting a range of points

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

Add information in Triangulation while inserting a range of points

sanlingtonCGAL
Hi,

I know the Delaunay and Regular triangulation in CGAL can already add
information to vertices while inserting /a range of points/, as introduced
in
https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay

But it seems that the Triangulation_2/3 (not Delaunay triangulation or
Regular triangulation) can't do that, am I correct?

What I want to do is to construct Triangulation by inserting a range of
points, and each point or vertex would carry extra information, like an
index.
I am using codes like:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef Triangulation::Point                                            
Point;
int main()
{
        std::vector< std::pair<Point, unsigned> > points;
        points.push_back(std::make_pair(Point(0, 0, 0), 0));
        points.push_back(std::make_pair(Point(1, 0, 0), 1));
        points.push_back(std::make_pair(Point(0, 1, 0), 2));
        points.push_back(std::make_pair(Point(0, 0, 1), 3));
        points.push_back(std::make_pair(Point(2, 2, 2), 4));
        points.push_back(std::make_pair(Point(-1, 0, 1), 5));

        Triangulation T(points.begin(), points.end());
        CGAL_assertion(T.number_of_vertices() == 6);
       
        return 0;
}

The above codes are similar to those in the manual document, I just replaced
the Delaunay with Triangulation. But the compiler gave me errors like:

c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
convert argument 1 from '_Ty' to 'const CGAL::Origin &'
1>        with
1>        [
1>            Kernel_=CGAL::Epick
1>        ]
1>        and
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]
1>c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
1>        with
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]


What should I do to add information to point/vertex of a Triangulation while
inserting a range of points?

Thank you.





--
Sent from: http://cgal-discuss.949826.n4.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: Add information in Triangulation while inserting a range of points

MaelRL
Hello,

Insertion of a range of points is basically the insertion of points
one-by-one, except that points are sorted before. Thus, if you're not
inserting a lot of points, the spatial sorting of points will not make a
big difference, and you can simply do something like

for(const My_point_with_info& pt : my_pts)
{
   vertex_handle vh = tr.insert(pt.point());
   vh->info() = pt.info();
}

and you're done.

If you're going to insert a lot of points, you can simply copy the
function that inserts a range with info from DT3 or RT3
(https://github.com/CGAL/cgal/blob/master/Triangulation_3/include/CGAL/Delaunay_triangulation_3.h#L431)
into Triangulation_3.h and it should work almost out of the box.

Best,
Mael

On 13/05/2019 04:25, sanlingtonCGAL wrote:

> Hi,
>
> I know the Delaunay and Regular triangulation in CGAL can already add
> information to vertices while inserting /a range of points/, as introduced
> in
> https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay
>
> But it seems that the Triangulation_2/3 (not Delaunay triangulation or
> Regular triangulation) can't do that, am I correct?
>
> What I want to do is to construct Triangulation by inserting a range of
> points, and each point or vertex would carry extra information, like an
> index.
> I am using codes like:
>
> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> #include <CGAL/Triangulation_3.h>
> #include <CGAL/Triangulation_cell_base_3.h>
> #include <CGAL/Triangulation_vertex_base_with_info_3.h>
> #include <vector>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
> typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
> typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
> typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
> //Use the Fast_location tag. Default or Compact_location works too.
> typedef CGAL::Triangulation_3<K, Tds> Triangulation;
> typedef Triangulation::Point
> Point;
> int main()
> {
> std::vector< std::pair<Point, unsigned> > points;
> points.push_back(std::make_pair(Point(0, 0, 0), 0));
> points.push_back(std::make_pair(Point(1, 0, 0), 1));
> points.push_back(std::make_pair(Point(0, 1, 0), 2));
> points.push_back(std::make_pair(Point(0, 0, 1), 3));
> points.push_back(std::make_pair(Point(2, 2, 2), 4));
> points.push_back(std::make_pair(Point(-1, 0, 1), 5));
>
> Triangulation T(points.begin(), points.end());
> CGAL_assertion(T.number_of_vertices() == 6);
>
> return 0;
> }
>
> The above codes are similar to those in the manual document, I just replaced
> the Delaunay with Triangulation. But the compiler gave me errors like:
>
> c:\program files (x86)\microsoft visual
> studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
> C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
> convert argument 1 from '_Ty' to 'const CGAL::Origin &'
> 1>        with
> 1>        [
> 1>            Kernel_=CGAL::Epick
> 1>        ]
> 1>        and
> 1>        [
> 1>            _Ty=std::pair<Point,unsigned int>
> 1>        ]
> 1>c:\program files (x86)\microsoft visual
> studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
> Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
> 1>        with
> 1>        [
> 1>            _Ty=std::pair<Point,unsigned int>
> 1>        ]
>
>
> What should I do to add information to point/vertex of a Triangulation while
> inserting a range of points?
>
> Thank you.
>
>
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.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: Add information in Triangulation while inserting a range of points

Marc Alexa
In reply to this post by sanlingtonCGAL
Yes, CGAL is sometimes mysterious in what types are accepted by what functions. I agree you’d expect that the insert method for Triangulation_3 should be able to understand how to handle the pairs if Delaunay_triangulation_3 does. But, no. If you insist on using the pairs and are ok with initially getting a Delaunay triangulation, the following code works just fine:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Delaunay_Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef CGAL::Delaunay_triangulation_3<K, Tds> DT;
typedef Triangulation::Point
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

    Triangulation T = DT(points.begin(), points.end());

    CGAL_assertion(T.number_of_vertices() == 6);


return 0;
}

I believe speed-wise there is very little to be gained from not using Delaunay. If you don’t care about what coordinate in space carries which number, you could insert the range of points first and then set the info later. In this case, however, the order of the points you get form the vertex iterator will likely differ from the order in which you provided the points. 



-Marc



On 13. May 2019, at 04:25, sanlingtonCGAL <[hidden email]> wrote:

Hi,

I know the Delaunay and Regular triangulation in CGAL can already add
information to vertices while inserting /a range of points/, as introduced
in
https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay

But it seems that the Triangulation_2/3 (not Delaunay triangulation or
Regular triangulation) can't do that, am I correct?

What I want to do is to construct Triangulation by inserting a range of
points, and each point or vertex would carry extra information, like an
index.
I am using codes like:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef Triangulation::Point                                            
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

Triangulation T(points.begin(), points.end());
CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

The above codes are similar to those in the manual document, I just replaced
the Delaunay with Triangulation. But the compiler gave me errors like:

c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
convert argument 1 from '_Ty' to 'const CGAL::Origin &'
1>        with
1>        [
1>            Kernel_=CGAL::Epick
1>        ]
1>        and
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]
1>c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
1>        with
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]


What should I do to add information to point/vertex of a Triangulation while
inserting a range of points?

Thank you.





--
Sent from: http://cgal-discuss.949826.n4.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: Add information in Triangulation while inserting a range of points

andreas.fabri


We could add an insertion of a range to the Triangulation_3 class, but then no
reshuffling of the points should happen as the insertion order implies which
triangles you have.  This is different for the Delaunay/Regular triangulation
where the resulting triangulation is unique, that is independent from the
insertion order.

andreas


On 5/13/2019 9:01 AM, Marc Alexa wrote:
Yes, CGAL is sometimes mysterious in what types are accepted by what functions. I agree you’d expect that the insert method for Triangulation_3 should be able to understand how to handle the pairs if Delaunay_triangulation_3 does. But, no. If you insist on using the pairs and are ok with initially getting a Delaunay triangulation, the following code works just fine:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Delaunay_Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef CGAL::Delaunay_triangulation_3<K, Tds> DT;
typedef Triangulation::Point
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

    Triangulation T = DT(points.begin(), points.end());

    CGAL_assertion(T.number_of_vertices() == 6);


return 0;
}

I believe speed-wise there is very little to be gained from not using Delaunay. If you don’t care about what coordinate in space carries which number, you could insert the range of points first and then set the info later. In this case, however, the order of the points you get form the vertex iterator will likely differ from the order in which you provided the points. 



-Marc



On 13. May 2019, at 04:25, sanlingtonCGAL <[hidden email]> wrote:

Hi,

I know the Delaunay and Regular triangulation in CGAL can already add
information to vertices while inserting /a range of points/, as introduced
in
https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay

But it seems that the Triangulation_2/3 (not Delaunay triangulation or
Regular triangulation) can't do that, am I correct?

What I want to do is to construct Triangulation by inserting a range of
points, and each point or vertex would carry extra information, like an
index.
I am using codes like:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef Triangulation::Point                                            
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

Triangulation T(points.begin(), points.end());
CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

The above codes are similar to those in the manual document, I just replaced
the Delaunay with Triangulation. But the compiler gave me errors like:

c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
convert argument 1 from '_Ty' to 'const CGAL::Origin &'
1>        with
1>        [
1>            Kernel_=CGAL::Epick
1>        ]
1>        and
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]
1>c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
1>        with
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]


What should I do to add information to point/vertex of a Triangulation while
inserting a range of points?

Thank you.





--
Sent from: http://cgal-discuss.949826.n4.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



-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
Reply | Threaded
Open this post in threaded view
|

Re: Add information in Triangulation while inserting a range of points

andreas.fabri


Let me correct myself, The constructor with a range, as well as the insert function   
with a range exist, and they perform a spatial sort, so we do what I  explained to
better not do in my previous mail.   And I didn't adress at all your request for
dealing with points with info.

We can look into this, but can you tell me why you would construct a Triangulation_3?

best,

andreas

On 5/13/2019 10:10 AM, Andreas Fabri wrote:


We could add an insertion of a range to the Triangulation_3 class, but then no
reshuffling of the points should happen as the insertion order implies which
triangles you have.  This is different for the Delaunay/Regular triangulation
where the resulting triangulation is unique, that is independent from the
insertion order.

andreas


On 5/13/2019 9:01 AM, Marc Alexa wrote:
Yes, CGAL is sometimes mysterious in what types are accepted by what functions. I agree you’d expect that the insert method for Triangulation_3 should be able to understand how to handle the pairs if Delaunay_triangulation_3 does. But, no. If you insist on using the pairs and are ok with initially getting a Delaunay triangulation, the following code works just fine:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Delaunay_Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef CGAL::Delaunay_triangulation_3<K, Tds> DT;
typedef Triangulation::Point
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

    Triangulation T = DT(points.begin(), points.end());

    CGAL_assertion(T.number_of_vertices() == 6);


return 0;
}

I believe speed-wise there is very little to be gained from not using Delaunay. If you don’t care about what coordinate in space carries which number, you could insert the range of points first and then set the info later. In this case, however, the order of the points you get form the vertex iterator will likely differ from the order in which you provided the points. 



-Marc



On 13. May 2019, at 04:25, sanlingtonCGAL <[hidden email]> wrote:

Hi,

I know the Delaunay and Regular triangulation in CGAL can already add
information to vertices while inserting /a range of points/, as introduced
in
https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay

But it seems that the Triangulation_2/3 (not Delaunay triangulation or
Regular triangulation) can't do that, am I correct?

What I want to do is to construct Triangulation by inserting a range of
points, and each point or vertex would carry extra information, like an
index.
I am using codes like:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef Triangulation::Point                                            
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

Triangulation T(points.begin(), points.end());
CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

The above codes are similar to those in the manual document, I just replaced
the Delaunay with Triangulation. But the compiler gave me errors like:

c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
convert argument 1 from '_Ty' to 'const CGAL::Origin &'
1>        with
1>        [
1>            Kernel_=CGAL::Epick
1>        ]
1>        and
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]
1>c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
1>        with
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]


What should I do to add information to point/vertex of a Triangulation while
inserting a range of points?

Thank you.





--
Sent from: http://cgal-discuss.949826.n4.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



-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
Reply | Threaded
Open this post in threaded view
|

Re: Add information in Triangulation while inserting a range of points

Marc Alexa
I think the question is less why one would like to call some function, but consistency among derived classes (see below). If you absolutely need some reasons:
1. One could hope that a triangulation may be generated slightly faster than Delaunay if less flips are performed, such as for the pushing/placing triangulation. 
(2. [much less of a reason] an order dependent triangulation would allow creating many different triangulations in a convenient way, just by permuting the order and then calling the constructor. I would have liked to make use of this.)

Consistency: Delaunay_triangulation_3 has the following methods:
std::ptrdiff_t CGAL::Delaunay_triangulation_3< Traits, TDS, LP, SLDS >::insert (PointInputIterator first, 
PointInputIterator last 
)
std::ptrdiff_t CGAL::Delaunay_triangulation_3< Traits, TDS, LP, SLDS >::insert (PointWithInfoInputIterator first, 
PointWithInfoInputIterator last 
)
The second one apparently accepts std::pair as a way to provide points with info. 

Triangulation_3, from which Delaunay_triangulation_3 is derived, offers
std::ptrdiff_t CGAL::Triangulation_3< Traits, TDS, SLDS >::insert (InputIterator first, 
InputIterator last 
)
and the InputIterator seems to only accept Points, but not pairs.  

On the other hand, the vertex type used for Delaunay_triangulation_3 is Triangulation_vertex_base_3 or Triangulation_vertex_base_with_info_3 (and not something specialized for Delaunay_triangulation_3). 

From the perspective of using these interfaces this may seem odd. 

BTW: what is even more inconvenient is that Regular_triangulation_3 has no _with_info type at all. 

It would really be nice to have an easy way to access the vertices in a triangulation based on some existing integer indices. One way, as Mael pointed out, is to insert the vertices one by one. This allows creating maps from and to the vertex handles. But it is inefficient. It seems the way out is to apply spatial sorting to the points, keep track of the permutation, and then insert one by one. Is this expected to be as fast as calling the insert function with a range (modulo parallelism)?

-Marc



On 13. May 2019, at 10:32, Andreas Fabri <[hidden email]> wrote:


Let me correct myself, The constructor with a range, as well as the insert function   
with a range exist, and they perform a spatial sort, so we do what I  explained to
better not do in my previous mail.   And I didn't adress at all your request for
dealing with points with info.

We can look into this, but can you tell me why you would construct a Triangulation_3?

best,

andreas

On 5/13/2019 10:10 AM, Andreas Fabri wrote:


We could add an insertion of a range to the Triangulation_3 class, but then no
reshuffling of the points should happen as the insertion order implies which
triangles you have.  This is different for the Delaunay/Regular triangulation
where the resulting triangulation is unique, that is independent from the
insertion order.

andreas


On 5/13/2019 9:01 AM, Marc Alexa wrote:
Yes, CGAL is sometimes mysterious in what types are accepted by what functions. I agree you’d expect that the insert method for Triangulation_3 should be able to understand how to handle the pairs if Delaunay_triangulation_3 does. But, no. If you insist on using the pairs and are ok with initially getting a Delaunay triangulation, the following code works just fine:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Delaunay_Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef CGAL::Delaunay_triangulation_3<K, Tds> DT;
typedef Triangulation::Point
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

    Triangulation T = DT(points.begin(), points.end());

    CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

I believe speed-wise there is very little to be gained from not using Delaunay. If you don’t care about what coordinate in space carries which number, you could insert the range of points first and then set the info later. In this case, however, the order of the points you get form the vertex iterator will likely differ from the order in which you provided the points. 



-Marc



On 13. May 2019, at 04:25, sanlingtonCGAL <[hidden email]> wrote:

Hi,

I know the Delaunay and Regular triangulation in CGAL can already add
information to vertices while inserting /a range of points/, as introduced
in
https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay

But it seems that the Triangulation_2/3 (not Delaunay triangulation or
Regular triangulation) can't do that, am I correct?

What I want to do is to construct Triangulation by inserting a range of
points, and each point or vertex would carry extra information, like an
index.
I am using codes like:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef Triangulation::Point                                            
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

Triangulation T(points.begin(), points.end());
CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

The above codes are similar to those in the manual document, I just replaced
the Delaunay with Triangulation. But the compiler gave me errors like:

c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
convert argument 1 from '_Ty' to 'const CGAL::Origin &'
1>        with
1>        [
1>            Kernel_=CGAL::Epick
1>        ]
1>        and
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]
1>c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
1>        with
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]


What should I do to add information to point/vertex of a Triangulation while
inserting a range of points?

Thank you.





--
Sent from: http://cgal-discuss.949826.n4.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



-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri

Reply | Threaded
Open this post in threaded view
|

Re: Add information in Triangulation while inserting a range of points

MaelRL
On 15/05/2019 11:09, Marc Alexa wrote:
I think the question is less why one would like to call some function, but consistency among derived classes (see below). If you absolutely need some reasons:
1. One could hope that a triangulation may be generated slightly faster than Delaunay if less flips are performed, such as for the pushing/placing triangulation. 
(2. [much less of a reason] an order dependent triangulation would allow creating many different triangulations in a convenient way, just by permuting the order and then calling the constructor. I would have liked to make use of this.)
There probably shouldn't be a call to spatial sort in the range insertions of Triangulation_3.h in the first place. Note that the doc still warns you that spatial sorting is applied.

Consistency: Delaunay_triangulation_3 has the following methods:
std::ptrdiff_t CGAL::Delaunay_triangulation_3< Traits, TDS, LP, SLDS >::insert  ( PointInputIterator  first, 


PointInputIterator  last 

)
std::ptrdiff_t CGAL::Delaunay_triangulation_3< Traits, TDS, LP, SLDS >::insert  ( PointWithInfoInputIterator  first, 


PointWithInfoInputIterator  last 

)
The second one apparently accepts std::pair as a way to provide points with info. 

Triangulation_3, from which Delaunay_triangulation_3 is derived, offers
std::ptrdiff_t CGAL::Triangulation_3< Traits, TDS, SLDS >::insert  ( InputIterator  first, 


InputIterator  last 

)
and the InputIterator seems to only accept Points, but not pairs.  

On the other hand, the vertex type used for Delaunay_triangulation_3 is Triangulation_vertex_base_3 or Triangulation_vertex_base_with_info_3 (and not something specialized for Delaunay_triangulation_3). 

From the perspective of using these interfaces this may seem odd.
There is nothing that Delaunay_triangulation_3 requires from its vertex base class that isn't already required by Triangulation_3. Thus the simplest model that fits is Triangulation_vertex_base_3.

BTW: what is even more inconvenient is that Regular_triangulation_3 has no _with_info type at all.

Most vertex / base classes provided within CGAL take a vertex base class in template parameter and inherit this base. You are supposed to use that to nest classes to add whatever you want to your classes, not create new classes. For example, a periodic regular triangulation vertex base with info is:

Triangulation_vertex_base_with_info_3<Regular_triangulation_vertex_base_3<Periodic_3_triangulation_ds_vertex_base_3<> > >


It would really be nice to have an easy way to access the vertices in a triangulation based on some existing integer indices. One way, as Mael pointed out, is to insert the vertices one by one. This allows creating maps from and to the vertex handles. But it is inefficient. It seems the way out is to apply spatial sorting to the points, keep track of the permutation, and then insert one by one. Is this expected to be as fast as calling the insert function with a range (modulo parallelism)?

It will be as fast: the range insert function is just a call to spatial sort followed by iterative insertion. Note that you have to make use of the 'hint' mechanism -- see e.g. https://github.com/CGAL/cgal/blob/master/Triangulation_3/include/CGAL/Delaunay_triangulation_3.h#L404 -- when inserting (that's the whole point of sorting first).


-Marc



On 13. May 2019, at 10:32, Andreas Fabri <[hidden email]> wrote:


Let me correct myself, The constructor with a range, as well as the insert function   
with a range exist, and they perform a spatial sort, so we do what I  explained to
better not do in my previous mail.   And I didn't adress at all your request for
dealing with points with info.

We can look into this, but can you tell me why you would construct a Triangulation_3?

best,

andreas

On 5/13/2019 10:10 AM, Andreas Fabri wrote:


We could add an insertion of a range to the Triangulation_3 class, but then no
reshuffling of the points should happen as the insertion order implies which
triangles you have.  This is different for the Delaunay/Regular triangulation
where the resulting triangulation is unique, that is independent from the
insertion order.

andreas


On 5/13/2019 9:01 AM, Marc Alexa wrote:
Yes, CGAL is sometimes mysterious in what types are accepted by what functions. I agree you’d expect that the insert method for Triangulation_3 should be able to understand how to handle the pairs if Delaunay_triangulation_3 does. But, no. If you insist on using the pairs and are ok with initially getting a Delaunay triangulation, the following code works just fine:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Delaunay_Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef CGAL::Delaunay_triangulation_3<K, Tds> DT;
typedef Triangulation::Point
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

    Triangulation T = DT(points.begin(), points.end());

    CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

I believe speed-wise there is very little to be gained from not using Delaunay. If you don’t care about what coordinate in space carries which number, you could insert the range of points first and then set the info later. In this case, however, the order of the points you get form the vertex iterator will likely differ from the order in which you provided the points. 



-Marc



On 13. May 2019, at 04:25, sanlingtonCGAL <[hidden email]> wrote:

Hi,

I know the Delaunay and Regular triangulation in CGAL can already add
information to vertices while inserting /a range of points/, as introduced
in
https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation_3Delaunay

But it seems that the Triangulation_2/3 (not Delaunay triangulation or
Regular triangulation) can't do that, am I correct?

What I want to do is to construct Triangulation by inserting a range of
points, and each point or vertex would carry extra information, like an
index.
I am using codes like:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_cell_base_3.h>
#include <CGAL/Triangulation_vertex_base_with_info_3.h>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel         K;
typedef CGAL::Triangulation_vertex_base_with_info_3<unsigned, K>    Vb;
typedef CGAL::Triangulation_cell_base_3<K>                 Cb;
typedef CGAL::Triangulation_data_structure_3<Vb, Cb>                Tds;
//Use the Fast_location tag. Default or Compact_location works too.
typedef CGAL::Triangulation_3<K, Tds> Triangulation;
typedef Triangulation::Point                                            
Point;
int main()
{
std::vector< std::pair<Point, unsigned> > points;
points.push_back(std::make_pair(Point(0, 0, 0), 0));
points.push_back(std::make_pair(Point(1, 0, 0), 1));
points.push_back(std::make_pair(Point(0, 1, 0), 2));
points.push_back(std::make_pair(Point(0, 0, 1), 3));
points.push_back(std::make_pair(Point(2, 2, 2), 4));
points.push_back(std::make_pair(Point(-1, 0, 1), 5));

Triangulation T(points.begin(), points.end());
CGAL_assertion(T.number_of_vertices() == 6);

return 0;
}

The above codes are similar to those in the manual document, I just replaced
the Delaunay with Triangulation. But the compiler gave me errors like:

c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(881): error
C2664: 'CGAL::Point_3<Kernel_>::Point_3(CGAL::Point_3<Kernel_> &&)': cannot
convert argument 1 from '_Ty' to 'const CGAL::Origin &'
1>        with
1>        [
1>            Kernel_=CGAL::Epick
1>        ]
1>        and
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]
1>c:\program files (x86)\microsoft visual
studio\2017\community\vc\tools\msvc\14.16.27023\include\xmemory0(879): note:
Reason: cannot convert from '_Ty' to 'const CGAL::Origin'
1>        with
1>        [
1>            _Ty=std::pair<Point,unsigned int>
1>        ]


What should I do to add information to point/vertex of a Triangulation while
inserting a range of points?

Thank you.





--
Sent from: http://cgal-discuss.949826.n4.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



-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
-- 
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri

Reply | Threaded
Open this post in threaded view
|

Re: Add information in Triangulation while inserting a range of points

Laurent Rineau (CGAL/GeometryFactory)
On Wednesday, May 15, 2019 12:24:45 PM CEST Mael wrote:
> It will be as fast: the range insert function is just a call to spatial
> sort followed by iterative insertion. Note that you have to make use of
> the 'hint' mechanism -- see e.g.
> https://github.com/CGAL/cgal/blob/master/Triangulation_3/include/CGAL/Delaun
> ay_triangulation_3.h#L404 -- when inserting (that's the whole point of
> sorting first).

The permanent link is to that piece of code is:
https://github.com/CGAL/cgal/blob/934544dbdefbd17270f27e06f17463907bae8b34/Triangulation_3/include/CGAL/Delaunay_triangulation_3.h#L399-L406


--
Laurent Rineau, PhD
R&D Engineer at GeometryFactory           http://www.geometryfactory.com/
Release Manager of the CGAL Project       http://www.cgal.org/




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