Abstract
There are many structures, both classical and modern, involving convex polygonal geometries whose deeper understanding would be facilitated through interactive visualizations. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating geometric figures. One of its features is the capability to extend its functionality through programs called Ipelets. In this media submission, we showcase a collection of new Ipelets that construct a variety of geometric objects based on polygonal geometries. These include Macbeath regions, metric balls in the forward and reverse Funk distance, metric balls in the Hilbert metric, polar bodies, the minimum enclosing ball of a point set, and minimum spanning trees in both the Funk and Hilbert metrics. We also include a number of utilities on convex polygons, including union, intersection, subtraction, and Minkowski sum (previously implemented as a CGAL Ipelet). All of our Ipelets are programmed in Lua and are freely available.
Introduction
In computational geometry, researchers frequently encounter non-Euclidean metrics and complex convex structures, such as Funk or Hilbert metrics. While mathematically elegant, these structures are notoriously difficult to visualize accurately by hand or with standard vector drawing tools. The Ipe drawing editor is a staple in the geometry community due to its LaTeX-friendly output, but its core functionality is limited to basic shapes.
This paper introduces a suite of "Ipelets"—plugins for Ipe—designed to automate the construction of advanced geometric objects. Previously, illustrating a Macbeath region or a Hilbert ball required manual calculation or bespoke scripting. This toolkit provides a standardized, interactive environment to handle these sophisticated constructions directly within the drawing interface.
Technical Implementation
The Ipelets are written in Lua and integrate directly into the Ipe editor. Key technical implementations include:
- Metric Ball Construction: For Funk and Hilbert metrics, the tools use a "spoke" method. This involves calculating intersections between rays originating from a center point and the vertices of the boundary polygon.
- Duality Transformations: The Polar Body tool implements the mathematical dual of a convex polygon, mapping vertices in the primal space to edges in the dual space.
- Graph Algorithms: Classical algorithms like Kruskal’s and Prim’s have been adapted to work with non-standard distance functions, enabling the generation of Minimum Spanning Trees (MSTs) in Funk and Hilbert spaces.
- Boolean & Minkowski Operations: Robust utilities for polygon union, intersection, and subtraction are included, along with the Minkowski sum, which is essential for motion planning and collision detection research.
Key Insights
A central theme of this work is that interactive visualization serves as a catalyst for research. By providing tools to "play" with geometries, researchers can gain deeper intuitive understanding, potentially leading to new theoretical insights.
A notable feature is the support for the Funk metric, which is asymmetric—the distance from point $p$ to $q$ is not necessarily the same as from $q$ to $p$. The Ipelets allow users to visualize both "forward" and "reverse" Funk balls, making this counter-intuitive property visible. Furthermore, the tools demonstrate that while a Hilbert ball might appear complex, it remains a polygon with $O(m)$ sides (where $m$ is the number of sides of the container polygon), ensuring computational efficiency within the editor.
Results and Applications
The primary outcome is a functional, open-source library that automates several non-trivial geometric tasks:
- Macbeath Regions: These are automatically generated by intersecting a polygon with its reflection around a point.
- Non-Euclidean MSTs: This is the first known tool for interactively generating MSTs specifically for Funk and Hilbert metrics.
- Minimum Enclosing Ball: A tool that finds the smallest circle containing a set of points, handling cases defined by either two or three boundary points.
All tools are freely available via a public GitLab repository, encouraging community extension and modification.
Limitations and Future Scope
Currently, the Ipelets focus on 2D polygonal geometry. Many of these concepts, such as Macbeath regions, have significant implications in higher dimensions ($R^d$), which could be a focus for future development. Additionally, as the metrics and structures are strictly defined for convex bodies, extending these visualizations to non-convex containers would require entirely different mathematical frameworks. Future iterations might also include more dynamic "draggability," allowing geometric structures to update in real-time as users manipulate points within the polygon.
Summary updated