Does maximum Alphalevel always guarantee that none of the elements are classified as EXTERIOR type?

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

Does maximum Alphalevel always guarantee that none of the elements are classified as EXTERIOR type?

nsoonhui
This post was updated on .
I have the following (Pseudo) code:
 
     
       Alpha_shape_2 *A =new Alpha_shape_2(first,last, 100000,Mode.Regular);
      auto maxLevel =  A->number_of_alphas()-1;
      auto alphaLevel = A->get_nth_alpha(maxLevel);
        for(fit=A->finite_faces_begin(); fit!=A->finite_faces_end(); ++fit)
        {


                     A->set_alpha(alphaLevel);
                   auto classType2 = A->classify(fit);   //can this be EXTERIOR?
                       
        }


I know that if alphaLevel is not maximum, then    A->classify(fit) can be
EXTERIOR.

But, my question is that, is it even possible for the maximum alpha level to
classify one of the face as EXTERIOR?





--
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: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

MaelRL

Hello,

Assuming you are using a basic Delaunay_triangulation_2: for the maximal alpha value, the alpha shape is the Delaunay triangulation of the point set, thus the status of a vertex cannot be exterior since the Delaunay triangulation is a triangulation of the convex hull of the point set.

If you are using a weighted triangulation (Regular_triangulation_2), things are bit trickier: if the point has a weight such that it does not appear in the (weighted) Delaunay triangulation, then its status should be exterior, even at the greatest alpha value of the family. However, there is a known bug in Alpha_shape_2 when using the General mode that makes it so a vertex is never marked as exterior. I am not sure if its also present in regular mode.

Best,
Mael

On 03/08/2018 09:46, nsoonhui wrote:
I have the following (Pseudo) code:
 
      
       Alpha_shape_2 *A =new Alpha_shape_2(first,last, 100000,Mode.Regular);
      auto maxLevel =  A->number_of_alphas()-1;
      auto alphaLevel = A->get_nth_alpha(maxLevel);
	for(fit=A->finite_faces_begin(); fit!=A->finite_faces_end(); ++fit)
	{


		     A->set_alpha(alphaLevel);
	           auto classType2 = A->classify(fit);   //can this be EXTERIOR?
			
	}


I know that if alphaLevel is not maximum, then    A->classify(fit) can be
EXTERIOR.

But, my question is that, is it even possible for the maximum alpha level to
classify one of the face as EXTERIOR?





--
Sent from: http://cgal-discuss.949826.n4.nabble.com/


Reply | Threaded
Open this post in threaded view
|

Re: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

nsoonhui
/Assuming you are using a basic Delaunay_triangulation_2: for the maximal
alpha value, the alpha shape is the Delaunay triangulation of the point set,
thus the status of a vertex cannot be exterior since the Delaunay
triangulation is a triangulation of the convex hull of the point set./


I am using a basic Delaunay_triangulation_2. So I think this is a bug?



--
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: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

MaelRL
Could you please provide your data set?


On 03/08/2018 10:26, nsoonhui wrote:

> /Assuming you are using a basic Delaunay_triangulation_2: for the maximal
> alpha value, the alpha shape is the Delaunay triangulation of the point set,
> thus the status of a vertex cannot be exterior since the Delaunay
> triangulation is a triangulation of the convex hull of the point set./
>
>
> I am using a basic Delaunay_triangulation_2. So I think this is a bug?
>
>
>
> --
> 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: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

nsoonhui
Hi, I attach my dataset ( note that it is in Point3D format, but it shouldn't
matter as the z is 0 always and you can easily convert to Point2D).

And this is the gist of my code:

typedef CGAL::Triangulation_vertex_base_2<Kernel>                      VbT;
typedef CGAL::Triangulation_face_base_with_info_2<FaceInfo2,Kernel>    Fbb;
typedef CGAL::Constrained_triangulation_face_base_2<Kernel,Fbb>        FbT;
typedef CGAL::Triangulation_data_structure_2<VbT,FbT>               TDS;
typedef CGAL::Exact_predicates_tag                                Itag;
typedef CGAL::Constrained_Delaunay_triangulation_2<Kernel, TDS, Itag>  CDT;

typedef CGAL::Alpha_shape_vertex_base_2<Kernel> Vb;
typedef CGAL::Alpha_shape_face_base_2<Kernel>  Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb> Tds;
typedef CGAL::Delaunay_triangulation_2<Kernel,Tds> Alpha_Triangulation_2;
typedef CGAL::Alpha_shape_2<Alpha_Triangulation_2>  Alpha_shape_2;

