我的问题是内：测距点区域
我们在2D空间，每个具有权重的一组N点。鉴于任何矩形区域R，如何有效返回R内最大重量的点？
请注意，所有查询区域R具有相同的形状，即相同的长度和宽度。点和矩形坐标是浮点数。
我最初的想法是使用一个R树来存储点。对于一个区域R，提取R所有的点，然后找到最高点。权重。时间复杂度为O(logN + V)，其中V是R点数。我们可以做得更好吗？
我试图寻找解决方案，但仍然没有成功。任何建议？
感谢，
这听起来像在2D范围最大的查询问题。你有一些非常好的算法here。
更简单的是只使用2D segment tree。
基本上，你的段树的每个节点都将存储体2D的区域，而不是一维区间。因此每个节点将有4个子节点，减少到四叉树，然后您可以像经典分段树一样操作。这在here中有详细描述。
这将是O(log n)每个查询，其中n是总点数。它还可以让你做更多的操作，比如更新一个点的权重，更新一个地区的权重等。
@ IVlad：如果坐标是浮点数而不是整数，它是否工作？ – Arnold
@ user2210078在这种情况下，它也应该可以适应它的工作。例如，如果你有'n'个点，将它们标准化，所以它们的坐标是'[1，n]'中的整数。对于点1.4,3.4,5.6'，你可以对它们进行排序，并按排序顺序将它们替换为它们的索引，从而产生'1,2,3'。对于'x，y'查询，您可以在这个排序顺序中找到'x，y'位置。对于上述情况，“2.5,5”查询将导致“2,2”查询。我认为这应该也适用于2d。我不知道一个算法处理浮动的性质。 – IVlad
如果您可以承受增加的内存，您也可以将所有的坐标乘以10，使其与您关心的许多小数位数相乘，然后得到整数坐标。 – IVlad
如何为每个树节点添加一个额外的属性，其中包含所有点的最大权重任何一个孩子。
这将是很容易，同时增加点进行更新。当您移除一个可以改变最大值的点时，保持一点点工作。您必须向后遍历树并更新所有父节点的最大值。
使用此属性，如果要检索最大权重点，那么当您使用查询区域查询树时，只会在遍历树时检查具有最大权重的子节点。请注意，您可能有多个具有相同最大重量的点，因此您可能有多个子节点需要检查。
只有使用最大权重属性检查子节点才能提高查询吞吐量，但会增加内存和构建/修改树的时间。
查找所谓的范围树，在你的情况下，你会想要在二维实现。在所得到的树中的节点之一，这将是，在这里首先基于分割点的集合的2层“的树树” x坐标，然后对每个组的X点，则构建基于树在原始树中该节点上的那些点的y坐标上。您可以查看如何修改二维范围树以返回O（（log n）^ 2）时间内查询矩形中的点数，与点数无关。同样，不是将子矩形的点数存储在范围树中，而是可以存储该矩形内点的最大目标值。无论查询矩形中的点数如何，这将为您提供O（n log n）时间保证存储和构建时间以及O（（log n）^ 2）查询时间。
范围树“找到查询矩形中的所有点”的所谓“小数级联”的改编可能甚至能够使您的查询时间缩短到O（log n），但我不确定，因为您正在查询矩形内的点的最大值。
提示：
每个点具有“影响区”，它是矩形，使得该点支配（的左上角）的位置的轨迹。影响区域的集合定义了飞机的一个分区。分区的每条边都出现在给定点的横坐标[纵坐标]或其横坐标[纵坐标]减去查询区域的宽度[高度]。
如果将坐标值映射到它们的等级（通过在两个轴上排序），则可以将分区表示为尺寸为4N²的数字图像。为了预先计算这个图像，用负无穷初始化它，并且为每个点用它的权重填充它的影响区域，取最大值。如果查询窗口大小平均为R²像素，则构建图像的成本为NR²。
通过查找相关像素的行和列并返回像素值来进行查询。这需要两次二分搜索，时间为Lg(N)。
这种方法仅适用于中等数值的N（比如说最高为1000）。通过研究分区图的几何形状可以更好地了解这个问题。
你可以尝试一个加权voronoi图，当正面权重从euklidian距离减去。体重较重的地方往往会有大的细胞，而附近的地方体重很小。然后按照网站的数量对网格进行排序，并计算每个网格的最小边界框。将其与矩形搜索框匹配。
会[quadtree]（https://en.wikipedia.org/wiki/Quadtree）帮助吗？ –
如果R内点的权重是随机分布的，那么你必须检查矩形内的每个点。顺便说一句，你想要一个检查算法或实现？ SO主要是一种编码资源。 –
到目前为止您尝试了哪种搜索？我认为一个“扫描线”算法可能在这里工作 – bro