algorithm - 存储二维间隔的数据结构

Question

我正在尝试解决一个涉及巨大二维屏幕（40000 * 40000 点）的问题。有一些无效点，我得到了一个矩形窗口。适合矩形窗口的无效点左上角的所有点也都无效。

我需要构建一个支持以下操作的数据结构： 1）找出我必须处理的有效点数。2）查询某个点是否有效。

根据我的研究，我考虑过段/区间树，但我不能完全理解它们，而且不确定它们是否可以处理二维点。

谁能给我一些不错的文章/实现，详细描述可以实现上述操作的数据结构？

谢谢，罗希特

Answer 1

这是今年facebookhackercup的“坏点”问题。请参阅带有代码和解释的官方解决方案。

Answer 2

适合矩形窗口的无效点左上角的所有点也无效。

因此，如果 x1,y1 无效，并且 x2<=x1 且 y2<=y1，则 x2,y2 也无效。在这种情况下，我将存储定义点的有序列表，即每个无效矩形的右下角。您的列表可以这样排序x[i+1] > x[i]和y[i+1] < y[i]。如果您省略所有已被其他点暗示无效的点，则此方法有效。在这个有序列表上，您可以执行您的操作。

1）找出我必须处理的有效点数。

您可以遍历列表，并为每个点使用一个矩形条，这样两个这样的条就不会重叠。

2）查询某个点是否有效。

给定一个点xp,yp，您可以使用二进制搜索来定位一个定义点，这使得该点无效。如果x定义点的坐标太小，则必须在较高的位置查找，而如果y坐标太小，则应在较低的位置搜索。如果您发现两者都太小，则您知道该像素是有效的。否则，您会发现两个坐标都足够大，这意味着您给定的像素也是无效的。