DOCSEARCHbyAlgolia
Submit Docs

S2 Geometry

repository·master·Indexed 25 days ago

https://github.com/google/s2geometry

A library for computational geometry and spatial indexing on the sphere, designed for geographic and spherical data applications. It provides tools for manipulating geometric shapes, including a Python interface with both legacy SWIG and modern pybind11 bindings. The library includes comprehensive geometry validation models such as S2Valid, S2LegacyValid, OGCValid, STLibValid, and OGCSimple to ensure topological correctness for polygons, points, and polylines.

Tokens
3.2K
Snippets
10
Records
17
Agent score
82%

What's inside s2geometry

  1. Understand S2 Geometry Validation Semantic Models

    master

    S2 Geometry uses different semantic models to define what constitutes 'valid' geometry. Depending on your use case, you may need to validate against one of the following levels of strictness:

    • S2Valid: The most lax model. It performs basic checks (e.g., proper interior orientation, no overlaps) and explicitly supports degeneracies. This is the minimum requirement for using S2BooleanOperation.
    • S2LegacyValid: Designed to support S2Polygon validation semantics. It combines S2Valid with Single2DShape and other specific predicates.
    • OGCValid: Validates geometry according to the Open Geospatial Consortium (OGC) specification.
    • STLibValid: Adds additional constraints to OGCValid to ensure geometry is 'dissolved' (no overlapping/touching components that should be one).
    • OGCSimple: A strict OGC model that also checks for polyline self-intersection.

  2. Validate geometry in S2ShapeIndex

    master
    The S2ShapeIndex provides functionality to validate the geometry contained within an index instance using configurable correctness models. This allows you to verify that arbitrary geometry (points, lines, and polygons) stored in an S2ShapeIndex meets the specific constraints required to be treated as a particular geometric object, such as an S2Polygon or an STGeography.

  3. Install S2 Geometry via Bazel

    master

    To build and test S2 Geometry using Bazel, ensure you have Bazel 8 or newer installed. The build uses C++20 and relies on abseil-cpp and googletest from the Bazel central repository.

    From within the s2geometry/src directory, use the following commands:

    • To build and test: bazel test "//:*"
    • To build the library without testing: bazel build //:s2
    bazel test "//:*"
# or
bazel build //:s2

  4. Build S2 Geometry Python interface

    master

    To use the Python interface, you must build S2 with -DWITH_PYTHON=ON.

    Dependencies

    • Python 3.10 is required.
    • SWIG 4.0
    • python3-dev

    Install dependencies (Ubuntu):

    sudo apt-get install swig python3-dev

    Install dependencies (macOS):

    sudo port install swig

    Creating Python Wheels

    1. Create and activate a virtual environment, then install build:
    python3 -m venv venv
source venv/bin/activate
pip install build
    1. Build the wheel:
    python -m build

    The resulting wheel will be located in the dist directory.

    python -m build

  6. Detect Disconnected Interiors in Polygons

    master

    To ensure a polygon's interior is topologically connected (preventing 'split interiors'), the library identifies 'pinch points' where chains touch. A pinch point is detected when an incoming edge and the next edge (ordered clockwise around the vertex) belong to different chains.

    By building a graph where nodes are these tangent/pinch points and edges connect points along the same chain, a disconnected interior is identified if the graph contains a cycle. This can be implemented using a Disjoint Set (Union-Find) data structure.

    def CheckInteriorConnected(tangent_list):
  tangent_list = sort(tangent_list by chain) # exact ordering within chain is irrelevant
  ds = DisjointSet()

  # Create singleton sets for each point
  for value in tangent_list:
    ds.Make(value.vertex)

  # Add edges, if we find two vertices connected, we have a loop
  for ii < len(tangent_list)-1:
     curr = tangent_list[ii]
     next = tangent_list[ii+1]
     if (curr.chain == next.chain):
        curr_root = ds.Find(curr.vertex)
        next_root = ds.Find(next.vertex)

        if (curr_root == next_root):
           return Error("Disconnected interior found")
       ds.Union(curr_root, next_root)

  return true

  7. Install S2 Geometry via CMake

    master

    To build S2 Geometry using CMake, ensure you meet the following requirements:

    Prerequisites

    • CMake >= 3.22
    • C++ Compiler with C++17 support (e.g., g++ >= 7.5 or clang >= 14.0.0)
    • Abseil LTS version 20260526 (This exact version must be used)
    • OpenSSL (required for building tests)
    • googletest >= 1.10 (optional, for tests and examples)

    Platform-specific dependency installation

    Ubuntu:

    sudo apt-get install cmake libssl-dev

    macOS (via MacPorts):

    sudo port install cmake abseil gtest openssl

    Build Steps

    1. Install Abseil first. It must be configured with -DCMAKE_POSITION_INDEPENDENT_CODE=ON. It is recommended to pass -DCMAKE_CXX_STANDARD=17 to both Abseil and S2 to ensure C++ version compatibility.
    2. Configure and Build S2:

    From the S2 source directory:

    mkdir build
