ABSTRACT
When we are considering geographical data computers are both very good and very bad. They are very good at storing the connectivity between different objects – a graph in the mathematical sense. However, they are very bad at manipulating numbers being used as X–Y coordinates. This is because the limited precision of computer arithmetic means that the calculation of intersections and similar entities are only ever approximate. This is fine if you only want to draw them, but if you wish to calculate whether a point is on one side of a line segment or the other, there is no guarantee that the result will be correct – or, even worse, whether it will be consistent when recalculated at a later time. For this reason computer scientists – computational geometers – have defined a small number of predicates that, if calculated correctly, may be used for a large number of individual geometrical operations. A great deal of work has been done on providing effective algorithms for these predicates, but the predicates that we will be using in two-dimensional Euclidean space may easily be calculated and have proved to be robust enough for most applications.
