dhconnelly / rtreego Goto Github PK

I think there is a bug.
I tried bulk load, then deleting every 2nd element, and inserting back all elements deleted.
After that there are several copies of some elements and some are missing.
https://gist.github.com/codpe/c4b9ad39b91e4a79ab4647432b01bcca

I managed to find out, that this append sometimes changes entities in at least 2 nodes.

Hi, I noticed that in the r-tree implementation where in file "rtree.go", you only do the slicing at the root level, the other levels use just one slice whose length is the size of entire current subdataset (i.e. don't slice).

May i ask why you are doing this?

From what I have observed, if the slicing strategy is used in every height of recursion, it is possible to generate better leaf MBRs (their length and width are closer rather than one being much larger than the other).

is this support polygon (add, indexing and query) and spatial operation like within, intersect?

If condenseTree reduces the depth of the tree, the height variable does not get updated. If fact, height never decreases. It is only modified by increment, when a split occurs at the root. The result is that, by deleting noes, the tree may become invalid.

PR #11 overwrites the tree height with the root node level after deleting nodes. It also includes a simple test case that fails without the fix.

Hello I am using your library in one of the projects and it would be nice if you can help me out with using gob package to pack/unpack RTree.

We parse a lot of data from XML to RTree and this data is not changing after server start.
Good way will be to load it back from file (using gob encode/decode).

Thank you.

I noticed master is considerably ahead of the last tag. Is there a reason it hasn't recently been tagged and released?

https://go.dev/play/p/pnS0NlILZrm

From the README:

Bounding-box queries require a search *Rect. It returns all objects that touch the search rectangle.

However, we see from the demo that objects which are adjacent to the query input are not returned.

r2, _ := rtreego.NewRect(p2, []float64{0.0, 0.0})

if I set length to zero, the result will be empty

Currently, when one is performing a search with filters, the ApplyFilters function will execute every single filter even though some of them might already have refused the item. If the loop would stop as soon as the first filter refuses the item, one can achieve great performance improvements by placing the most expensive filters at the end of the list of filters. So I'd suggest breaking the loop on the first refuse or abort.

Seem quite weird to me that there is no way to take two points and create rect. I would expect to be able to create bounding box taking 2+ points and creating Rect based on min and max lng/lat/..(x/y/..) values.

I see there is private function for this, why not make it public?

hi ,
Would you consider upgrading the Rtree to R*tree?

I want to use NearestNeighbor() to find the closest Points, but this isn't supported. Is this something that could be added? Or could I just use 1x1x1 Spatials to approximate this?

Firstly, thanks for the library, really helpful.

I'm dealing with a set of documents that ranges from 10 points to 100,000 points. Each document has its own rtree and I'd be interested in "intelligently" picking the min/max children for each tree I generate.

Could you offer some advice about how I should go about picking appropriate min/max children?

thanks!

Often, bulk-loading a tree results in trees with more children than MaxChildren and more levels than returned by Rtree.Depth(). The searches seem to be unaffected, but that may cause issues when inserting or deleting entries after bulk load.

There are several issues in the OMT bulk-load implementation that cause the invalid trees:

• the calculated height by the algorithm does not match the depth reached during recursion
• the splitting of vertical slices results in not fully packed leaves
• the same problem results in non-leaf nodes containing more children than MaxChildren

We found this problem while trying to reduce the allocations in the KNN search, see issue #24.

NewRectFromPoints currently modifies its input slices without any warning in the documentation to the caller.

This can result in hours of troubleshooting, as it only happens if some first coordinate is above the second coordinate.

Also consider using value types (arrays) instead of reference types (slices).

R*Tree has better query performance.

I'm going to use RTree to do multi-dimension information query, instead of for spatial searching, for example, to query records witch satisfies [type, age, score... etc... ], I think rtree fits well for this situation.

rtreego.NewTree(3, 32, 64)},
find nearest point should be : lat 30.36424936824087, lon 104.03521157476646 ele 413.5494622178376，
but it is : Loc:[30.36001598001311 104.04658807033596 413.5494622178376]

I've been working with (a fork of) Patrick Higgins' fork of this package, but this same code exists in all three forks so I figured I should make note of this crash I've been seeing.

When inserting several Spatials at the same time at the same location and dimensions, this piece of code can break, as split tries to use indices to split with that are no longer valid, as it reset the entries in n.

func (n *node) split(minGroupSize int) (left, right *node) {
	// find the initial split
	l, r := n.pickSeeds()

	leftSeed, rightSeed := n.entries[l], n.entries[r]  <---- Crash here, index out of range, 2nd goroutine

	// get the entries to be divided between left and right
	remaining := append(n.entries[:l], n.entries[l+1:r]...)
	remaining = append(remaining, n.entries[r+1:]...)

	// setup the new split nodes, but re-use n as the left node
	left = n
	left.entries = []entry{leftSeed} <----- reset n's entries here, 1st goroutine
        ...

This can also show up sooner, here, when pickSeeds tries to range over entries[i+1:].

I don't think this is worth fixing, but I figured it was worth documenting. I just changed how the calling code worked so it wouldn't add duplicates.

Consider a point or a line which has the same y coordinates, the length of bounding box may be zero

When continuously running KNN-searches, we have noticed that sometimes the garbage collector (Go >= 1.9) stalls the process for more than 2s. That caused often deadline exceeded errors in our search services.

The issue occurs when sorting the nodes of each level: KNN goes depth first and at each node sorts its children in a temporary buffer of size <= MaxChildren. KNN then prunes some of the children and continues descending the tree in the recursion up to Rtree.Depth() levels. When the recursion returns and advances to siblings, more buffers are allocated down to the leaf nodes. That causes too many allocations for large trees and generate excessive trash for the garbage collector.

Instead of allocating a buffer for each node to sort its children, one can allocate one single buffer at the root and slide over the buffer the deeper one goes. The buffer should have the size MaxChildren*Rtree.Depth().

Do you have any plan to implement a disked-based Rtree in Golang?

We are using your project in a non-graphical context and we are still in the developement phase. For the sake of debugging we would like to know the current state of the rtree.

Many libraries for Quadtree can ouput a PNG with all the points and regions.

There is a String method but it only returns "foo" instead of a string representation of the rtree.

Hi,

Thanks for this awesome lib.
I am facing an issue :
I have following points:
keysBody := []byte([{"id": "1","name": "A","location": [88.495873,22.551802]},{"id": "2","name": "B","location": [88.490197,22.552743]},{"id": "3","name": "C","location": [88.492724,22.558270]}])
.................
type Storage struct {
Users map[string][]*user
geoIndex *rtreego.Rtree
nearestNeighbors int
}
.............
geoIndex.Insert(user)
............
lat := 22.562454
lon := 88.494374
...
geoIndex.NearestNeighbors(
20, rtreego.Point{lat, lon},
)

It always return : {"id": "2","name": "B","location": [88.490197,22.552743]} while id 3 (name c) is nearest

am I doing wrong or something ?