在一个矩形算分 [英] Count points in a rectangle
问题描述
我有很多的2D点，我可以preprocess，我想回答这是以下形式的查询（亿元）：
I have lots (billions) of points in 2D which I can preprocess and I would like to answer queries which are of the following form:
鉴于所有四个角的矩形的，输出的点的数量的矩形内。
Given all four corners of a rectangle, output the number of points inside the rectangle.
的矩形可以在任何方向（意味着矩形的轴可定向在任何角度，不只是水平或垂直地）。
The rectangle can be at any orientation (meaning the axis of the rectangle can be oriented at any angle, not just horizontally or vertically).
有没有一种快速实用的算法呢？
Is there a fast practical algorithm for this?
更新。是否有任何数据结构来存储，它允许查询点可证明是在次线性时间？
Update. Is there any data structure to store the points which allows queries provably to be in sub-linear time?
更新II 看来，答案是一个坚定的不<一href="http://cstheory.stackexchange.com/questions/18293/can-we-perform-an-n-d-range-search-over-an-arbitrary-box-without-resorting-to-si">http://cstheory.stackexchange.com/questions/18293/can-we-perform-an-n-d-range-search-over-an-arbitrary-box-without-resorting-to-si.接受最流行的答案在任何情况下。
Update II Seems the answer is a firm no http://cstheory.stackexchange.com/questions/18293/can-we-perform-an-n-d-range-search-over-an-arbitrary-box-without-resorting-to-si. Accepting the most popular answer in any case.
推荐答案
再present点为 kd树
Represent the points as a k-d tree.
然后，做一个查询：
-
当前节点=根
Current node = the root
目前面积=当前节点的区域（可以计算保留曲目/为你递归下降树）
Current area = the area of the current node (can be kept track of / calculated as you recurse down the tree)
如果当前区域的矩形内完全包含加点，该节点的孩子数（+1当前节点）。
If current area is completely contained inside the rectangle, add the number of points this node has as children (+1 for the current node).
如果当前区域是完全不在矩形内，什么也不做。
If current area is completely outside inside the rectangle, do nothing.
如果当前区域部分包含内部矩形：
If current area is partially contained inside rectangle:
- 添加当前节点的点，如果它被包含在矩形。
- 从2.两个孩子重复。
计算的区域或点是否包含在一个矩形应该足够简单。
Calculating whether an area or point is contained in a rectangle should be simple enough.
这篇关于在一个矩形算分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
