1[/============================================================================ 2 Boost.Geometry (aka GGL, Generic Geometry Library) 3 4 Copyright (c) 2013 Mateusz Loskot, London, UK. 5 6 Use, modification and distribution is subject to the Boost Software License, 7 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 8 http://www.boost.org/LICENSE_1_0.txt) 9=============================================================================/] 10 11[/ TODO: this is a basic draft only, should NOT be built into final docs yet ] 12[/ TODO: discuss numerical stability per algorithm (at least for line intersection and point in polygon) ] 13[/ TODO: integrate with doxygen_d_robustness.hpp and http://geometrylibrary.geodan.nl/formal_review/robustness.html ] 14[/ TODO: interlink the interesting discussion from Boost.Polygon at 15http://www.boost.org/doc/libs/release/libs/polygon/doc/voronoi_main.htm ] 16[/ TODO: discuss relation to EGC http://cs.nyu.edu/exact/intro/ ] 17 18[section Robustness] 19 20A numerical stability issues are a common problem in implementations of 21computational geometry algorithms. 22 23They lead to variety of unexpected sitautions at run-time: an application 24randomly throws segmentation faults, output computed by an algorithm 25contains degeneracies, unexpected artefacts or completely invalid. 26 27For example, according to the OpenGIS Simple Feature Specification, 28 29["A Polygon may not have cut lines, spikes or punctures] 30 31From mathematical point of view such condition is easy to verify. 32However, depending on computational method and in the presence of round-off 33or truncation errors, it is not easy to decided how "sharp" must be a part 34of polygon in order to consider it a spike. 35 36A 100% robust implementation of an algorithm gives expected result in 100% of cases. Achieving complete floating point robustness implies use of certain set of algorithms as well as platform specific assumptions about floating point representations. 37 38Despite Boost.Geometry does not promise absolute numerical stability, 39it attempts to offer balanced efficiency and robustness by: 40 41# selection of algorithms, often solved at case-by-case basis 42# compile-time selection of most precise and capacious C++ type on which to perform computations. 43# support for arbitrary precision numeric types 44 45 46[endsect] 47 48