Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Weighted Alpha shapes

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Weighted Alpha shapes


Chronological Thread 
  • From: Mael <>
  • To:
  • Subject: Re: [cgal-discuss] Weighted Alpha shapes
  • Date: Tue, 19 Jun 2018 17:09:31 +0200
  • Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=None ; spf=None
  • Ironport-phdr: 9a23:fGFfZh08/TsH+mfysmDT+DRfVm0co7zxezQtwd8ZseIVKvad9pjvdHbS+e9qxAeQG9mDtrQc06L/iOPJYSQ4+5GPsXQPItRndiQuroEopTEmG9OPEkbhLfTnPGQQFcVGU0J5rTngaRAGUMnxaEfPrXKs8DUcBgvwNRZvJuTyB4Xek9m72/q99pHPYwhEniaxba9vJxiqsAvdsdUbj5F/Iagr0BvJpXVIe+VSxWx2IF+Yggjx6MSt8pN96ipco/0u+dJOXqX8ZKQ4UKdXDC86PGAv5c3krgfMQA2S7XYBSGoWkx5IAw/Y7BHmW5r6ryX3uvZh1CScIMb7S60/Vza/4KdxUBLmlTkJNzA5/m/UhMJ/gq1UrxC9qBFk2YHYfJuYOeBicq7Tf94XQ3dKUMZLVyxGB4Oxd4wBAPAfMuZcsoLwoF4OogGgCgmoHu/v0DhIhmL53KIk1+QtCwXG0xY7EN0VrnvZt9r1O7kVUeCw0qbI0S/DbvNY2Tjn9IfIbhchoeuMXL5qbcXRzkwvGhrDg16Np4LlODaV2f4Ms2id9+dgWuOvi3InqwFsuTej3Nsjio7Mho8T11vK9j15zZ46KNC5UkJ3fMKoHZtKuyyVK4d6WN0uTmVwtCs+1rEKo522cSkQxJg52RLSZeaLf5WV7h/hUuuaPC12i2h/eL2lgha/6UigxfP4VsmzyFtGsyVInsPJtnAK2BHf8M2HReF8/kelwDqP0B3T6v1eLUAzi6rbK4QtwrgumZoPqUjDHyn2l1vqjKKOeUgp+/Kk5/n7brjmvJOROJN4hhvgPqkqgsC/BP43MgkKX2iV4+S807jj8FX8QLpQkPI2lrPVsIrdJcQGqa+2HQtV3pwn6xmlFDipy8oXkGIILF1bfxKHipbmO03UIPH4A/ewmUijkCtsx/DcPrztGInCLn/GkLv5Z7Zy91ZcyBYvzdBY/59bFr4BL+j3WkPoqdPYDwQ5PBCpw+b8E9VwzZgeWGKKAq+BKqzeq16I5uQ1I+mNfoAZojj9K+J2r8Lp2HQ2kFtYcaiy1oYMc1i5GO5nKgOXeynCmNAEREIDsw52GOnjhVnESzlOd3u2GaY17Ds2II2rCoLOWpq8jrWKwCChD9tdYWUQWQPEKmvha4jRA6REUymVOMI0ymVVB4jkcJco0FSVjCG/zrNmKuTO/ShC7MDs2d9w6vHJhB87/iBzFdXb2GaIHTktwjE4AgQu1aU6mnRTj0+Z2PIh0fNVEtle++lYXA4xKZnG3qpxDNWgAlucLOfMc06vR5CdOR90Tt81xIVTMR8hXdCl0lbG1iuuRrgIi/qMGpxy9K/AjSD8

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









Archive powered by MHonArc 2.6.18.

Top of Page