Offers efficient computational geometry algorithms and data structures, addressing common geometric problems with implementations like Closest Pair using naive and divide-and-conquer approaches.
Surfaced from shared tags and platforms — no rankings paid for.
Komp-Geom is a Kotlin Multiplatform library for computational geometry. It provides immutable-by-default geometric primitives, precision-aware operations, mutable alternatives for performance-sensitive code, and a growing collection of geometry algorithms.
The library currently targets JVM, JavaScript, WebAssembly, and Kotlin/Native platforms including Linux, Windows, macOS, iOS, Android Native, watchOS, and tvOS.
[!IMPORTANT] Komp-Geom is currently in a pre-1.0 release (
0.4.0-rc7). The public API may change before1.0.0.
import io.github.cponfick.kompgeom.algorithms.convexhull.Quickhull2
import io.github.cponfick.kompgeom.euclidean.twod.Vec2
val points = listOf(
Vec2(0.0, 0.0),
Vec2(2.0, 0.0),
Vec2(1.0, 1.0),
Vec2(1.0, 0.25),
)
val hull = Quickhull2(points).execute()
println(hull)
For more examples and the complete API reference, see the documentation. A visualization application is also available in the komp-geom-visualizer project.
Explore Komp-Geom's geometry algorithms and primitives in the komp-geom visualizer.
For the current development version:
The latest release is available
on Maven Central. Replace VERSION below
with the version you want to use.
Add the dependency to the appropriate source set, usually commonMain:
dependencies {
implementation("io.github.cponfick:komp-geom:VERSION")
}
JVM-only projects can depend on the JVM-specific artifact:
dependencies {
implementation("io.github.cponfick:komp-geom-jvm:VERSION")
}
Maven users can use the corresponding artifact in their pom.xml:
<dependency>
<groupId>io.github.cponfick</groupId>
<artifactId>komp-geom</artifactId>
<version>VERSION</version>
</dependency>
For a JVM-only project, use komp-geom-jvm as the artifactId.
Sweep precision limitation: These complexity bounds assume consistent geometric predicates. Near the floating-point tolerance boundary, pairwise segment intersection and computed sweep events can disagree, so the sweeps may miss intersections even for finite inputs. Do not rely on them for guaranteed topology in such cases. A reproducible failing case and plans for robust predicates are tracked in issue #184.
If you are looking for an algorithm that is not listed, feel free to open an issue or contribute an implementation.
| Data structure | Implementation | Operations | Time complexity |
|---|
Floating-point arithmetic introduces rounding errors that can affect geometric calculations. Komp-Geom uses
DoubleEquivalence to make comparisons explicit and configurable.
The default implementation, EpsilonDoubleEquivalence, uses GEOMETRIC_EPSILON = 1e-10. For finite values, two values
are considered equal when:
abs(a - b) <= epsilon * max(1, abs(a), abs(b))
This combines an absolute tolerance near zero with a relative tolerance for larger values:
import io.github.cponfick.kompgeom.core.equivalence.EpsilonDoubleEquivalence
val relaxed = EpsilonDoubleEquivalence(epsilon = 1e-6)
relaxed.eq(0.3000001, 0.3) // true
Most geometry types and operations use DEFAULT_DOUBLE_EQUIVALENCE by default, while operations that accept an
equivalence can be given application-specific precision:
import io.github.cponfick.kompgeom.core.equivalence.EpsilonDoubleEquivalence
import io.github.cponfick.kompgeom.euclidean.twod.AffineTransformationMatrix2
val precision = EpsilonDoubleEquivalence(epsilon = 1e-8)
val first = AffineTransformationMatrix2.createRotation(Math.PI / 4.0)
val second = AffineTransformationMatrix2.createRotation(0.7853981634)
val equivalent = first.eq(second, precision)
Choose an epsilon appropriate for the scale and accuracy requirements of your application. For consistent behavior, create one equivalence instance and pass it to the operations that support custom precision instead of relying on mutable global state.
The standard geometric types are immutable. This makes values easier to share, reason about, and use in functional-style code. Mutable alternatives are available where in-place updates are useful, including:
MutableVec1, MutableVec2, and MutableVec3MutableSeg2 and MutableSeg3Benchmarks show that mutable implementations can substantially reduce allocations and improve throughput for repeated operations. For example, the affine transformation benchmark reports the following improvements for one million transformations:
See the benchmark results for details and context. Benchmark results depend on the platform, runtime, hardware, and workload.
Contributions, bug reports, feature requests, and documentation improvements are welcome. Please read the contributing guide before opening a pull request.
Before submitting a change, run:
./gradlew spotlessApply
./gradlew spotlessCheck
./gradlew allTests
allTests runs the tests available on the current host. Browser-based JavaScript and WebAssembly tests require Chrome;
CI covers additional platforms.
DoubleEquivalence implementations| Algorithm | Implementation | Dimensions | Mutable input | Time complexity | Space complexity |
|---|
| Closest pair | Naive | 2D, 3D | Yes | O(n²) | O(1) |
| Closest pair | Divide and conquer | 2D | Yes | O(n log n) | O(n) |
| Convex hull | Quickhull | 2D | Yes | O(n log n) average, O(n²) worst case | O(n) |
| Segment intersection detection | Shamos–Hoey sweep line | 2D | Yes | O(n log n) | O(n) |
| Segment intersection reporting | Bentley–Ottmann sweep line | 2D | Yes | O((n + k) log n) | O(n + k) |
| Space complexity |
|---|
| Sorted map | MutableRedBlackTreeMap | Insert, delete, lookup, neighbor queries, and ordered iteration | O(log n) per update or lookup; O(n) iteration | O(n) |