search

DesignEngrLab / MIConvexHull

A .Net fast convex hull library for 2, 3, and higher dimensions.
http://designengrlab.github.io/MIConvexHull/
MIT License
341 stars 60 forks source link

Triangulation of geo coordinates #38

Open Ilia-SB opened 4 years ago

Ilia-SB commented 4 years ago

Hi. Thanks for the great library. I was going to use it to triangulate sets of lat/lang values. Unfortunately the algorithm throws a NullReferenceException in CalculateVertexCentroid because vertexIndices is null. Turns out that variance between points is too small (in my case longitude changes in 38.3536 - 38.3668 range, and latitude in even smaller range). If I multiply the values by 10000 triangulation runs just fine. Is this the intended/expected behaviour? The algorithm is too complex for me to figure out if there is a more elegant solution than the one I use.

realgpasternak commented 4 years ago

I also ran into this issue, with general high-resolution data - working with angles in radian, where the data points variance is sometimes as small as 0.1 millirad (1e-4 radian).

micampbell commented 4 years ago

sorry, I've been away from the project for a while. If you send me some test data, I can see if I can get it to work with the raw values. Also - if I recall correctly - there are some optional tolerances that can be set.

Ilia-SB commented 4 years ago

Sorry for the delayed response. Here's the set that gives me the exception. Actually, it's 100 points, but I guess 10 should be enough.

38.359052882483887, 56.02282713353344 38.365112304786429, 56.0218508829207 38.36001531819803, 56.023416987346707 38.35803713543698, 56.023549757868032 38.357863216371037, 56.02234061233267 38.35408882004424, 56.020852611291083 38.365794195423483, 56.020557681089535 38.356048644009491, 56.022278568289735 38.365965425182253, 56.023300153013373 38.355903158948735, 56.022913716654188

Edit: after rereading your post I tried playing with constants in constants.cs and setting DefaultPlaneDistanceTolerance to 1e-30 and FractionalNegligibleVolume to 1e-50 seems to fix the problem. Thanks for the hint!