educative.io

What exactly I am searching in the quad tree?

Courses
,
#1

Can someone explain me with an example.
Let’s say my location is (20,20). now how will I scan this quad-tree ds having radius of 100KM around my location(20,20)?
Not to mention, my location is not registered in this DS yet. And as per author we need find all the locations between (X+D,X-D) and (Y+D,Y-D)
So, exactly what I am searching in the tree?

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5649050225344512
Lesson: https://www.educative.io/collection/page/5668639101419520/5649050225344512/5639274879778816

#2

@Design_Gurus
It would be great if you can explain with an example

#3

So Earth is divided into squares with side = 100 KM. Circle with radius of 100 KM is containted in maximum of 9 such squares. You look for the ID of square where your (20, 20) is, and IDs of 8 surrounding squares in the database. Then your query will include exact IDs of those squares and so will only have to scan locations that belong to those squares Select * from Places where Latitude between X-D and X+D and Longitude between Y-D and Y+D and GridID in (GridID, GridID1, GridID2, …, GridID8).