Computational geometry and spatial indexing on the sphere

Overview

S2 Geometry Library

Build Status

Overview

This is 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.

Requirements for End Users

On Ubuntu, all of these can be installed via apt-get:

sudo apt-get install cmake libgflags-dev libgoogle-glog-dev libgtest-dev libssl-dev

Otherwise, you may need to install some from source.

On macOS, use MacPorts or Homebrew. For MacPorts:

sudo port install cmake gflags google-glog openssl

Do not install gtest from MacPorts; instead download release 1.8.0, unpack, and substitute

cmake -DGTEST_ROOT=/...absolute path to.../googletest-release-1.8.0/googletest ..

in the build instructions below.

Thorough testing has only been done on Ubuntu 14.04.3 and macOS 10.12.

Build and Install

You may either download the source as a ZIP archive, or clone the git repository.

Via ZIP archive

Download ZIP file

cd [parent of directory where you want to put S2]
unzip [path to ZIP file]/s2geometry-master.zip
cd s2geometry-master

Via git clone

cd [parent of directory where you want to put S2]
git clone https://github.com/google/s2geometry.git
cd s2geometry

Building

From the appropriate directory depending on how you got the source:

mkdir build
cd build
# You can omit -DGTEST_ROOT to skip tests; see above for macOS.
cmake -DGTEST_ROOT=/usr/src/gtest ..
make
make test  # If GTEST_ROOT specified above.
sudo make install

Enable gflags and glog with cmake -DWITH_GFLAGS=ON -DWITH_GLOG=ON ....

Disable building of shared libraries with -DBUILD_SHARED_LIBS=OFF.

Python

If you want the Python interface, you will also need:

  • SWIG (for Python support, optional)

which can be installed via

sudo apt-get install swig

or on macOS:

sudo port install swig

Expect to see some warnings if you build with swig 2.0.

Python 3 is required.

Other S2 implementations

  • Go (Approximately 40% complete.)
  • Java (Older version; last updated in 2011.)

Disclaimer

This is not an official Google product.

