I need a spatial index in C

Question

I am working on my gEDA plug and want to get rid of the existing simple system based on tile ¹ in favor of real spatial index ² .

An algorithm that effectively finds points is not enough: I need to find objects with a nonzero degree. Think in terms of objects with bounding boxes, which largely reflects the level of detail I need in the index. Given the search rectangle, I need to be able to efficiently find all objects whose bounding rectangles are inside or intersect the search rectangle.

The index cannot be read-only: gschem is a schematic capture program, and the whole point is to move elements around the schema. So everything will be all right. Therefore, although I can let you insert a little more expensive than a search, it cannot be too expensive, and removal should also be both possible and inexpensive. But the most important requirement is asymptotic behavior: the search must be O (log n) if it cannot be O (1). The insertion / deletion should preferably be O (log n), but O (n) will be fine. I definitely don't want anything> O (n) (per action, obviously, O (n log n) is expected for operation with objects).

What are my options? I do not feel smart enough to appreciate various parameters . Ideally, there would be some C library that will do all the smart things for me, but I will mechanically implement an algorithm that I may or may not fully understand if necessary. gEDA uses glib by the way, if that helps make a recommendation.

Footnote:

¹ Standard gEDA divides the schematic diagram into a fixed number (currently 100) of tiles, which serves to speed up the search for objects in the bounding box. This is obviously good enough to make most circuits fast enough to search, but the way to fix them causes other problems: too many functions require a pointer to a de facto global object. The tile geometry has also been fixed: it would be possible to completely defeat this tile system, simply by panning (and possibly enlarging) to an area covered by only one tile.

^{2 The} acceptable answer was to preserve the elements of the tile system, but to correct its shortcomings: to teach it to cover the entire space and, if necessary, to divide into two parts. But I would like others to add their two cents before I arbitrarily decide that this is the best way.

Answer 1

A good data structure for combining points and lines would be an R-tree or one of its derivatives (for example, R * -Tree or Hilbert's R-Tree). If you want this index to be dynamic and serializable, I think using a SQLite R * -Tree module would be a smart approach.

If you can tolerate C ++, libspatialindex has a mature and flexible R-tree implementation that supports dynamic insertion / deletion and serialization.

Answer 2

Your needs sound very similar to what is used in collision detection algorithms for games and physical simulations. There are several open source C ++ libraries that handle this in 2-D (Box2D) or 3-D (Bullet Physics) . Although your question relates to C, you may find their documentation and implementations useful.

This is usually divided into two phases :

• A fast, wide phase that approximates objects along an axis aligned axis (AABB) and identifies AABB pairs that touch or overlap.
• A slower narrow phase that calculates geometric overlap points for pairs of objects whose AABBs touch or overlap.

Physical engines also use spatial coherence to further reduce the pairs of objects being compared, but this optimization will probably not help your application.

The wide phase is usually implemented using an O (N log N) algorithm such as Read and Trim . You can speed it up by using it in combination with the current tile-based approach ( one of the Nvidia GPUGems describes this hybrid approach). The narrow phase is quite expensive for each pair, and may be redundant for your needs. The GJK algorithm is often used for convex objects at this stage, although for more specialized cases there are faster algorithms (for example: box / circle and box / sphere collisions).

Answer 3

This is like an application that is well suited for the quadrant (assuming you are only interested in 2D.) Quadtree is hierarchical (good for searching), and spatial resolution is dynamic (allows higher resolution in the areas it needs).

I always rolled back my own quadrants, but here is a library that seems reasonable: http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C

Answer 4

It is easy to do. This is hard to do quickly. It seems like the problem I was working with, where there was a huge list of min, max values ​​and a value was set that he needed to return, how many minutes, max pairs overlap this value. You just have it in two dimensions. So you do this with two trees for each direction. Then do the intersection of the results. It's very fast.

#include <iostream> #include <fstream> #include <map> using namespace std; typedef unsigned int UInt; class payLoad { public: UInt starts; UInt finishes; bool isStart; bool isFinish; payLoad () { starts = 0; finishes = 0; isStart = false; isFinish = false; } }; typedef map<UInt,payLoad> ExtentMap; //============================================================================== class Extents { ExtentMap myExtentMap; public: void ReadAndInsertExtents ( const char* fileName ) { UInt start, finish; ExtentMap::iterator EMStart; ExtentMap::iterator EMFinish; ifstream efile ( fileName); cout << fileName << " filename" << endl; while (!efile.eof()) { efile >> start >> finish; //cout << start << " start " << finish << " finish" << endl; EMStart = myExtentMap.find(start); if (EMStart==myExtentMap.end()) { payLoad pay; pay.isStart = true; myExtentMap[start] = pay; EMStart = myExtentMap.find(start); } EMFinish = myExtentMap.find(finish); if (EMFinish==myExtentMap.end()) { payLoad pay; pay.isFinish = true; myExtentMap[finish] = pay; EMFinish = myExtentMap.find(finish); } EMStart->second.starts++; EMFinish->second.finishes++; EMStart->second.isStart = true; EMFinish->second.isFinish = true; // for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) // cout << "| key " << EMStart->first << " count " << EMStart->second.value << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish << endl; } efile.close(); UInt count = 0; for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) { count += EMStart->second.starts - EMStart->second.finishes; EMStart->second.starts = count + EMStart->second.finishes; } // for (EMStart=myExtentMap.begin(); EMStart!=myExtentMap.end(); EMStart++) // cout << "||| key " << EMStart->first << " count " << EMStart->second.starts << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish << endl; } void ReadAndCountNumbers ( const char* fileName ) { UInt number, count; ExtentMap::iterator EMStart; ExtentMap::iterator EMTemp; if (myExtentMap.empty()) return; ifstream nfile ( fileName); cout << fileName << " filename" << endl; while (!nfile.eof()) { count = 0; nfile >> number; //cout << number << " number "; EMStart = myExtentMap.find(number); EMTemp = myExtentMap.end(); if (EMStart==myExtentMap.end()) { // if we don't find the number then create one so we can find the nearest number. payLoad pay; myExtentMap[ number ] = pay; EMStart = EMTemp = myExtentMap.find(number); if ((EMStart!=myExtentMap.begin()) && (!EMStart->second.isStart)) { EMStart--; } } if (EMStart->first < number) { while (!EMStart->second.isFinish) { //cout << "stepped through looking for end - key" << EMStart->first << endl; EMStart++; } if (EMStart->first >= number) { count = EMStart->second.starts; //cout << "found " << count << endl; } } else if (EMStart->first==number) { count = EMStart->second.starts; } cout << count << endl; //cout << "| count " << count << " key " << EMStart->first << " S " << EMStart->second.isStart << " F " << EMStart->second.isFinish<< " V " << EMStart->second.value << endl; if (EMTemp != myExtentMap.end()) { myExtentMap.erase(EMTemp->first); } } nfile.close(); } }; //============================================================================== int main (int argc, char* argv[]) { Extents exts; exts.ReadAndInsertExtents ( "..//..//extents.txt" ); exts.ReadAndCountNumbers ( "..//../numbers.txt" ); return 0; } 

the extents test file was 1.5 MB:

 0 200000 1 199999 2 199998 3 199997 4 199996 5 199995 .... 99995 100005 99996 100004 99997 100003 99998 100002 99999 100001 

The file with the numbers was as follows:

 102731 104279 109316 104859 102165 105762 101464 100755 101068 108442 107777 101193 104299 107080 100958 ..... 

Even when reading two files from disk, extents were equal to 1.5 MB, and the numbers were 780 KB and a really large number of values ​​and search queries, this is done in a split second. If in memory it will be quickly lightning fast.