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...
  
   mask layout
  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

• orthogonally convex rectilinear polygon
• Axis-aligned rectangle
  • Minimum bounding rectangle
    Minimum bounding rectangle
    The 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...
    
    
• Monotone rectilinear polygon, a monotone polygon
  Monotone polygon
  In 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 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