GEOMETRY
Geometric Calculations

GEOMETRY is a FORTRAN77 library which carries out geometric calculations in 2, 3 and N dimensional 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.

Licensing:

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

Related Data and Programs:

DUTCH is a FORTRAN90 library which carries out tasks in computational geometry.

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

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

TETRAHEDRONS, a dataset directory which contains examplesof tetrahedrons;

TRIANGULATION_DISPLAY_OPEN_GL is a C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_TRIANGLE_NEIGHBORS is a FORTRAN90 program which reads data defining a triangulation, determines the neighboring triangles of each triangle, and writes that information to a file.

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.
7. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0.
8. Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart,
   LINPACK User's Guide,
   SIAM, 1979,
   ISBN13: 978-0-898711-72-1.
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
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. Jack Kuipers,
    Quaternions and Rotation Sequences,
    Princeton, 1998,
    ISBN: 0691102988.
16. 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.
17. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
18. Atsuyuki Okabe, Barry Boots, Kokichi Sugihara, Sung Nok Chiu,
    Spatial Tesselations: Concepts and Applications of Voronoi Diagrams,
    Second Edition,
    Wiley, 2000,
    , LC: QA278.2.O36,
    ISBN: 0-471-98635-6.
19. Joseph ORourke,
    Computational Geometry,
    Second Edition,
    Cambridge, 1998,
    ISBN: 0521649765,
    LC: QA448.D38.
20. Edward Saff, Arno Kuijlaars,
    Distributing Many Points on a Sphere,
    The Mathematical Intelligencer,
    Volume 19, Number 1, 1997, pages 5-11.
21. 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.
22. M Shimrat,
    Position of Point Relative to Polygon,
    ACM Algorithm 112,
    Communications of the ACM,
    Volume 5, Number 8, page 434, August 1962.
23. Kenneth Stephenson,
    Introduction to Circle Packing, The Theory of Discrete Analytic Functions,
    Cambridge, 2005,
    ISBN: 0521823560,
    LC: QA640.7S74.
24. 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.
25. Daniel Zwillinger, Steven Kokoska,
    Standard Probability and Statistical Tables,
    CRC Press, 2000,
    ISBN 1-58488-059-7.

Source Code:

• geometry.f, the source code;
• geometry.csh, commands to compile the source code;

Examples and Tests:

• geometry_prb.f, the calling program;
• geometry_prb.csh, commands to compile, link and run the sample test program;
• geometry_prb_output.txt, the output file.

List of Routines:

