Is there an efficient way to see if N number of (x,y) points are inside K number of rectangles? Right now I am doing a brute force approach and looping through all points and rectangles but its taking about 2 minutes and 30 seconds with 200,000 points and 44 rectangles.
I am working with Google maps and creating a program to check if points are close to a route on a map. I calculate multiple Rectangles and Circles along the path and test to see if the existing points lay within these rectangles and circles.
1.The rectangles can overlap depending on the nature of the route.
2.The point only has to be in ONE of the rectangles
3.If the point is on the edge of the rectangle I would like to make it count as inside the rectangle (but if its easier to not count then I won't count it)
4.The rectangles are dependent on what the area I want to search for off the route. Typically they will be 2 miles High (1 mile each direction from point) and the distance from point1 to point2 Wide.
In theory at the very best you'll have to iterate through all 200,000 points -- and in the worst case you'll have to check all of those points against all 44 rectangles (which is what you're doing right now).
Since you know you'll have to loop through all 200,000 points the best you can do is attempt to not have to check all 44 rectangles.
In order to do this you'll have to do some calculations on the rectangles, you find the closest two rectangles and form a larger rectangle which encloses both of them (a cluster if you will). Then you find the next closest rectangle to the rectangle you just formed form another cluster rectangle. You keep doing this until you enclose all of the rectangles (You'll end up having 43 cluster rectangles).
Now loop through the points and check against the largest rectangle, if the point falls within that rectangle, then you check the next largest rectangle, if it doesn't fall within that rectangle then you only need to check the to see if it falls within the rectangle which was used to form that rectangle. If it doesn't fall within that rectangle, then you can move onto the next point because that point doesn't fall within any rectangles (and you discovered this with only 3 checks).