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.

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.

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.

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 :)

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.

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

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.

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.

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?

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.

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.

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.

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!

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?

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?

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.

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?