Comments
  • S2 compatible with python3?

    S2 compatible with python3?

    I followed the instructions as given here - http://s2geometry.io/about/platforms.html but I am getting these errors when I run cmake

    -- The following features have been enabled:

    • GFLAGS, allows changing command line flags.
    • GLOG, provides logging configurability.
    • SHARED_LIBS, builds shared libraries instead of static.

    GTEST_ROOT: /usr/src/googletest File "/usr/lib/python3.6/site.py", line 183 file=sys.stderr) ^ SyntaxError: invalid syntax CMake Error at src/python/CMakeLists.txt:30 (install): install TARGETS given no LIBRARY DESTINATION for module target "_pywraps2".

    CMake Error at src/python/CMakeLists.txt:31 (install): install FILES given no DESTINATION!

    -- Configuring incomplete, errors occurred! See also "/home/winash12/S2source/s2geometry/CMakeFiles/CMakeOutput.log". See also "/home/winash12/S2source/s2geometry/CMakeFiles/CMakeError.log". This is on Ubuntu 18.04 LTS.

    opened by winash12 27
  • Array bounds warning when compiling with gcc11

    Array bounds warning when compiling with gcc11

    We're trying to track down the source of a warning that we are required to silence for the R package s2 (in order to keep the package on CRAN). A new test has been added to the CRAN servers with the development version of gcc (i.e., gcc11). Compiling the s2 package gives new warnings with -Warray-bounds in s2/util/gtl/btree.h, and nether myself nor @edzer have the expertise to know if these errors are (1) a bug in gcc11, (2) real but not important, or (3) an actual out-of-bounds array error. There is an issue thread of our struggles with this here: https://github.com/r-spatial/s2/issues/79

    I've put together a reprex to illustrate the problem...unfortunately it involves building gcc11 from source (which is what CRAN has done). The gist version is here: https://gist.github.com/paleolimbot/51db5e587b5f3e57a637b6a24655fe87

    Note that all of

    • gcc11/devel
    • map[4] = 4; (i.e., insertion)
    • -DNDEBUG and
    • -O2

    ...are necessary to reproduce.

    git clone https://gist.github.com/51db5e587b5f3e57a637b6a24655fe87.git gcc11-gtl-btree
    cd gcc11-gtl-btree
    # this takes several hours
    docker build . --tag r-gcc11
    docker run --rm r-gcc11 g++ --version
    
    g++ (GCC) 11.0.0 20201024 (experimental)
    Copyright (C) 2020 Free Software Foundation, Inc.
    This is free software; see the source for copying conditions.  There is NO
    warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    
    # with latest github s2
    curl -L https://github.com/google/s2geometry/archive/master.zip --output s2.zip
    unzip s2.zip
    docker run --rm -v $(pwd):/test -w /test r-gcc11 g++ -std=c++11 -I s2geometry-master/src -O2 -DNDEBUG -Warray-bounds test.cpp -o test
    
    In file included from s2geometry-master/src/s2/util/gtl/btree_map.h:34,
                     from test.cpp:3:
    s2geometry-master/src/s2/util/gtl/btree.h: In function ‘int main()’:
    s2geometry-master/src/s2/util/gtl/btree.h:604:22: warning: array subscript [33, 287] is outside array bounds of ‘absl::container_internal::Allocate<8, std::allocator<std::pair<int* const, std::pair<int, bool> > > >::M [32]’ [-Warray-bounds]
      604 |     mutable_child(i) = c;
          |     ~~~~~~~~~~~~~~~~~^~~
    In file included from /usr/local/include/c++/11.0.0/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                     from /usr/local/include/c++/11.0.0/bits/allocator.h:46,
                     from /usr/local/include/c++/11.0.0/memory:64,
                     from s2geometry-master/src/s2/util/gtl/btree_map.h:30,
                     from test.cpp:3:
    /usr/local/include/c++/11.0.0/ext/new_allocator.h:121:48: note: referencing an object of size between 48 and 256 allocated by ‘void* operator new(std::size_t)’
      121 |         return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
          |                                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
    In file included from s2geometry-master/src/s2/util/gtl/btree_map.h:34,
                     from test.cpp:3:
    s2geometry-master/src/s2/util/gtl/btree.h:597:58: warning: array subscript [32, 287] is outside array bounds of ‘absl::container_internal::Allocate<8, std::allocator<std::pair<int* const, std::pair<int, bool> > > >::M [32]’ [-Warray-bounds]
      597 |   btree_node *child(int i) const { return GetField<3>()[i]; }
          |                                                          ^
    In file included from /usr/local/include/c++/11.0.0/x86_64-pc-linux-gnu/bits/c++allocator.h:33,
                     from /usr/local/include/c++/11.0.0/bits/allocator.h:46,
                     from /usr/local/include/c++/11.0.0/memory:64,
                     from s2geometry-master/src/s2/util/gtl/btree_map.h:30,
                     from test.cpp:3:
    /usr/local/include/c++/11.0.0/ext/new_allocator.h:121:48: note: referencing an object of size between 48 and 256 allocated by ‘void* operator new(std::size_t)’
      121 |         return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
          |                                  ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
    
    opened by paleolimbot 20
  • Tag a release

    Tag a release

    Hey, having read #40, I'd like to push again for a tagged release. Reason for asking is that package managers, e.g. Homebrew, won't accept a package for S2 unless there is a tagged version. It would be very much appreciated.

    opened by DennisOSRM 20
  • Adding openssl 1.1 compat code

    Adding openssl 1.1 compat code

    I added some code which should make the exactfloat class compatible with OpenSSL 1.1 Could probably be faster by using unaligned memory access on x86 https://github.com/google/s2geometry/issues/5

    For reference see the manual page: https://www.openssl.org/docs/man1.1.0/crypto/BN_bn2lebinpad.html

    opened by graetzer 14
  • Request: Option to not require external dependencies for static linking scenarios

    Request: Option to not require external dependencies for static linking scenarios

    Hi, great to see the new version of S2 out - very cool!

    I know a lot of people use the old version of S2 (us for example) and link it statically into their application. That was fairly easy to do with the old version, but now with the GFlags, GLog dependencies it's a lot more onerous and also affects downstream build system requirements.

    Is there any chance you might consider an option to allow building the core without requiring any dependencies, aside from libssl of course.

    Best

    opened by socmag 13
  • S2Loop and S2Builder for mbr intersection

    S2Loop and S2Builder for mbr intersection

    I am trying to write a function to check if two MBRs intersect. My first thought was to create two S2Polygons and use the intersectsmethod. In order to do that I have to create S2Loops from the points of each MBR with something like this:

        vector<S2Point> points1;
    
        points1.push_back(S2Point(s.xLow, s.yLow,0));
        points1.push_back(S2Point(s.xHigh, s.yLow,0));
        points1.push_back(S2Point(s.xHigh, s.yHigh,0));
        points1.push_back(S2Point(s.xLow, s.yHigh,0));
        S2Polygon a(make_unique<S2Loop>(points1));
    

    I do not use .Normalize() as my points are already normalized. I get the following error ERROR Edge 1 crosses edge 3. I believe that this is caused because S2Loop creates the full loop and connects every point with every other.

    Question 1: Is it possible to connect only the 4 points I give in that order?

    Following the recommendations given at the S2Loop manual, I then tried S2Builder. I had the same error as before when I was using S2Loop. I somehow managed to bypass it using S2Polyline and here comes

    Question 2: How can I use S2Builder to check for intersection?

    I found no documentation regarding S2Builder, even though it is recommended for unsorted collection of edges. As a result, all my efforts are based on reading tests from the source code and trying to adapt the methods to my problem.

    opened by DinosL 11
  • Remove

    Remove "using std::string" from port.h.

    Exposing the "using" directive in the port header will cause it to be leaked into any codebase that uses this library. While it is possible to just fix up the headers and use the directive only in the source files, this change uses std::string everywhere.

    opened by gregcoombe 11
  • compilation error because of deprecated BIGNUM functions in openssl 1.1

    compilation error because of deprecated BIGNUM functions in openssl 1.1

    as of 8a8746c7f4d4c53e8561e78e6ca380e8d4a0b9d3

    compilation is failing on Arch because of openssl 1.1:

    In file included from /home/akh/tmp/s2geometry/src/s2/s2predicates_internal.h:29:0,
                     from /home/akh/tmp/s2geometry/src/s2/s2edge_crossings.cc:28:
    /home/akh/tmp/s2geometry/src/s2/util/math/exactfloat/exactfloat.h:516:10: error: field ‘bn_’ has incomplete type ‘BIGNUM {aka bignum_st}’
       BIGNUM bn_;
              ^~~
    In file included from /usr/include/openssl/bn.h:32:0,
                     from /home/akh/tmp/s2geometry/src/s2/util/math/exactfloat/exactfloat.h:119,
                     from /home/akh/tmp/s2geometry/src/s2/s2predicates_internal.h:29,
                     from /home/akh/tmp/s2geometry/src/s2/s2edge_crossings.cc:28:
    /usr/include/openssl/ossl_typ.h:80:16: note: forward declaration of ‘BIGNUM {aka struct bignum_st}’
     typedef struct bignum_st BIGNUM;
                    ^~~~~~~~~
    In file included from /home/akh/tmp/s2geometry/src/s2/s2predicates_internal.h:29:0,
                     from /home/akh/tmp/s2geometry/src/s2/s2edge_crossings.cc:28:
    /home/akh/tmp/s2geometry/src/s2/util/math/exactfloat/exactfloat.h: In constructor ‘ExactFloat::ExactFloat()’:
    /home/akh/tmp/s2geometry/src/s2/util/math/exactfloat/exactfloat.h:576:3: error: ‘BN_init’ was not declared in this scope
       BN_init(&bn_);
       ^~~~~~~
    /home/akh/tmp/s2geometry/src/s2/util/math/exactfloat/exactfloat.h:576:3: note: suggested alternative: ‘BN_print’
       BN_init(&bn_);
       ^~~~~~~
       BN_print
    make[2]: *** [CMakeFiles/s2.dir/build.make:879: CMakeFiles/s2.dir/src/s2/s2edge_crossings.cc.o] Error 1
    make[1]: *** [CMakeFiles/Makefile2:105: CMakeFiles/s2.dir/all] Error 2
    make: *** [Makefile:130: all] Error 2
    
    

    BN_init() was removed in OpenSSL 1.1.0; use BN_new() instead. source https://www.openssl.org/docs/man1.1.0/crypto/BN_new.html

    Solution for Arch is: cmake -DOPENSSL_INCLUDE_DIR="/usr/include/openssl-1.0" -DOPENSSL_SSL_LIBRARY=/usr/lib/openssl-1.0/libssl.so ..

    It will become an issue for every distribution with recent openssl.

    opened by akhenakh 11
  • Please make a new release 0.10 (and tag it)

    Please make a new release 0.10 (and tag it)

    I would love to package libs2 for Debian (in fact I have a local packaging repo at at https://salsa.debian.org/Mobian-team/puremaps-packaging/s2geometry-deb), but would love to package a nice reference release, instead of a random commit hash. The last formal release is 2 years ago, libs2 already announces itself as 0.10.0 to the world, so can we make a release please?

    Would be appreciated, and thanks for s2geometry!

    opened by spaetz 9
  • Improve portability and reduce warnings

    Improve portability and reduce warnings

    We've been working on integrating S2 into our project for a little while, and we've found a few issues with portability (especially compiling on Windows), and with some extraneous compile warnings (e.g. with gcc-7.2). This PR contains a mish-mash of small changes to address these concerns, hopefully in a way that can benefit everyone.

    opened by dhly-etc 9
  • Cannot find load file error on cmake

    Cannot find load file error on cmake

    Hi, I am trying to cmake s2 using the following command, cmake -DWITH_GFLAGS=ON -WITH_GTEST=ON \ -DGTEST_ROOT=/usr/src/gtest \ -DOPENSSL_INCLUDE_DIR=/usr/include/openssl -Dabsl_DIR=/home/vidhi/Documents/BII/abseil/Source/abseil-cpp/build -DWITH_PYTHON=ON ..

    I get this error on running the command, -- The following features have been enabled:

    • GFLAGS, allows changing command line flags.
    • GLOG, provides logging configurability.
    • SHARED_LIBS, builds shared libraries instead of static.
    • PYTHON, provides python interface to S2

    CMake Error at /home/vidhi/Documents/BII/abseil/Source/abseil-cpp/build/abslConfig.cmake:32 (include): include could not find load file:

    /home/vidhi/Documents/BII/abseil/Source/abseil-cpp/build/abslTargets.cmake
    

    Call Stack (most recent call first): CMakeLists.txt:74 (find_package)

    I have abseil build and installed following the instructions from here https://abseil.io/docs/cpp/quickstart-cmake. But I cannot find this abslTargets.cmake file anywhere. What did I miss?

    opened by elixir-1 8
  • Add vcpkg installation instructions

    Add vcpkg installation instructions

    s2geometry is available as a port in vcpkg, a C++ library manager that simplifies installation for s2geometry and other project dependencies. Documenting the install process here will help users get started by providing a single set of commands to build s2geometry, ready to be included in their projects.

    We also test whether our library ports build in various configurations (dynamic, static) on various platforms (OSX, Linux, Windows: x86, x64) to keep a wide coverage for users.

    I'm a maintainer for vcpkg, and here is what the port script looks like. We try to keep the library maintained as close as possible to the original library. :)

    opened by JonLiu1993 2
  • Can't compile since abseil moved out

    Can't compile since abseil moved out

    Hello,

    My project depends on s2geometry, but now that abseil was made external I can't compile anymore.

    Indeed in my CMakeLists.txt I added add_subdirectory(third-party/abseil) before add_subdirectory(third-party/s2geometry) but s2 complained that it couldn't find abslConfig.cmake so I used set(ABSL_ENABLE_INSTALL ON) to have it, but now I'm stuck on the following error: CMake Error at build/third-party/abseil-cpp/abslConfig.cmake:32 (include): [cmake] include could not find load file: [cmake] [cmake] [...]/build/third-party/abseil-cpp/abslTargets.cmake [cmake] Call Stack (most recent call first): [cmake] third-party/s2geometry/CMakeLists.txt:71 (find_package)

    The targets don't seem to be installed when add_subdirectory(third-party/abseil) finishes, when s2 launches find_package(absl REQUIRED). Which brings me to my question: is there a way to compile abseil before s2 in the same CMake, or am I missing something here?

    Best regards, Paul

    opened by paro- 1
  • Can't compile with the new version of abseil

    Can't compile with the new version of abseil

    Environment information

    System info

    Linux pop-os 5.17.15-76051715-generic #202206141358~1655919116~22.04~1db9e34 SMP PREEMPT Wed Jun 22 19 x86_64 x86_64 x86_64 GNU/Linux

    CPU: inte i7-12700K @ 5.1GHz 20 threads

    GPU: RTX 3070 Ti

    Abseil compilation details

    Abseil version: 20211102.0

    First installed gtest from source at /usr/local/gtest, the generated make file using the following command in abseil directory:

    cmake -S . -B build -DCMAKE_PREFIX_PATH=/usr/local/gtest -DCMAKE_INSTALL_PREFIX=/usr/local/absl -DABSL_ENABLE_INSTALL=ON -DABSL_USE_EXTERNAL_GOOGLETEST=ON -DABSL_FIND_GOOGLETEST=ON -DCMAKE_CXX_STANDARD=17 -DCMAKE_POSITION_INDEPENDENT_CODE=ON -DABSL_BUILD_TESTING=ON

    Then I ran all the tests(after compilation) and it passed, after that I did:

    sudo make install

    which installed abseil in /usr/local/absl

    S2geometry compilation

    I downloaded the 0.10.0 version from releases and generated the make file using:

    cmake -DGTEST_ROOT=/usr/src/gtest -DCMAKE_PREFIX_PATH=/usr/local/absl -DCMAKE_CXX_STANDARD=17 ..

    then after trying to compile I get the following linking error:

    image

    opened by ehsandu15 1
  • Document that googletest version 1.10.0 is required

    Document that googletest version 1.10.0 is required

    With revision 7a40135059545396237a0199c558d749fe3be0b1 I get this build failure:

    /home/mike/devel/github/google/s2geometry/src/s2/s2shape_nesting_query_test.cc:452:25: error: expected constructor, destructor, or type conversion before ‘(’ token
     INSTANTIATE_TEST_SUITE_P(
                             ^
    /home/mike/devel/github/google/s2geometry/src/s2/s2shape_nesting_query_test.cc:470:6: error: expected unqualified-id before ‘)’ token
         }));
          ^
    

    It was introduced by change 0df6f8cf9d3d7671ab8943430ffc4eac5ae20123, which added s2shape_nesting_query_test.cc.

    I can't find any other references to INSTANTIATE_TEST_SUITE_P. Removing it gets me a successful build, but am I removing test coverage?

    I think somebody who understands this macro should advise on how to fix this.

    opened by MikePlayle 4
  • Does S2 support Windows?

    Does S2 support Windows?

    Hi, I noticed there are several closed issues that relate to Windows, and based on their contents it appears S2 supports Windows. Code in the ae470b7 version committed on April 11, 2022 doesn't contain getrusage() or headers that indicate POSIX like unistd.h.

    However, the official website http://s2geometry.io/about/platforms says Windows is not supported at this time and that POSIX getrusage() is needed.

    Could you elaborate on why Windows isn't supported? Or, is the doc out of date? Thanks!

    opened by Leedehai 1
  • OSS-Fuzz issue 38342

    OSS-Fuzz issue 38342

    OSS-Fuzz has found a bug in this project. Please see https://oss-fuzz.com/testcase?key=6287054808416256 for details and reproducers.

    This issue is mirrored from https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=38342 and will auto-close if the status changes there.

    If you have trouble accessing this report, please file an issue at https://github.com/google/oss-fuzz/issues/new.

    opened by oss-fuzz-robot 0
