##### Personal tools
You are here: Home Generating Grid Ogons and Ogons
« October 2021 »
October
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31

# Generating Grid Ogons and Ogons ### Abstract

We developed a C++ library for creating orthogonal polygons and some subclasses (row-convex, column-convex, convex, path and spiral orthogonal polygons), with a given number of vertices.

The algorithms are based on the Inflate-Paste method , which generates grid orthogonal polygons (a.k.a. permutominoes). A grid orthogonal polygon is an orthogonal polygon without collinear edges, defined in a unit square lattice and that has exactly one edge on all the grid lines that intersect their minimum bounding square.

The Inflate-Paste method constructs an n-vertex grid orthogonal polygon iteratively from a unit square in O(n2) time and O(n) space. At each iteration, it applies two transformations (called Inflate and Paste) to glue a new rectangle to the previous grid orthogonal polygon, yielding a new grid orthogonal polygon with one more reflex vertex. We designed tailored versions of the Inflate-Paste algorithm to generate grid orthogonal polygons in the aforementioned subclasses. For the row-convex, column-convex and convex grid orthogonal polygons, the algorithm runs in O(n) time.

Generic orthogonal polygons are obtained from grid orthogonal polygons by sliding their edges, while preserving their relative order (in a plane sweep). The sliding procedure is executed k times, where k is a user-defined parameter, running in O(n*k) time, using O(n) space. The generator may create polygons with collinear edges. For that purpose, it performs a final transformation making use of another parameter that defines the probability of moving an edge to the same line of the previous one (if that is possible). This transformation runs in O(n2) time.

The project uses `CGAL::Arrangement_2` from the "2D Arrangements" CGAL package, to have a DCEL as a possible representation for the generated orthogonal polygon. It is also possible to have as output a doubly linked list of vertices of type `CGAL::Point_2` in counterclockwise order.

### Publications

1. C. L. Ferreira
Algorithms for Chromatic Art Gallery Problems with Vertex α-Guards
MSc Thesis in Computer Science, Faculty of Sciences, University of Porto, 2016
2. A. P. Tomás and A. L. Bajuelos
Quadratic-Time Linear-Space Algorithms for Generating Orthogonal Polygons with a Given Number of Vertices
In Laganá A. et al (Eds), ICCSA 2004. LNCS, vol. 3045, pp. 117-126, Springer. 