Journal for Geometry and Graphics 29 (2025), No. 2, 223--254
Copyright by the authors licensed under CC BY SA 4.0
An Efficient Method for Obtaining the Maximum k-Gon in a Closed Contour with Obstacles
Rubén Molano
University of Extremadura, Cáceres, Spain
rmolano@unex.es
Mar Avila
University of Extremadura, Cáceres, Spain
mmavila@unex.es
Mohammadhossein Homaei
University of Extremadura, Cáceres, Spain
mhomaein@alumnos.unex.es
Pablo G. Rodríguez
University of Extremadura, Cáceres, Spain
pablogr@unex.es
Andrés Caro
University of Extremadura, Cáceres, Spain
andresc@unex.es
Geometric optimization has been frequently studied in a recurrent way, where it has been fundamental to developing more complete algorithms. Regions of interest can be obtained as user-defined polygons as a first step toward many practical applications. This article focuses on lattice polygons defined on a regular partition and presents an efficient method for computing all possible polygons contained within regions of interest bounded by arbitrary obstacles such as points, segments, and holes. The developed algorithm calculates all the simple polygons with the maximum area or perimeter contained within the region of interest with O(n5k) computational time. The user can define the polygon to be calculated (triangle, quadrilateral, pentagon, hexagon, etc.) as well as the desired solution: maximum area or maximum perimeter. The paper presents several practical applications that demonstrate the efficiency and versatility of the algorithm. The pseudocode for the algorithm is presented, as well as the source code (Java and Python) in a GitHub repository for research purposes.
Keywords: k-gon, closed contour, polygon, area, perimeter.
MSC: 97G30; 97N80, 68-04.
[ Fulltext-pdf (41655 KB)]