If the size of the root node, which is the first node inserted, changes size in that the new size is bigger than the old one the delete won't delete because tr.root.contains(&item) returns false and hence is truein the code below.

Because the Replace function is just a Delete and Insert, this leads to a bug where the root node is now inserted once again. So after the Replace we have RTree.Len() + 1 , which is wrong. RTree.Len() has to be the same before and after the Replace.

https://github.com/tidwall/rbang/blob/ecaccd2e0367c5dd8e735fe40d6780dfa38f7806/rbang.go#L370-L375

I tried to use https://github.com/Workiva/go-datastructures/tree/master/rtree, but it seems buggy when you are changing some members' coordinates; deleting and inserting doesn't seem to work correctly.

However, it claims that the RTree can be used threadsafe. From looking at the source, I think rbang is not threadsafe. Is that correct? Any plans to make it threadsafe?

Hi! I came here via a twitter post about performance. I was curious, so I poked around a bit for fun. A few minor comments, in the hopes that they are useful.

First, BenchmarkRandomInsert can be a bit misleading. If you make it run faster, it gets to a higher b.N, but at higher b.N, each iteration has to do more work. Thus code improvements don't necessarily show up in improved benchmark results. Picking a fixed number of iterations to do each time would be better. Perhaps like:

func BenchmarkRandomInsert(b *testing.B) {
	const iters = 10000
	boxes := randBoxes(iters)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		var tr RTree
		for iter := 0; iter < iters; iter++ {
			tr.Insert(boxes[iter].min[:], boxes[iter].max[:], iter)
		}
	}
}

Second, I can get a ~15% speedup on BenchmarkRandomInsert on my machine by unrolling the loops in chooseLeastEnlargement. Here's the 3d version:

// min is a sloppy float min function.
// It is faster than math.Min, at the cost
// of sloppy handling of the usual
// floating point delights: NaN and Inf.
func min(x, y float64) float64 {
	if x < y {
		return x
	}
	return y
}

// max is like min, only max.
func max(x, y float64) float64 {
	if x < y {
		return y
	}
	return x
}

func (r *box) chooseLeastEnlargement(b *box) int {
	j, jenlargement, jarea := -1, 0.0, 0.0
	n := r.data.(*node)
	for i := 0; i < n.count; i++ {
		area := (n.boxes[i].max[0] - n.boxes[i].min[0]) *
			(n.boxes[i].max[1] - n.boxes[i].min[1]) *
			(n.boxes[i].max[2] - n.boxes[i].min[2])

		enlargedArea := (max(b.max[0], n.boxes[i].max[0]) - min(b.min[0], n.boxes[i].min[0])) *
			(max(b.max[1], n.boxes[i].max[1]) - min(b.min[1], n.boxes[i].min[1])) *
			(max(b.max[2], n.boxes[i].max[2]) - min(b.min[2], n.boxes[i].min[2]))

		enlargement := enlargedArea - area

		if j == -1 || enlargement < jenlargement || (enlargement == jenlargement && area < jarea) {
			j, jenlargement, jarea = i, enlargement, area
		}
	}
	return j
}

IMHO, it also improves readability a bit. Of course, it makes your code generation more complicated.

The current splitting mechanism seems quite simple and based on recent papers on node splitting for r-trees I think there is a lot of room for improving it.

One way is instead of splitting the rectangle (when it reached maximum entries) based on its largest axis we can split it based on the axis which makes a smaller overlapping area after the split.

This way it generates more efficient splitting because the smaller the overlapping area helps find the right rectangle faster. When there is no overlapping area (the overlapping area is zero) we can use the largest axis like before.

I run this benchmark from the test file for 10 million records for 5 times go test -bench=. -run=TestGeoIndex -count=5 which gives these results.

Largest axis:

