Rectilinear polygon

This article is about right-angled polygons. For "rectilineal figure" as defined in Euclid's Elements, seeSimple polygon.

Arectilinear polygonis apolygonall of whosesidesmeet atright angles.Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case ofisothetic polygons.

Some examples of rectilinear polygons

In many cases another definition is preferable: arectilinear polygonis a polygon with sides parallel to the axes ofCartesian 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 ofhorizontal edgesandvertical edgesof a rectilinear polygon.

Rectilinear polygons are also known asorthogonal polygons.Other terms in use areiso-oriented,axis-aligned,andaxis-oriented polygons.These adjectives are less confusing when the polygons of this type arerectangles,and the termaxis-aligned rectangleis preferred, althoughorthogonal rectangleandrectilinear rectangleare in use as well.

The importance of the class of rectilinear polygons comes from the following.

• They are convenient for the representation of shapes inintegrated circuitmask layoutsdue to their simplicity for design and manufacturing. Many manufactured objects result in orthogonal polygons.
• Problems incomputational geometrystated in terms of polygons often allow for moreefficient algorithmswhen restricted to orthogonal polygons. An example is provided by theart gallery theoremfor orthogonal polygons, which leads to more efficient guard coverage than is possible for arbitrary polygons.

Edges

A rectilinear polygon has edges of two types:horizontalandvertical.

• Lemma:The number of horizontal edges is equal to the number of vertical edges (because every horizontal edge is followed by a vertical edge and vice versa).
  • Corollary: Orthogonal polygons have an even number of edges.

X marks convex corners; O marks concave corners. Blue lines are knobs; red lines are anti-knobs; yellow lines are neither.

A rectilinear polygon has corners of two types: corners in which the smaller angle (90°) is interior to the polygon are calledconvexand corners in which the larger angle (270°) is interior are calledconcave.

Aknobis an edge whose two endpoints are convex corners. Anantiknobis an edge whose two endpoints are concave corners.

Simple rectilinear polygon

A rectilinear polygon that is alsosimpleis also calledhole-freebecause it has no holes - only a single continuous boundary. It has several interesting properties:

1. The number of convex corners is four more than the number of concave corners. To see why, imagine that you traverse the boundary of the polygon clockwise (with your right hand inside the polygon and your left hand outside). At a convex corner, you turn 90° right; at any concave corner, you turn 90° left. Finally you must make an entire 360° turn and come back to the original point; hence the number of right turns must be 4 more than the number of left turns.
   • Corollary: every rectilinear polygon has at least 4 convex corners.
2. The number of knobs (sides connecting two convex corners) is four more than the number of antiknobs (sides connecting two concave corners).To see why, letXbe the number of convex corners andYthe number of concave corners. By the previous fact,X=Y+4.LetXXthe number of convex corners followed by a convex corner,XYthe number of convex corners followed by a concave corner,YXandYYdefined analogously. Then obviouslyX=XX+XY=XX+YXandY=XY+YY=YX+YY.HenceXX=X-XY=X-(Y-YY)=YY+(X-Y)=YY+4.
   • Corollary: every rectilinear polygon has at least 4 knobs.

Squares and rectangles in a rectilinear polygon

A rectilinear polygon can be covered by a finite number of squares or rectangles with edges parallel to the edges of the polygon (seePolygon covering). It is possible to distinguish several types of squares/rectangles contained in a certain rectilinear polygonP:

Amaximal squarein a polygonPis a square inPwhich is not contained in any other square inP.Similarly, a maximal rectangle is a rectangle not contained in any other rectangle inP.

A squaresis maximal inPif each pair of adjacent edges ofsintersects the boundary ofP.The proof of both sides is by contradiction:

• If a certain adjacent pair insdoes not intersect the boundary ofP,then this pair be pushed further towards the boundary, sosis not maximal.
• Ifsis not maximal inP,then there is a larger square inPcontainings;the interior of this larger square contains a pair of adjacent edges ofs,hence this pair does not intersect the boundary ofP.

The first direction is also true for rectangles, i.e.: If a rectanglesis maximal, then each pair of adjacent edges ofsintersects the boundary ofP.The second direction is not necessarily true: a rectangle can intersect the boundary ofPin even 3 adjacent sides and still not be maximal as it can be stretched in the 4th side.

Corollary: every maximal square/rectangle inPhas at least two points, on two opposite edges, that intersect the boundary ofP.

Acorner squareis a maximal squaresin a polygonPsuch that at least one corner ofsoverlaps a convex corner ofP.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.

continuator and separator

continuator types

Aseparator squarein a polygonPis a squaresinPsuch thatP−sis not connected.

• Lemma:in a simple rectilinear polygon, a maximal square that does not contain a knob is a separator.A square containing a knob may or may not be a separator. The number of different separator squares may be infinite and even uncountable. For example, in a rectangle, every maximal square not touching one of the shorter sides is a separator.

Acontinuator squareis a squaresin a polygonPsuch that the intersection between the boundary ofsand the boundary ofPis 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). Thebalconyof 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. In a simple rectilinear polygon, every maximal square is either a separator or a continuator. This is also true for rectangles: every maximal rectangle is either a separator or a continuator.
2. In a simple rectilinear polygon which is not a square, there are at least two continuators.

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.

Special cases

The simplest rectilinear polygon is an axis-alignedrectangle- a rectangle with 2 sides parallel to the x axis and 2 sides parallel to the y axis. See also:Minimum bounding rectangle.

Agolygonis a rectilinear polygon whose side lengths in sequence are consecutive integers.

A rectilinear polygon which is not a rectangle is neverconvex,but it can be orthogonally convex. SeeOrthogonally convexrectilinear polygon.

Amonotone rectilinear polygonis amonotone polygonwhich is also rectilinear.

AT-squareis a fractal generated from a sequence of rectilinear polygons with interesting properties.

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 hullconstruction
• Boolean operations on polygonsfor orthogonal polygons (e.g.,intersectionandunion)
• Motion planning/path planning/routingamong rectilinear obstacles
• Visibility problems(Illumination problems)
• Maximal empty rectangle

Rectangular decomposition

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:

• Incoveringproblems, the goal is to find a smallest set of units (squares or rectangles) whose union is equal to the polygon. The units may overlap. SeePolygon covering.
• Inpackingproblems, the goal is to find a largest set of non-overlapping units whose union is contained in the polygon. The union may be smaller than the polygon.
• Inpartitioningproblems, the goal is to find a smallest set of non-overlapping units whose union is exactly equal to the polygon. SeePolygon partition.

See also

• Orthogonal polyhedra,a natural generalization of orthogonal polygons to 3D.

References

• Franco P. PreparataandMichael Ian Shamos(1985).Computational Geometry - An Introduction.Springer.ISBN0-387-96131-3.1st edition; 2nd printing, corrected and expanded, 1988.,chapter 8: "The Geometry of Rectangles"