S2 Geometry Library (Dart)
Overview
This is a Dart port of Google's S2 Geometry Library, a package for manipulating geometric shapes. Unlike many geometry libraries, S2 is primarily designed to work with spherical geometry, i.e., shapes drawn on a sphere rather than on a planar 2D map. This makes it especially suitable for working with geographic data.
If you want to learn more about the library, start by reading the overview and quick start document, then read the introduction to the basic types.
S2 documentation can be found on s2geometry.io.
Installation
Add this to your pubspec.yaml:
dependencies:
s2geometry: ^0.2.1
Usage
import 'package:s2geometry/s2geometry.dart';
// Create a viewport rectangle (e.g., for a map view)
final viewport = S2LatLngRect.fromPointPair(
S2LatLng.fromDegrees(40.0, -112.0), // SW corner
S2LatLng.fromDegrees(41.0, -111.0), // NE corner
);
// Get covering cells for efficient spatial queries
final coverer = S2RegionCoverer(maxCells: 8);
final covering = coverer.getCovering(viewport);
// Use cell IDs for database range queries
for (int i = 0; i < covering.size; i++) {
final cellId = covering.cellId(i);
final minId = cellId.rangeMin.id;
final maxId = cellId.rangeMax.id;
// SELECT * FROM positions WHERE s2_cell_id BETWEEN minId AND maxId
}
Build and Test
This package uses Melos for build management.
# Install dependencies
dart pub get
# Run tests
melos run test
# Run tests with coverage
melos run coverage
# Analyze code
melos run analyze
# Format code
melos run format
S2 Implementations
The S2 library has implementations in several languages. In addition to this Dart port, Google provides:
- Java (The source for this port)
- C++ (The reference implementation and the most full featured)
- Go (Approximately 40% complete)
- Python
About This Port
AI-Generated Port
This Dart library is an AI-assisted port of Google's s2-geometry-library-java. The port was created using AI code generation tools to translate Java source code to idiomatic Dart while maintaining functional equivalence.
Why This Port Was Created
This port was created to enable local, disk-backed spatial indexing in Dart/Flutter applications without requiring external databases like MySQL or PostgreSQL for spatial queries. The S2 library's cell-based indexing system allows efficient viewport-based POI (Points of Interest) queries using simple range scans on any key-value store.
How It Was Created
The port was created by:
- Selective porting - Only the core classes needed for spatial indexing and region covering were ported, focusing on the most essential functionality
- 1:1 Java-to-Dart translation - Each Java class was directly translated to Dart, preserving the original logic and algorithms
- Test porting - The corresponding Java unit tests were ported to Dart to validate correctness
How much of the original Java library was ported to Dart.
| Category | Ported | Total (Java) | Percentage |
|---|---|---|---|
| Core Source Files | 102 | ~124 | 82% |
| Source Lines | ~23,500 | ~69,800 | 34% |
| Test Files | 83 | ~100 | 83% |
| Test Lines | ~17,000 | ~46,200 | 37% |
| Passing Tests | 1,413 | — | — |
| Skipped Tests | 5 | — | — |
Ported Classes
| Dart File | Java Equivalent | Description |
|---|---|---|
r1_interval.dart |
R1Interval.java |
1D interval on the real line |
r2_vector.dart |
R2Vector.java |
2D vector |
r2_rect.dart |
R2Rect.java |
2D axis-aligned rectangle |
r2_edge.dart |
R2Edge.java |
Mutable edge in 2D space |
r2_edge_clipper.dart |
R2EdgeClipper.java |
Cohen-Sutherland edge clipping to rectangles |
s1_angle.dart |
S1Angle.java |
1D angle |
s1_interval.dart |
S1Interval.java |
1D interval on a circle |
s1_chord_angle.dart |
S1ChordAngle.java |
Angle represented as chord length squared |
s1_distance.dart |
S1Distance.java |
Abstract distance on the sphere surface |
s2.dart |
S2.java |
Core S2 utilities |
s2_point.dart |
S2Point.java |
Point on the unit sphere |
s2_latlng.dart |
S2LatLng.java |
Latitude/longitude coordinates |
s2_cell_id.dart |
S2CellId.java |
64-bit cell identifier |
s2_cell.dart |
S2Cell.java |
Cell on the sphere |
s2_cell_index.dart |
S2CellIndex.java |
Spatial index for cells with labels |
s2_cell_union.dart |
S2CellUnion.java |
Union of S2 cells |
s2_region.dart |
S2Region.java |
Abstract region interface |
s2_cap.dart |
S2Cap.java |
Spherical cap region |
s2_latlng_rect.dart |
S2LatLngRect.java |
Lat/lng bounding rectangle |
s2_region_coverer.dart |
S2RegionCoverer.java |
Converts regions to cell coverings |
s2_region_intersection.dart |
S2RegionIntersection.java |
Intersection of multiple regions |
s2_region_sharder.dart |
S2RegionSharder.java |
Shards data by region intersection |
s2_region_union.dart |
S2RegionUnion.java |
Union of multiple regions |
s2_projections.dart |
S2Projections.java |
Cell projection utilities |
s2_predicates.dart |
S2Predicates.java |
Robust geometric predicates |
s2_robust_cross_prod.dart |
S2RobustCrossProd.java |
Robust cross product calculation |
s2_edge_util.dart |
S2EdgeUtil.java |
Edge utilities (crossing, distance, interpolation) |
s2_edge.dart |
S2Edge.java |
Edge between two points |
s2_edge_tessellator.dart |
S2EdgeTessellator.java |
Converts between geodesic and projected edges |
s2_edge_vector_shape.dart |
S2EdgeVectorShape.java |
Shape containing arbitrary edges |
s2_shape.dart |
S2Shape.java |
Abstract shape interface |
s2_lax_polyline_shape.dart |
S2LaxPolylineShape.java |
Lightweight polyline shape |
s2_point_index.dart |
S2PointIndex.java |
Spatial index for points |
s2_point_region.dart |
S2PointRegion.java |
Region containing a single point |
s2_point_compression.dart |
S2PointCompression.java |
Compressed encoding for S2 points |
s2_polyline.dart |
S2Polyline.java |
Polyline (sequence of vertices) |
s2_polyline_simplifier.dart |
S2PolylineSimplifier.java |
Helper for simplifying polylines |
s2_chain_interpolation_query.dart |
S2ChainInterpolationQuery.java |
Interpolates along shape chains |
s2_closest_point_query.dart |
S2ClosestPointQuery.java |
Finds closest points in an index |
s2_contains_vertex_query.dart |
S2ContainsVertexQuery.java |
Determines if polygon contains a vertex |
s2_fractal_builder.dart |
S2FractalBuilder.java |
Generates fractal shapes for testing |
s2_area_centroid.dart |
S2AreaCentroid.java |
Area and centroid calculation |
s2_earth.dart |
S2Earth.java |
Earth-related constants and conversions |
s2_error.dart |
S2Error.java |
Error codes for S2 operations |
s2_exception.dart |
S2Exception.java |
Exception wrapper for S2Error |
s2_padded_cell.dart |
S2PaddedCell.java |
Cell with padding for recursive traversal |
s2_text_format.dart |
S2TextFormat.java |
Text parsing/formatting for S2 objects |
real.dart |
Real.java |
Exact arithmetic for predicates |
big_point.dart |
BigPoint.java |
Extended precision 3D point |
matrix.dart |
Matrix.java |
3x3 matrix operations |
platform.dart |
Platform.java |
Platform-specific utilities |
projection.dart |
Projection.java |
Map projections (Mercator, PlateCarree) |
parametrized_s2_point.dart |
ParametrizedS2Point.java |
S2Point with time parameter for ordering |
distance_collector.dart |
DistanceCollector.java |
Interface for tracking "best" distance |
encoded_ints.dart |
EncodedInts.java |
Varint encoding, ZigZag encoding, bit interleaving |
little_endian_input.dart |
LittleEndianInput.java |
Reading little-endian primitives |
little_endian_output.dart |
LittleEndianOutput.java |
Writing little-endian primitives |
sorter.dart |
primitives/Sorter.java |
Sorting utilities |
pullable.dart |
primitives/Pullable.java |
Pullable interface for sorting |
mutable_s2_point.dart |
MutableS2Point.java |
Mutable S2Point and MutableS2PointList |
uv_edge_clipper.dart |
UVEdgeClipper.java |
Edge clipping to faces in UV space |
primitive_arrays.dart |
PrimitiveArrays.java |
Bytes, Longs, and Cursor classes |
s2_coder.dart |
S2Coder.java |
Encoding/decoding interface |
s2_cell_id_vector.dart |
S2CellIdVector.java |
Abstract cell ID list |
buffer_utils.dart |
BufferUtils.java |
ByteBuffer utilities |
input_streams.dart |
InputStreams.java |
Input stream utilities |
in_memory_output_stream.dart |
InMemoryOutputStream.java |
In-memory output stream |
uint_vector_coder.dart |
UintVectorCoder.java |
Encoder/decoder for integer arrays |
s2_cell_id_vector_coder.dart |
S2CellIdVectorCoder.java |
Encoder/decoder for S2CellId lists |
vector_coder.dart |
VectorCoder.java |
Generic list encoder/decoder |
s2_point_vector_coder.dart |
S2PointVectorCoder.java |
Encoder/decoder for S2Point lists |
s2_shape_measures.dart |
S2ShapeMeasures.java |
Length, area, centroid for shapes |
s2_contains_point_query.dart |
S2ContainsPointQuery.java |
Point-in-shape containment queries |
s2_crossing_edge_query.dart |
S2CrossingEdgeQuery.java |
Edge crossing queries in shape index |
s2_loop.dart |
S2Loop.java |
Simple spherical polygon (single loop) |
s2_polygon.dart |
S2Polygon.java |
Multi-loop spherical polygon |
s2_cell_iterator_join.dart |
S2CellIteratorJoin.java |
Inner join over two shape indices (exact) |
s2_closest_edge_query.dart |
S2ClosestEdgeQuery.java + S2BestEdgesQueryBase.java |
Closest edge query (point/edge/cell targets) |
min_chord_angle_collector.dart |
(internal to S2ClosestEdgeQuery) | MinDistance collector for S1ChordAngle |
s2_shape_index_buffered_region.dart |
S2ShapeIndexBufferedRegion.java |
Geometry expansion by radius for coverings |
s2_furthest_edge_query.dart |
S2FurthestEdgeQuery.java |
Furthest edge query (point/edge/cell targets) |
max_chord_angle_collector.dart |
(internal to S2FurthestEdgeQuery) | MaxDistance collector for S1ChordAngle |
s2_hausdorff_distance_query.dart |
S2HausdorffDistanceQuery.java |
Discrete Hausdorff distance between geometries |
s2_builder.dart |
S2Builder.java |
Geometry assembly with snapping and graph construction |
s2_builder_graph.dart |
S2BuilderGraph.java |
Edge graph passed to layers for assembly |
s2_builder_layer.dart |
S2BuilderLayer.java |
Interface for output geometry assembly |
s2_builder_snap_functions.dart |
S2BuilderSnapFunctions.java |
Identity, S2CellId, IntLatLng snap functions |
id_set_lexicon.dart |
IdSetLexicon.java |
Compact integer set storage with deduplication |
s2_incident_edge_tracker.dart |
S2IncidentEdgeTracker.java |
Tracks vertices with >2 incident edges |
s2_indexing_helper.dart |
S2IndexingHelper[Impl].java |
Spatial indexing helper with index/query terms |
s2_edge_iterator.dart |
S2EdgeIterator.java |
Iterator over all edges in a shape index |
s2_shape_index_measures.dart |
S2ShapeIndexMeasures.java |
Dimension, length, area, centroid for shape index |
s2_best_distance_target.dart |
S2BestDistanceTarget.java |
Abstract target for distance queries |
s2_cell_range_iterator.dart |
S2CellRangeIterator.java |
Range-based iterator with seekTo/seekBeyond |
s2_lax_polygon_shape.dart |
S2LaxPolygonShape.java |
Lightweight polygon shape with degeneracy support |
s2_convex_hull_query.dart |
S2ConvexHullQuery.java |
Convex hull computation on the sphere |
s2_shape_index_region.dart |
S2ShapeIndexRegion.java |
S2Region adapter for S2ShapeIndex |
s2_iterator.dart |
S2Iterator.java |
Iterator interface for S2ShapeIndex |
s2_shape_index.dart |
S2ShapeIndex.java |
Core spatial index for shapes |
Test Porting Progress
Comparison of Dart test lines vs Java test lines for key test files:
| Test File | Dart Lines | Java Lines | Ported |
|---|---|---|---|
s2_cell_union_test.dart |
503 | 604 | 83% |
s2_cap_test.dart |
267 | 368 | 73% |
s2_region_coverer_test.dart |
357 | 270 | 100%+ |
s2_polyline_test.dart |
311 | 634 | 49% |
s2_edge_util_test.dart |
663 | 1,720 | 39% |
s2_cell_test.dart |
260 | 771 | 34% |
s2_shape_index_test.dart |
177 | 549 | 32% |
s2_loop_test.dart |
443 | 1,304 | 34% |
s2_cell_id_test.dart |
181 | 617 | 29% |
s2_latlng_rect_test.dart |
261 | 1,111 | 23% |
s2_closest_edge_query_test.dart |
139 | 788 | 18% |
s2_builder_test.dart |
271 | 1,875 | 14% |
s2_predicates_test.dart |
159 | 1,494 | 11% |
s2_polygon_test.dart |
223 | 3,175 | 7% |
s2_boolean_operation_test.dart |
137 | 2,523 | 5% |
Code Coverage
All 1,413 tests pass (5 skipped). Code coverage for ported source files:
| File | Lines | Covered | Coverage |
|---|---|---|---|
| src/big_point.dart | 41 | 41 | 100.0% |
| src/little_endian_input.dart | 60 | 60 | 100.0% |
| src/little_endian_output.dart | 50 | 50 | 100.0% |
| src/matrix.dart | 95 | 95 | 100.0% |
| src/r1_interval.dart | 99 | 99 | 100.0% |
| src/r2_edge.dart | 17 | 17 | 100.0% |
| src/r2_rect.dart | 91 | 91 | 100.0% |
| src/r2_vector.dart | 63 | 63 | 100.0% |
| src/s1_angle.dart | 70 | 70 | 100.0% |
| src/s1_chord_angle.dart | 103 | 103 | 100.0% |
| src/s1_interval.dart | 198 | 198 | 100.0% |
| src/s2_area_centroid.dart | 11 | 11 | 100.0% |
| src/s2_cap.dart | 117 | 117 | 100.0% |
| src/s2_contains_point_query.dart | 78 | 78 | 100.0% |
| src/s2_contains_vertex_query.dart | 50 | 50 | 100.0% |
| src/s2_edge_iterator.dart | 22 | 22 | 100.0% |
| src/s2_edge_tessellator.dart | 45 | 45 | 100.0% |
| src/s2_error.dart | 27 | 27 | 100.0% |
| src/s2_exception.dart | 5 | 5 | 100.0% |
| src/s2_hausdorff_distance_query.dart | 49 | 49 | 100.0% |
| src/s2_latlng.dart | 83 | 83 | 100.0% |
| src/s2_latlng_rect.dart | 94 | 94 | 100.0% |
| src/s2_point_region.dart | 29 | 29 | 100.0% |
| src/s2_polyline.dart | 91 | 91 | 100.0% |
| src/s2_polyline_layer.dart | 35 | 35 | 100.0% |
| src/s2_region_coverer.dart | 165 | 165 | 100.0% |
| src/s2_region_intersection.dart | 26 | 26 | 100.0% |
| src/s2_region_union.dart | 31 | 31 | 100.0% |
| src/s2_shape.dart | 34 | 34 | 100.0% |
| src/s2_text_format.dart | 187 | 186 | 99.5% |
| src/encoded_ints.dart | 86 | 85 | 98.8% |
| src/s2_cell_union.dart | 299 | 295 | 98.7% |
| src/real.dart | 147 | 145 | 98.6% |
| src/s2_cell_id_vector_coder.dart | 121 | 119 | 98.3% |
| src/s2_convex_hull_query.dart | 58 | 57 | 98.3% |
| src/platform.dart | 108 | 106 | 98.1% |
| src/r2_edge_clipper.dart | 88 | 86 | 97.7% |
| src/s2_earth.dart | 43 | 42 | 97.7% |
| src/projection.dart | 42 | 41 | 97.6% |
| src/s2_predicates.dart | 119 | 116 | 97.5% |
| src/s2_region_sharder.dart | 36 | 35 | 97.2% |
| src/s2_cell.dart | 207 | 201 | 97.1% |
| src/s2_lax_polygon_shape.dart | 68 | 66 | 97.1% |
| src/s2_cell_index.dart | 189 | 182 | 96.3% |
| src/s2_chain_interpolation_query.dart | 80 | 77 | 96.3% |
| src/s2_shape_index_measures.dart | 26 | 25 | 96.2% |
| src/s2_projections.dart | 185 | 177 | 95.7% |
| src/mutable_s2_point.dart | 182 | 174 | 95.6% |
| src/s2_incident_edge_tracker.dart | 45 | 43 | 95.6% |
| src/s2_lax_polygon_layer.dart | 20 | 19 | 95.0% |
| src/s2.dart | 91 | 86 | 94.5% |
| src/s2_point.dart | 107 | 101 | 94.4% |
| src/s2_polyline_simplifier.dart | 70 | 66 | 94.3% |
| src/s2_cell_id.dart | 363 | 342 | 94.2% |
| src/s2_padded_cell.dart | 133 | 125 | 94.0% |
| src/s2_lax_polyline_shape.dart | 42 | 39 | 92.9% |
| src/s2_point_compression.dart | 138 | 128 | 92.8% |
| src/s2_edge.dart | 39 | 36 | 92.3% |
| src/s2_polygon_layer.dart | 25 | 23 | 92.0% |
| src/id_set_lexicon.dart | 37 | 34 | 91.9% |
| src/s2_crossing_edges_query.dart | 77 | 70 | 90.9% |
| src/uint_vector_coder.dart | 53 | 48 | 90.6% |
| src/uv_edge_clipper.dart | 45 | 40 | 88.9% |
| src/s2_lax_polyline_layer.dart | 17 | 15 | 88.2% |
| src/primitive_arrays.dart | 69 | 60 | 87.0% |
| src/s2_iterator.dart | 59 | 51 | 86.4% |
| src/s2_fractal_builder.dart | 65 | 56 | 86.2% |
| src/s2_shape_index.dart | 329 | 282 | 85.7% |
| src/s2_point_index.dart | 94 | 80 | 85.1% |
| src/s2_cell_iterator_join.dart | 31 | 26 | 83.9% |
| src/s2_robust_cross_prod.dart | 62 | 52 | 83.9% |
| src/s2_shape_measures.dart | 163 | 136 | 83.4% |
| src/s2_polygon.dart | 136 | 113 | 83.1% |
| src/s2_edge_vector_shape.dart | 41 | 33 | 80.5% |
| src/s2_shape_index_region.dart | 80 | 64 | 80.0% |
| src/s2_indexing_helper.dart | 99 | 79 | 79.8% |
| src/s2_loop.dart | 219 | 172 | 78.5% |
| src/s2_closest_point_query.dart | 210 | 160 | 76.2% |
| src/s2_shape_index_buffered_region.dart | 45 | 34 | 75.6% |
| src/s2_point_vector_layer.dart | 16 | 12 | 75.0% |
| src/s2_cell_range_iterator.dart | 59 | 44 | 74.6% |
| src/sorter.dart | 61 | 45 | 73.8% |
| src/s2_builder_graph.dart | 86 | 63 | 73.3% |
| src/s2_builder.dart | 147 | 105 | 71.4% |
| src/s2_edge_util.dart | 359 | 255 | 71.0% |
| src/s2_coder.dart | 41 | 29 | 70.7% |
| src/max_chord_angle_collector.dart | 30 | 19 | 63.3% |
| src/s2_point_vector_coder.dart | 487 | 301 | 61.8% |
| src/pullable.dart | 63 | 33 | 52.4% |
| src/s2_shape_util.dart | 287 | 140 | 48.8% |
| src/s2_boolean_operation.dart | 76 | 37 | 48.7% |
| src/min_chord_angle_collector.dart | 33 | 16 | 48.5% |
| src/in_memory_output_stream.dart | 15 | 7 | 46.7% |
| src/s2_closest_edge_query.dart | 297 | 120 | 40.4% |
| src/s2_furthest_edge_query.dart | 277 | 108 | 39.0% |
| src/s2_builder_snap_functions.dart | 75 | 29 | 38.7% |
| src/vector_coder.dart | 250 | 60 | 24.0% |
| src/s2_builder_util.dart | 48 | 9 | 18.8% |
| src/parametrized_s2_point.dart | 12 | 1 | 8.3% |
| src/buffer_utils.dart | 19 | 0 | 0.0% |
| src/distance_collector.dart | 2 | 0 | 0.0% |
| src/input_streams.dart | 7 | 0 | 0.0% |
| src/s1_distance.dart | 4 | 0 | 0.0% |
| src/s2_best_distance_target.dart | 4 | 0 | 0.0% |
| src/s2_buffer_operation.dart | 61 | 0 | 0.0% |
| src/s2_cell_id_vector.dart | 4 | 0 | 0.0% |
| src/s2_closed_set_normalizer.dart | 22 | 0 | 0.0% |
| src/s2_crossing_edge_query.dart | 126 | 0 | 0.0% |
| src/s2_density_tree.dart | 40 | 0 | 0.0% |
| src/s2_index_cell_data.dart | 31 | 0 | 0.0% |
| src/s2_polygon_degeneracy_finder.dart | 12 | 0 | 0.0% |
| src/s2_reclipped_shape.dart | 31 | 0 | 0.0% |
| src/s2_region.dart | 2 | 0 | 0.0% |
| src/s2_robust_cell_clipper.dart | 11 | 0 | 0.0% |
| src/s2_shape_index_coder.dart | 4 | 0 | 0.0% |
| src/s2_shape_tracker.dart | 8 | 0 | 0.0% |
| src/s2_tagged_shape_coder.dart | 4 | 0 | 0.0% |
| src/s2_validation_queries.dart | 22 | 0 | 0.0% |
| src/s2_winding_operation.dart | 23 | 0 | 0.0% |
| Overall | 10,310 | 8,140 | 79.0% |
Disclaimer
This is not an official Google product. This is an independent port of the open-source S2 Geometry Library.
Original package owner
Thank you to Jan Boon @kaetemi who was the original owner of this package. He originally ported the C++ library 7 Years ago. This code is not a continuation of that work but rather a port of the Java library to Dart.
Libraries
- s2geometry
- The S2 Geometry library provides classes for representing and manipulating geometric data on the sphere.