48 lines
2.2 KiB
Plaintext
48 lines
2.2 KiB
Plaintext
[/============================================================================
|
|
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]
|
|
|