Generation of Orthogonal Polygons

The generation of geometric objects has applications to the experimental evaluation and testing of geometric algorithms. The need for polygonal test data led several researchers to study generation of random polygons on a given set of vertices. No polynomial time algorithm is known for generating polygons uniformly, so that some generators employ heuristics (T. Auer and M. Held, 1996) or restrict to certain classes of polygons, e.g., monotone, convex (C. Zhu et al., 1996) or star-shaped (C. Sohler, 1999) polygons.

We studied the generation of a representative class of orthogonal polygons that we call grid orthogonal polygons (abbreviated as grid ogons) [Tomás and Bajuelos, 2003, 2004]. A polygon is called orthogonal (a.k.a., rectlinear) if its edges meet at right angles. A grid n-ogon is a n-vertex polyomino inscribed in a regular square grid having exactly one edge per grid line.

All free n-ogons for n=4,6,8
All free grid n-ogons,
for n=4,6,8.
Orthogonal polygons
Mapping orthogonal polygons to
grid ogons.

The grid n-ogons form a representative class of n-ogons. In fact, each n-vertex orthogonal polygon (abbr., n-ogon) which is not in general position may be mapped to an n-ogon in general position (i.e., without collinear edges) by small perturbations. Each n-ogon in general position is mapped to a unique grid n-ogon through top-to-bottom and left-to-right sweeping. Reciprocally, given a grid n-ogon, we may create an n-ogon that is an instance of its class by randomly spacing the grid lines in such a way that their relative order is kept. Hence, we consider the generation of grid ogons with a predefined number of vertices.

Generating grid n-ogons by Inflate-Cut and Inflate-Paste

Inflate-Cut and Inflate-Paste are two novel techniques for generating grid n-ogons. These techniques are complete: every grid n-ogon results from a unit square by applying Inflate-Paste (resp., Inflate-Cut) r times, where r=(n-4)/2 is its number of reflex vertices [Tomás and Bajuelos, 2003, 2004].

Inflate-Cut works by cutting rectangles and Inflate-Paste by gluing rectangles in a restricted way. Inflate-Cut (and Inflate-Paste) may be applied to a unit square to construct a "random" grid ogon, with pre-defined number of vertices, but there is no guarantee that samples are uniformly distributed.


The Idea of Inflate-Cut...

Start (n=4)

Screenshot 0
1st cut (n=6)

Screenshot 1
2nd cut (n=8)

Screenshot 2

Three larger examples

n = 30

Simulation n = 30
n = 50

Simulation n = 50
n = 100

Simulation n = 100


A Demo of Inflate-Paste... at each iteration, the grid ogon is extended by gluing the rectangle defined by the green (convex) vertex and the center of black cell marked with a dot.

n = 38

Screenshot of an implementation

by Luís Carvalho, DCC student, 2007/08.

Monotone Grid Orthogonal Polygons

An orthogonal polygon is called monotone with respect to the x-axis (y-axis, resp.) if its intersection with every vertical (horizontal) line is either empty or a single line segment. They are also called to column-convex (row-convex, resp.). A generator of monotone grid orthogonal polygons based on the inflate-paste technique is available.

Related publications:

Copyright © 2004-2009, Ana Paula Tomás, DCC-FCUP & LIACC , University of Porto, Portugal.