Geom2D is a computational geometry library for Go, designed for 2D polygon operations and other fundamental geometric types, and is currently reaching its release candidate phase, nearing production readiness.
As of March 2025, thid package is actively in development.
Geom2D aims to provide a robust, flexible, and efficient implementation of 2D geometric operations, featuring:
- Geometry Types:
- Point: Basic 2D point representation.
- LineSegment: Represents a line segment and supports operations such as intersection and reflection.
- Circle: Support for operations like circumference, area, and intersection checks.
- Rectangle: Axis-aligned bounding box with methods for containment, intersection, and transformation.
- Polygon: Support polygons with holes and nested structures, with methods for orientation, correction, and Boolean operations.
- Polygon Boolean Operations: Union, intersection, and subtraction.
- Geometry to Geometry Relationships: Fast and reliable algorithms for determining geometric relationships.
To install Geom2D, use go get:
go get github.com/mikenye/geom2dFor detailed examples, please see the package documentation, where almost every public function has an example.
For detailed API documentation and usage examples, visit the geom2d documentation at the Go Package Discovery and Documentation site.
This section describes the geometric relationships between different types of geometric objects supported by the library. Relationships can include concepts like disjoint, intersection, containment, and equality. The relationships are determined using efficient algorithms for each pair of types.
This table describes the relationship of the left-side type (column) to the top-side type (row).
Each cell indicates the valid relationship types.
| Left ↓, Right → | Point | Line Segment | Circle | Rectangle | Polygon within PolyTree |
|---|---|---|---|---|---|
| Point | RelationshipDisjointRelationshipEqual |
RelationshipDisjointRelationshipIntersection |
RelationshipDisjointRelationshipIntersectionRelationshipContainedBy |
RelationshipDisjointRelationshipIntersectionRelationshipContainedBy |
RelationshipDisjointRelationshipIntersectionRelationshipContainedBy |
| Line Segment | RelationshipDisjointRelationshipIntersection |
RelationshipDisjointRelationshipIntersectionRelationshipEqual |
RelationshipDisjointRelationshipIntersectionRelationshipContainedBy |
RelationshipDisjointRelationshipIntersectionRelationshipContainedBy |
RelationshipDisjointRelationshipIntersectionRelationshipContainedBy |
| Circle | RelationshipDisjointRelationshipIntersectionRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContainsRelationshipEqual |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContains |
| Rectangle | RelationshipDisjointRelationshipIntersectionRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContainsRelationshipEqual |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContains |
| Polygon within PolyTree | RelationshipDisjointRelationshipIntersectionRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContains |
RelationshipDisjointRelationshipIntersectionRelationshipContainedByRelationshipContainsRelationshipEqual |
RelationshipDisjoint: The two geometric objects do not overlap.RelationshipIntersection: The two geometric objects overlap partially or at boundaries.RelationshipContains: The left-side geometric object fully contains the right-side object.RelationshipContainedBy: The left-side geometric object is fully contained by the right-side object.RelationshipEqual: The two geometric objects are identical.
Geom2D builds upon the work of others and is grateful for the foundations they have laid. Specifically:
-
Computational Geometry: Algorithms and Applications: The implementation of geometric algorithms in Geom2D follows the approach presented in Computational Geometry: Algorithms and Applications (3rd edition) by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. This book serves as the primary reference for methods such as the sweep line algorithm for line segment intersections, polygon operations, and spatial relationships.
-
Martínez et al.: the work of Martínez et al. on Boolean operations for polygons provided valuable insight into polygonal computational geometry. See A simple algorithm for Boolean operations on polygons.
-
Bentley-Ottmann Algorithm: The Bentley-Ottmann algorithm for efficiently reporting line segment intersections served as the foundation for the sweep line approach used in this library. While Geom2D follows the refined method outlined in Computational Geometry: Algorithms and Applications, the Bentley-Ottmann technique remains an influential cornerstone in computational geometry. See Bentley, J. L., & Ottmann, T. A. "Algorithms for reporting and counting geometric intersections." Communications of the ACM, 1979, or the "Bentley–Ottmann algorithm" article on Wikipedia.
-
Tom Wright: The inspiration for starting this library came from Tom Wright’s repository Provably Correct Polygon Algorithms and his accompanying paper. While Geom2D follows its own approach, certain ideas have been influenced by his work.
-
Jack Bresenham: The Bresenham's Line Algorithm and Bresenham's Circle Algorithm implemented in this library are inspired by Jack Bresenham's pioneering work. These algorithms are efficient methods for rasterizing lines and circles in computer graphics. For more details, see Bresenham's original paper "Algorithm for computer control of a digital plotter." IBM Systems Journal, 1965.
-
This project is a collaborative effort, with significant assistance from OpenAI's Assistant for brainstorming, debugging, and refining implementations.
To learn more about the work that inspired this library, visit the linked papers and repositories.
- Support for additional geometric types (e.g., ellipses, splines).
- Enhanced visualisation tools using libraries like Ebitengine.
- Performance optimizations for large datasets.
- Pathfinding within geometric types: Efficient algorithms for finding shortest paths constrained by geometric boundaries.
Contributions are welcome! Please see CONTRIBUTING.md for details.
See the LICENSE file for details.