View Javadoc

1   package cz.cuni.amis.pogamut.defcon.utils.quadtree;
2   
3   import java.util.Iterator;
4   import java.util.LinkedList;
5   import java.util.List;
6   
7   import cz.cuni.amis.pogamut.base3d.worldview.object.Location;
8   
9   /**
10   * QuadTree implementation. Made iterable for convenience. The order of
11   * evaluation is prefix with [ ul, ur, ll, lr ] as the order of nodes.
12   * 
13   * @author Radek 'Black_Hand' Pibil
14   * 
15   */
16  public class QuadTree implements Iterable<QuadTreeNode> {
17  
18  	private QuadTreeNode root;
19  
20  	/**
21  	 * Constructor
22  	 * 
23  	 * @param vertices
24  	 *            polygon to be represented by the QuadTree.
25  	 */
26  	@SuppressWarnings("unchecked")
27  	public QuadTree(List<? extends Location> vertices) {
28  
29  		double min_x = Double.MAX_VALUE, max_x = -min_x;
30  		double min_y = Double.MAX_VALUE, max_y = -min_y;
31  
32  		for (Location vertex : vertices) {
33  			if (vertex.getX() < min_x)
34  				min_x = vertex.getX();
35  			if (vertex.getX() > max_x)
36  				max_x = vertex.getX();
37  			if (vertex.getY() < min_y)
38  				min_y = vertex.getY();
39  			if (vertex.getY() > max_y)
40  				max_y = vertex.getY();
41  		}
42  		min_x -= 1d;
43  		min_y -= 1d;
44  		max_x += 1d;
45  		max_y += 1d;
46  
47  		double diffx = max_x - min_x;
48  		double diffy = max_y - min_y;
49  
50  		if (diffx > diffy) {
51  			max_y = min_y + diffx;
52  		} else {
53  			max_x = min_x + diffy;
54  		}
55  
56  		LinkedList<List<Location>> vrts = new LinkedList<List<Location>>();
57  		vrts.add((List<Location>) vertices);
58  
59  		root = new QuadTreeNode(this, min_x, min_y, max_x, max_y, null, vrts);
60  	}
61  
62  	/**
63  	 * Retrieves the root node.
64  	 * 
65  	 * @return root node
66  	 */
67  	public final QuadTreeNode getRoot() {
68  		return root;
69  	}
70  	
71  	@Override
72  	public String toString() {
73  		StringBuilder builder = new StringBuilder();
74  
75  		builder.append(String.format("QuadTree: [\n%s\n]", root.toString()));
76  		
77  		return builder.toString();
78  	}
79  
80  	/**
81  	 * Returns the iterator over QuadTree. The order of evaluation is prefix
82  	 * with [ ul, ur, ll, lr ] as the order of nodes.
83  	 */
84  	@Override
85  	public Iterator<QuadTreeNode> iterator() {
86  		return new QuadTreePostorderIterator(this);
87  	}
88  }