GEOMETRY
Geometric Calculations


GEOMETRY is a MATLAB library which carries out geometric calculations in 2, 3 and N space.

These calculations include angles, areas, containment, distances, intersections, lengths, and volumes.

Some geometric objects can be described in a variety of ways. For instance, a line has implicit, explicit and parametric representations. The names of routines often will specify the representation used, and there are routines to convert from one representation to another.

Another useful task is the delineation of a standard geometric object. For instance, there is a routine that will return the location of the vertices of an octahedron, and others to produce a series of "equally spaced" points on a circle, ellipse, sphere, or within the interior of a triangle.

Note that I much prefer vectors to be expressed as column vectors; MATLAB, on the other hand, seems to make it easier to work with row vectors. In my original codes, I primarily used row vectors, but I have determined to convert to column vectors; the code is in the middle of this transition, so in some cases there may be be some inconsistencies in style, and accidental inconsistencies in use. On the other hand, I am willing to put up with the practice of declaring a column vector's entries as though they were in a matrix of dimension n by 1, since this guarantees me that, for instance, a dot product is written as (u' * v), and everything finally makes sense to me.

An open source directory of computational geometry routines is available at http://www.cgal.org, the Computational Geometry Algorithms Library.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

GEOMETRY is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Programs:

DUTCH, a FORTRAN90 library which carries out various computational geometry tasks.

GEOMPACK, a MATLAB library which computes the Delaunay triangulation and Voronoi diagram of 2D data.

POLYGON_MOMENTS, a MATLAB library which computes arbitrary moments of a polygon.

SIMPLEX_COORDINATES, a MATLAB library which computes the Cartesian coordinates of the vertices of a regular simplex in M dimensions.

SPHERE_GRID, a MATLAB library which provides a number of ways of generating grids of points, or of points and lines, or of points and lines and faces, over the unit sphere.

SPHERE_STEREOGRAPH, a MATLAB library which computes the stereographic mapping between points on the unit sphere and points on the plane Z = 1.

TETRAHEDRON_PROPERTIES, a MATLAB program which computes properties of a given tetrahedron.

TETRAHEDRONS, a dataset directory which contains examples of tetrahedrons;

TRIANGLES, a dataset directory which contains examples of triangles;

TRIANGULATE, a C program which triangulates a (possibly nonconvex) polygon.

TRIANGULATION, a MATLAB library which defines and analyzes triangulations.

