Generating Grid Ogons and Ogons
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
in counterclockwise order.
- C. L. Ferreira
Algorithms for Chromatic Art Gallery Problems with Vertex α-Guards
MSc Thesis in Computer Science, Faculty of Sciences, University of Porto, 2016
- 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.
- Webpage project: http://genogons.dcc.fc.up.pt.