I need to figure out how to check if certain points lie inside or outside a rectangle given as coordinates (x1,x2,y1,y2) i.e. top left and bottom right points of rectangle. The total number of points are pretty large approx. 2 million. I know a quadtree is used in such cases but I can't seem to figure out how to apply that here. Like what to store in the tree and how to query it.

Also if someone can help me understand how to solve this problem for a small number of points efficiently then that would be great too !

CodePudding user response：

If you already have all the n points stored statically in a random order and want to process them, there is nothing better than a linear search checking the condition for each point (the only improvement you can do is to put processes and threads to parcel different blocks of the array of points).

If you receive them dynamically, you can store them in a quadtree as you receive. Then you can search in logarithmic time in n (in average) for the quantity of points in a rectangle.

CodePudding user response：

Quad trees are quite easy and worth it.

However a simple solution (sufficient but not that good):

You can also sort the points in two lists

• Sorted by x
• Sorted by y

Say you have two lists of both 10_000 points. For an x matching you get 200 points, for an y matching you get 80 points.

A matching is done by the two rectangle boundary coordinates: (left, right) resp. (top, bottom). With binary search O(log n).

Insertion of a new point can also be done with binary search.

The intersection of both results lies exactly inside your rectangle.