Rectilinear polygon

Rectilinear polygon
Some examples of rectilinear polygons

A rectilinear polygon is a polygon all of whose edges 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.

  • They are convenient for the representation of shapes in integrated circuit mask layouts due to their simplicity for design and manufacturing. Many manufactured objects result in orthogonal polygons.
  • Problems in computational geometry stated in terms polygons often allow for more efficient algorithms 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.



  • 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 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
  • Monotone rectilinear polygon, a monotone polygon which is also rectilinear
  • Rectilinear polygon with (rectilinear) holes
  • Rectilinear polyhedron
  • Rectilinearity [1]

See also orthogonal polyhedra (under polyhedron, "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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Rectilinear — may refer to:* Rectilinear grid, a tessellation of the Euclidean plane * Rectilinear lens, a photographic lens * Rectilinear locomotion, a form of animal locomotion * Rectilinear polygon, a polygon whose edges meet at right angles * Rectilinear… …   Wikipedia

  • Polygon — For other uses, see Polygon (disambiguation). Some polygons of different kinds In geometry a polygon (   …   Wikipedia

  • 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 (possibly in the infinity). The most well known example of isothetic polygons are… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Axis-aligned object — In mathematics, an axis aligned object (axis parallel, axis oriented) is an object in n dimensional space whose shape is aligned with the coordinate axes of the space. Examples are axis aligned rectangles (or hyperrectangles), the ones with edges …   Wikipedia

  • Problem der Museumswächter — Das Problem der Museumswächter (en: Art gallery problem) ist eine Fragestellung der Algorithmischen Geometrie. Dabei wird folgende Situation untersucht: „Gegeben sei eine polygonale Fläche G mit Rand , interpretiert als Grundriss eines Museums.… …   Deutsch Wikipedia

  • Point location — The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”