FastGEO - version 5.0.1

 www.partow.net  .: Home :.   .: Links :.   .: Search :.   .: Contact :. 


FastGEO Logo - Copyright Arash Partow

Description

FastGEO is a library that contains a wide range of highly optimized computational geometry algorithms and routines for many different types of geometrical operations such as geometrical primitives and predicates, hull construction, triangulation, clipping, rotations and projections.

FastGEO offers a concise, predictable, highly deterministic interface for geometric primitives and complex geometric routines using the Object Pascal language.

In the past it has been widely acknowledged by many computational geometers that vectorized primitives are in general the most efficient and highly optimized path for computational geometry solutions. Hence FastGEO's primitives are mainly based around vector primitives that allow for seemingly complex operations to be carried out with little computational over-head hence allowing for high levels of efficiency in more complex algorithms which in theory are composites of the provided geometric primitives.

FastGEO however does not provide an environment for arbitrary precision in its calculations. The results rendered will only be as good as the floating point processor's error rating. A user of the library if needed could in theory modify FastGEO's routines to be forward error correcting, and allow for the sampling of calculation errors, and hence allow for some corrective measures to be undertaken. This is left to the end user of the library.

FastGEO as a library is not object oriented but rather structured, this is due to the fact that many of the algorithms are tightly coupled with the data structures they munge and hence would be computationally irresponsible to also have them endure the over-heads of object orientation. However this doesn't mean FastGEO can't be integrated into an object hierarchy. In fact for complex algorithms such as triangulation and convex hulls it is recommended that an object oriented approach be taken and to use the FastGEO library as a utilities library within the solution.

FastGEO provides an environment where mathematical theory regarding computational geometry can be observed in the real-world using real-world data with little fuss and computational overhead. This type of programming model in conjunction with the usage of the object pascal language provide a good learning base for people interested in computational geometry and its related fields.

The current version of FastGEO has the following capabilities:

  • 2D/3D Orientation primitive
  • 2D/3D Signed area and volume primitive
  • 2D/3D Collinear and coplanar point determination
  • 2D/3D Segment intersection detection
  • 2D/3D Thick segment intersection detection
  • 2D/3D Segment intersection point calculation
  • 2D/3D Segment half point calculation
  • 2D/3D Parallel segment determination
  • 2D/3D Point to point Euclidean, Ley, Manhattan, Chebyshev and inverse Chebyshev distances
  • 2D/3D Vertex angle calculation
  • 2D/3D Geometric span
  • 2D/3D Triangle, quadix, rectangle, circle and polygon area calculation
  • 2D/3D Triangle, quadix, rectangle, circle and polygon perimeter calculation
  • 2D/3D Polygon centroid calculation
  • Polygon-Segment intersection detection
  • Polygon-Polygon intersection detection (convex\concave)
  • Polygon construction routine
  • Point in/on triangle detection
  • Point in/on rectangle detection
  • Point in/on circle detection
  • Point in/on quadix detection
  • Point in/on sphere detection
  • Point in/on convex\concave (non-complex) polygon region detection
  • Circular hull and rectangular hull
  • Spherical hull calculation
  • Torricelli point
  • Incenter
  • Circum-center
  • Inscribed circle
  • Circum-circle
  • Closest point on segment from a point (2D/3D)
  • Closest point on line from a point
  • Closest point on triangle from a point (2D/3D)
  • Closest point on quadix from a point (2D/3D)
  • Closest point on circle from a point
  • Closest point on sphere from a point
  • Closest point on Axis Aligned Bounding Box (AABB) from a point
  • Closest point on circle from a 2D segment
  • Closest point on sphere from a 3D segment
  • Minimum distance from point to segment (2D/3D)
  • Minimum distance from point to line (2D/3D)
  • Cartesian angle relative to point of origin in 2D
  • Point of reflection
  • Point projection along linear path (2D/3D)
  • Clipping of segments against triangles, quadii, rectangles, circles and polygons
  • Conversion from cartesian coordiante to the barycentric coordinate system
  • Conversion from barycentric coordinate to cartesian coordiante system
  • Generate random points within AABB, 2D Triangle, 2D Quadix and Circle
  • Generate random points within 2D Pentagon, Hexagon, Heptagon and Octagon
  • Generate random triangles and circles within AABB
  • 2D/3D Quadratic and Cubic Bezier curve creation
  • Bezier curve length calculation
  • Polygon approximation of supported geometrical objects
  • Mirroring of 2D geometric primitives relative to an arbitrary axis
  • Non-Symmetric mirroring of 2D geometric primitives relative to an arbitrary axis
  • Centering of 2D geometric primitives at a specified location
  • Axis aligned bounding boxes for segments, triangles, quadii, circles and polygons
  • Distance Between 2D/3D Line Segments
  • Distance Between 2D/3D Lines
  • Lay Distance Between 2D/3D Line Segments
  • Lay Distance Between 2D/3D Lines
  • 2D/3D Rotations, fast rotations, translations, scaling and shear
  • 2D/3D Vector addition, subtraction and multiplicationn
  • 2D/3D Unit and magnitude vector calculation
  • 2D/3D Dot product calculation
  • Degenerate type evaluation for geometric primitives such as segments, lines, triangles, quadii, sphere and circle

Compatability

FastGEO is compatible with the following object pascal compilers:

  • Free Pascal Compiler (1.9.x)
  • Borland Delphi (4,5,6,7,8,2005,2006)
  • Borland Kylix (1,2,3)

Credits

The algorithms in FastGEO have been developed using information, techniques and code from the following people and sources:


FastGEO FAQ

A FAQ that covers general questions relating to FastGEO and computational geometry with FastGEO.


FastGEO License

Free use of the FastGEO computational geometry library is permitted under the guidelines and in accordance with the most current version of the "Common Public License."


Current FastGEO Release Version

The current version of the FastGEO computational geometry library has been set at version 5.0.1(stable). No new major release (aka version increment) will be made until the majority of the following capabilities are implemented within the FastGEO frame-work:

  • Rotating Caliper
  • Edge constrained Delaunay Triangulation
  • Convex hull in 3D
  • Additional visualization infrastructure

-Friday 7th Of January 2005


Download


History

  • 21st July 2006

    • Wykobi C++ Computational Geometry Library has been released! www.wykobi.com


  • 6th March 2006

    • Minor bug fix in 3D Bezier curve calculation routine.


  • 1st January 2006

    • Added robust perpendicular tests for segments and lines in 2D/3D.


  • 1st December 2005

    • Added 2D/3D quadratic and cubic Bezier support.
    • Added curve length calculations for Beziers.
    • Added polygon approximations of geometrical objects.
    • Added random point generation for various convex polygons


  • 28th November 2005

    • Optimizations made for segment to triangle, rectangle and quadix intersection routines.
    • Addition of geometric object projections per angle and per vector.


  • 20th November 2005

    • Updated segment and circle intersection point routine


  • 1st November 2005

    • Addition of 2D/3D Robust parallel routine
    • Addition of 3D closest point on line from point routine other various related routines.
    • Minor bug fixes and enhancements


  • 1st August 2005

    • Addition of 2D/3D thick line segment intersection routine
    • Various minor bug fixes and enhancements


  • FastGEO History Of Updates


Recommended Books





Copyright Arash Partow