查找矩形内所有点的快速算法 [英] Fast algorithm to find all points inside a rectangle

问题描述

给定2D空间中的一组不同点和一个矩形（所有四个点的坐标，与xy轴平行的边），如何快速找到矩形内的点？

Given a set of distinct points in 2D space, and a rectangle (coordinates of all four points, sides parallel with xy axis) how can I quickly find which points are inside the rectangle?

我对遍历所有点并查看哪一个在矩形内的基本解决方案不感兴趣。我正在寻找的是一种算法，该算法将为我提供每个矩形的快速查询时间。

I'm not interested in the basic solution of going through all points and seeing which one is inside the rectangle. What I'm looking for is an algorithm which will give me fast query times per rectangle.

我不在乎在预处理步骤中花费了多少时间。我关心的是，在处理完数据后，我得到了一个有用的结构，该结构使我可以快速查询每个矩形。

I don't care how much time I spend in the preprocessing step. What I do care is that after I process my data I obtain a useful structure which gives me fast query times per rectangle.

例如，我知道我可以计算多少个点我在O（logN）中有一个矩形。之所以行得通，是因为我一开始做了很多繁重的处理，然后每次都用一个新的矩形查询处理后的数据，并在logN时间获得一个新的计数。我正在寻找一种类似的算法来查找实际点，而不仅仅是点数。

I know for example I can count how many points I have inside a rectangle in O(logN). That works because I do a lot of heavy processing in the beginning and then query the processed data with a new rectangle every time and get a new count in logN time. I'm looking for a similar algorithm for finding the actual points not just their count.

推荐答案

经典的答案是kD-树（在这种情况下为2D树）。

A classical answer is the kD-tree (2D-tree in this case).

作为一种简单的替代方法，如果点的分布足够均匀，则可以通过网格进行尝试。

For a simple alternative, if your points are spread uniformly enough, you can try by gridding.

选择正方形网格的像元大小（如果问题是各向异性的，则使用矩形网格）。将每个点分配给包含在链表中的网格单元。当您执行查询时，找到所有与矩形重叠的单元格并对其进行扫描以遍历其列表。对于部分覆盖的单元格，您将需要执行矩形点测试。

Choose a cell size for a square grid (if the problem is anisotropic, use a rectangular grid). Assign every point to the grid cell that contains it, stored in a linked list. When you perform a query, find all cells that are overlapped by the rectangle and scan them to traverse their lists. For the partially covered cells, you will need to perform the point-in-rectangle test.

大小的选择很重要：太大会导致太多点无论如何都需要测试；太小会导致太多的空单元格。

The choice of the size is important: too large can result in too many points needing to be tested anyway; too small can result in too many empty cells.

这篇关于查找矩形内所有点的快速算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！