Rectilinear polygon

<h2 id="edges">Edges</h2>
A rectilinear polygon has edges of two types: horizontal and vertical. 

<ul><li>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).
<ul><li>Corollary: Orthogonal polygons have an even number of edges.</li></ul></li></ul>

A rectilinear polygon has corners of two types: corners in which the smaller angle (90°) is interior to the polygon are called convex and corners in which the larger angle (270°) is interior are called concave.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
A knob is an edge whose two endpoints are convex corners. An antiknob is an edge whose two endpoints are concave corners.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="simple-rectilinear-polygon">Simple rectilinear polygon</h2>
A rectilinear polygon that is also <a href="/facts/Simple_polygon/C5CfrPWf">simple</a> is also called hole-free because it has no holes - only a single continuous boundary. It has several interesting properties:

<ol><li>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.
<ul><li>Corollary: every rectilinear polygon has at least 4 convex corners.</li></ul></li>
<li>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, let X be the number of convex corners and Y the number of concave corners. By the previous fact, X=Y+4. Let XX the number of convex corners followed by a convex corner, XY the number of convex corners followed by a concave corner, YX and YY defined analogously. Then obviously X=XX+XY=XX+YX and Y=XY+YY=YX+YY. Hence XX=X-XY=X-(Y-YY)=YY+(X-Y)=YY+4.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
<ul><li>Corollary: every rectilinear polygon has at least 4 knobs.</li></ul></li></ol>
<h2 id="squares-and-rectangles-in-a-rectilinear-polygon">Squares and rectangles in a rectilinear polygon</h2>
A rectilinear polygon can be covered by a finite number of squares or rectangles with edges parallel to the edges of the polygon (see <a href="/facts/Polygon_covering/xAaWDl11">Polygon covering</a>). It is possible to distinguish several types of squares/rectangles contained in a certain rectilinear polygon P:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
A maximal square in a polygon P is a square in P which is not contained in any other square in P. Similarly, a maximal rectangle is a rectangle not contained in any other rectangle in P.
A square s is maximal in P if each pair of adjacent edges of s intersects the boundary of P. The proof of both sides is by contradiction:

<ul><li>If a certain adjacent pair in s does not intersect the boundary of P, then this pair be pushed further towards the boundary, so s is not maximal.</li>
<li>If s is not maximal in P, then there is a larger square in P containing s; the interior of this larger square contains a pair of adjacent edges of s, hence this pair does not intersect the boundary of P.</li></ul>
The first direction is also true for rectangles, i.e.: If a rectangle s is maximal, then each pair of adjacent edges of s intersects the boundary of P. The second direction is not necessarily true: a rectangle can intersect the boundary of P in even 3 adjacent sides and still not be maximal as it can be stretched in the 4th side.
Corollary: every maximal square/rectangle in P has at least two points, on two opposite edges, that intersect the boundary of P.
A corner square is a maximal square s in a polygon P such that at least one corner of s overlaps a convex corner of P. 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.

A separator square in a polygon P is a square s in P such that P−s is not connected.

<ul><li>Lemma: in a simple rectilinear polygon, a maximal square that does not contain a knob is a separator.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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.</li></ul>
A continuator square is a square s in a polygon P such that the intersection between the boundary of s and the boundary of P is 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). The balcony of 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:<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<ol><li>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.</li>
<li>In a simple rectilinear polygon which is not a square, there are at least two continuators.</li></ol>
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.

<h2 id="special-cases">Special cases</h2>
The simplest rectilinear polygon is an axis-aligned <a href="/facts/Rectangle/mdLfIGKA">rectangle</a> - a rectangle with 2 sides parallel to the x axis and 2 sides parallel to the y axis. See also: <a href="/facts/Minimum_bounding_rectangle/yfDEoK8d">Minimum bounding rectangle</a>.
A <a href="/facts/Golygon/Bvf84x2w">golygon</a> is a rectilinear polygon whose side lengths in sequence are consecutive integers.
A rectilinear polygon which is not a rectangle is never <a href="/facts/Convex_polygon/7x35w610">convex</a>, but it can be orthogonally convex. See <a href="/facts/Orthogonally_convex/XRxv9Qg1">Orthogonally convex</a> rectilinear polygon .
A monotone rectilinear polygon is a <a href="/facts/Monotone_polygon/16N42zJL">monotone polygon</a> which is also rectilinear.
A <a href="/facts/T-square_(fractal)/z4ERel87">T-square</a> is a fractal generated from a sequence of rectilinear polygons with interesting properties.

<h2 id="algorithmic-problems-involving-rectilinear-polygons">Algorithmic problems involving rectilinear polygons</h2>
Most of them may be stated for general polygons as well, but expectation of more efficient algorithms warrants a separate consideration

<ul><li><a href="/facts/Orthogonal_range_searching/Fkls9MD3">Orthogonal range searching</a></li>
<li><a href="/facts/Orthogonal_convex_hull/XRxv9Qg1">Orthogonal convex hull</a> construction</li>
<li><a href="/facts/Boolean_operations_on_polygons/5lp152nx">Boolean operations on polygons</a> for orthogonal polygons (e.g., <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> and <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a>)</li>
<li><a href="/facts/Motion_planning/DoSPv4dB">Motion planning</a>/<a href="/facts/Path_planning/DoSPv4dB">path planning</a>/<a href="/facts/Routing/Ml6MVCaC">routing</a> among rectilinear obstacles</li>
<li><a href="/facts/Visibility_problem/Wu1C49qu">Visibility problems</a> (<a href="/facts/Illumination_problem/PyJ6V3Qn">Illumination problems</a>)</li>
<li><a href="/facts/Maximal_empty_rectangle/CueyC31r">Maximal empty rectangle</a></li></ul>
<h2 id="rectangular-decomposition">Rectangular decomposition</h2>
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:

<ul><li>In covering problems, the goal is to find a smallest set of units (squares or rectangles) whose union is equal to the polygon. The units may overlap. See <a href="/facts/Polygon_covering/xAaWDl11">Polygon covering</a>.</li>
<li>In packing problems, 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.</li>
<li>In partitioning problems, the goal is to find a smallest set of non-overlapping units whose union is exactly equal to the polygon. See <a href="/facts/Polygon_partition/LvpV1moS">Polygon partition</a>.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Polyhedron/UC0p9FTF">Orthogonal polyhedra</a>, a natural generalization of orthogonal polygons to 3D.</li></ul>

<ul><li><a href="/facts/Franco_P._Preparata/MDXAqRCW">Franco P. Preparata</a> and <a href="/facts/Michael_Ian_Shamos/38cn2KNA">Michael Ian Shamos</a> (1985). Computational Geometry - An Introduction. <a href="/facts/Springer_Science%252BBusiness_Media/nAesf6nT">Springer</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-96131-3. 1st edition; 2nd printing, corrected and expanded, 1988., chapter 8: "The Geometry of Rectangles"</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"Counting pairs of bits". Stack Exchange. November 17, 2013. <a href="https://math.stackexchange.com/q/570546" target="_blank">https://math.stackexchange.com/q/570546</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Albertson, M. O.; o’Keefe, C. J. (1981). "Covering Regions with Squares". SIAM Journal on Algebraic and Discrete Methods. 2 (3): 240. doi:10.1137/0602026. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time Algorithm for Covering Simple Polygons with Similar Rectangles". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Rectilinear polygon open-in-new

Rectilinear polygon