Rectilinear polygon

Encyclopedia

A

all of whose edges meet at right angle

s. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of isothetic polygon

s.

In many cases another definition is preferable: a

. 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

Rectilinear polygons are also known as

s, and the term

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

See also

(under polyhedron

, "Other important families of polyhedra"),

the natural generalization of orthogonal polygons to 3D.

**rectilinear polygon**is a polygonPolygon

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 coordinatesCartesian 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 rectangleRectangle

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 circuitIntegrated circuitAn 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...

mask layoutIntegrated circuit layoutIntegrated 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 geometryComputational geometryComputational 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 algorithmsComputational complexity theoryComputational 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 simpleSimple polygonIn 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

**orthogonally convex rectilinear polygon**- Axis-aligned rectangle
- Minimum bounding rectangleMinimum bounding rectangleThe minimum bounding rectangle , also known as bounding box or envelope, is an expression of the maximum extents of a 2-dimensional object within its 2-D coordinate system, in other words min, max, min, max...

- Minimum bounding rectangle
**Monotone rectilinear polygon**, a monotone polygonMonotone polygonIn geometry, a polygon P in the plane is called monotone with respect to a straight line L, if every line orthogonal to L intersects P at most twice....

which is also rectilinear- Rectilinear polygon with (rectilinear) holes
- Rectilinear polyhedron
- Rectilinearity http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tp/&toc=comp/trans/tp/2003/09/i9toc.xml&DOI=10.1109/TPAMI.2003.1227997

See also

**orthogonal polyhedra**(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 hullOrthogonal convex hullIn 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 operationBoolean operationBoolean 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 expressionBoolean expressionIn 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., intersectionIntersection (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 unionUnion (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 planningMotion planningMotion planning is a term used in robotics for the process of detailing a task into discrete motions....

/path planning/routingRoutingRouting 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 problemIllumination problemThe 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