2
$\begingroup$

What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it)

Whats the most efficient way to determine if a point is in one of the rectangles

From some previous research I found that quad trees are good for that and I think I also understand how they work but I can't figure out how they help to solve my problem. I can find points close to one point but how to I find out if my point is in one of the many rectangles?

Improve this question
$\endgroup$
2
  • $\begingroup$ Probably duplication of this question? $\endgroup$
    – TilmannZ
    Commented Mar 8, 2022 at 11:30
  • $\begingroup$ Another potential duplicate is this question. $\endgroup$
    – TilmannZ
    Commented Mar 8, 2022 at 11:36

1 Answer 1

Reset to default
2
$\begingroup$

Use a segment tree or interval tree.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the response, but what are the benefits over a Quadtree (if there are any) $\endgroup$
    – derteufelqwe
    Commented Mar 11, 2022 at 18:07
  • $\begingroup$ @derteufelqwe, those can be used to solve your problem; there are standard, well-documented explanations how to use them to solve your problem. It sounds like you don't know how to use a quadtree to solve your problem (and I don't have anything in particular to propose, either). Given those two facts, the benefit seems pretty clear! $\endgroup$
    – D.W. ♦
    Commented Mar 11, 2022 at 18:56
  • $\begingroup$ Note for further readers: I ended up using quad trees as they are simpler IMO but this answer got me some good inspiration and contain also suitable solutions. $\endgroup$
    – derteufelqwe
    Commented Mar 17, 2022 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.