search

bellockk / alphashape

Toolbox for constructing alpha shapes.
MIT License
258 stars 28 forks source link

What about the computational complexity of AlphaShape? #39

Open Neronjust2017 opened 1 year ago

Neronjust2017 commented 1 year ago

Hi, I'm trying to detect the edges of a bunch of cloud points. I wonder what is the computational complexity of the AlphaShape algorithm you implemented. Is it O(n^2)? What about using Delaunay Triangulation?

hschoeller commented 1 year ago

It is in fact based on Delauney triangulation and O(n^2). See also https://dl.acm.org/doi/10.1145/174462.156635

niederha commented 1 year ago

Also a question concening this topic, I'm running it with a fair ammount of points (anywherer between 5000 and 30000 and ideally I would like to scale up). I am noticing that most of the computational time is taken by circumcenter... about 70-80% of the time is spent in circumcenter where only 15-20% is spend in Delaunay.

What would you think about switching from a iterator to a single vectorized operation?

niederha commented 1 year ago

Hey so I have built a implementation that vectorizes the circumradius operation in 3d without computing the circumcenter. This effectively reduces the computation time by 50-100 times. I think it might be portable in 2D and would have to check the math for higher dims.

Only drawback is that the computational error is higher and really loses a lot of precision for triangles with low volumes.

@bellockk if you think there is a point in doing this, I am willing to clean up the code, check the math and do a proper pull request for this.