 x Rectilinear polygon Encyclopedia
A rectilinear polygon is a polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...

all of whose edges meet at right angle
Right angle
In geometry and trigonometry, a right angle is an angle that bisects the angle formed by two halves of a straight line. More precisely, if a ray is placed so that its endpoint is on a line and the adjacent angles are equal, then they are right angles...

s. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygon
Isothetic polygon
An isothetic polygon is a polygon whose alternate sides belong to two parametric families of straight lines which are pencils of lines with centers at two points...

s.

In many cases another definition is preferable: a rectilinear polygon is a polygon with sides parallel to the axes of Cartesian coordinates
Cartesian coordinate system
A Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...

. 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 rectangle
Rectangle
In Euclidean plane geometry, a rectangle is any quadrilateral with four right angles. The term "oblong" is occasionally used to refer to a non-square rectangle...

s, 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.
• They are convenient for the representation of shapes in integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...

Integrated circuit layout
Integrated circuit layout, also known IC layout, IC mask layout, or mask design, is the representation of an integrated circuit in terms of planar geometric shapes which correspond to the patterns of metal, oxide, or semiconductor layers that make up the components of the integrated circuit.When...

s due to their simplicity for design and manufacturing. Many manufactured objects result in orthogonal polygons.
• Problems in computational geometry
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

stated in terms polygons often allow for more efficient algorithms
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

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.

## 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
Simple polygon
In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....

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

(under polyhedron
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...

, "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
Orthogonal convex hull
In Euclidean geometry, a set K\subset\R^n is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single interval...

construction
• Boolean operation
Boolean operation
Boolean operation or Boolean operator may refer to one of the following related meanings.*Boolean function*an operation in a Boolean algebra; in particular:**operations over the algebra of sets: union , intersection , etc....

s/Boolean expression
Boolean expression
In computer science, a Boolean expression is an expression in a programming language that produces a Boolean value when evaluated, i.e. one of true or false...

s for orthogonal polygons (e.g., intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....

and union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

)
• Motion planning
Motion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....

/path planning/routing
Routing
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...

among restilinear obstacles
• Visibility problems (Illumination problem
Illumination problem
The illumination problem is a resolved mathematical problem first posed by Ernst Straus in the 1950s. Straus asked if a room with mirrored walls can always be illuminated by a single point light source, allowing for repeated reflection of light off the mirrored walls...

s)
• Rectilinear art gallery problems
• Rectangular decomposition (partition/packing/covering with rectangles)
• Maximal empty rectangle 