go-datastructures
go-datastructures copied to clipboard
Workiva
State of rtree different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10)
The state of rtree is different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10).
The difference is that maxHilbert changed from 0 to 34 in the (0,0,10,10) case. Is this intentional or a bug? I expect that the rtree behaves the same, independently of what kind of rectangles I have.
Maybe it's not relevant but I have one case, where an other rTree gives a correct search result whereas this one here is wrong. I search for P1 = (1,1,1,1) and P2 = (1001,1,1001,1) The sequence is:
Node-1: (0,0, 2000, 1000) Node-12: (0,0,2000,1000)
P1 and P2 are correctly found.
Adding Node-13 and changing Node-12 by remove and insert:
Node-1: (0,0, 2000, 1000) Node-12: (0,0,1000,1000) Node-13: (1000,0,2000,1000)
P1 correctly found, P2 reports Node-1 and Node-12 as result, which is wrong.
The problem seems to be when two nodes Node-1 and Node-12 have the same size but the Node objects are different.
func equal(r1, r2 rtree.Rectangle) bool returns true in such a case because only the geometry is compared. Within func (n *node) insert (kb *KeyBundle) the same equal function is used (there is even a comment, which states that we can have multiple keys with the same Hilbert number) und the old node is returned. But this old node isn't used to add the new node. Instead the new node replaces the old node.
These test cases fail, because the search only returns one result.
package main
import (
"testing"
"github.com/Workiva/go-datastructures/rtree"
"github.com/Workiva/go-datastructures/rtree/hilbert"
"github.com/stretchr/testify/assert"
)
// Implement Rectangles Interface
type rects []rect
type rect struct {
xll, yll, xur, yur int32
}
func (r *rect) LowerLeft() (int32, int32) {
return r.xll, r.yll
}
func (r *rect) UpperRight() (int32, int32) {
return r.xur, r.yur
}
func TestSameSizeSearch1(t *testing.T) {
r0 := &rect {0,0,0,0}
r1 := &rect {0,0,0,0}
rt := hilbert.New(3,3)
rt.Insert(r0)
rt.Insert(r1)
q1 := &rect {0,0,0,0}
result := rt.Search(q1)
assert.Equal(t, 2, len(result))
}
func TestSameSizeSearch2(t *testing.T) {
r0 := &rect {0,0,10,10}
r1 := &rect {0,0,10,10}
rt := hilbert.New(3,3)
rt.Insert(r0)
rt.Insert(r1)
q1 := &rect {1,1,1,1}
result := rt.Search(q1)
assert.Equal(t, 2, len(result))
}
Not sure if it's enough to change equal to check for same address of r1 & r2, or if taking these into account is only valid at specific places in the implementation, and other places just need to check the rect dimensions.
Converting to "addres equality" doesn't cover geometry simplification, and any "simple equality" does not sufficiently describe the needed comparisons. "area equality" is being performed, and @Robert-M-Muench, you point out this is valid in some places. "location equality" is a more complicated notion, but duplex containment might be a suitable stand-in.
