Robustness

Geometric algorithms involve a combination of combinatorial and numerical computation. As with all numerical computation using finite-precision numbers, the algorithms chosen are susceptible to problems of robustness. A robustness problem occurs when a numerical calculation produces an inexact answer due to round-off errors. Robustness problems are especially serious in geometric computation, since the numerical errors can propagate into the combinatorial computations and result in complete failure of the algorithm.

There are many approaches to dealing with the problem of robustness in geometric computation. Not surprisingly, most robust algorithms are substantially more complex and less performant than the non-robust versions. Holixa Infra Suite attempts to deal with the problem of robustness in two ways:

• The important fundamental geometric algorithms (such as Line Orientation, Line Intersection and the Point-In-Polygon test) have been implemented using robust algorithms. In particular, the implementation of several algorithms relies on the robust determinant evaluation).
• The algorithms used to implement the SFS predicates and functions have been developed to eliminate or minimize robustness problems. The binary predicate algorithm is completely robust. The spatial overlay and buffer algorithms are non-robust, but will return correct answers in the majority of cases.

Dimensional Collapse

Geometries computed by spatial analysis methods may contain constructed points which are not present in the input geometries. These new points arise from intersections between line segments in the edges of the input geometries. In the general case it is not possible to represent constructed points exactly. This is due to the fact that the coordinates of an intersection point may contain as much as twice as many bits of precision as the coordinates of the input line segments. In order to represent these constructed points explicitly, Infra Suite must round them to fit the given Precision Model.

Unfortunately, rounding coordinates moves them slightly. Line segments which would not be coincident in the exact result may become coincident in the truncated representation. For Line-Line combinations, this can produce result geometries containing points which were not in the interior of the input geometries. More seriously, for Line-Area combinations, this can lead to dimensional collapses, which are situations where a computed component has a lower dimension than it would in the exact result.

       

Infra Suite handles dimensional collapses as gracefully as possible, by forming the lower-dimension geometry resulting from the collapse. For instance, an Area-Area intersection with a dimensional collapse would return a Line or Point geometry as a component of the result.

Numerical Stability

A desirable feature of numerical algorithms is that they exhibit stability. The stability of a numerical algorithm is determined by the bound on the maximum error in its outputs. An algorithm is considered to be stable if this bound is small. The primary numerical algorithm used in Infra Suite is the computation of the intersection point between two segments. This algorithm is inherently inexact, since the bits of precision required to represent the intersection point is several times greater than the precision of the inputs. A stable algorithm for this computation will always produce approximate answers that are close to the exact answer. In particular, the computed points should at least lie within the bounding box of the input line segments! Ideally, the computed points will lie within a single precision model grid unit of the exact answer.

One way to increase the stability of numerical algorithms is to condition their inputs. Conditioning inputs involves numerically manipulating them in some way that produces the same answer while preserving more precision during the calculations. Infra Suite uses a technique of "normalizing" the input line segments to the line intersection computation. Normalized line segments have been translated to be as close to the origin as possible. This has the effect of removing common significant digits from each ordinate, and thus increases the bits of precision available to maintain the accuracy of the line intersection computation.