# Weighted Alpha shapes Classic List Threaded 4 messages Reply | Threaded
Open this post in threaded view
|

## Weighted Alpha shapes

 Hello, I want to compute Alpha shapes of weighted points in 2D (and later 3D). When I compare my own implementation with CGAL, I get very different results for the alpha values of the simplices. I tried this basic example: point 0: 4 5.7 weight 16 point 1: 2.5 5 weight 4 point 2: 3 3 point 3: 6 4 weight -9 point 4: 8 3 We get the triangles 012 and 024, which is fine. They should have squared radius 6.06 and 11.79, but CGAL gives me 2.15 and 6.62. I don't know where these numbers come from. Just to be clear, my definition for the weighted Alpha shape is the following: A simplex is contained in the Alpha shape of radius r if the smallest sphere orthogonal to all its points (AB orthogonal if d(A,B)^2-weight_A-weight_B=0) has weight <= r^2. For triangle 012 I compute solve (4 - x)^2 + (5.7 - y)^2 - 16 - w = 0, (2.5 - x)^2 + (5 - y)^2 -  4 - w = 0, (3 - x)^2 + (3 - y)^2 - 0 - w = 0 to get the center (x,y) and weight/radius^2 w of this weighted circumsphere, which indeed gives w=6.06... Why is the alpha value in CGAL 2.15? The correct value does not even appear in the list of alpha values (which are 0.685 1.0625 2.15052 5.8225 6.25 6.6212). Did I understand something wrong about how to use alpha shapes in CGAL? Thanks for your help, Kathi -- 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: Weighted Alpha shapes

 Hello, What is your version of CGAL? There was a bug in AS_2 till not so long ago where it failed to use weights sometimes. As far as I remember the bug fix came with CGAL 4.12. With master, and the following test code, I get the following output: Alpha Shape computed 4 alpha shape edges Optimal alpha: 11.7899 Faces...     face:         2.5 5 4         3 3 0         4 5.7 16     squared radius directly from the kernel: 6.06026     compute with AS, sq_r: 6.06026         face:         3 3 0         8 3 0         4 5.7 16     squared radius directly from the kernel: 11.7899     AS sq_r: 11.7899 Alpha values     value: 0.57046     value: 1.79264     value: 3.82369     value: 6.06026     value: 11.7899 which seem to be what you expect. Mael On 06/04/2018 05:03 PM, Kathi Oe wrote: Hello, I want to compute Alpha shapes of weighted points in 2D (and later 3D). When I compare my own implementation with CGAL, I get very different results for the alpha values of the simplices. I tried this basic example: point 0: 4 5.7 weight 16 point 1: 2.5 5 weight 4 point 2: 3 3 point 3: 6 4 weight -9 point 4: 8 3 We get the triangles 012 and 024, which is fine. They should have squared radius 6.06 and 11.79, but CGAL gives me 2.15 and 6.62. I don't know where these numbers come from. Just to be clear, my definition for the weighted Alpha shape is the following: A simplex is contained in the Alpha shape of radius r if the smallest sphere orthogonal to all its points (AB orthogonal if d(A,B)^2-weight_A-weight_B=0) has weight <= r^2. For triangle 012 I compute solve (4 - x)^2 + (5.7 - y)^2 - 16 - w = 0, (2.5 - x)^2 + (5 - y)^2 -  4 - w = 0, (3 - x)^2 + (3 - y)^2 - 0 - w = 0 to get the center (x,y) and weight/radius^2 w of this weighted circumsphere, which indeed gives w=6.06... Why is the alpha value in CGAL 2.15? The correct value does not even appear in the list of alpha values (which are 0.685 1.0625 2.15052 5.8225 6.25 6.6212). Did I understand something wrong about how to use alpha shapes in CGAL? Thanks for your help, Kathi
Reply | Threaded
Open this post in threaded view
|

