search

less0 / nAlpha

A C# implementation of Alpha Shapes
MIT License
3 stars 2 forks source link

unable to retrieve L shaped boundary #2

Open jeremytammik opened 5 years ago

jeremytammik commented 5 years ago

i cannot get this to return an L shape boundary for six points in an L shape, cf. attached image.

jeremytammik commented 5 years ago
nAlpha_L_shape
jeremytammik commented 5 years ago

the six points are hardcoded in the pull request

less0 commented 5 years ago

I haven't had time to have a closer look at the issue, but does this occur for any value of α?

jeremytammik commented 5 years ago

i tried a whole range of values for alpha. for small alpha, it creates a convex hull, not a concave one. for larger alpha, it does not create a closed shape at all, only the two short end segments at the extreme ends of the L shape, and the rest remains open, no segments displayed. approximately what range of alpha do you think might help solve the problem?

less0 commented 5 years ago

I've started adding a test case for that very shape. For a radius of .8 (α=1.25) it should (theoretically) work, but it does not. I think I might have found the solution, but I'll have to check with the original definition of alpha shapes, that I did not get it wrong.

jeremytammik commented 5 years ago

wow! thank you very much for checking and adding the very relevant test case. good luck fixing!

less0 commented 5 years ago

@jeremytammik I think I already did fix it (see my changes in the branch fix_#2), but I'll have to check the fixed implementation against the original definition of alpha shapes. I've just organized myself a copy of Edelsbrunner et al., 1983, who originally introduced the idea of alpha shapes and will have a look at it later.

less0 commented 5 years ago

@jeremytammik Hey, could you merge the branch I mentioned in my last post into your changes and try if it works (it should now, the test case runs successfully, at least)

jeremytammik commented 5 years ago

i merged your changes. unfortunately, the result is the same as before:

nAlpha_non_concave
jeremytammik commented 5 years ago

i pushed my changes to my forked repo, in case you want to take a look.

less0 commented 5 years ago

After reconsidering the definition and manually checking the results, it may well be that the L-Boundary is just not a valid α-shape. For a Radius of .4 (α=2.5), the points constitute an edge, but the points at (.1, .1) and (.9, .1) do not (the α-disk is exactly at the center between the points and includes the Point at (.8, .2), hence there is no edge. When the radius gets larger, they constitute an edge, but the points at (.8,.2) and (.8,.9) do not, since the α-disks contain the points at (.1, .2) and (.9, .9) respectively. I will try to create a demo that outputs the disks for the purpose of understanding the matter better.

jeremytammik commented 5 years ago

thank you very much for the explanation! that makes a lot of sense. i am looking for a simple implementation of a concave hull for non-convex rooms in a building information model. many rooms are convex, but some are obviously not. i am wondering how to easily determine a concave hull for those, and thought that an alpha shape might be much simpler to implement and provide useful results as well. maybe that is not the case after all?