search

mourner / delaunator-rs

Fast 2D Delaunay triangulation in Rust. A port of Delaunator.
https://docs.rs/delaunator
ISC License
201 stars 28 forks source link

Accept other number types #4

Open mourner opened 6 years ago

mourner commented 6 years ago

Currently delaunator only works with f64. I need to learn how Rust generics and numeric traits work to enable using the library with other numeric types.

urschrei commented 5 years ago

@mourner If you use the Point implementation from Geo-Types, it's generic over f32, f64, and various integer types via CoordinateType.

mourner commented 5 years ago

@urschrei thanks and great work on the geo/geo-types crates — seen that! The difficulty for this task is not only about making point types generic, but also making sure the geometric operations all work without loosing precision / going out of bounds etc.

Stoeoef commented 5 years ago

Maybe I can share some of my experiences when developing Spade.

Support for f32

When investigating different number types for Spade, I started to riddle my code with debug_assert! calls that would check various preconditions, e.g. "Is the given point really on the right side of this edge?". Maybe that is applicable for you as well to detect precision loss as early as possible? Also, lots of randomized tests helped. These tests would usually triangulate some random points and, if no panic occurred during triangulation, perform a sanity check on the triangulation structure. This check would ensure that important invariants (e.g. are the points of triangles always sorted ccw?) or structural requirements (Has every half edge a twin?) are met.

I have had bad experiences with f32 and precision for spade, up to the point that I stopped using it even for very small point sets. However, delaunator seems to be more robust for f64, maybe this robustness is also true for f32.

One last note: I have not had any problems with overflowing f32 or f64 values, their range seems to be large enough for any realistic input set.

Support for integer types

If you decide to support integer coordinates, integer overflow is checked in debug configuration. Also, I noted some divisions ( / ) in your code, those may not work as intended for integer coordinates.

Support for custom number types (BigIntegers, arbitrary precision floats)

When I ran into precision problems back then, my first attempt to fix this was to use arbitrary precision floating point numbers. Besides being terribly slow, they are also very cumbersome to handle as there is no Copy bound on the number type.

oovm commented 1 year ago

Seems that robust does not support F: Float and arbitrary precision, it only supports f64