使用四叉树获取边界圈内的所有点 [英] Using a QuadTree to get all points within a bounding circle

问题描述

我有一组100到200点（x，y）。我必须检查哪些落在其他人的特定距离内。整个程序的特定距离是固定的，例如50.说点1落在5,7,25,90,96,105点等等的范围内。类似地，点2在23,45的范围内，等等...
存储通过x，y坐标定位的对象

这里提供了QuadTree，但可用于获取边界矩形内的所有点。但是如何在边界圈内获得所有分数？有一种方法可以在最大距离内返回一个最接近纬度/长度的点，但是如何获取距离内的所有点？
http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree（float，float，float，float，int ）

一种方法可能是从树中删除每个点，因为我得到它，然后再次查询最接近的点，直到我变为null。这是唯一的方法吗？

解决方案

假设你有一个圆圈以（x，y）为中心，半径为r，找到圆圈中的四叉树中的所有点。一个想法如下：

1. 构造刻有圆的边界框。这是包含圆的最小矩形，它具有左上角（x-r，y-r）和右下角（x + r，y + r）。圆圈中的任何一个点也必须在正方形中，而不是其他方向。




2. 查询四边形中位于该矩形中的点。让这些点为P。




3. 对于已知在矩形中的P中的每个点，查看它是否也在圆圈中。您可以通过检查从该点到（x，y）的距离是否不大于r来做到这一点。换句话说，给出一个点（x ₀ ，y ₀ ），你将计算（x-x ₀ ） ² +（y-y <0> ） ² ，如果该值小于或等于r ^{2，那么该点包含在圈子中。}

虽然这看起来效率似乎不高，但实际上相当快。正方形面积与圆面积之比为4 / pi;大约1.27。换句话说，假设您的积分分布均匀，您只能找到比您需要的点多27％。

I have a set of 100 to 200 points (x,y). I have to check which ones fall within a particular distance of the others. The particular distance is fixed for the entire program, say 50. Say point 1 falls within the range of points 5,7,25,90,96,105...etc. Similarly point 2 falls within range of 23,45, etc... Storing objects for locating by x,y coordinates

Here QuadTree is suggested, but it can be used to get all the points within a bounding rectangle. But how to get all points within a bounding circle? there is a method which returns a point closest to a lat/long within a maximum distance, but how to get all the points within the distance? http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float, float, float, float, int)

one way maybe to remove each point from the tree as I get it, then query for the closest point again, until i get null. is that the only way?

解决方案

Suppose that you have a circle centered at (x, y) with radius r and want to find all points in a quadtree that are in the circle. One idea is as follows:

1. Construct the bounding box inscribing the circle. This is the smallest rectangle containing the circle, which has upper-left corner (x - r, y - r) and lower-right corner (x + r, y + r). Any point in the circle must also be in the square, but not the other way around.

2. Query the quadtree for the set of points lying in that rectangle. Let these points be P.

3. For each point in P which is known to be in the rectangle, see if it is also in the circle. You can do this by checking whether the distance from that point to (x, y) is no greater than r. In other words, given a point (x₀, y₀), you would compute (x - x₀)² + (y - y₀)², and if this value is less than or equal to r², then the point is contained in the circle.

Although this may seem inefficient, it's actually quite fast. The ratio of the area of the square to the area of the circle is 4 / π ≈ 1.27. In other words, assuming that your points are distributed somewhat evenly, you'll only find about 27% more points than you need to.

这篇关于使用四叉树获取边界圈内的所有点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！