1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 |
- [/============================================================================
- Boost.Geometry (aka GGL, Generic Geometry Library)
- Copyright (c) 2013 Mateusz Loskot, London, UK.
- Use, modification and distribution is subject to the Boost Software License,
- Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- =============================================================================/]
- [/ TODO: this is a basic draft only, should NOT be built into final docs yet ]
- [/ TODO: discuss numerical stability per algorithm (at least for line intersection and point in polygon) ]
- [/ TODO: integrate with doxygen_d_robustness.hpp and http://geometrylibrary.geodan.nl/formal_review/robustness.html ]
- [/ TODO: interlink the interesting discussion from Boost.Polygon at
- http://www.boost.org/doc/libs/release/libs/polygon/doc/voronoi_main.htm ]
- [/ TODO: discuss relation to EGC http://cs.nyu.edu/exact/intro/ ]
- [section Robustness]
- A numerical stability issues are a common problem in implementations of
- computational geometry algorithms.
- They lead to variety of unexpected sitautions at run-time: an application
- randomly throws segmentation faults, output computed by an algorithm
- contains degeneracies, unexpected artefacts or completely invalid.
- For example, according to the OpenGIS Simple Feature Specification,
- ["A Polygon may not have cut lines, spikes or punctures]
- From mathematical point of view such condition is easy to verify.
- However, depending on computational method and in the presence of round-off
- or truncation errors, it is not easy to decided how "sharp" must be a part
- of polygon in order to consider it a spike.
- A 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.
- Despite Boost.Geometry does not promise absolute numerical stability,
- it attempts to offer balanced efficiency and robustness by:
- # selection of algorithms, often solved at case-by-case basis
- # compile-time selection of most precise and capacious C++ type on which to perform computations.
- # support for arbitrary precision numeric types
- [endsect]
|