## Re: Weighted Alpha shapes

 Hello, The weighted alpha shape computation works now (on this basic example) with CGAL 4.12. Thanks for your help, Mael. :) I just wanted to mention some problems I encountered on the way. Switching from CGAL 4.10 to 4.12, my code initially did not work any more and I found the following reason: The Triangulation_vertex_base_with_info_2 class (as a basis for Alpha shapes or Delaunay triangulations) combined with the Exact_predicates_exact_constructions_kernel results in segfaults (which I could trace to the Hilbert spatial sorting procedure). Not using vertices with info OR using the inexact_constructions_kernel OR inserting the points one after the other (so that no spatial sorting is done) would work. I thought this might be interesting for others too. Best, Kathi Am 08.06.2018 um 15:20 schrieb Kathi Oe: Hello, My CGAL-Version was 4.10. I will try to upgrade to CGAL 4.12 and see if it works. Thanks for your help! Kathi Am 07.06.2018 um 12:47 schrieb Mael: Hello, What is your version of CGAL? There was a bug in AS_2 till not so long ago where it failed to use weights sometimes. As far as I remember the bug fix came with CGAL 4.12. With master, and the following test code, I get the following output: Alpha Shape computed 4 alpha shape edges Optimal alpha: 11.7899 Faces...     face:         2.5 5 4         3 3 0         4 5.7 16     squared radius directly from the kernel: 6.06026     compute with AS, sq_r: 6.06026         face:         3 3 0         8 3 0         4 5.7 16     squared radius directly from the kernel: 11.7899     AS sq_r: 11.7899 Alpha values     value: 0.57046     value: 1.79264     value: 3.82369     value: 6.06026     value: 11.7899 which seem to be what you expect. Mael On 06/04/2018 05:03 PM, Kathi Oe wrote: Hello, I want to compute Alpha shapes of weighted points in 2D (and later 3D). When I compare my own implementation with CGAL, I get very different results for the alpha values of the simplices. I tried this basic example: point 0: 4 5.7 weight 16 point 1: 2.5 5 weight 4 point 2: 3 3 point 3: 6 4 weight -9 point 4: 8 3 We get the triangles 012 and 024, which is fine. They should have squared radius 6.06 and 11.79, but CGAL gives me 2.15 and 6.62. I don't know where these numbers come from. Just to be clear, my definition for the weighted Alpha shape is the following: A simplex is contained in the Alpha shape of radius r if the smallest sphere orthogonal to all its points (AB orthogonal if d(A,B)^2-weight_A-weight_B=0) has weight <= r^2. For triangle 012 I compute solve (4 - x)^2 + (5.7 - y)^2 - 16 - w = 0, (2.5 - x)^2 + (5 - y)^2 -  4 - w = 0, (3 - x)^2 + (3 - y)^2 - 0 - w = 0 to get the center (x,y) and weight/radius^2 w of this weighted circumsphere, which indeed gives w=6.06... Why is the alpha value in CGAL 2.15? The correct value does not even appear in the list of alpha values (which are 0.685 1.0625 2.15052 5.8225 6.25 6.6212). Did I understand something wrong about how to use alpha shapes in CGAL? Thanks for your help, Kathi
Reply | Threaded
Open this post in threaded view
|

## Re: Weighted Alpha shapes

 Hello, On 06/19/2018 04:57 PM, Kathi Oe wrote: Hello, The weighted alpha shape computation works now (on this basic example) with CGAL 4.12. Thanks for your help, Mael. :) Great! I just wanted to mention some problems I encountered on the way. Switching from CGAL 4.10 to 4.12, my code initially did not work any more and I found the following reason: The Triangulation_vertex_base_with_info_2 class (as a basis for Alpha shapes or Delaunay triangulations) combined with the Exact_predicates_exact_constructions_kernel results in segfaults (which I could trace to the Hilbert spatial sorting procedure). Not using vertices with info OR using the inexact_constructions_kernel OR inserting the points one after the other (so that no spatial sorting is done) would work. I thought this might be interesting for others too. This pull request might solve that issue, it fixes a problem with the insertion of a range of weighted points in a Regular_triangulation_2 using EPECK). I'll try to reproduce it, but do you still have by any chance some problematic code? Thanks, Mael Best, Kathi Am 08.06.2018 um 15:20 schrieb Kathi Oe: Hello, My CGAL-Version was 4.10. I will try to upgrade to CGAL 4.12 and see if it works. Thanks for your help! Kathi Am 07.06.2018 um 12:47 schrieb Mael: Hello, What is your version of CGAL? There was a bug in AS_2 till not so long ago where it failed to use weights sometimes. As far as I remember the bug fix came with CGAL 4.12. With master, and the following test code, I get the following output: Alpha Shape computed 4 alpha shape edges Optimal alpha: 11.7899 Faces...     face:         2.5 5 4         3 3 0         4 5.7 16     squared radius directly from the kernel: 6.06026     compute with AS, sq_r: 6.06026         face:         3 3 0         8 3 0         4 5.7 16     squared radius directly from the kernel: 11.7899     AS sq_r: 11.7899 Alpha values     value: 0.57046     value: 1.79264     value: 3.82369     value: 6.06026     value: 11.7899 which seem to be what you expect. Mael On 06/04/2018 05:03 PM, Kathi Oe wrote: Hello, I want to compute Alpha shapes of weighted points in 2D (and later 3D). When I compare my own implementation with CGAL, I get very different results for the alpha values of the simplices. I tried this basic example: point 0: 4 5.7 weight 16 point 1: 2.5 5 weight 4 point 2: 3 3 point 3: 6 4 weight -9 point 4: 8 3 We get the triangles 012 and 024, which is fine. They should have squared radius 6.06 and 11.79, but CGAL gives me 2.15 and 6.62. I don't know where these numbers come from. Just to be clear, my definition for the weighted Alpha shape is the following: A simplex is contained in the Alpha shape of radius r if the smallest sphere orthogonal to all its points (AB orthogonal if d(A,B)^2-weight_A-weight_B=0) has weight <= r^2. For triangle 012 I compute solve (4 - x)^2 + (5.7 - y)^2 - 16 - w = 0, (2.5 - x)^2 + (5 - y)^2 -  4 - w = 0, (3 - x)^2 + (3 - y)^2 - 0 - w = 0 to get the center (x,y) and weight/radius^2 w of this weighted circumsphere, which indeed gives w=6.06... Why is the alpha value in CGAL 2.15? The correct value does not even appear in the list of alpha values (which are 0.685 1.0625 2.15052 5.8225 6.25 6.6212). Did I understand something wrong about how to use alpha shapes in CGAL? Thanks for your help, Kathi