Skip to Content.
Sympa Menu

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

Subject: CGAL users discussion list

List archive

[cgal-discuss] Weighted Alpha shapes


Chronological Thread 
  • From: Kathi Oe <>
  • To:
  • Subject: [cgal-discuss] Weighted Alpha shapes
  • Date: Mon, 4 Jun 2018 17:03:54 +0200
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=None
  • Ironport-phdr: 9a23:HQQ2VRDLfeSU7UtGupCcUyQJP3N1i/DPJgcQr6AfoPdwSPr8ocbcNUDSrc9gkEXOFd2Cra4c1qyO6+jJYi8p2d65qncMcZhBBVcuqP49uEgeOvODElDxN/XwbiY3T4xoXV5h+GynYwAOQJ6tL1LdrWev4jEMBx7xKRR6JvjvGo7Vks+7y/2+94fcbglUhDexe69+IAmrpgjNq8cahpdvJLwswRXTuHtIfOpWxWJsJV2Nmhv3+9m98p1+/SlOovwt78FPX7n0cKQ+VrxYES8pM3sp683xtBnMVhWA630BWWgLiBVIAgzF7BbnXpfttybxq+Rw1DWGMcDwULs5Xymp4aV2Rx/ykCoJNyA3/nzUhMJ+gq1Urw6uqRNkzo7IY4yYLuZycr/TcN4YQ2dKQ8ZfVzZGAoO5d4YBCvAOPfpYr4n8ulAAtAWxDhSrCePs0DBImn/23aw90+s/CgzG0wkgHt0UvHTSstr1KL4fXOaox6fL1TXOd+1a1Srj5ITSbBwtv/OBUahtfcfR00UjCgfIgk2NpYHhMT6ZzPkBvmqH4+Z6SO6ii3ArpxtzrzWhwMonl5PHiZgPyl/e8CV02IY1KsO8SE58edOkFZxQtzyGN4dsTcMiRm5ptDw8yrIYpZ63ZCkKyJI5yB7Dc/GLbZWE7gz5WOqPPzt1hmhpdK+/ihqo7EStzvXwVsyu31ZLqipFnMPMtncI1xHL6ciIUOd9/keg2TaIyQ/e8e5EIUU7lKbBLZ4u3KIwmoIJsUvfBi/2hFn2jKiOe0o49ein8eDnbqz7qZ+dLI97lhz+Mr81msGkGuQ5Mg0OX3CB9uim1b3j+1f5QLRQgfEsnKnZqsOSGcNOraGwB0pZ050o9g2kJzagytUR23cdf3xffxfSrIH1O1CGB/2wWfS2n1StlzpDyPXWeLvsHsOefTD4jL79cOMluAZnww0pwIUHvsMGOvQ6OPv2H3TJmpndBx49PRazxre1B9BtkIUTRTDWW/PLAObpqVaNo9kXDayUfoZE6jn4O74j6uK81SZky29YRrGg2N4sUF79HvliJBzFM3/rn8tHHmIa+AwzUL6yhQ==

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