Reference:

  1. Gerard Bashein, Paul Detmer,
    Centroid of a Polygon,
    in Graphics Gems IV,
    edited by Paul Heckbert,
    AP Professional, 1994,
    ISBN: 0123361559,
    LC: T385.G6974.
  2. SF Bockman,
    Generalizing the Formula for Areas of Polygons to Moments,
    American Mathematical Society Monthly,
    Volume 96, Number 2, February 1989, pages 131-132.
  3. Adrian Bowyer, John Woodwark,
    A Programmer's Geometry,
    Butterworths, 1983,
    ISBN: 0408012420.
  4. Paulo Cezar Pinto Carvalho, Paulo Roma Cavalcanti,
    Point in Polyhedron Testing Using Spherical Polygons,
    in Graphics Gems V,
    edited by Alan Paeth,
    Academic Press, 1995,
    ISBN: 0125434553,
    LC: T385.G6975.
  5. Daniel Cohen,
    Voxel Traversal along a 3D Line,
    in Graphics Gems IV,
    edited by Paul Heckbert,
    AP Professional, 1994,
    ISBN: 0123361559,
    LC: T385.G6974.
  6. Thomas Cormen, Charles Leiserson, Ronald Rivest,
    Introduction to Algorithms,
    MIT Press, 2001,
    ISBN: 0262032937,
    LC: QA76.C662.
  7. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
    Computational Geometry,
    Springer, 2000,
    ISBN: 3-540-65620-0,
    LC: QA448.D38.C65.
  8. Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart,
    LINPACK User's Guide,
    SIAM, 1979,
    ISBN13: 978-0-898711-72-1,
    LC: QA214.L56.
  9. James Foley, Andries vanDam, Steven Feiner, John Hughes,
    Computer Graphics, Principles and Practice,
    Second Edition,
    Addison Wesley, 1995,
    ISBN: 0201848406,
    LC: T385.C5735.
  10. Martin Gardner,
    The Mathematical Carnival,
    Knopf, 1975,
    ISBN: 0394494067,
    LC: QA95.G286.
  11. Priamos Georgiades,
    Signed Distance From Point To Plane,
    in Graphics Gems III,
    edited by David Kirk,
    Academic Press, 1992,
    ISBN: 0124096735,
    LC: T385.G6973.
  12. Branko Gruenbaum, Geoffrey Shephard,
    Pick's Theorem,
    The American Mathematical Monthly,
    Volume 100, Number 2, February 1993, pages 150-161.
  13. John Harris, Horst Stocker,
    Handbook of Mathematics and Computational Science,
    Springer, 1998,
    ISBN: 0-387-94746-9,
    LC: QA40.S76.
  14. Barry Joe,
    GEOMPACK - a software package for the generation of meshes using geometric algorithms,
    Advances in Engineering Software,
    Volume 13, 1991, pages 325-331.
  15. Anwei Liu, Barry Joe,
    Quality Local Refinement of Tetrahedral Meshes Based on 8-Subtetrahedron Subdivision,
    Mathematics of Computation,
    Volume 65, Number 215, July 1996, pages 1183-1200.
  16. Jack Kuipers,
    Quaternions and Rotation Sequences,
    Princeton, 1998,
    ISBN: 0691102988,
    LC: QA196.K85.
  17. Robert Miller,
    Computing the Area of a Spherical Polygon,
    in Graphics Gems IV,
    edited by Paul Heckbert,
    Academic Press, 1994,
    ISBN: 0123361559,
    LC: T385.G6974.
  18. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
  19. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
    Spatial Tesselations: Concepts and Applications of Voronoi Diagrams,
    Second Edition,
    Wiley, 2000,
    , ISBN: 0-471-98635-6,
    LC: QA278.2.O36.
  20. Joseph ORourke,
    Computational Geometry,
    Second Edition,
    Cambridge, 1998,
    ISBN: 0521649765,
    LC: QA448.D38.
  21. Edward Saff, Arno Kuijlaars,
    Distributing Many Points on a Sphere,
    The Mathematical Intelligencer,
    Volume 19, Number 1, 1997, pages 5-11.
  22. Philip Schneider, David Eberly,
    Geometric Tools for Computer Graphics,
    Elsevier, 2002,
    ISBN: 1558605940,
    LC: T385.S334.
  23. Peter Schorn, Frederick Fisher,
    Testing the Convexity of a Polygon,
    in Graphics Gems IV,
    edited by Paul Heckbert,
    AP Professional, 1994,
    ISBN: 0123361559,
    LC: T385.G6974.
  24. Moshe Shimrat,
    Algorithm 112: Position of Point Relative to Polygon,
    Communications of the ACM,
    Volume 5, Number 8, August 1962, page 434.
  25. Kenneth Stephenson,
    Introduction to Circle Packing, The Theory of Discrete Analytic Functions,
    Cambridge, 2005,
    ISBN: 0521823560,
    LC: QA640.7S74.
  26. Allen VanGelder,
    Efficient Computation of Polygon Area and Polyhedron Volume,
    in Graphics Gems V,
    edited by Alan Paeth,
    AP Professional, 1995,
    ISBN: 0125434553,
    LC: T385.G6975.
  27. Daniel Zwillinger, Steven Kokoska,
    Standard Probability and Statistical Tables,
    CRC Press, 2000,
    ISBN: 1-58488-059-7,
    LC: QA273.3.Z95.

Source code:

Examples and Tests:

You can go up one level to the MATLAB source codes.


Last revised on 25 July 2011.