ceph/src/boost/libs/geometry/doc/robustness.qbk

   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
  15 http://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
  20 A numerical stability issues are a common problem in implementations of
  21 computational geometry algorithms.
  22
  23 They lead to variety of unexpected sitautions at run-time: an application
  24 randomly throws segmentation faults, output computed by an algorithm
  25 contains degeneracies, unexpected artefacts or completely invalid.
  26
  27 For example, according to the OpenGIS Simple Feature Specification,
  28
  29 ["A Polygon may not have cut lines, spikes or punctures]
  30
  31 From mathematical point of view such condition is easy to verify.
  32 However, depending on computational method and in the presence of round-off
  33 or truncation errors, it is not easy to decided how "sharp" must be a part
  34 of polygon in order to consider it a spike.
  35
  36 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.
  37
  38 Despite Boost.Geometry does not promise absolute numerical stability,
  39 it 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