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.
Inflate-Cut
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
Inflate-Paste
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.
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.