Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Handle "degenerate" rectangles #6

Open
lukas-shawford opened this issue May 3, 2020 · 0 comments
Open

Handle "degenerate" rectangles #6

lukas-shawford opened this issue May 3, 2020 · 0 comments

Comments

@lukas-shawford
Copy link
Owner

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant