 Rectilinear polygon

A rectilinear polygon is a polygon all of whose edges meet at right angles. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygons.
In many cases another definition is preferable: a rectilinear polygon is a polygon with sides parallel to the axes of Cartesian coordinates. The distinction becomes crucial when spoken about sets of polygons: the latter definition would imply that sides of all polygons in the set are aligned with the same coordinate axes. Within the framework of the second definition it is natural to speak of horizontal edges and vertical edges of a rectilinear polygon.
Rectilinear polygons are also known as orthogonal polygons. Other terms in use are isooriented, axisaligned, and axisoriented polygons. These adjectives are less confusing when the polygons of this type are rectangles, and the term axisaligned rectangle is preferred, although orthogonal rectangle and rectilinear rectangle are in use as well.
The importance of the class of rectilinear polygons comes from the following.
 They are convenient for the representation of shapes in integrated circuit mask layouts due to their simplicity for design and manufacturing. Many manufactured objects result in orthogonal polygons.
 Problems in computational geometry stated in terms polygons often allow for more efficient algorithms when restricted to orthogonal polygons. An example is provided by the art gallery theorem for orthogonal polygons, which leads to more efficient guard coverage than is possible for arbitrary polygons.
Contents
Properties
 The numbers of vertical and horizontal edges of a rectilinear polygon are equal.
 Corollary: Orthogonal polygons have an even number of edges.
 The number of 270° interior angles in a simple orthogonal polygon is four less than the number of 90° interior angles.
 Corollary: any rectilinear polygon has at least four 90° interior angles.
Special cases and generalizations
 orthogonally convex rectilinear polygon
 Axisaligned rectangle
 Monotone rectilinear polygon, a monotone polygon which is also rectilinear
 Rectilinear polygon with (rectilinear) holes
 Rectilinear polyhedron
 Rectilinearity [1]
See also orthogonal polyhedra (under polyhedron, "Other important families of polyhedra"), the natural generalization of orthogonal polygons to 3D.
Algorithmic problems involving rectilinear polygons
Most of them may be stated for general polygons as well, but expectation of more efficient algorithms warrants a separate consideration
 Orthogonal range searching
 Orthogonal convex hull construction
 Boolean operations/Boolean expressions for orthogonal polygons (e.g., intersection and union)
 Motion planning/path planning/routing among restilinear obstacles
 Visibility problems (Illumination problems)
 Rectilinear art gallery problems
 Rectangular decomposition (partition/packing/covering with rectangles)
 Maximal empty rectangle
References
 Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry  An Introduction. Springer. 1st edition: ISBN 0387961313; 2nd printing, corrected and expanded, 1988: ISBN 3540961313., chapter 8: "The Geometry of Rectangles"
Categories: Polygons
Wikimedia Foundation. 2010.