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

Allow inserting Point entries #5

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

Allow inserting Point entries #5

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

Comments

@lukas-shawford
Copy link
Owner

lukas-shawford commented May 3, 2020

The R-tree should allow storing points in addition to rectangles.

When implementing query, a Point type was added to allow querying the R-tree using a point location (instead of a rectangle). It seems expected that if one can query using a point, one should be able to store an entry using Point also.

The initial thought is that RTreeBase.insert should accept a Location (which can be either Point or Rect), instead of Rect (which is the only type it accepts currently). Whether something like Point(3, 5) then gets converted to a degenerate rectangle such as Rect(3, 5, 3, 5) so it works with the existing algorithms unchanged, or whether the algorithms need to be adjusted, is something that needs to be investigated.

Using a "degenerate" rectangle such as Rect(1, 1, 1, 1) with the current code does not work with query, and currently results in unexpected behavior:

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

Proper handling of "degenerate" rectangles will be handled in #6.

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