• ANGLE_CONTAINS_POINT_2D determines if an angle contains a point, in 2D.
• ANGLE_DEG_2D returns the angle swept out between two rays in 2D.
• ANGLE_HALF_2D finds half an angle in 2D.
• ANGLE_RAD_2D returns the angle in radians swept out between two rays in 2D.
• ANGLE_RAD_3D returns the angle in radians between two rays in 3D.
• ANNULUS_AREA_2D computes the area of a circular annulus in 2D.
• ANNULUS_SECTOR_AREA_2D computes the area of an annular sector in 2D.
• ANNULUS_SECTOR_CENTROID_2D computes the centroid of an annular sector in 2D.
• ARC_COSINE computes the arc cosine function, with argument truncation.
• ARC_SINE computes the arc sine function, with argument truncation.
• ATAN4 computes the inverse tangent of the ratio Y / X.
• BALL_UNIT_SAMPLE_2D picks a random point in the unit ball in 2D.
• BALL_UNIT_SAMPLE_3D picks a random point in the unit ball in 3D.
• BALL_UNIT_SAMPLE_ND picks a random point in the unit ball in ND.
• BOX_01_CONTAINS_POINT_2D determines if a point is inside the unit box in 2D.
• BOX_01_CONTAINS_POINT_ND determines if a point is inside the unit box in ND.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CIRCLE_AREA_2D computes the area of a circle in 2D.
• CIRCLE_DIA2IMP_2D converts a diameter to an implicit circle in 2D.
• CIRCLE_IMP_CONTAINS_POINT_2D: implicit circle contains a point in 2D?
• CIRCLE_IMP_LINE_EXP_DIST_2D: distance ( implicit circle, explicit line ) in 2D.
• CIRCLE_IMP_LINE_PAR_INT_2D: ( implicit circle, parametric line ) intersection in 2D.
• CIRCLE_SECTOR_AREA_2D computes the area of a circular sector in 2D.
• CIRCLE_SECTOR_CENTROID_2D returns the centroid of a circular sector in 2D.
• CIRCLE_TRIANGLE_AREA_2D returns the area of a circle triangle in 2D.
• CONE_AREA_3D computes the surface area of a right circular cone in 3D.
• CONE_CENTROID_3D returns the centroid of a cone in 3D.
• CONE_VOLUME_3D computes the volume of a right circular cone in 3D.
• COS_DEG returns the cosine of an angle given in degrees.
• CUBE_SIZE_3D gives "sizes" for a cube in 3D.
• CYLINDER_VOLUME_3D determines the volume of a cylinder in 3D.
• DEGREES_TO_RADIANS converts an angle from degrees to radians.
• DODEC_SIZE_3D gives "sizes" for a dodecahedron in 3D.
• DUAL_SIZE_3D determines sizes for a dual of a shape in 3D.
• ELLIPSE_AREA_2D returns the area of an ellipse in 2D.
• GET_SEED returns a seed for the random number generator.
• GET_UNIT returns a free FORTRAN unit number.
• I4_GCD finds the greatest common divisor of I and J.
• I4_HUGE returns a "huge" I4.
• I4_LCM computes the least common multiple of two I4's.
• I4_MODP returns the nonnegative remainder of integer division.
• I4_SWAP switches two I4's.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4COL_COMPARE compares columns I and J of an I4COL.
• I4COL_FIND_ITEM searches an I4COL for a given scalar value.
• I4COL_FIND_PAIR_WRAP searches an I4COL for a pair of items.
• I4COL_SORT_A ascending sorts an I4COL.
• I4COL_SORTED_UNIQUE_COUNT counts unique elements in an I4COL.
• I4COL_SWAP swaps columns J1 and J2 of an I4COL.
• I4MAT_PRINT prints an I4MAT.
• I4MAT_PRINT_SOME prints some of an I4MAT.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• I4VEC_LCM returns the least common multiple of an I4VEC.
• I4VEC_PRODUCT returns the product of the entries of an I4VEC.
• I4VEC_HEAP_D reorders an I4VEC into an descending heap.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_REVERSE reverses the elements of an I4VEC.
• I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.
• I4VEC_ZERO sets the entries of an I4VEC to 0.
• ICOS_SIZE_3D gives "sizes" for an icosahedron in 3D.
• LINE_EXP_IS_DEGENERATE_ND finds if an explicit line is degenerate in ND.
• LINE_EXP_POINT_DIST_2D: distance ( explicit line, point ) in 2D.
• OCTAHEDRON_SIZE_3D returns size information for an octahedron in 3D.
• POINTS_HULL_2D computes the convex hull of 2D points.
• POLAR_TO_XY converts polar coordinates to XY coordinates.
• POLYHEDRON_VOLUME_3D computes the volume of a polyhedron in 3D.
• PYRAMID_VOLUME_3D computes the volume of a pyramid with square base in 3D.
• QUAD_AREA_2D computes the area of a quadrilateral in 2D.
• QUAD_CONTAINS_POINT_2D finds if a point is inside a convex quadrilateral in 2D.
• QUAD_CONVEX_RANDOM returns a random convex quadrilateral.
• QUAD_POINT_DIST_2D: distance ( quadrilateral, point ) in 2D.
• QUAT_CONJ conjugates a quaternion.
• QUAT_INV inverts a quaternion.
• QUAT_MUL multiplies two quaternions.
• QUAT_NORM computes the norm of a quaternion.
• R4_UNIFORM_01 returns a unit pseudorandom R4.
• R8_IS_INT determines if an R8 represents an integer value.
• R8_MODP returns the nonnegative remainder of R8 division.
• R8_NORMAL_01 returns a unit pseudonormal R8.
• R8_PI returns the value of pi as an R8.
• R8_SWAP switches two R8's.
• R8_UNIFORM returns a scaled pseudorandom R8.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8VEC_BRACKET searches a sorted array for successive brackets of a value.
• R8VEC_CROSS_3D computes the cross product of two R8VEC's in 3D.
• R8VEC_DOT finds the dot product of a pair of R8VEC's.
• R8VEC_GT == ( A1 > A2 ) for double precision vectors.
• R8VEC_LENGTH returns the Euclidean length of a vector.
• R8VEC_LT == ( A1 < A2 ) for double precision vectors.
• R8VEC_NORMAL_01 returns a unit pseudonormal R8VEC.
• R8VEC_UNIFORM returns a scaled pseudorandom R8VEC.
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• RADIANS_TO_DEGREES converts an angle from radians to degrees.
• SOCCER_SIZE_3D gives "sizes" for a truncated icosahedron in 3D.
• SIMPLEX_LATTICE_LAYER_POINT_NEXT: next simplex lattice layer point.
• SIMPLEX_LATTICE_POINT_NEXT returns the next simplex lattice point.
• SIMPLEX_UNIT_LATTICE_POINT_NUM_ND: count lattice points.
• SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
• SPHERE_DISTANCE1 computes great circle distances on a sphere.
• SPHERE_DISTANCE2 computes great circle distances on a sphere.
• SPHERE_DISTANCE3 computes great circle distances on a sphere.
• SUPER_ELLIPSE_POINTS_2D returns N points on a tilted superellipse in 2D.
• TAN_DEG returns the tangent of an angle given in degrees.
• TETRAHEDRON_FACE_ANGLES_3D returns the 12 face angles of a tetrahedron 3D.
• TETRAHEDRON_LATTICE_LAYER_POINT_NEXT: next tetrahedron lattice layer point.
• TETRAHEDRON_LATTICE_POINT_NEXT returns the next tetrahedron lattice point.
• TETRAHEDRON_RHOMBIC_SIZE_3D gives "sizes" for a rhombic tetrahedron in 3D.
• TETRAHEDRON_SIZE_3D gives "sizes" for a tetrahedron in 3D.
• TETRAHEDRON_UNIT_LATTICE_POINT_NUM_3D: count lattice points.
• TIMESTAMP prints out the current YMDHMS date as a timestamp.
• TORUS_AREA_3D returns the area of a torus in 3D.
• TORUS_VOLUME_3D computes the volume of a torus in 3D.
• TRIANGLE_ANGLES_2D computes the angles of a triangle in 2D.
• TRIANGLE_ANGLES_3D computes the angles of a triangle in 3D.
• TRIANGLE_AREA_2D computes the area of a triangle in 2D.
• TRIANGLE_AREA_3D computes the area of a triangle in 3D.
• TRIANGLE_AREA_3D_2 computes the area of a triangle in 3D.
• TRIANGLE_AREA_HERON computes the area of a triangle using Heron's formula.
• TRIANGLE_CENTROID_2D computes the centroid of a triangle in 2D.
• TRIANGLE_CENTROID_3D computes the centroid of a triangle in 3D.
• TRIANGLE_LATTICE_LAYER_POINT_NEXT: next triangle lattice layer point.
• TRIANGLE_LATTICE_POINT_NEXT returns the next triangle lattice point.
• TRIANGLE_RIGHT_LATTICE_POINT_NUM_2D: count lattice points.
• TRIANGLE_UNIT_LATTICE_POINT_NUM_2D: count lattice points.
• TRUNCATED_OCTAHEDRON_SIZE_3D gives "sizes" for a truncated octahedron in 3D.
• XY_TO_POLAR converts XY coordinates to polar coordinates.
• XYZ_TO_RADEC converts (X,Y,Z) to right ascension/declination coordinates.
• XYZ_TO_RTP converts (X,Y,Z) to (R,Theta,Phi) coordinates.

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