alternative initial split ?
andreasplesch opened this issue · 4 comments
Thanks, very intriguing. After the initial split, the refinement should be unique because there is only one way to split a right-angle triangle into two right-angle triangles by splitting the diagonal. So the resulting mesh can be reproduced given the same input DEM and max. error.
However, there are two options for the initial split. Currently, the diagonal from 0,0 to sizeX, sizeY is used for the initial split (https://github.com/mapbox/martini/blob/master/index.js#L159). Equally valid would be an alternative, initial split: from 0, sizeY to sizeX, 0.
In some cases, the alternative, initial split may lead to a more optimized mesh, eg. fewer triangles and there may be situations where exploring both options would be worth the (doubled) cost. Perhaps this is discussed in the original publication. In most cases, it should not matter much. It may be possible to prove that at most only a few triangles can be saved.
Consider adding an option to choose which initial split to use ? Then a user could explore both if wanted, and choose one.
Looking just at the figures of https://www.cs.ubc.ca/~will/papers/rtin.pdf, there is also the option to divide the initial square into four triangles, using the center as an additional vertex. This would avoid the ambiguity of having two alternatives for the initial split, probably a benefit. That would require a minimum size of 3 rather than 1 which should not have practical consequences.
Since the second split should generate the exact same four triangles for both alternatives, it actually should not matter at all which initial split to choose. So I think I can close this.
yeah, tested in fork. sorry for the noise.
After the second split there should be no difference between the two initial splits. Unless the second split is not necessary which is essentially never the case anyways. Just for completeness.