Росен Матев 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 <[EMAIL PROTECTED]> _______________________________________________ grass-dev mailing list [email protected] http://lists.osgeo.org/mailman/listinfo/grass-dev
