leomccormack
commented
2 years ago I should first disclose that I'm not really an expert in computational geometry. ;)
However, it is my understanding that the convex hull is not always unique in practice, due to problems with numerical precision (or rather, in-precision). For a spherical arrangement of points, or any other arrangement where the points do not exist on the same plane, the number of faces should always be the same. However, if, for example, there are indeed many points on the same plane, e.g. as in the airboat example, even if one is ever so slightly elevated due to some different numerical rounding, it can change the computed convex hull quite a lot:
However, for most intents and purposes, both solutions are fine. Perhaps the latter may even be more preferable in some cases, as there are fewer faces. For the subsequent task of Delaunay triangulation, however, the latter will then produce (in 3D) some tetrahedrons that have near zero volume, or (in 2D) some triangles with near zero area etc. Which you may want to remove based on some threshold parameter. Actually, perhaps this would be a nice future addition for this project...
On the topic of deliberately introducing noise, however, it actually remains a bit of a mystery to me. It was included in the original MATLAB implementation: https://se.mathworks.com/matlabcentral/fileexchange/48509-computational-geometry-toolbox?focused=3851286&tab=function And I have tried computing convex hulls both with and without it, and have concluded that it is often much better with it enabled. I suppose it does encourage the above described behaviour, leading to fewer faces for points on the same plane, which people may want? However, maybe more importantly, without the noise, I encounted some cases where the convex hull would fail to be computed for some geometries. Perhaps there is a better way to address this problem though...
AlexHarker
It looks like 6f61a29bc0e918479d601166bceab29c6b13b13e changes the output of the test code due to the difference in the random numbers. the committed files haven't been updated in some time (there's something creating a minor accuracy difference in one file before that, but this seems very minor)
I expected that the difference might just be in terms of ordering, but in convhull_airboat.obj the first change looks quite large (in that the first two values stay the same, but the Z value changes radically:
-v 7.711631 -1.639892 -2.027359 +v 7.711631 -1.639892 2.043359
I couldn't find the old value of z ==-2.027359 or anything particularly close to it elsewhere in the new file (there are also many other changes, so tracing all of them is not viable). Intuitively that doesn't seem right, but I tested rnd() and it is producing values in the range 0-1 as I'd expect, and I can't see how it could be affecting values to this degree.
I'm not sure if this needs investigating. It's simple enough to commit the results if they are valid (which would be useful as changes (or not) in the repo can then be used to verify further changes to the codebase), but I didn't want to make a PR for this without raising the issue of the changed values first.