Algorithm finds shortest enclosing polygon for digital triangles
Computing the minimal perimeter polygon for digital objects in the triangular tiling
Computational Geometry
Summary
This paper tackles the problem of finding the smallest boundary shape that exactly covers certain collections of triangular tiles on a flat surface. The authors develop a step-by-step method that carefully traces the edges of these shapes and uses visibility rules to build the shortest enclosing polygon. Their approach is guaranteed to produce the minimal perimeter polygon and works even if the shapes have complex boundary paths. They also introduce a way to follow the edges of these objects computationally.
What this means in practice
- •For computer graphics developers: Generate minimal enclosing polygons for complex triangular mesh sections to optimize rendering or collision detection.
- •For robot path planners: Construct shortest boundary polygons around obstacle sets modeled as triangular tilings for efficient navigation and coverage.
Authors
Petra Wiederhold
Abstract
This work presents an algorithm, together with its correctness proof, to determine the minimum perimeter polygon (MPP) for digital objects given as regular complexes in the triangular plane tiling. Such objects are edge-adjacency-connected sets of triangle tiles that have no end tiles, and the point set union of all their tiles forms a simple polygon. Nevertheless, the boundary paths of the objects are not assumed to be simple. Then the MPP is a weakly simple polygon that coincides with the relative convex hull (i.e., geodesic hull) of a set $A$ with respect to a simple polygon $B$, where $A\subset B$, but $A$ is not necessarily a polygon, in fact it is generally not connected. Our MPP algorithm relies on constructing and iteratively constraining cones of visibility through forthcoming boundary tiles, it uses the structure of the canonical boundary path, the MPP frontier is the shortest polygonal curve following this path. We also propose a boundary tracing algorithm to obtain such paths from the objects.