Releases(v0.10.0)
  • v0.10.0(Apr 8, 2022)

    • Add new files
      • s2buffer_operation
      • s2builderutil_get_snapped_winding_delta
      • s2builderutil_lax_polyline_layer
      • s2memory_tracker
      • s2shapeutil_conversion
      • s2winding_operation
      • s2wrapped_shape
      • thread_testing
    • Expose some new functions in pywraps2
    • Remove internal absl; depend on released absl
    • Require SWIG 4
    • Remove internal files that are no longer needed
    • Improved documentation of EncodedS2ShapeIndex
    • Fix accidental dependence on gtest even when not enabled.
    Source code(tar.gz)
    Source code(zip)
  • v0.10.0-2022.02.23.00(Feb 23, 2022)

    • Add new files
      • s2buffer_operation
      • s2builderutil_get_snapped_winding_delta
      • s2builderutil_lax_polyline_layer
      • s2memory_tracker
      • s2shapeutil_conversion
      • s2winding_operation
      • s2wrapped_shape
      • thread_testing
    • Expose some new functions in pywraps2
    • Remove internal absl; depend on released absl
    • Require SWIG 4
    • Remove internal files that are no longer needed
    • Improved documentation of EncodedS2ShapeIndex
    Source code(tar.gz)
    Source code(zip)
  • v0.9.0(Mar 5, 2019)

  • v0.9.0-2019.03.04.00(Mar 4, 2019)

  • v0.9.0-2019.03.01.00(Mar 1, 2019)

    Changes since v0.9.0-2019.02.11.00:

    New functionality:

    • Add S2ShapeIndex Dump function
    • Add Init to Graph nested classes
    • S2Polygon::InitToOperation: Propagate S2Error

    Bug fixes:

    • Fix S2BooleanOperation empty/full handling
    • Minor compilation fixes for nacl
    • Fix LaxPolygonLayer bug
    • Fix rare bug in S2BooleanOperation
    • Fix rare bug in VisitCrossingEdgePairs
    • Fix UB discovered by -D_GLIBCXX_DEBUG
    • S2Cap::Add: Fix bug with empty other cap
    • OwningShape: Fix potential memory leak
    • S2Builder: Clear layer_is_full_polygon_predicates_
    • S2EdgeTesselator: Improve error estimation
    Source code(tar.gz)
    Source code(zip)
  • v0.9.0-2019.02.11.00(Feb 11, 2019)

Owner
Google
Google ❤️ Open Source
Google
Interactive, thoroughly customizable maps in native Android, iOS, macOS, Node.js, and Qt applications, powered by vector tiles and OpenGL

Mapbox GL Native A C++ library that powers customizable vector maps in native applications on multiple platforms by taking stylesheets that conform to

Mapbox 4.2k Sep 21, 2022
C++ implementation of R*-tree, an MVR-tree and a TPR-tree with C API

libspatialindex Author: Marios Hadjieleftheriou Contact: [email protected] Revision: 1.9.3 Date: 10/23/2019 See http://libspatialindex.org for full doc

null 622 Sep 20, 2022
2D and 3D map renderer using OpenGL ES

Tangram ES Tangram ES is a C++ library for rendering 2D and 3D maps from vector data using OpenGL ES. It is a counterpart to Tangram. This repository

Tangram 739 Sep 13, 2022
Terrain Analysis Using Digital Elevation Models (TauDEM) software for hydrologic terrain analysis and channel network extraction.

TauDEM (Terrain Analysis Using Digital Elevation Models) is a suite of Digital Elevation Model (DEM) tools for the extraction and analysis of hydrolog

David Tarboton 188 Aug 31, 2022
Alternative LAZ implementation for C++ and JavaScript

What is this? Alternative LAZ implementation. It supports compilation and usage in JavaScript, usage in database contexts such as pgpointcloud and Ora

Howard Butler 54 Sep 14, 2022
A command line toolkit to generate maps, point clouds, 3D models and DEMs from drone, balloon or kite images. 📷

An open source command line toolkit for processing aerial drone imagery. ODM turns simple 2D images into: Classified Point Clouds 3D Textured Models G

OpenDroneMap 3.8k Sep 15, 2022
A C++17 image representation, processing and I/O library.

Selene Selene is a C++17 image representation, processing, and I/O library, focusing on ease of use and a clean, modern, type-safe API. Overview: Brie

Michael Hofmann 276 Sep 11, 2022
A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)

A fast algorithm for finding polygon pole of inaccessibility, the most distant internal point from the polygon outline (not to be confused with centroid), implemented as a JavaScript library. Useful for optimal placement of a text label on a polygon.

Mapbox 1.2k Sep 20, 2022
A lean, efficient, accurate geohash encoder and decoder library implemented in C

Geohash encoder/decoder in C A lean, efficient, accurate geohash encoder and decoder library implemented in C. It does not depend on the C standard li

Christopher Wellons 19 Aug 28, 2022
A library of distance and occlusion generation routines

Distance/Occlusion Library + Tool From left to right: original, signed distance with zero at 0.5, red/green SDF, delta vectors to closest boundary poi

Andrew Willmott 98 Jan 3, 2022
Experimental 'RTree' Spatial Indexing