seed: 1649339938841388500 insert: 10,000,000 ops in 9713ms, 1,029,571/sec, 971 ns/op search: 10,000,000 ops in 11043ms, 905,545/sec, 1104 ns/op delete: 10,000,000 ops in 18059ms, 553,752/sec, 1805 ns/op insert: 10,000,000 ops in 9486ms, 1,054,226/sec, 948 ns/op search: 10,000,000 ops in 13304ms, 751,670/sec, 1330 ns/op delete: 10,000,000 ops in 14877ms, 672,192/sec, 1487 ns/op insert: 10,000,000 ops in 8545ms, 1,170,221/sec, 854 ns/op search: 10,000,000 ops in 8024ms, 1,246,227/sec, 802 ns/op delete: 10,000,000 ops in 13623ms, 734,071/sec, 1362 ns/op insert: 10,000,000 ops in 9244ms, 1,081,823/sec, 924 ns/op search: 10,000,000 ops in 8730ms, 1,145,484/sec, 872 ns/op delete: 10,000,000 ops in 14045ms, 711,980/sec, 1404 ns/op insert: 10,000,000 ops in 8570ms, 1,166,880/sec, 856 ns/op search: 10,000,000 ops in 9173ms, 1,090,108/sec, 917 ns/op delete: 10,000,000 ops in 14159ms, 706,288/sec, 1415 ns/op goos: linux goarch: amd64 pkg: github.com/tidwall/rtree cpu: Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz BenchmarkRandomInsert-8 2106502 662.1 ns/op BenchmarkRandomInsert-8 2076409 649.2 ns/op BenchmarkRandomInsert-8 1785523 671.1 ns/op BenchmarkRandomInsert-8 1993303 698.6 ns/op BenchmarkRandomInsert-8 1968975 668.6 ns/op PASS ok github.com/tidwall/rtree 187.575s

Minimum overlapping:

seed: 1649340172027585044 insert: 10,000,000 ops in 10305ms, 970,424/sec, 1030 ns/op search: 10,000,000 ops in 8469ms, 1,180,722/sec, 846 ns/op delete: 10,000,000 ops in 17717ms, 564,439/sec, 1771 ns/op insert: 10,000,000 ops in 9831ms, 1,017,192/sec, 983 ns/op search: 10,000,000 ops in 7829ms, 1,277,341/sec, 782 ns/op delete: 10,000,000 ops in 13622ms, 734,104/sec, 1362 ns/op insert: 10,000,000 ops in 8415ms, 1,188,372/sec, 841 ns/op search: 10,000,000 ops in 7520ms, 1,329,788/sec, 751 ns/op delete: 10,000,000 ops in 12974ms, 770,768/sec, 1297 ns/op insert: 10,000,000 ops in 9586ms, 1,043,225/sec, 958 ns/op search: 10,000,000 ops in 9120ms, 1,096,486/sec, 912 ns/op delete: 10,000,000 ops in 14197ms, 704,351/sec, 1419 ns/op insert: 10,000,000 ops in 9437ms, 1,059,663/sec, 943 ns/op search: 10,000,000 ops in 7609ms, 1,314,176/sec, 760 ns/op delete: 10,000,000 ops in 13316ms, 750,948/sec, 1331 ns/op goos: linux goarch: amd64 pkg: github.com/tidwall/rtree cpu: Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz BenchmarkRandomInsert-8 1834258 735.7 ns/op BenchmarkRandomInsert-8 1822066 719.2 ns/op BenchmarkRandomInsert-8 1780968 716.1 ns/op BenchmarkRandomInsert-8 1821146 765.8 ns/op BenchmarkRandomInsert-8 1800307 716.3 ns/op PASS ok github.com/tidwall/rtree 176.871s

Searching took about 810 ns/op for minimum_overlap and 1005 ns/op for the largest axis which seems a fairly good imporvment.

Insertion time increased a bit from about 669 ns/op to about 730 ns/op because we do more jobs in the splitting phase.

I think in geo indexing people insert the data once and query it many times so this algorithm may speed up queries for most of the users.

This adds a ReadOnly RTree that is generated from a Generic type.

It's intended to be serializable to allow saving large datasets that are never updated.

I have a graphics lib, where the origin (0,0) is at the top/left, and rects use a top/left and width/height notation.

rbang origin (0,0) is bottom/left and uses a bottom/left, top/right notation.

So, when inserting rects from the graphics lib, I use code like this to update the same rectangle:

• r = rectangle
• xll = x lower-left
• yll = y lower-left
• xur = x upper-right
• your = y upper-right

rbang.Replace(
	[2]float64{
		float64(r.xll),
		float64(r.yll)},
	[2]float64{
		float64(r.xur),
		float64(r.yur)},
	r,
	[2]float64{
		float64(r.GetLeft()),
		float64(r.GetTop())},
	[2]float64{
		float64(r.GetLeft() + r.GetWidth()),
		float64(r.GetTop() + r.GetHeight())}, r)

The problem is, that I have a very simple three rects layout (root, two childs with 50% width and 100% height of root), where a search with a point inside c2, returns the root node and c1... and not the root node and c2.