POLYGON_GRID
Grid Points in a Polygon

POLYGON_GRID is a Python library which generates a grid of points over the interior of a polygon in 2D.

The program relies on a simple idea in which the "vertex centroid" (average of the vertices) is computed, allowing the polygon to be triangulated. Each triangle can then easily be gridded. The collection of triangular grids joins up to form a grid over the polygon, although the spacing of the the grid points will vary from triangle to triangle.

The program really only works properly for convex polygons. If the polygon is not convex, then the vertex centroid need not lie inside the polygon, consequently the grid points may also seem misaligned.

Licensing:

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

Languages:

POLYGON_GRID 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:

BALL_GRID, a Python library which computes a grid of points over the interior of a ball in 3D.

CIRCLE_ARC_GRID, a Python program which computes points equally spaced along a circular arc;

CUBE_GRID, a Python library which computes a grid of points over the interior of a cube in 3D.

DISK_GRID, a Python library which computes a grid of points over the interior of a disk in 2D.

ELLIPSE_GRID, a Python library which computes a grid of points over the interior of an ellipse in 2D.

ELLIPSOID_GRID, a Python library which computes a grid of points over the interior of an ellipsoid in 3D.

HYPERCUBE_GRID, a Python library which computes a grid of points over the interior of a hypercube in M dimensions.

LINE_GRID, a Python library which computes a grid of points over the interior of a line segment in 1D.

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

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

POLYGON_PROPERTIES, a Python library which computes properties of an arbitrary polygon in the plane, defined by a sequence of vertices, including interior angles, area, centroid, containment of a point, convexity, diameter, distance to a point, inradius, lattice area, nearest point in set, outradius, uniform sampling.

POLYGON_TRIANGULATE, a Python library which triangulates a possibly nonconvex polygon.

PYRAMID_GRID, a Python library which computes a grid of points over the interior of the unit pyramid in 3D;

SIMPLEX_GRID, a Python library which generates a grid of points over the interior of a simplex in M dimensions.

SPHERE_FIBONACCI_GRID, a Python library which uses a Fibonacci spiral to create a grid of points on the surface of the unit sphere in 3D.

SPHERE_LLQ_GRID, a Python library which uses longitudes and latitudes to create grids of points, lines, and quadrilaterals on the surface of the unit sphere in 3D.

SPHERE_LLT_GRID, a Python library which uses longitudes and latitudes to create grids of points, lines, and triangles on the surface of the unit sphere in 3D.

SQUARE_GRID, a Python library which computes a grid of points over the interior of a square in 2D.

TETRAHEDRON_GRID, a Python library which computes a grid of points over the interior of a tetrahedron in 3D.

TRIANGLE_GRID, a Python library which computes a grid of points over the interior of a triangle in 2D.

WEDGE_GRID, a Python library which computes a grid of points over the interior of the unit wedge in 3D.

Source Code:

• polygon_grid_count.py, counts grid points inside a polygon.
• polygon_grid_display.py, displays grid points inside a polygon.
• polygon_grid_points.py, computes grid points inside a polygon.
• r8mat_print.py, prints an R8MAT.
• r8mat_print_some.py, prints some of an R8MAT.
• r8mat_write.py, writes an R8MAT to a file.
• timestamp.py, prints the current YMDHMS date as a time stamp.

Examples and Tests:

• polygon_grid_test.py, calls all the tests.
• polygon_grid_test.sh, runs all the tests.
• polygon_grid_test.txt, the output file.

• polygon_grid_prb.f90, a sample calling program.
• polygon_grid_prb.sh, BASH commands to compile and run the sample program.
• polygon_grid_prb.txt, the output file.

ELL is an L-shaped (non-convex!) polygon for which the program output doesn't look too bad, although the grid is degenerate.

• ell.png a plot of the grid.
• ell.xy the grid points.

QUAD is a quadrilateral polygon.

• quad.png a plot of the grid.
• quad.xy the grid points.

TRIANGLE is a triangular polygon.

• triangle.png a plot of the grid.
• triangle.xy the grid points.

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