采用四叉树得到的边界圆圈内的所有点 [英] 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，等等。 <一href="http://stackoverflow.com/questions/132319/storing-objects-for-locating-by-x-y-coordinates">Storing用X定位对象，y坐标

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

下面四叉树建议，但它可以被用来获得一个矩形边框中的所有点。可是如何才能让边界圆圈内的所有点？有返回最接近点到纬度/经度的最大距离内的方法，但如何让距离内的所有点？ <一href="http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree%28float,%20float,%20float,%20float,%20int%29">http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float,浮球，浮球，浮球，INT）

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?

推荐答案

假设你有集中在一个圆圈（X，Y），半径为r，并希望找到一个四叉树是在圈子里的所有问题。一种想法是如下：

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. 构建边框内接圆。这是包含圆，其具有左上角的最小矩形（X - R，Y - r）和右下角（X + R，Y + R）。任何点在圈内也必须是在广场上，而不是周围的其他方式。

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.

查询四叉树的集合点，位在矩形的。让这些点为P。

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

有关在P中的每个点被称为是在矩形，看它是否也是在圆。可以通过检查从该点到（x，y）处的距离是否不除R更大做到这一点。换句话说，给定一个点（x <子> 0 ，Y <子> 0 ），你会计算（X - X <子> 0 ） ² +（Y - 是<子> 0 ） ² ，并且如果该值小于等于r ² ，则该点是包含在圈子。

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.

虽然似乎效率不高，它实际上是相当快的。正方形的面积与圆的面积的比例为4 /＆圆周率;与约; 1.27。换句话说，假设你点分布均匀几分，你会发现只有约27％的百分点，比你需要。

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屋！