rtree The goal of rtree is to experiment with a few different types of spatial indexes at a pretty low level. Installation You can install the develop

Dewey Dunnington 6 May 20, 2022
Wykobi is an efficient, robust and simple to use multi-platform 2D/3D computational geometry library.

Description Wykobi is an efficient, robust and simple to use multi-platform 2D/3D computational geometry library. Wykobi provides a concise, predictab

Arash Partow 129 Sep 13, 2022
✔️The smallest header-only GUI library(4 KLOC) for all platforms

Welcome to GUI-lite The smallest header-only GUI library (4 KLOC) for all platforms. 中文 Lightweight ✂️ Small: 4,000+ lines of C++ code, zero dependenc

null 6.4k Sep 21, 2022
GlueGD is a mod loader for Geometry Dash that does not require a modification to any existing Geometry Dash files or an external injector or launcher.

GlueGD is a mod loader for Geometry Dash that does not require a modification to any existing Geometry Dash files or an external injector or la

Aly Cerruti 9 Apr 10, 2022
graphics and computational physics framework

atto Graphics and computational physics research framework: aligned memory allocation, string manipulation, file IO, etc. 2-, 3- and 4-dimensional vec

Carlos Correia 0 Jul 24, 2022
OpenFOAM is a free, open source computational fluid dynamics (CFD) software package

acousticStreamingFoam About OpenFOAM OpenFOAM is a free, open source computational fluid dynamics (CFD) software package released by the OpenFOAM Foun

Bruno 1 Nov 2, 2021
RediSearch is a Redis module that provides querying, secondary indexing, and full-text search for Redis.

A query and indexing engine for Redis, providing secondary indexing, full-text search, and aggregations.

null 3.9k Sep 20, 2022
Slow5tools is a toolkit for converting (FAST5 <-> SLOW5), compressing, viewing, indexing and manipulating data in SLOW5 format.

slow5tools Slow5tools is a simple toolkit for converting (FAST5 <-> SLOW5), compressing, viewing, indexing and manipulating data in SLOW5 format. Abou

Hasindu Gamaarachchi 51 Sep 9, 2022
network packet indexing and querying

_______ _____.___. ________ _____ _____ \ \\__ | |/ _____/ / \ / _ \ / | \/ | / \ ___ / \ / \ / /_\

64k & stackless-goto 18 Dec 15, 2021
Hexagonal hierarchical geospatial indexing system

H3: A Hexagonal Hierarchical Geospatial Indexing System H3 is a geospatial indexing system using a hexagonal grid that can be (approximately) subdivid

Uber Open Source 3.6k Sep 22, 2022