Alpha_shape_2 *A =new Alpha_shape_2(first,last, 100000,Mode.Regular);
      auto maxLevel =  A->number_of_alphas()-1;
      auto alphaLevel = A->get_nth_alpha(maxLevel);
     int i=0;
        for(fit=A->finite_faces_begin(); fit!=A->finite_faces_end(); ++fit)
        {


                     A->set_alpha(alphaLevel);
                   auto classType2 = A->classify(fit);   //i==504 is
EXTERIOR
               i++;
                       
        }

From what I can tell, there is an element at i==504, which is EXTERIOR. (
there are 545 elements).

Do let me know whether you can reproduce the problem with the dataset and
the above pseudo code. If not I will prepare a fully working sample.

I am using CGAL 4.6.2. Not sure whether it matters or not

coordinate.csv
<http://cgal-discuss.949826.n4.nabble.com/file/t212754/coordinate.csv>  






--
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: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

MaelRL
Hello,

Thanks for the data set. I can't reproduce the issue neither with the
4.6 release nor with CGAL's master branch. I do get the 545 faces, but
they're all marked as 'interior' for the max alpha value (~1e14).

It's probably a good idea to update your version of CGAL in any case as
4.6 is a couple years old and there have been bug fixes and new features
in Alpha_shape_2 and in other packages.

Best,
Mael

On 07/08/18 06:51, nsoonhui wrote:

> Hi, I attach my dataset ( note that it is in Point3D format, but it shouldn't
> matter as the z is 0 always and you can easily convert to Point2D).
>
> And this is the gist of my code:
>
> typedef CGAL::Triangulation_vertex_base_2<Kernel>                      VbT;
> typedef CGAL::Triangulation_face_base_with_info_2<FaceInfo2,Kernel>    Fbb;
> typedef CGAL::Constrained_triangulation_face_base_2<Kernel,Fbb>        FbT;
> typedef CGAL::Triangulation_data_structure_2<VbT,FbT>               TDS;
> typedef CGAL::Exact_predicates_tag                                Itag;
> typedef CGAL::Constrained_Delaunay_triangulation_2<Kernel, TDS, Itag>  CDT;
>
> typedef CGAL::Alpha_shape_vertex_base_2<Kernel> Vb;
> typedef CGAL::Alpha_shape_face_base_2<Kernel>  Fb;
> typedef CGAL::Triangulation_data_structure_2<Vb,Fb> Tds;
> typedef CGAL::Delaunay_triangulation_2<Kernel,Tds> Alpha_Triangulation_2;
> typedef CGAL::Alpha_shape_2<Alpha_Triangulation_2>  Alpha_shape_2;
>
> Alpha_shape_2 *A =new Alpha_shape_2(first,last, 100000,Mode.Regular);
>        auto maxLevel =  A->number_of_alphas()-1;
>        auto alphaLevel = A->get_nth_alpha(maxLevel);
>       int i=0;
>          for(fit=A->finite_faces_begin(); fit!=A->finite_faces_end(); ++fit)
>          {
>
>
>                       A->set_alpha(alphaLevel);
>                     auto classType2 = A->classify(fit);   //i==504 is
> EXTERIOR
>                 i++;
>                          
>          }
>
>  From what I can tell, there is an element at i==504, which is EXTERIOR. (
> there are 545 elements).
>
> Do let me know whether you can reproduce the problem with the dataset and
> the above pseudo code. If not I will prepare a fully working sample.
>
> I am using CGAL 4.6.2. Not sure whether it matters or not
>
> coordinate.csv
> <http://cgal-discuss.949826.n4.nabble.com/file/t212754/coordinate.csv>
>
>
>
>
>
>
> --
> 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: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

nsoonhui
I guess I know why-- there is nothing wrong with the CGAL ( even version
4.6). The problem lies with the Max Alpha value which is passed in from .Net
-- it is truncated so it is not the real Max. Value.



--
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: Does maximum Alphalevel always guarantee that all of the elements are classified as EXTERIOR type?

nsoonhui
In reply to this post by MaelRL
I think I know why; the CGAL library is solid ( even with 4.6). The problem
lies with the Max. Alpha Level. The Max. Alpha Level I set is not the actual
one; it's suffers digit truncation when it's passed in from .Net side.



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