cd build
cmake -DBUILD_TESTS=yes -DCMAKE_PREFIX_PATH=/path/to/absl/install -DCMAKE_CXX_STANDARD=17 ..
make -j $(nproc)
make test ARGS="-j$(nproc)"
sudo make install

    Note: On macOS, replace $(nproc) with $(sysctl -n hw.logicalcpu).

    mkdir build
cd build
cmake -DBUILD_TESTS=yes -DCMAKE_PREFIX_PATH=/path/to/absl/install -DCMAKE_CXX_STANDARD=17 ..
make -j $(nproc)
make test ARGS="-j$(nproc)"
sudo make install

  8. Build legacy SWIG bindings with CMake

    master

    The CMake build system currently only supports the legacy SWIG-based s2geometry package. To build it, ensure you have the dependencies installed and use the -DWITH_PYTHON=ON flag.

    Dependencies: sudo apt-get install cmake libssl-dev swig python3-dev

    Build Steps:

    mkdir build && cd build
cmake -DBUILD_TESTS=yes -DWITH_PYTHON=ON -DCMAKE_PREFIX_PATH=/path/to/absl/install -DCMAKE_CXX_STANDARD=17 ..
make -j $(nproc)
make test ARGS="-j$(nproc)"
sudo make install
    mkdir build && cd build
cmake -DBUILD_TESTS=yes -DWITH_PYTHON=ON -DCMAKE_PREFIX_PATH=/path/to/absl/install -DCMAKE_CXX_STANDARD=17 ..
make -j $(nproc)
make test ARGS="-j$(nproc)"
sudo make install

  9. Install S2 Geometry to system

    master

    After building the project in the build directory, install the headers and libraries using make install. Files are installed to the location specified by CMAKE_INSTALL_PREFIX.

    If you need to modify the installation paths, you can use make edit_cache to edit the CMake cache or pass the following variables to cmake via -D:

    • CMAKE_INSTALL_INCLUDEDIR: Directory for header files (default: include)
    • CMAKE_INSTALL_BINDIR: Directory for executables (default: bin)
    • CMAKE_INSTALL_LIBDIR: Directory for library files (default: lib)
    cd build
sudo make install

  10. Choose between SWIG and pybind11 Python bindings

    master

    The S2 Geometry Python SDK is currently transitioning between two binding implementations. Choose the one that fits your needs:

    • Legacy SWIG bindings (s2geometry): The current production bindings. They are built using CMake. Use import s2geometry to access them.
    • New pybind11 bindings (s2geometry_pybind): The modern bindings currently under development. They are built using Bazel. Use import s2geometry_pybind to access them.

    Once the pybind11 bindings are stable, they will be renamed to s2geometry and become the primary API.

  11. Use the pybind11 Python bindings

    master

    The s2geometry_pybind package provides a Pythonic interface to the S2 Geometry library. While it follows the C++ API closely, it uses snake_case for methods and provides properties for simple accessors.

    Example usage:

    import s2geometry_pybind as s2

p1 = s2.S2Point(1.0, 0.0, 0.0)
p2 = s2.S2Point(0.0, 1.0, 0.0)
sum_point = p1 + p2
print(sum_point)
    import s2geometry_pybind as s2

p1 = s2.S2Point(1.0, 0.0, 0.0)
p2 = s2.S2Point(0.0, 1.0, 0.0)
sum_point = p1 + p2
print(sum_point)

  12. Validate geometry for S2BooleanOperation

    master

    The requirements for geometry to be valid for use with S2BooleanOperation are more relaxed than S2Polygon or OGC Geography.

    Required constraints:

    • Polygon interiors must be disjoint from all other geometry.
    • Duplicate polygon edges are not allowed (even among separate polygons).

    Allowed configurations:

    • S2ShapeIndex may contain any number of points, polylines, and polygons.
    • Point polylines composed of a degenerate edge AA.
    • Point loops composed of a single degenerate edge AA.
    • Sibling edge pairs such as {AB, BA} (can represent shells, holes, or separate polygons touching).
    • Points and polyline edges are treated as a multiset and may have duplicates.
    • Polylines may have duplicate edges and self-intersect.
    S2BooleanOperation