A rectilinear polygon is a polygon all of whose sides 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 iso-oriented, axis-aligned, and axis-oriented polygons. These adjectives are less confusing when the polygons of this type are rectangles, and the term axis-aligned 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.
A rectilinear polygon has edges of two types: horizontal and vertical.
A rectilinear polygon has corners of two types: corners in which the smaller angle (90°) is interior to the polygon are called convex and corners in which the larger angle (270°) is interior are called concave.[1]
A knob is an edge whose two endpoints are convex corners. An antiknob is an edge whose two endpoints are concave corners.[1]
A rectilinear polygon that is also simple is also called hole-free because it has no holes - only a single continuous boundary. It has several interesting properties:
A rectilinear polygon can be covered by a finite number of squares or rectangles with edges parallel to the edges of the polygon (see Polygon covering). It is possible to distinguish several types of squares/rectangles contained in a certain rectilinear polygon P:[1]
A maximal square in a polygon P is a square in P which is not contained in any other square in P. Similarly, a maximal rectangle is a rectangle not contained in any other rectangle in P.
A square s is maximal in P if each pair of adjacent edges of s intersects the boundary of P. The proof of both sides is by contradiction:
The first direction is also true for rectangles, i.e.: If a rectangle s is maximal, then each pair of adjacent edges of s intersects the boundary of P. The second direction is not necessarily true: a rectangle can intersect the boundary of P in even 3 adjacent sides and still not be maximal as it can be stretched in the 4th side.
Corollary: every maximal square/rectangle in P has at least two points, on two opposite edges, that intersect the boundary of P.
A corner square is a maximal square s in a polygon P such that at least one corner of s overlaps a convex corner of P. For every convex corner, there is exactly one maximal (corner) square covering it, but a single maximal square may cover more than one corner. For every corner, there may by many different maximal rectangles covering it.
A separator square in a polygon P is a square s in P such that P-s is not connected.
A continuator square is a square s in a polygon P such that the intersection between the boundary of s and the boundary of P is continuous. A maximal continuator is always a corner square. Moreover, a maximal continuator always contains a knob. Hence the number of continuators is always finite and bounded by the number of knobs.
There are several different types of continuators, based on the number of knobs they contain and their internal structure (see figure). The balcony of a continuator is defined as its points that are not covered by any other maximal square (see figure).
No square can be both a continuator and a separator. In general polygons, there may be squares that are neither continuators nor separators, but in simple polygons this cannot happen:[1]
There is an interesting analogy between maximal squares in a simple polygon and nodes in a tree: a continuator is analogous to a leaf node and a separator is analogous to an internal node.
The simplest rectilinear polygon is an axis-aligned rectangle - a rectangle with 2 sides parallel to the x axis and 2 sides parallel to the y axis. See also: Minimum bounding rectangle.
A golygon is a rectilinear polygon whose side lengths in sequence are consecutive integers.
A rectilinear polygon which is not a rectangle is never convex, but it can be orthogonally convex. See Orthogonally convex rectilinear polygon .
A monotone rectilinear polygon is a monotone polygon which is also rectilinear.
A T-square is a fractal generated from a sequence of rectilinear polygons with interesting properties.
Most of them may be stated for general polygons as well, but expectation of more efficient algorithms warrants a separate consideration
Of particular interest to rectilinear polygons are problems of decomposing a given rectilinear polygon to simple units - usually rectangles or squares. There are several types of decomposition problems: