[ceph.git] / ceph / src / boost / libs / geometry / doc / robustness.qbk

[/============================================================================
  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]
Commit	Line	Data
7c673cae FG	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