Polygon with holes

Polygons with holes, with simply connected brown regions and interior boundaries, including degenerate cases of single vertices and edges, (a,b,f).
An annulus can be approximated by two n-sided boundaries with the same center, but different radius.

In geometry, a polygon with holes is an area-connected planar polygon with one external boundary and one or more interior boundaries (holes).[1] Polygons with holes can be dissected into multiple polygons by adding new edges, so they are not frequently needed.

An ordinary polygon can be called simply-connected, while a polygon-with-holes is multiply-connected. An H-holed-polygon is H-connected.[2]

Degenerate holes

[edit]

Degenerate cases may be considered, but a well-formed holed-polygon must have no contact between exterior and interior boundaries, or between interior boundaries. Nondegenerate holes should have 3 or more sides, excluding internal point boundaries (monogons) and single edge boundaries (digons).

Boundary orientation

[edit]

Area fill algorithms in computational lists the external boundary vertices can be listed in counter-clockwise order, and interior boundaries clockwise. This allows the interior area to be defined as left of each edge.[3]

Conversion to ordinary polygon

[edit]

A polygons with holes can be transformed into an ordinary unicursal boundary path by adding (degenerate) connecting double-edges between boundaries, or by dissecting or triangulating it into 2 or more simple polygons.

Example conversion of a single-holed polygon by connecting edges, or dissection

In polyhedra

[edit]

Polygons with holes can be seen as faces in polyhedra, like a cube with a smaller cube externally placed on one of its square faces (augmented), with their common surfaces removed. A toroidal polyhedron can also be defined connecting a holed-face to a holed-faced on the opposite side (excavated). The 1-skeleton (vertices and edges) of a polyhedron with holed-faces is not a connected graph. Each set of connected edges will make a separate polyhedron if their edge-connected holes are replaced with faces.

The Euler characteristic of hole-faced polyhedron is χ = V - E + F = 2(1-g) + H, genus g, for V vertices, E edges, F faces, and H holes in the faces.

Examples
Examples with degenerate holes

A face with a point hole is considered a monogonal hole, adding one vertex, and one edge, and can attached to a degenerate monogonal hosohedron hole, like a cylinder hole with zero radius. A face with a degenerate digon hole adds 2 vertices and 2 coinciding edges, where the two edges attach to two coplanar faces, as a dihedron hole.

See also

[edit]

References

[edit]
  1. ^ Somerville, D. M. Y. (1929), "IX.4: Polyhedra with ring-shaped faces", An Introduction To The Geometry Of Dimensions, Methuen & Co., pp. 144–145
  2. ^ O'Rourke, Joseph (1987), "Chapter 5: Holes" (PDF), Art Gallery Theorems and Algorithms, International Series of Monographs on Computer Science, vol. 3, Oxford University Press, pp. 125–145, ISBN 0-19-503965-3
  3. ^ Urrutia, Jorge (2000), "Art Gallery and Illumination Problems", Handbook of Computational Geometry, Elsevier, pp. 973–1027, doi:10.1016/b978-044482537-7/50023-1, ISBN 9780444825377