[GRASS-dev] Add GMP library to GRASS

[Glynn Clements]

Росен Матев wrote:

> As I was writing the new v.buffer module, I came along some problems
> connected to the inacurate floating point maths. To be more specific,
> I needed to rewrite Vect_segment_intersection(), so that it behaved
> correctly all the time. At first, I thought that incorporating a
> "tolerance" feature in Vect_segment_intersection() (in order to avoid
> doing exact fp comparisons) will solve the problems. However, it
> turned out that there is no way to set a correct tolerance, even if it
> is calculated dynamically from input. Vect_segment_intersection() kept
> reporting inexisting intersections or missed existing ones. That is a
> problem for correct topology extraction in some inputs. So I decided I
> should use the multi-precision library http://gmplib.org/ . At first,
> v.parallel ran 30 times slower with the correct
> Vect_segment_intersection() than with the existing one. After some
> optimizations I managed to make it ~4 times slower than the original.
> This, however, doesn't mean that the correct
> Vect_segment_intersection() is 4 times slower than the original (I
> haven't done separate benchmarks). (Also have in mind that v.buffer is
> currently suboptimal in the place where I use
> Vect_segment_intersection())
> Briefly, my v.buffer/v.parallel module doesn't work correctly on some
> inputs with the original Vect_segment_intersection(). With GMP
> everything is just fine and just a bit slower.

> I hope everyone agrees that we need library like GMP in GRASS.

I don't agree.

IEEE double precision is more than sufficient for representing
geographic data. It's not as if you're actually going to get
coordinates which are accurate to sub-micron precision.

If an algorithm doesn't work with "double", it's usually because it
assumes that floating-point arithmetic obeys the axioms of real
arithmetic (e.g. a*b=c => a=c/b); in which case, it's a bug in the
algorithm.

Regarding line intersection, the usual flaw is to assume that it's
always possible to calculate a point of intersection. Realistically,
you need to detect and allow for the case where two lines are either
collinear or so close to collinear that an intersection calculation is
meaningless.

Increasing the precision just makes it less likely that the flaw will
manifest. That might be fine if you could ensure that it's unlikely to
ever manifest in actual use, but in practice you can't normally do
much beyond determining whether or not it actually manifests during
testing, which isn't the same thing (in fact, it's not uncommon to
explicitly reduce precision during testing just to flush out such
flaws).

-- 
Glynn Clements <glynn at gclements.plus.com>