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 grid n-ogons,
for n=4,6,8.

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

Select a cell in the interior of the current grid ogon.
Inflate this cell... i.e., insert one free H-edge and one free V-edge.
Cut a rectangle, to obtain a grid ogon with one more reflex vertex (placed in the center of the inflated cell).

Start (n=4)

1st cut (n=6)

2nd cut (n=8)

Three larger examples

n = 30

n = 50

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.

Related publications:

Ana Paula Tomás and António Leslie Bajuelos: Generating Random Orthogonal Polygons. In R.Conejo, M.Urretavizcaya, J.-L. Pérez-de-la-Cruz (Eds), Current Topics in Artificial Intelligence: 10th Conf. of the Spanish Association for Artificial Intelligence, CAEPIA 2003, and 5th Conference on Technology Transfer, TTIA 2003. Revised Selected Papers, Lecture Notes in Computer Science 3040, Springer, 364-373, 2004.
Ana Paula Tomás and António Leslie Bajuelos: Quadratic-Time Linear-Space Algorithms for Generating Orthogonal Polygons with a Given Number of Vertices. In A. Laganà et al. (Eds), Computational Science and Its Applications (CGA'04/ICCSA 2004), Lecture Notes in Computer Science 3045, Springer, 117-126, 2004. (also as extended abstract in J. M. Diaz-Báñez et al. (Eds), Proc. 20th European Workshop on Computational Geometry (EuroCG'04) 189-192, 2004.)
Available prototype: An implementation of Random-Inflate-Cut is available upon request. Please contact A.P.Tomás.