448 switched the Delaunay triangle circumcentre calculation to use DD arithmetic to improve the robustness of Voronoi diagram computation. This fixed an issue where the circumcentres of adjacent right isosceles triangles were computed slighly differently due to roundoff.
This probably introduces a performance degradation. It may be possible to add a filter to the circumcentre function which only uses DD arithmetic in sensitive cases. Ideas for this include:
check for isosceles triangles (up to a tolerance) and fall back to the double-precision calc if not.
additionally, detect when the circumcentre lies "close" to a isosceles triangle opposite edge and if so recompute with higher precision
perhaps some inspection/experimentation with the circumcentre calculation would reveal a way of creating a filter based on intermediate values during the computation (e.g. if the denom is very large or the numx and numy are very close)
maybe very close Delaunay triangle circumcentres could be detected and snapped together. This could perhaps be done by processing each triangle after circumcentre calculation, and comparing centres of each adjacent triangle. Alternatively, if close circumcentres are found then recalculate using high precision.
dr-jts
commented
5 years ago
448 switched the Delaunay triangle circumcentre calculation to use DD arithmetic to improve the robustness of Voronoi diagram computation. This fixed an issue where the circumcentres of adjacent right isosceles triangles were computed slighly differently due to roundoff.
This probably introduces a performance degradation. It may be possible to add a filter to the circumcentre function which only uses DD arithmetic in sensitive cases. Ideas for this include: