POLYGON_PROPERTIES
Compute Properties of an Arbitrary Polygon

POLYGON_PROPERTIES is a C++ library which computes properties of an arbitrary polygon in the plane, defined by a sequence of vertices, including

• angles;
• area;
• centroid;
• containment of a point;
• diameter;
• expand polygon outward by H;
• inradius of regular polygon to area, outradius side length;
• integral over polygon of 1, x, x^2, xy, y, y^2;
• is polygon convex?;
• lattice area;
• outradius of regular polygon to area, inradius, side length;
• perimeter;
• point to polygon distance;
• point to nearest point on polygon;
• sampling uniformly;
• side length of regular polygon to area, inradius, outradius;
• triangulation (decomposition into N-3 triangles).

Licensing:

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

Languages:

POLYGON_PROPERTIES is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

GEOMETRY, a C++ library which performs geometric calculations in 2, 3 and N dimensional space.

HYPERSPHERE_PROPERTIES, a C++ library which carries out various operations for an M-dimensional hypersphere, including converting between Cartesian and spherical coordinates, stereographic projection, sampling the surface of the sphere, and computing the surface area and volume.

POLYGON_INTEGRALS, a C++ library which returns the exact value of the integral of any monomial over the interior of a polygon in 2D.

POLYGON_MONTE_CARLO, a C++ library which applies a Monte Carlo method to estimate the integral of a function over the interior of a polygon in 2D.

POLYGON_TRIANGULATE, a C++ library which triangulates a possibly nonconvex polygon, and which can use gnuplot to display the external edges and internal diagonals of the triangulation.

TETRAHEDRON_PROPERTIES, a C++ program which computes properties of a given tetrahedron.

TRIANGLE_PROPERTIES, a C++ program which computes properties of a triangle whose vertex coordinates are read from 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. 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.
5. Moshe Shimrat,
   Algorithm 112: Position of Point Relative to Polygon,
   Communications of the ACM,
   Volume 5, Number 8, August 1962, page 434.
6. 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.

Source Code:

• polygon_properties.cpp, the source code.
• polygon_properties.hpp, the include file.

Examples and Tests:

• polygon_properties_test.cppa>, a sample calling program.
• polygon_properties_test.txt, the output file.

List of Routines:

• ANGLE_HALF finds half an angle.
• ANGLE_RAD returns the angle in radians swept out between two rays.
• BETWEEN is TRUE if vertex C is between vertices A and B.
• COLLINEAR returns a measure of collinearity for three points.
• DIAGONAL: VERTEX(IM1) to VERTEX(IP1) is a proper internal diagonal.
• DIAGONALIE is true if VERTEX(IM1):VERTEX(IP1) is a proper diagonal.
• I4_MODP returns the nonnegative remainder of I4 division.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• IN_CONE is TRUE if the diagonal VERTEX(IM1):VERTEX(IP1) is strictly internal.
• INTERSECT is true if lines VA:VB and VC:VD intersect.
• INTERSECT_PROP is TRUE if lines VA:VB and VC:VD have a proper intersection.
• L4_XOR returns the exclusive OR of two L4's.
• POLYGON_ANGLES computes the interior angles of a polygon.
• POLYGON_AREA computes the area of a polygon.
• POLYGON_AREA_2 computes the area of a polygon.
• POLYGON_CENTROID computes the centroid of a polygon.
• POLYGON_CENTROID_2 computes the centroid of a polygon.
• POLYGON_CONTAINS_POINT finds if a point is inside a simple polygon .
• POLYGON_CONTAINS_POINT_2 finds if a point is inside a convex polygon.
• POLYGON_DIAMETER computes the diameter of a polygon.
• POLYGON_EXPAND expands a polygon.
• POLYGON_INRAD_DATA determines polygonal data from its inner radius.
• POLYGON_INTEGRAL_1 integrates the function 1 over a polygon.
• POLYGON_INTEGRAL_X integrates the function X over a polygon.
• POLYGON_INTEGRAL_XX integrates the function X*X over a polygon.
• POLYGON_INTEGRAL_XY integrates the function X*Y over a polygon.
• POLYGON_Y integrates the function Y over a polygon.
• POLYGON_INTEGRAL_YY integrates the function Y*Y over a polygon.
• POLYGON_IS_CONVEX determines whether a polygon is convex in 2D.
• POLYGON_LATTICE_AREA computes the area of a lattice polygon.
• POLYGON_OUTRAD_DATA determines polygonal data from its outer radius.
• POLYGON_POINT_DIST: distance ( polygon, point ).
• POLYGON_POINT_NEAR computes the nearest point on a polygon.
• POLYGON_SAMPLE uniformly samples a polygon.
• POLYGON_SIDE_DATA determines polygonal data from its side length.
• POLYGON_TRIANGULATE determines a triangulation of a polygon.
• R8_DEGREES converts an angle from radian to degree measure.
• R8_HUGE returns a "huge" R8.
• R8_MAX returns the maximum of two R8's.
• R8_MIN returns the minimum of two R8's.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8MAT_SOLVE uses Gauss-Jordan elimination to solve an N by N linear system.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• R8VEC_NORM returns the L2 norm of an R8VEC.
• R8VEC_PRINT prints an R8VEC.
• R8VEC_SUM returns the sum of an R8VEC.
• R8VEC_UNIFORM_01_NEW returns a new unit pseudorandom R8VEC.
• SEGMENT_POINT_DIST: distance ( line segment, point ).
• SEGMENT_POINT_NEAR finds the point on a line segment nearest a point.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRIANGLE_AREA computes the signed area of a triangle.
• TRIANGLE_BARYCENTRIC finds the barycentric coordinates of a point.
• TRIANGLE_CONTAINS_POINT_1 finds if a point is inside a triangle.

You can go up one level to the C++ source codes.