C++ implementation of R*-tree, an MVR-tree and a TPR-tree with C API

Overview
Comments
  • Segmentation Fault

    Segmentation Fault

    HI,

    Im not expert with linux and c libraries, so probaly my description is incomplete or not very handful. Anyway Im experiencing a problem with libspatialindex.so.3.0.0. Basically I have a plone (python) instance using a rtree library (https://github.com/Toblerity/Rtree). Now and then the instance dies with no clues and message. I've checked the dmesg report from linux and here is what I see:

    [1476438.713131] traps: python[317] general protection ip:7fb04f5a2ff9 sp:7fb04a3440b0 error:0 in libspatialindex.so.3.0.0[7fb04f506000+b8000] [1476763.870627] python[379]: segfault at 0 ip 00007f855e9ccaea sp 00007f85409640f8 error 4 in libc-2.19.so[7f855e944000+1bb000] [1478334.385962] traps: python[1211] general protection ip:7ff88dbf5ff9 sp:7ff889198390 error:0 in libspatialindex.so.3.0.0[7ff88db59000+b8000] [1526321.346560] traps: python[17381] general protection ip:7f33d0f48ff9 sp:7f33cc4eb390 error:0 in libspatialindex.so.3.0.0[7f33d0eac000+b8000] [1527794.507131] traps: python[20645] general protection ip:7f8ccb8c6ff9 sp:7f8cc5766390 error:0 in libspatialindex.so.3.0.0[7f8ccb82a000+b8000] [1528432.553798] python[20984]: segfault at 22 ip 00007f8f4de55ff2 sp 00007f8f404f6390 error 4 in libspatialindex.so.3.0.0[7f8f4ddb9000+b8000] [1528892.762885] traps: python[21271] general protection ip:7f97170eeff2 sp:7f9711e90390 error:0 in libspatialindex.so.3.0.0[7f9717052000+b8000] [1529146.029769] python[21388]: segfault at 0 ip 00007f29b5d25aea sp 00007f298bff9a88 error 4 in libc-2.19.so[7f29b5c9d000+1bb000] [1529364.634798] python[21435]: segfault at 0 ip 00007fa394931aea sp 00007fa3780cc148 error 4 in libc-2.19.so[7fa3948a9000+1bb000] [1529636.648433] python[21533]: segfault at 0 ip 00007f7c14cbaaea sp 00007f7bf37f6af8 error 4 in libc-2.19.so[7f7c14c32000+1bb000]

    Im working on a linux instance (a VPS):

    Linux 3.13.0-46-generic #79-Ubuntu SMP Tue Mar 10 20:06:50 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

    Any suggestion is very appreciated. Thank you in advance.

    opened by marfago 31
  • Inaccessible index property IndexIdentifier

    Inaccessible index property IndexIdentifier

    I was implementing a custom storage manager the other day and had a few issues getting the IndexIdentifier through the C API. I could always be missing a call to find it somewhere, but my reading of things makes it appear to be hidden.

    Near as I can tell, the IndexIdentifier is set on the PropertySet instance here:

    https://github.com/libspatialindex/libspatialindex/blob/53fe4df16d3499f85e2aa6e7805f3cc97714ce66/src/rtree/RTree.cc#L394

    That PropertySet is the member on the un-namespaced Index class from the C API here:

    https://github.com/libspatialindex/libspatialindex/blob/53fe4df16d3499f85e2aa6e7805f3cc97714ce66/include/spatialindex/capi/Index.h#L70

    But the Index_GetProperties call ends up returning the PropertySet from the underlying instance that the unnamespaced Index wraps:

    https://github.com/libspatialindex/libspatialindex/blob/53fe4df16d3499f85e2aa6e7805f3cc97714ce66/src/capi/sidx_api.cc#L1170

    The two solutions i saw were to either patch each of the indexes to set the IndexIdentifier in the PropertySet that they return, or to return a PropertySet that is some sort of merge between the two Index instances. I'm not super familiar with the library internals so I didn't really know which approach would be preferred. For the time being I just peek into the Index class directly so its not a pressing issue.

    opened by davisp 9
  • Include directory unchanged in Point.h

    Include directory unchanged in Point.h

    Point.h has the following line:

    include <spatialindex/tools/Tools.h>

    As you seemingly switched to "libspatialindex" for your include directory, that doesn't work anymore.

    opened by volter 9
  • Windows thread support

    Windows thread support

    Hello, can you add thread support for the windows? Now its only possible with the POSIX threads https://www.sourceware.org/pthreads-win32/. I want to use the libspatialindex as database and those semaphores can help me to keep the consistency of data stored when there will be many queries. I am not an expert on this so correct me if i am wrong about semaphores that with them i can use that library as a database,because they provide consistency of the data? You know,there will be many requests coming in and i think that these locks will prevent the data from being corrupted. I just heard about this at school, we didn´t go into much details :)

    opened by ghost 8
  • Expose Segment Based intersection

    Expose Segment Based intersection

    This request is in regards to improving performance of segment intersection queries.

    In the case where the objects stored in the spatialindex have bounds with dimensions that are an order of magnitude smaller than the segment we are intersecting with, the number of results is often MUCH greater than would be if the intersection were performed with a LineSegment-to-Region intersection (rather than the current Region-to-Region intersection).

    I have implemented this LineSegment-to-Region intersection in a fork (https://github.com/chrisnatali/libspatialindex). This modification improved the performance for our Network Planning application by 10x where the stored objects were much smaller than the segments we were intersecting by.

    If you think this modification is valuable to your code-base, I'll issue a Pull Request. If not, alternative solutions are welcome. Thanks.

    opened by chrisnatali 8
  • Patch for android ndk build

    Patch for android ndk build

    This is the easyest way to get spatialindez 1.7.1 to crosscompile using android ndk (tested with r6b)

    --- a/configure
    +++ b/configure
    @@ -9846,8 +9846,17 @@ linux* | k*bsd*-gnu | kopensolaris*-gnu)
       version_type=linux
       need_lib_prefix=no
       need_version=no
    -  library_names_spec='${libname}${release}${shared_ext}$versuffix ${libname}${release}${shared_ext}$major $libname${shared_ext}'
    -  soname_spec='${libname}${release}${shared_ext}$major'
    +  case $host_os in
    +  # This must be Linux Android ELF.
    +  linux-android*)
    +    library_names_spec='$libname${shared_ext}'
    +    soname_spec='${libname}${shared_ext}'
    +    ;;
    +  *)  
    +    library_names_spec='${libname}${release}${shared_ext}$versuffix ${libname}${release}${shared_ext}$major $libname${shared_ext}'
    +    soname_spec='${libname}${release}${shared_ext}$major'
    +    ;;
    +  esac
       finish_cmds='PATH="\$PATH:/sbin" ldconfig -n $libdir'
       shlibpath_var=LD_LIBRARY_PATH
       shlibpath_overrides_runpath=no
    @@ -13971,8 +13980,17 @@ linux* | k*bsd*-gnu | kopensolaris*-gnu)
       version_type=linux
       need_lib_prefix=no
       need_version=no
    -  library_names_spec='${libname}${release}${shared_ext}$versuffix ${libname}${release}${shared_ext}$major $libname${shared_ext}'
    -  soname_spec='${libname}${release}${shared_ext}$major'
    +  case $host_os in
    +  # This must be Linux Android ELF.
    +  linux-android*)
    +    library_names_spec='$libname${shared_ext}'
    +    soname_spec='${libname}${shared_ext}'
    +    ;;
    +  *)  
    +    library_names_spec='${libname}${release}${shared_ext}$versuffix ${libname}${release}${shared_ext}$major $libname${shared_ext}'
    +    soname_spec='${libname}${release}${shared_ext}$major'
    +    ;;
    +  esac
       finish_cmds='PATH="\$PATH:/sbin" ldconfig -n $libdir'
       shlibpath_var=LD_LIBRARY_PATH
       shlibpath_overrides_runpath=no
    @@ -15699,7 +15717,7 @@ if test `eval echo '${'$as_ac_Header'}'` = yes; then
       cat >>confdefs.h <<_ACEOF
     #define `echo "HAVE_$ac_header" | $as_tr_cpp` 1
     _ACEOF
    - LIBS="$LIBS -lpthread"
    +# LIBS="$LIBS -lpthread"
     fi
    
     done
    
    
    opened by mbernasocchi 8
  • Migration problems v1.9.0 --> v1.9.3

    Migration problems v1.9.0 --> v1.9.3

    We've been using libSpatialIndex with MapWinGIS (Open Source as well) for years now. We're currently in the process of migrating MapWinGIS from building with VS2017 (toolset v140) to VS2019 (toolset v142) and upgrading GDAL2 and PROJ.4 to GDAL3+ and PROJ.7.

    We also want to upgrade our current version of libSpatialIndex from v1.9.0 to the latest version (v1.9.3). But when we do we get strange link errors, like

    LNK2005	"public: char const * __thiscall std::_Locinfo::_Getdays(void)const " ([email protected][email protected]@@QBEPBDXZ) already defined in SpatialIndex-mw.lib(Statistics2.obj)
    

    We're not sure what this means. Are there breaking changes in the latest version we need to address?

    We compile libSpatialIndex ourselves using stdcpp14 and stdc11 and we make a few changes to the code:

    • Build as a static lib
    • Remove the SIDX_DLL keyword from include files
    • Change the project name to "spatialindex-mw"
    • Change the index file extensions from "dat" and "idx" to "mwd" and "mwx"

    The last step is for historical reasons because before we used libSpatialIndex we used a custom spatial indexer. The calling code is at https://github.com/MapWindow/MapWinGIS/tree/develop/src/Utilities/SpatialIndex

    When we stick with v1.9.0 we don't have any problems.

    Please advice.

    opened by pmeems 7
  • Task: update website

    Task: update website

    This is an easy task for anyone with GitHub admin access.

    The current website is http://libspatialindex.github.com/ which redirects to https://libspatialindex.org

    This task is to update the website to https://libspatialindex.org using the GitHub website interface.

    opened by mwtoews 7
  • Compilation Error

    Compilation Error

    I am currently trying to compile to TARGET=x86_64-apple-darwin14 (installation script here) but am running into the following error:

    __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEEC2Ev in libtools.a(Tools.o)
      "__ZNSt3__17num_putIcNS_19ostreambuf_iteratorIcNS_11char_traitsIcEEEEE2idE", referenced from:
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(Point.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(Region.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(LineSegment.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(MovingPoint.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(MovingRegion.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(TimePoint.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(TimeRegion.o)
          ...
      "__ZNSt3__18ios_base33__set_badbit_and_consider_rethrowEv", referenced from:
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(Point.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5flushEv in liblibrary.a(Point.o)
          __ZNSt3__124__put_character_sequenceIcNS_11char_traitsIcEEEERNS_13basic_ostreamIT_T0_EES7_PKS4_m in liblibrary.a(Point.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(Region.o)
          __ZNSt3__124__put_character_sequenceIcNS_11char_traitsIcEEEERNS_13basic_ostreamIT_T0_EES7_PKS4_m in liblibrary.a(Region.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5flushEv in liblibrary.a(Region.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(LineSegment.o)
          ...
      "__ZNSt3__18ios_base4initEPv", referenced from:
          __ZN12SpatialIndex20InvalidPageExceptionC2Ex in liblibrary.a(SpatialIndexImpl.o)
          __Z16CheckFilesExistsRN5Tools11PropertySetE in libstoragemanager.a(DiskStorageManager.o)
          __ZN12SpatialIndex14StorageManager18DiskStorageManagerC2ERN5Tools11PropertySetE in libstoragemanager.a(DiskStorageManager.o)
          __ZNK12SpatialIndex7MVRTree7MVRTree13printRootInfoEv in libmvrtree.a(MVRTree.o)
          __ZN5Tools25IndexOutOfBoundsExceptionC2Em in libtools.a(Tools.o)
          __ZN5Tools12BufferedFileC2Ej in libtools.a(Tools.o)
      "__ZNSt3__18ios_base5clearEj", referenced from:
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(Point.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5flushEv in liblibrary.a(Point.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE6sentryD2Ev in liblibrary.a(Point.o)
          __ZNSt3__124__put_character_sequenceIcNS_11char_traitsIcEEEERNS_13basic_ostreamIT_T0_EES7_PKS4_m in liblibrary.a(Point.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEElsEd in liblibrary.a(Region.o)
          __ZNSt3__124__put_character_sequenceIcNS_11char_traitsIcEEEERNS_13basic_ostreamIT_T0_EES7_PKS4_m in liblibrary.a(Region.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5flushEv in liblibrary.a(Region.o)
          ...
      "__ZNSt3__18ios_base7failureC1EPKcRKNS_10error_codeE", referenced from:
          __ZN5Tools18BufferedFileReader4openERKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEE in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileReader6rewindEv in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileReader4seekEx in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter4openERKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEENS_8FileModeE in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter6rewindEv in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter4seekEx in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter5writeEh in libtools.a(Tools.o)
          ...
      "__ZNSt3__18ios_base7failureD1Ev", referenced from:
          __ZN5Tools18BufferedFileReader4openERKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEE in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileReader6rewindEv in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileReader4seekEx in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter4openERKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEENS_8FileModeE in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter6rewindEv in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter4seekEx in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter5writeEh in libtools.a(Tools.o)
          ...
      "__ZNSt3__18ios_baseD2Ev", referenced from:
          __ZN12SpatialIndex20InvalidPageExceptionC2Ex in liblibrary.a(SpatialIndexImpl.o)
          __ZNSt3__119basic_ostringstreamIcNS_11char_traitsIcEENS_9allocatorIcEEED1Ev in liblibrary.a(SpatialIndexImpl.o)
          __ZTv0_n24_NSt3__119basic_ostringstreamIcNS_11char_traitsIcEENS_9allocatorIcEEED1Ev in liblibrary.a(SpatialIndexImpl.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEED1Ev in liblibrary.a(SpatialIndexImpl.o)
          __ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEED0Ev in liblibrary.a(SpatialIndexImpl.o)
          __ZTv0_n24_NSt3__113basic_ostreamIcNS_11char_traitsIcEEED1Ev in liblibrary.a(SpatialIndexImpl.o)
          __ZTv0_n24_NSt3__113basic_ostreamIcNS_11char_traitsIcEEED0Ev in liblibrary.a(SpatialIndexImpl.o)
          ...
      "__ZNSt3__1plIcNS_11char_traitsIcEENS_9allocatorIcEEEENS_12basic_stringIT_T0_T1_EEPKS6_RKS9_", referenced from:
          __ZN12SpatialIndex20InvalidPageException4whatEv in liblibrary.a(SpatialIndexImpl.o)
          __ZN5Tools25IndexOutOfBoundsException4whatEv in libtools.a(Tools.o)
          __ZN5Tools24IllegalArgumentException4whatEv in libtools.a(Tools.o)
          __ZN5Tools21IllegalStateException4whatEv in libtools.a(Tools.o)
          __ZN5Tools20EndOfStreamException4whatEv in libtools.a(Tools.o)
          __ZN5Tools23ResourceLockedException4whatEv in libtools.a(Tools.o)
          __ZN5Tools21NotSupportedException4whatEv in libtools.a(Tools.o)
          ...
      "__ZNSt8bad_castC1Ev", referenced from:
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE7seekoffExNS_8ios_base7seekdirEj in libstoragemanager.a(DiskStorageManager.o)
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE4syncEv in libstoragemanager.a(DiskStorageManager.o)
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE9underflowEv in libstoragemanager.a(DiskStorageManager.o)
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE8overflowEi in libstoragemanager.a(DiskStorageManager.o)
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE7seekoffExNS_8ios_base7seekdirEj in libtools.a(Tools.o)
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE4syncEv in libtools.a(Tools.o)
          __ZNSt3__113basic_filebufIcNS_11char_traitsIcEEE9underflowEv in libtools.a(Tools.o)
          ...
      "__ZTINSt3__18ios_base7failureE", referenced from:
          __ZN5Tools18BufferedFileReader4openERKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEE in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileReader6rewindEv in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileReader4seekEx in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter4openERKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEENS_8FileModeE in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter6rewindEv in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter4seekEx in libtools.a(Tools.o)
          __ZN5Tools18BufferedFileWriter5writeEh in libtools.a(Tools.o)
          ...
      "__ZTINSt3__18ios_baseE", referenced from:
          __ZTINSt3__19basic_iosIcNS_11char_traitsIcEEEE in liblibrary.a(SpatialIndexImpl.o)
          __ZTINSt3__19basic_iosIcNS_11char_traitsIcEEEE in libstoragemanager.a(DiskStorageManager.o)
          __ZTINSt3__19basic_iosIcNS_11char_traitsIcEEEE in libmvrtree.a(MVRTree.o)
          __ZTINSt3__19basic_iosIcNS_11char_traitsIcEEEE in libtools.a(Tools.o)
    ld: symbol(s) not found for architecture x86_64
    clang-6.0: error: linker command failed with exit code 1 (use -v to see invocation)
    make[1]: *** [Makefile:496: libspatialindex.la] Error 1
    make[1]: Leaving directory '/workspace/srcdir/spatialindex-src-1.8.5'
    make: *** [Makefile:523: all-recursive] Error 1
    ERROR: LoadError: Build for SpatialIndex on x86_64-apple-darwin14 did not complete successfully
    

    (full travis log). Any hints?

    opened by yeesian 7
  • Impossible to use libspatialindex using MSVS2013 in combination with boost

    Impossible to use libspatialindex using MSVS2013 in combination with boost

    I am using libspatialindex in one of my projects. I am currently switching to MSVS2013. As of now, I used MSVS2008 on the Windows side. As it appears, it is impossible to use libspatialindex in combination with Boost (which is used in the same project) starting with MSVS2010.

    Reason: Starting with MSVS2010, Microsoft defines its own stdint.h header file. Boost starts pulling this header file as soon as it is available.

    See: include\boost\config\compiler\visualc.hpp:

    if _MSC_VER >= 1600

    define BOOST_HAS_STDINT_H

    endif

    Libspatialindex has its own defines in Tools.h. These are created independently of the Visual Studio version. There is just a simple check for the MS OS.

    As the defines created by Libspatialindex even differ from the MS version of stdint.h, compile errors are inevitable:

    \libspatialindex\include\spatialindex\tools/Tools.h(31): error C2371: 'int8_t' : redefinition; different basic types \VC\include\stdint.h(8) : see declaration of 'int8_t'

    Could you please adapt the check in Tools.h before setting own stdint defines. Instead of just checking for Windows OS, there should be the same _MSC_VER check just like Boost does it.

    opened by SieLink 7
  • Fix Node::reinsertData selection criteria

    Fix Node::reinsertData selection criteria

    Fix Incorrect R*-tree reinsertion implementation

    I'm pretty sure that libspatialindex has an incorrect R*-tree implementation related to the structure optimizations. I'm still working on groking the algorithm completely so I may be missing a detail.

    First I've listed code snippets from the paper's algorithms as well as from the source to libspatialindex. The end of this writeup describes the bug as I understand it with a discussion the fix.

    The R*-tree paper's "Algorithm Reinsert"

    This is on page 327 on the copy I'm reading (which is the one linked from Wikipedia).

    http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf

    Algorithm Reinsert
    
    RI1 - For all M+l entries of a node N, compute the distance
          between the centers of their rectangles and the center
          of the bounding rectangle of N
    
    RI2 - Sort the entries in decreasing order of their distances
          computed m RI1
    
    RI3 - Remove the first p entries from N and adjust the
          bounding rectangle of N
    
    RI4 - In the sort, defined 111 R12, starting with the maximum
          distance (= far reinsert) or minimum distance (= close
          reinsert), invoke Insert to reinsert the entries
    

    Node::reinsertData

    https://github.com/libspatialindex/libspatialindex/blob/master/src/rtree/Node.cc#L548

    This is a fairly close adherence to the algorithm as specified in the R*-tree paper. I've separated for clarity and commented on deviations from the algorithm as dictated in the paper.

    RI1

    This is a simple and straightforward step.

    void Node::reinsertData(uint32_t dataLength, byte* pData, Region& mbr, id_type id, std::vector& reinsert, std::vector& keep)
    {
        ReinsertEntry** v = new ReinsertEntry*[m_capacity + 1];
    
        m_pDataLength[m_children] = dataLength;
        m_pData[m_children] = pData;
        m_ptrMBR[m_children] = m_pTree->m_regionPool.acquire();
        *(m_ptrMBR[m_children]) = mbr;
        m_pIdentifier[m_children] = id;
    
        PointPtr nc = m_pTree->m_pointPool.acquire();
        m_nodeMBR.getCenter(*nc);
        PointPtr c = m_pTree->m_pointPool.acquire();
    
        for (uint32_t u32Child = 0; u32Child < m_capacity + 1; ++u32Child)
        {
            try
            {
                v[u32Child] = new ReinsertEntry(u32Child, 0.0);
            }
            catch (...)
            {
                for (uint32_t i = 0; i < u32Child; ++i) delete v[i];
                delete[] v;
                throw;
            }
    
            m_ptrMBR[u32Child]->getCenter(*c);
    
            // calculate relative distance of every entry from the node MBR (ignore square root.)
            for (uint32_t cDim = 0; cDim < m_nodeMBR.m_dimension; ++cDim)
            {
                double d = nc->m_pCoords[cDim] - c->m_pCoords[cDim];
                v[u32Child]->m_dist += d * d;
            }
        }
    

    RI2

    Notice the comment and how it disagrees with the paper's request for a sort in decreasing order. I've included the definition of ReinsertEntry below this code so that we can see that we're not being silly and reversing the sort by changing the semantics of the compare function.

        // sort by increasing order of distances.
        ::qsort(v, m_capacity + 1, sizeof(ReinsertEntry*), ReinsertEntry::compareReinsertEntry);
    

    RI3 - RI4

    This is a combination of the last two steps. Technically we're not making the actual modifications requested here, we're just splitting the child nodes into two groups and returning them. The actual mutations are handled in Node::insertData here:

    https://github.com/libspatialindex/libspatialindex/blob/master/src/rtree/Node.cc#L378

    The important point to note though is that the nodes placed into the reinsertion group are from the front of the sorted array which does follow the algorithm from the paper.

        uint32_t cReinsert = static_cast(std::floor((m_capacity + 1) * m_pTree->m_reinsertFactor));
    
        uint32_t cCount;
    
        for (cCount = 0; cCount < cReinsert; ++cCount)
        {
            reinsert.push_back(v[cCount]->m_index);
            delete v[cCount];
        }
    
        for (cCount = cReinsert; cCount < m_capacity + 1; ++cCount)
        {
            keep.push_back(v[cCount]->m_index);
            delete v[cCount];
        }
    
        delete[] v;
    }
    

    ReinsertEntry comparator

    Included for reference from above.

    https://github.com/cloudant/libspatialindex/blob/master/src/rtree/Node.h#L174

    class ReinsertEntry
    {
    public:
        uint32_t m_index;
        double m_dist;
    
        ReinsertEntry(uint32_t index, double dist) : m_index(index), m_dist(dist) {}
    
        static int compareReinsertEntry(const void* pv1, const void* pv2)
        {
            ReinsertEntry* pe1 = * (ReinsertEntry**) pv1;
            ReinsertEntry* pe2 = * (ReinsertEntry**) pv2;
    
            if (pe1->m_dist < pe2->m_dist) return -1;
            if (pe1->m_dist > pe2->m_dist) return 1;
            return 0;
        }
    }; // ReinsertEntry
    

    Discussion

    First, my understanding of the reinsertion algorithm:

    1. Sort the node's children based on distance from the center of each child's MBR to the center of the node's enclosing MBR.
    2. Remove the p farthest entries from the center of the node's enclosing MBR
    3. Insert these entries back into the tree at the appropriate level.

    And my understanding of the implementation in libspatialindex

    1. Same as the algorithm and what I've stated above
    2. Remove the p nearest entries from the center of the node's enclosing MBR
    3. Insert these entries back into the tree at the appropriate level (which would not unlikely be the same node, though I haven't verified that and it'd obviously depend on operation ordering).

    The reason for the discrepancy is that libspatialindex sorts its nodes in ascending order without correctly accounting for that and switching the end of the array to remove.

    However, in RI4 the paper mentions a choice in the order of reinserts by switching the order in which reinserts are applied. If you reinsert the nodes nearest first its a close reinsert, and reinserting the farther nodes first is a far insert. The paper then goes on to say:

    The experiments have shown that p = 30% of M for leaf nodes
    as well as for nonleaf nodes yields the best performance.
    Furthermore, for all data files and query files close reinsert
    outperforms far reinsert.
    

    When I first read this I thought it meant the sort in RI2, however it made me pause and think because it didn't make sense why removing nodes from the middle of a node's MBR would be more efficient than removing the outliers.

    The conclusion I came to was that the paper is actually only referring to the nodes to be reinserted. Thus, after we select the farthest-from-center nodes to reinsert, we then have a choice on which order to reinsert them.

    Given that we're already sorting in ascending order we can just go ahead and push these into the vector to match the suggested order of reinserts.

    opened by davisp 7
  • Move `dependabot.yml` to `.github` directory

    Move `dependabot.yml` to `.github` directory

    I made a mistake in #228 and put the Dependabot configuration file in the wrong directory. This PR fixes that and moves the dependabot.yml file to the correct directory, which is .github instead of .github/workflows.

    opened by EwoutH 0
  • New tagged version after 3 years?

    New tagged version after 3 years?

    I see that there are commits for the past years, but no new release - which is difficult for software repositories to keep up.

    Right now, we are still providing our users with 1.9.3. If there are significant changes, that would be nice to know. Thanks!

    opened by surak 0
  • Cast a ISpatialIndex to a Rtree object

    Cast a ISpatialIndex to a Rtree object

    Hey,

    I wrote a method to extend the functionality of the RTree and I cannot access it directly because the type of the tree is ISpatialIndex instead of RTree. I tried different ways to do it but without success so I thought of casting it but maybe I am missing something. My code:

    ISpatialIndex* tree1 = RTree::createNewRTree(*file1, 0.7, capacity, leafCapacity, 2, SpatialIndex::RTree::RV_RSTAR, indexIdentifierR);
    const SpatialIndex::RTree::RTree* pRTree = dynamic_cast<const SpatialIndex::RTree::RTree*>(&tree1);    
    
    

    That gives me a

    error: 'RTree' in namespace 'SpatialIndex::RTree' does not name a type error.

    I should mention that I am using namespace SpatialIndex.

    What am I missing?

    opened by DinosL 0
  • LibSpatial cannot handle filenames with unicode chars

    LibSpatial cannot handle filenames with unicode chars

    We use the latest LibSpatial using vcpkg.

    When we want to create index files for a shapefile with names like MyPolygon.shp it works fine. But when we use names like Воздух.shp the process fails and no index files are created.

    We're now investigating where the problem is. In our code before we call StorageManager::createNewDiskStorageManager or if LibSpatial just can't handle these kinds of filenames.

    Can you confirm LibSpatial should be able to handle these unicode filenames?

    opened by pmeems 10
  • MacOS CMake doesnt seem to produce relative RPATH

    MacOS CMake doesnt seem to produce relative RPATH

    I've built libspatialindex as follows:

    git clone https://github.com/libspatialindex/libspatialindex
    cd libspatialindex
    cmake .
    make install
    

    Then I move the produced dylib files to another directory during the CI pipeline of RTree and the checks fail with:

    OSError: dlopen(/usr/local/miniconda/envs/test/lib/python3.8/site-packages/rtree/lib/libspatialindex_c.dylib, 6): Library not loaded: @rpath/libspatialindex.6.dylib
    E     Referenced from: /usr/local/miniconda/envs/test/lib/python3.8/site-packages/rtree/lib/libspatialindex_c.dylib
    E     Reason: image not found
    

    Even though an ls of the folder that contains the libspatialindex_c.dylib (visible as the list of filenames right above the error in the build log) contains the file:

    libspatialindex.6.1.1.dylib
    libspatialindex.6.dylib
    libspatialindex.dylib
    libspatialindex_c.6.1.1.dylib
    libspatialindex_c.6.dylib
    libspatialindex_c.dylib
    

    Going back and forth with test prints in the GitHub Actions log is not my favorite debug environment and I have no Mac device to reproduce so I can't investigate further.

    Assuming it's because of moving the dylib files after they've been linked, could it be possible to switch to something that's relative to their current directory ... like ./libspatialindex.6.dylib? :) That shouldn't cause any regression or issues because well currently they can't be moved and are always linked in the same folder, switching from @rpath/libspatialindex*.dylib to ./libspatialindex*.dylib atleast makes it possible to move them together.

    opened by Helveg 5
  • Thread Safety

    Thread Safety

    I've been working on making the query functions reentrant. It looks as though the primary challenge to this is that the memory pool is shared, causing contention or race conditions.

    I would whether it might make sense to either (a) make another class whose query methods take an externally-defined pool as an argument or (b) add another set of query methods which take an argument to an external pool and avoid touching the class's internal pool.

    Both of these approaches would preserve the existing API.

    Alternatively, the memory pool could be made thread safe, but I think it would be harder to prove that it behaves as it ought and this introduces indirect memory accesses.

    What do folks think?

    opened by r-barnes 3
Releases(1.9.3)
MITRE's C/C++ implementation of WGS84 geodesic algorithms documented in FAA Order 8260.58A, Appendix E.

MITRE Geodetic Library Geodetic library (or geolib) is a library for performing WGS-84 calculations with high precision. We think it's very handy and

The MITRE Corporation 2 Oct 14, 2022
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 Jan 6, 2023
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 750 Jan 1, 2023
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 191 Dec 28, 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.9k Jan 6, 2023
Computational geometry and spatial indexing on the sphere

S2 Geometry Library Overview This is a package for manipulating geometric shapes. Unlike many geometry libraries, S2 is primarily designed to work wit

Google 1.9k Dec 31, 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 286 Oct 26, 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 Jan 6, 2023
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 20 Nov 20, 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 105 Nov 2, 2022
An intrusive C++17 implementation of a Red-Black-Tree, a Weight Balanced Tree, a Dynamic Segment Tree and much more!

This is Ygg (short for Yggdrasil), a C++17 implementation of several intrusive data structures: several balanced binary search trees: a red-black Tree

Lukas Barth 98 Dec 25, 2022
This is like Inverting Binary Tree, but instead of a Binary Tree it's a File Tree.

Invert File Tree in C++ This is like Inverting Binary Tree, but instead of the Binary Tree it's a File Tree. This is intended as a simple exercise to

Tsoding 12 Nov 23, 2022
log4cplus is a simple to use C++ logging API providing thread-safe, flexible, and arbitrarily granular control over log management and configuration. It is modelled after the Java log4j API.

% log4cplus README Short Description log4cplus is a simple to use C++17 logging API providing thread--safe, flexible, and arbitrarily granular control

null 1.4k Jan 4, 2023
Simple-MySQL-API is a free and easy API to manipulate MySQL with C99 and GCC compiler under GNU/Linux OS.

Simple-MySQL-API is a free and easy API to manipulate MySQL with C99 and GCC compiler under GNU/Linux OS.

Neptune 8 Aug 21, 2022
The goal of arrowvctrs is to wrap the Arrow Data C API and Arrow Stream C API to provide lightweight Arrow support for R packages

The goal of arrowvctrs is to wrap the Arrow Data C API and Arrow Stream C API to provide lightweight Arrow support for R packages to consume and produce streams of data in Arrow format. Right now it’s just a fun way for me to learn about Arrow!

Dewey Dunnington 30 Aug 5, 2022
The Telegram Bot API provides an HTTP API for creating Telegram Bots.

The Telegram Bot API provides an HTTP API for creating Telegram Bots.

Telegram Library 1.9k Jan 1, 2023
ResNet Implementation, Training, and Inference Using LibTorch C++ API

LibTorch C++ ResNet CIFAR Example Introduction ResNet implementation, training, and inference using LibTorch C++ API. Because there is no native imple

Lei Mao 23 Oct 29, 2022
Deno gl - WIP Low-level OpenGL (GLFW) bindings and WebGL API implementation for Deno.

deno_gl WIP Low-level OpenGL (GLFW) bindings and WebGL API implementation for Deno. Building Make dist directory if it doesn't exist. Build gl helper

DjDeveloper 14 Jun 11, 2022
Probabilistic Risk Analysis Tool (fault tree analysis, event tree analysis, etc.)

SCRAM SCRAM is a Command-line Risk Analysis Multi-tool. This project aims to build a command line tool for probabilistic risk analysis. SCRAM is capab

Olzhas Rakhimov 115 Dec 30, 2022