rtreelib icon indicating copy to clipboard operation
rtreelib copied to clipboard

Handle "degenerate" rectangles

Open lukas-shawford opened this issue 4 years ago • 0 comments

The library currently results in unexpected behavior when inserting or querying with "degenerate" rectangles (having a width and/or height of zero).

Example (from discussion in #4):

my_tree = RTree()
my_tree.insert("A", Rect(1, 1, 1, 1))
my_tree.insert("B", Rect(2, 2, 2, 2))

print(list(my_tree.query(Rect(0, 0, 5, 5)))) # is [] but expected "A" and "B"

# debug
found = list(my_tree.query_nodes(Rect(0, 0, 5, 5))) # returns one node
for x in found:
    for b in x.entries:
        print(b.rect.intersects(Rect(0, 0, 5, 5))) # always False

How to properly handle such degenerate rectangles will require more investigation. I'm not sure if the algorithms that have been implemented thus far (Guttman and R*) were even designed to handle them, as both rely on calculating perimeter/area for certain steps, and I'm not sure what will happen if (for instance) the area comes out as 0.

There is also the question of whether the library should convert a rectangle like Rect(3, 5, 3, 5) into a Point(3, 5) behind the scenes, as soon as the entry is inserted, or whether it should preserve what the user put in.

lukas-shawford avatar May 03 '20 18:05 lukas-shawford