• +86-156-1535-0639
  • jianpengqi@126.com

利用PRTree形成正方形区域粗略提取内切圆的数据

  • QI-Jianpeng

相关介绍

PRTree is an implementation of a priority R-Tree, a spatial index. The code is written in java and the jar file is very small, this package does not come with anything extra.
This implementation tries to be memory efficient, one of the things it does it that it does not force you to create an Box or MBR for each object you have in the tree. You provide a class that can provide the bounds of each object when it is needed. This means that you can control how caching of bounds is done.

以上内容引自:PRTree, a Priority R-Tree, a spatial index for java code

使用正方形区域进行数据提取的思路及方法

在PRTree中并没有提供给定一个点,给定一个半径来过滤所形成的圆形区域数据的方法,但是我们可以采用一个替代的形成正方形的方法来实现,大体的思路如图:

思路示例图

假设我们给的点是center , 而我们想要以center为中心 radius 为半径的圆形区域的数据。
这是很难实现的,本思路采用以blur两个边界点所围成的正方形区域的方法来进行过滤。
根据所提供的半径radius以及center,我们可以很方便的计算出两个边界点的位置,即:bl(centerX-radius,centerY-radius),up(centerX+radius,centerY+radius).
再根据PRTree提供的方法find()函数,可以得到最终的结果。

以下给出关键的测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
@Test
public void testRectangle(){
PRTree<Point> tree =
new PRTree<> (this.converter, 30);
List<Point> list = new ArrayList<Point>();
list.add( new Point(1,1.0,1.0));
list.add( new Point(2,2.0,2.0));
list.add( new Point(3,3.0,3.0));
list.add( new Point(4,4.0,4.0));
list.add( new Point(5,2.0,3.0));
list.add( new Point(6,2.0,4.0));
list.add( new Point(7,1.0,3.0));
//loading data
tree.load (list);
/**
* Iterable<T> find(double xmin, double ymin, double xmax, double ymax)
* Find all objects that intersect the given rectangle.
*/
double centerX = 1.0;
double centerY = 1.0;
double radius = 1.0;
Point bottomLeft = calcBLBound(centerX, centerY, radius);
Point upperRight = calcURBound(centerX, centerY, radius);
Iterator<Point> pointsIter = tree.find(bottomLeft.getX(), bottomLeft.getY(), upperRight.getX(), upperRight.getY()).iterator();
while(pointsIter.hasNext()){
Point point = pointsIter.next();
System.out.println(point.getPid()+"\t"+"("+point.getX()+" , "+point.getY()+")");
}
/**
* void find(double xmin, double ymin, double xmax, double ymax, List<T> resultNodes)
* Finds all objects that intersect the given rectangle and stores the found node in the given list.
*/
System.out.println("-------");
List<Point> resultNodes = new ArrayList<Point>();
tree.find(bottomLeft.getX(), bottomLeft.getY(), upperRight.getX(), upperRight.getY(), resultNodes);
for(Point p: resultNodes){
System.out.println(p.getPid()+"\t"+"("+p.getX()+" , "+p.getY()+")");
}
}
/**
* 计算左下角的点位置
* @param centerX
* @param centerY
* @param radius
* @return
*/
private Point calcBLBound(double centerX, double centerY, double radius){
return new Point(-1,centerX-radius,centerY-radius);
}
/**
* 计算右上角点的位置
* @param centerX
* @param centerY
* @param radius
* @return
*/
private Point calcURBound(double centerX, double centerY, double radius){
return new Point(-1,centerX+radius,centerY+radius);
}

数据

  • center: (1.0,1.0)
  • radius: 1.0
id x y
1 1.0 1.0
2 2.0 2.0
3 3.0 3.0
4 4.0 4.0
5 2.0 3.0
6 2.0 4.0
7 1.0 3.0

测试结果

Iterable<T> find(double xmin, double ymin, double xmax, double ymax)

2 (2.0 , 2.0)

1 (1.0 , 1.0)

void find(double xmin, double ymin, double xmax, double ymax, List<T> resultNodes)

1 (1.0 , 1.0)

2 (2.0 , 2.0)