acad2012
asked on
GIS: Problem in the intersection point of two lines will be rounded to the nearest grid point
As a basis for geometric modeling very often Euclidean space is used or implicitly assumed. Essentially this means that a point in the plane is given by a pair of real numbers. Unfortunately, in practice, there are no real numbers in computers but only finite and mostly rather limited approximations. This leads to a lot of problems in geometric computation [GrY86, Fran84]. For example, the intersection point of two lines will be rounded to the nearest grid (that is, representable) point; a subsequent test whether the intersection point is on one of the lines yields false. If the fact that finite representations are used is ignored in modeling, these problems are left to the implementor of a spatial DBMS, which will rather inevitably lead to errors in query processing. Some authors have therefore suggested to introduce a discrete geometric basis for modeling as well as implementation [FraK86, EgFJ89, GütS93a].
What the problem here when the intersection point of two lines will be rounded to the nearest grid point ?
What the problem here when the intersection point of two lines will be rounded to the nearest grid point ?
If just using binary represntation its easy to see where values may not match. See the advantages of bcd here:
http://en.m.wikipedia.org/wiki/Binary-coded_decimal#section_8
But dont forget that you have to get the results of the calculations converted into bcd if you are going to use it so mismatches can occur at any point, even back to the original measurements.
http://en.m.wikipedia.org/wiki/Binary-coded_decimal#section_8
But dont forget that you have to get the results of the calculations converted into bcd if you are going to use it so mismatches can occur at any point, even back to the original measurements.
Some further reading:
"We call the difference between the real value of a number and the actual value of the floating point an approximation error. This error is a fundamental property of floats and with regard to rounding there are two important points; firstly, the approximation can be either under or over the exact number so, for example, imagine that .37 is represented as .369999998 rather than .370000004. Secondly, for a given value the approximation error isn't always the same; it depends on how the value was calculated. This means we cannot predict if the approximation will be above or below the real number."
http://www.theregister.co.uk/2006/08/12/floating_point_approximation/
Until you have come across a real-life rounding issue it is hard o imagine why it is such a problem. I met mine trying to remove the tax amount from a large list of sales transactions, summing the list and re-applying the tax rate. It doesn't work.
The reason it fails is that you have to stop calculating at a given number of decimal places.
The tax rate I was working with was 17.5%.
A simple example is subtract the tax amount from 1.10, 1.11 to get values 1.10, 1.10. Summing and re-adding the tax gives .01 less than the original. You can't use any more decimal places as there is no smaller coin. Imaging a list of several million of these figures and you can begin to see the problem.
It's the same with a grid - you are expecting an exact number to say that your intersection is on the line (or an exact number of pennies), but you don't know if the line has been rounded up or down, or if your intersect calculation has done the same. Combine this with the huge quantity of irrational binary numbers (only fractions that have divisors that are powers of 2 are rational in binary) and you can hopefully see why the calculation is tougher than simply rounding up both values. They could already be higher or lower than they should be and may have crossed the grid line already.
"We call the difference between the real value of a number and the actual value of the floating point an approximation error. This error is a fundamental property of floats and with regard to rounding there are two important points; firstly, the approximation can be either under or over the exact number so, for example, imagine that .37 is represented as .369999998 rather than .370000004. Secondly, for a given value the approximation error isn't always the same; it depends on how the value was calculated. This means we cannot predict if the approximation will be above or below the real number."
http://www.theregister.co.uk/2006/08/12/floating_point_approximation/
Until you have come across a real-life rounding issue it is hard o imagine why it is such a problem. I met mine trying to remove the tax amount from a large list of sales transactions, summing the list and re-applying the tax rate. It doesn't work.
The reason it fails is that you have to stop calculating at a given number of decimal places.
The tax rate I was working with was 17.5%.
A simple example is subtract the tax amount from 1.10, 1.11 to get values 1.10, 1.10. Summing and re-adding the tax gives .01 less than the original. You can't use any more decimal places as there is no smaller coin. Imaging a list of several million of these figures and you can begin to see the problem.
It's the same with a grid - you are expecting an exact number to say that your intersection is on the line (or an exact number of pennies), but you don't know if the line has been rounded up or down, or if your intersect calculation has done the same. Combine this with the huge quantity of irrational binary numbers (only fractions that have divisors that are powers of 2 are rational in binary) and you can hopefully see why the calculation is tougher than simply rounding up both values. They could already be higher or lower than they should be and may have crossed the grid line already.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
It's rather hard to guess what you understand or don't understand unless you let me know?
Are any of those posts above helpful in any way?
Are any of those posts above helpful in any way?
I think this is where your problem lies. The comparison is being done between two approximates. The numbers may be rounded and may be very close, but as that rounded number cannot be stored exactly in a computer memory, you can rarely get an exact match.
A very rough example could be:
1.9999999989=1.999999999
Rounded to 8 places these are written the same in decimal, but in binary coded decimal there is no reason to chop off at the 8th place and have any following places zeroed. It may display that way but the stored values are not the same and so a test for equality will say they don't match.