VisiLibity.org for Floating-Point Visibility Computations

What is VisiLibity?
Download VisiLibity
Using VisiLibity

Math behind VisiLibity
Acknowledgements
License, Links
What is VisiLibity?

VisiLibity is a free open source C++ library for floating-point visibility algorithms, path planning, and supporting data types. It is intended for use in robot and sensor network design software. Other possible applications include, e.g., architectural/urban planning, computer games, and education. The entire library consists only of a single compilation unit (one .hpp + one .cpp file) with no dependence on third party libraries. It is therefore suitable for applications where visibility and path planning computations are needed but the power of a fully fledged computational geometry library, e.g., LEDA or CGAL, is not necessary. VisiLibity offers

Current Functionality (for polygonal environments with polygonal holes)

  • visibility polygons
  • visibility graphs
  • Euclidean shortest path planning for a point
Ideas for Future Functionality
  • time complexity improvements
  • curves and generalized polygons
  • shortest paths of bounded curvature (Dubins and Reeds-Shepp vehicles)
  • Minkowski sums and Boolean operations
  • Voronoi partitions (geodesic and standard)
  • extensions to 3D
    • Visibility complexes and path planning over terrains
    • Visibility complexes in general mesh environments
  • efficient point-pair visibility queries via kd-trees
  • triangulations
  • sensor placement / visibility optimization algorithms
Exact/arbitrary precision arithmetic is avoided and robustness is achieved by considering two points to be colocated whenever the Euclidean distance between them is less or equal to a user defined tolerance &epsilon called the robustness constant. If the robustness constant is chosen poorly or the scale of environment features varies too dramatically, library functions can and will return errors. However, provided the user tunes the robustness constant appropriately, we find the library works well for a large range of useful environments. Examples of environments and a Matlab interface (via MEX-files) are available with the download package below.


Download

The following set of files includes the VisiLibity source code as well some other files, one of which is a README file with more detailed instructions:

Version 2010:02:04 (gzip'd tarball)
VisiLibity.2010_02_04.tgz


Using VisiLibity
To use VisiLibity in your C++ program, you simply need to

1. Extract and unzip, e.g., with the terminal command line
    tar -xzf VisiLibity.yyyy_mm_dd.tgz
 2. place an #include "visilibity.hpp" directive at the beginning of your program, and
3. link your program with visilibity.cpp when compiling.

Here is the source code documentation.

When possible, please Cite VisiLibity. For your convenience, here is a BibTeX item 

	@Misc{VisiLibity:08,
	   author =       {Karl J. Obermeyer},
	   title =        {The {VisiLibity} library},
	   howpublished = {\texttt{http://www.VisiLibity.org}},
	   year =         2008,
	   note =         {R-1},
	   abstract =     {A C++ library for floating-point visibility
	                   computations},
	}
Also, I would be very interested to learn what projects VisiLibity has been used for, so if you like, send me an email.

Help and Contributions: To report a bug/bugfix or ask a question, send me an email, but please be sure to check Frequently Asked Questions first. Any other comments you may have are also very welcome, e.g., on overall organization/style of the library, possible future functionality, etc..

Contribution Thanks to
SWIG/Python Bindings Stefanie T. of MIT, United States
Python Bindings with Example Ramiro C. of UNC, Argentina
SWIG/Ruby Bindings Brad E. of Madriska Media Group, United States
Notes on Matlab Interface under Windows Lu L. of TUM, Germany

The Math behind VisiLibity

VisiLibity uses the C++ double type. In this floating-point system a discrete string of bits represents a number from the continuum of real numbers. One indicator of how precisely a floating point system can represent a real number is the so-called machine epsilon (AKA machine precision or unit roundoff) defined as the difference between 1 and the smallest exactly representable number greater than one. In the IEEE 754 Standard for Binary Floating-Point Arithmetic, machine epsilon for double precision on a 32-bit machine is 2^-52 (roughly 2.22x10^-16). Despite this small value, it is well known that the inexact nature of floating-point representation can lead to many problems, e.g.,

  • overflow, underflow, round-off error
  • divide by zero
  • complex values
  • loss of significance when subtracting nearly equal numbers
  • addition and multiplication are both commutative, but not necessarily associative
  • computational sequences that are analytically equal may produce different values
  • small errors can grow very large during an iterative process
  • evaluation of transcentental functions is approximate.
More details on problems associated with floating-point arithmetic can be found, e.g., in ``What Every Computer Scientist Should Know About Floating Point Arithmetic".

So why use floating-point arithmetic? This question is answered quite well in the ``Handbook of Discrete and Computational Geometry" (2nd Edition, p. 930), where Chee K. Yap wrote

``...fast floating-point hardware has become a de facto standard in every computer. If we can make our geometric algorithms robust within machine arithmetic, we are assured of the fastest possible implementation..."
To achieve robustness using floating-point arithmetic, VisiLibity operates using a technique called &epsilon -geometry (AKA interval geometry) in which geometric primitives are fattened by very small amount &epsilon . This involves the use of so-called fuzzy comparisons in which equality tests such as x==y are replaced by fabs(x-y) ≤ &epsilon . When using VisiLibity, &epsilon should typically be chosen somewhere between machine epsilon and the smallest dimension of any feature in the environment geometry at hand.

The aglorithms and methods used in VisiLibity come mostly from these sources: VisiLibity.bib (BibTeX file)


Acknowledgements
License

VisiLibity is licensed under version 3 of the GNU Lesser General Public License.


Links

CGAL: Computational Geometry Algorithms Library
LEDA: Library of Efficient Data types and Algorithms
VISPAK: A package of visibility algorithms written in LEDA
MSL: Motion Strategy Library
MPK: Motion Planning Kit
Proposed Boost Geometry Library
Goemetry Junkyard
Stony-Brook Algorithms Repository
Karl J. Obermeyer | UCSB Mechanical Engineering | UCSB Center for Control and Dynamical Systems