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'm
willing to rewrite the parts of the code which generate most of the
inaccuracies and thus avoid all that cleaning, snapping, pruning, etc.
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).
I'm doing some extensive testing right now. We actually might not need
GMP, but I'm not sure yet. However, I definitely need to improve the
current segment intersection function, because now it misses many
intersections (which spoil my module). I know how to do it and I can
provide the fixed version to someone who can commit to trunc.
I'm doing some extensive testing right now. We actually might not need
GMP, but I'm not sure yet. However, I definitely need to improve the
current segment intersection function, because now it misses many
intersections (which spoil my module). I know how to do it and I can
provide the fixed version to someone who can commit to trunc.
Just add it as a separate file in your addons directory. It can be merged to develbranch_6 and trunk from there.