Offers efficient computational geometry algorithms and data structures, addressing common geometric problems with implementations like Closest Pair using naive and divide-and-conquer approaches.
Komp-Geom is a comprehensive Kotlin Multiplatform (KMP) library for computational geometry, designed to provide a robust and efficient toolkit for solving geometric problems. It offers a set of algorithms and data structures with an idiomatic Kotlin API that should feel natural to Kotlin developers.
The library is built with cross-platform compatibility in mind, supporting JVM, JS, WebAssembly, and Native (iOS, Linux, Windows, macOS). This ensures that your geometric code works consistently everywhere.
Key features include:
[!IMPORTANT] This project is in its early stages. Until the first stable release 1.0.0, the API may change frequently. After the 1.0.0 release, versioning will follow semantic versioning principles.
Usage examples are provided inside the documentation.
A demo application is available at komp-geom-visualization. It allows you to visualize the algorithms and data structures implemented in this library. The goal is to provide visual representations for most, if not all, algorithms and data structures.
To add the library to your multiplatform project, include the following dependency:
Gradle:
implementation("io.github.cponfick:komp-geom:{VERSION}")
Maven:
<dependency>
<groupId>io.github.cponfick</groupId>
<artifactId>komp-geom</artifactId>
<version>{VERSION}</version>
</dependency>
You can also use the library directly in a JVM-only project by adding the following dependency:
Gradle:
implementation("io.github.cponfick:komp-geom-jvm:{VERSION}")
Maven:
<dependency>
<groupId>io.github.cponfick</groupId>
<artifactId>komp-geom-jvm</artifactId>
<version>{VERSION}</version>
</dependency>
This section provides an overview of the core components of the library, which are designed to serve as building blocks for implementing geometric algorithms.
The library currently provides the following geometric elements:
Floating-point arithmetic inherently introduces small rounding errors that can cause issues in geometric computations. The library addresses this challenge through a configurable epsilon-based comparison system, ensuring robust and reliable geometric operations across all platforms.
By default, the library uses an epsilon based comparison with a default GEOMETRIC_EPSILON of 1e-10 as the tolerance
threshold. Two double values are considered equal if their absolute difference is within this epsilon:
// Using default precision
val a = 0.30000000000000004
val b = 0.3
DEFAULT_DOUBLE_EQUIVALENCE.eq(a, b) // true
You can create custom EpsilonDoubleEquivalence instances to adjust precision for specific use cases:
// More lenient precision for approximate calculations
val relaxed = EpsilonDoubleEquivalence(epsilon = 1e-6)
relaxed.eq(0.3000001, 0.3) // true
// Stricter precision for high-accuracy requirements
val strict = DoubleEquivalence(epsilon = 1e-12)
strict.eq(0.30000000001, 0.3) // false
Further, it is possible to provide a custom implementation of the Equivalence interface if you need
specialized comparison logic.
The DoubleEquivalence class provides a complete set of comparison methods:
val precision = DoubleEquivalence()
precision.eq(a, b) // Equal to
precision.eqZero(a) // Equal to zero
precision.lt(a, b) // Less than
precision.lte(a, b) // Less than or equal to
precision.gt(a, b) // Greater than
precision.gte(a, b) // Greater than or equal to
Many geometric data structures and algorithms accept an optional DoubleEquivalence parameter to control
precision-aware operations. The parameter defaults to DEFAULT_DOUBLE_EQUIVALENCE, making it optional in most cases:
// Comparing transformation matrices with default precision
val matrix1 = AffineTransformationMatrix3.createRotationX(Math.PI / 4)
val matrix2 = AffineTransformationMatrix3.createRotationX(0.7853981634)
matrix1.eq(matrix2) // Uses default precision
// Custom precision for specific requirements
matrix1.eq(matrix2, EpsilonDoubleEquivalence(epsilon = 1e-9)) // true
For applications requiring consistent custom precision across all operations, you can modify the global defaults:
// Adjust global epsilon (affects all new DoubleEquivalence instances)
GEOMETRIC_EPSILON = 1e-8
// Replace the global default equivalence
DEFAULT_DOUBLE_EQUIVALENCE = EpsilonDoubleEquivalence(epsilon = 1e-8)
Note: Modifying global defaults should be done during application initialization, as it affects all subsequent geometric operations throughout the library.
The library follows Kotlin's philosophy of immutability by default. Immutable data structures offer several advantages:
However, for performance-critical applications involving large-scale operations, immutability can introduce overhead due to object allocations. To address this, the library also provides mutable implementations for certain data types that modify objects in-place. Currently, mutable implementations are available for:
Further, following algorithms support mutable implementations:
Based on benchmark results, mutable implementations offer significant performance improvements when performing large numbers of operations:
The following is a list of implemented algorithms. If you are missing an algorithm, feel free to open an issue or contribute a pull request.
Contributions are welcome! Please check the contributing guidelines for more information on how to get started. Feel free to open issues for bugs, feature requests, or general questions.
| Algorithm | Implementation | Supported Dimensions | Mutable Input Supported | Runtime Complexity | Space Complexity |
|---|
| Closest Pair | Naive | 2D, 3D | yes | O(n^2) | O(1) |
| Closest Pair | Divide and Conquer | 2D | yes | O(n log n) | O(n) |
| Convex Hull | QuickHull | 2D | yes | O(n log n) | O(n) |
Surfaced from shared tags and platforms — no rankings paid for.