found = false
for each r in rectangles:
if point.x > r.x1 && point.x < r.x2:
if point.y > r.y1 && point.y < r.y2
found = true
break
稍微不那么有效（但更快）的方法将按左下角排序矩形（例如），然后您只需要搜索矩形的子集。
如果坐标是整数类型，您可以创建一个二进制掩码-然后查找就是单个操作（在您的情况下，这将需要512MB的查找表）。如果您的空间相对稀疏（即“未命中”的概率相当大），则可以考虑使用欠采样的位图（例如，使用坐标/8）-然后映射大小降至8M，如果您没有命中，则可以节省查看更仔细的费用。当然，您必须将左/底部舍入，并将顶部/右侧坐标舍入以使其正常工作。
举个例子：
假设坐标只能是x轴0-15和y轴0-7。有三个矩形（全部为[x1 y1 x2 y2]: [2 3 4 5]、[3 4 6 7]和[7 1 10 5]）。我们可以在一个矩阵中绘制它们（我用矩形的编号标记左下角-请注意，1和2重叠）：
...xxxx.........
...xxxx.........
..xxxxx.........
..x2xxxxxxx.....
..1xx..xxxx.....
.......xxxx.....
.......3xxx.....
................
.oxx....
.xxooo..
.oooxo..
...ooo..
x来标记“如果您到达此点，则肯定在矩形内”，而使用o表示“其中一些是矩形”。现在许多点都是“可能的”，节省的时间更少。如果您进行更严格的下采样，可以考虑使用两位掩码：这将允许您说“整个块都填满了矩形”（即 - 不需要进一步处理：x上面），或者“需要进一步处理”（如上所述o）。这很快开始变得比Q树方法更复杂...
底线：您越是事先对矩形进行排序/组织，查找速度就越快。
将矩形的坐标部分存储到树结构中。对于任何左值，都要创建一个条目，指向相应的右值、相应的顶部值和相应的底部值。
要进行搜索，您必须检查点的x值与左值的值。如果所有左值都不匹配，意味着它们大于您的x值，则知道该点在任何矩形外。否则，您将检查x值是否与相应左值的右值匹配。同样，如果所有右值都不匹配，则说明您在外面。否则，与顶部和底部值相同。一旦找到匹配的底部值，就知道您在任何矩形内部，并且完成了检查。
如我在下面的评论中所述，有很多优化的空间，例如最小的左值和顶部值以及最大的右值和底部值，可以快速检查是否在外面。
以下方法使用C#编写，并需要适应您偏好的语言:
public class RectangleUnion
{
private readonly Dictionary<int, Dictionary<int, Dictionary<int, HashSet<int>>>> coordinates =
new Dictionary<int, Dictionary<int, Dictionary<int, HashSet<int>>>>();
public void Add(Rectangle rect)
{
Dictionary<int, Dictionary<int, HashSet<int>>> verticalMap;
if (coordinates.TryGetValue(rect.Left, out verticalMap))
AddVertical(rect, verticalMap);
else
coordinates.Add(rect.Left, CreateVerticalMap(rect));
}
public bool IsInUnion(Point point)
{
foreach (var left in coordinates)
{
if (point.X < left.Key) continue;
foreach (var right in left.Value)
{
if (right.Key < point.X) continue;
foreach (var top in right.Value)
{
if (point.Y < top.Key) continue;
foreach (var bottom in top.Value)
{
if (point.Y > bottom) continue;
return true;
}
}
}
}
return false;
}
private static void AddVertical(Rectangle rect,
IDictionary<int, Dictionary<int, HashSet<int>>> verticalMap)
{
Dictionary<int, HashSet<int>> bottomMap;
if (verticalMap.TryGetValue(rect.Right, out bottomMap))
AddBottom(rect, bottomMap);
else
verticalMap.Add(rect.Right, CreateBottomMap(rect));
}
private static void AddBottom(
Rectangle rect,
IDictionary<int, HashSet<int>> bottomMap)
{
HashSet<int> bottomList;
if (bottomMap.TryGetValue(rect.Top, out bottomList))
bottomList.Add(rect.Bottom);
else
bottomMap.Add(rect.Top, new HashSet<int> { rect.Bottom });
}
private static Dictionary<int, Dictionary<int, HashSet<int>>> CreateVerticalMap(
Rectangle rect)
{
var bottomMap = CreateBottomMap(rect);
return new Dictionary<int, Dictionary<int, HashSet<int>>>
{
{ rect.Right, bottomMap }
};
}
private static Dictionary<int, HashSet<int>> CreateBottomMap(Rectangle rect)
{
var bottomList = new HashSet<int> { rect.Bottom };
return new Dictionary<int, HashSet<int>>
{
{ rect.Top, bottomList }
};
}
}
这不是很美观，但应该能指引你朝正确的方向前进。
我最喜欢用于各种2D几何查询的算法是扫描线算法。它被广泛应用于CAD软件中，这可能是你的程序目的的猜测。
基本上，你需要按照X轴对所有点和多边形顶点（在你的情况下为所有4个矩形角）进行排序，并沿着X轴从一个点到下一个点前进。对于非曼哈顿几何图形，您还需要引入中间点，即线段交点。
数据结构是当前X位置处垂直线与点和多边形（矩形）边缘交点的平衡树，按Y方向排序。如果正确维护该结构，则可以很容易地确定当前X位置处的点是否包含在矩形内：只需检查相邻于该点的垂直边缘交点的Y方向。如果允许矩形重叠或具有矩形孔，则稍微复杂一些，但仍然非常快速。
N个点和M个矩形的总体复杂度为O（（N + M）* log（N + M））。实际上可以证明这是渐近最优的。