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

Inefficient retrival of elements within an area #122

Closed
gaganjyot opened this Issue Oct 2, 2017 · 2 comments

Comments

Projects
None yet
3 participants
@gaganjyot

gaganjyot commented Oct 2, 2017

From what I understand,

Lets say there is an area { 5000, 5000 } , { -5000, -5000 } area1 ( area of quadtree )

If I want to retrieve elements in area { 100, 100 }, { 200, 200 } called area2

it checks if the area2 is in the area1 and returns all the elemets so present in the area1

I don't have a *nix platform to unittest and make sure about it. but if the understanding is correct it will be retrieving lots of entities that are not even the area. Not sure if painter will paint all the entities or only a few

void _retrieve(std::vector<E>& list, const geo::Area& area, const short maxLevel) const {

@feragon

This comment has been minimized.

Show comment
Hide comment
@feragon

feragon Oct 3, 2017

Member

That's right, this test fails:

TEST(Test, Test) {
    lc::QuadTree<lc::entity::CADEntity_CSPtr> qt;
    qt.insert(std::make_shared<lc::entity::Line>(lc::geo::Coordinate(-5000, -5000),
                                                 lc::geo::Coordinate(5000, 5000),
                                                 std::make_shared<lc::Layer>())
    );

    ASSERT_EQ(0, qt.retrieve(lc::geo::Area(lc::geo::Coordinate(1, -1), lc::geo::Coordinate(5000, -5000))).size()); //Returns 1 element
}
Member

feragon commented Oct 3, 2017

That's right, this test fails:

TEST(Test, Test) {
    lc::QuadTree<lc::entity::CADEntity_CSPtr> qt;
    qt.insert(std::make_shared<lc::entity::Line>(lc::geo::Coordinate(-5000, -5000),
                                                 lc::geo::Coordinate(5000, 5000),
                                                 std::make_shared<lc::Layer>())
    );

    ASSERT_EQ(0, qt.retrieve(lc::geo::Area(lc::geo::Coordinate(1, -1), lc::geo::Coordinate(5000, -5000))).size()); //Returns 1 element
}
@rvt

This comment has been minimized.

Show comment
Hide comment
@rvt

rvt Oct 3, 2017

Member

In context of quad tree this is correct. The quad tree doesn't care about exact coordinates but it just finds the area's that include (even partially) in the requested area.
Since the bounding box of the lines falls over the boundig box of the requested area the line is included.

For painting it matters such that element's really outside of a quad will not be retreived, but even taht depends.

For example if you have 10 elements in a quad tree, no matter what you do, you will always retrieve them all. If you have 1000 they will be pushed down the quad tree levels and store them at finer granularity.

This could even optmise painting during canvas moving. Because you could easely request all entities up to some level X and you will only get a maximum number of entities but nothing below that (if it applies).

For the painter is doesn't matter much in some conditions. We need to be carefull not to optimise to much because sometimes it can be faster to just paint it rather than to find out if we need to paint it. The quad tree just helps with it... We do have some more exact routines that can find all entities within a bounding box, thet just take a lot more time to calculate.

For OpenGL it could even slow things down because with OpenGL you can keep everything in memory (I hope :) ) and as such it's properly faster to let the GPU handle it.
In addition, both the painter and kernel can use there own implementation to speed up operations if they wish...

Hope that makes sense...

Member

rvt commented Oct 3, 2017

In context of quad tree this is correct. The quad tree doesn't care about exact coordinates but it just finds the area's that include (even partially) in the requested area.
Since the bounding box of the lines falls over the boundig box of the requested area the line is included.

For painting it matters such that element's really outside of a quad will not be retreived, but even taht depends.

For example if you have 10 elements in a quad tree, no matter what you do, you will always retrieve them all. If you have 1000 they will be pushed down the quad tree levels and store them at finer granularity.

This could even optmise painting during canvas moving. Because you could easely request all entities up to some level X and you will only get a maximum number of entities but nothing below that (if it applies).

For the painter is doesn't matter much in some conditions. We need to be carefull not to optimise to much because sometimes it can be faster to just paint it rather than to find out if we need to paint it. The quad tree just helps with it... We do have some more exact routines that can find all entities within a bounding box, thet just take a lot more time to calculate.

For OpenGL it could even slow things down because with OpenGL you can keep everything in memory (I hope :) ) and as such it's properly faster to let the GPU handle it.
In addition, both the painter and kernel can use there own implementation to speed up operations if they wish...

Hope that makes sense...

@feragon feragon closed this Jun 25, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment