有没有一种有效的方法来查看 N 个 (x,y) 点是否在 K 个矩形内？现在我正在做一个蛮力方法并遍历所有点和矩形，但它需要大约 2 分 30 秒，有 200,000 个点和 44 个矩形。
我正在使用谷歌地图并创建一个程序来检查点是否靠近地图上的路线。我沿路径计算多个矩形和圆形并测试现有点是否位于这些矩形和圆形内。
1.矩形可以重叠，具体取决于路线的性质。
2.该点只能在一个矩形中
3.如果该点位于矩形的边缘，我想让它算在矩形内（但如果它更容易不计算，那么我不会计算它）
4.矩形取决于我想在路线外搜索的区域。通常，它们将高 2 英里（从点的每个方向 1 英里）和从点 1 到点 2 的距离宽。
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).
以下是一些可能的想法：