rtree.java

一个java实现的R树

     * @return An Enumeration containing all tree nodes in the correct order.
     */
    public Enumeration traversePreOrder() {
	class PreOrderEnum implements Enumeration {
	    private boolean hasNext = true;

	    private Vector nodes;

	    private int index = 0;

	    public PreOrderEnum() {
		AbstractNode root = file.readNode(0);
		nodes = traversePreOrder(root);
	    }

	    public boolean hasMoreElements() {
		return hasNext;
	    }

	    public Object nextElement() {
		if (! hasNext) {
		    throw new NoSuchElementException("traversePreOrder");
		}

		Object n = nodes.elementAt(index);
		index++;
		if (index == nodes.size()) {
		    hasNext = false;
		}
		return n;
	    }
	};

	return new PreOrderEnum();
    }
    
    /**
     * Returns a Vector with all nodes that intersect with the given HyperCube.
     * The nodes are returned in post order traversing
     *
     * @param h The given HyperCube that is tested for overlapping.
     * @param root The node where the search should begin.
     * @return A Vector containing the appropriate nodes in the correct order.
     */
    public Vector intersection(HyperCube h, AbstractNode root) {
	if (h == null || root == null) {
	    throw new IllegalArgumentException("Arguments cannot be null.");
	}

	if (h.getDimension() != file.dimension) {
	    throw new IllegalArgumentException("HyperCube dimension different than RTree dimension.");
	}

	Vector v = new Vector();
	
	if (root.getNodeMbb().intersection(h)) {
	    v.addElement(root);

	    if (!root.isLeaf()) {
		for (int i = 0; i < root.usedSpace; i++) {
		    if (root.data[i].intersection(h)) {
			Vector a = intersection(h, ((Index) root).getChild(i));
			for (int j = 0; j < a.size(); j++) {
			    v.addElement(a.elementAt(j));
			}
		    }
		}
	    }
	}
	return v;
    }

    /**
     * Returns an Enumeration with all nodes present in the tree that intersect with the given
     * HyperCube. The nodes are returned in post order traversing
     *
     * @param h The given HyperCube that is tested for overlapping.
     * @return An Enumeration containing the appropriate nodes in the correct order.
     */
    public Enumeration intersection(HyperCube h) {
	class IntersectionEnum implements Enumeration {
	    private boolean hasNext = true;

	    private Vector nodes;

	    private int index = 0;

	    public IntersectionEnum(HyperCube hh) {
		nodes = intersection(hh, file.readNode(0));
		if (nodes.isEmpty()) {
		    hasNext = false;
		}
	    }

	    public boolean hasMoreElements() {
		return hasNext;
	    }
	    
	    public Object nextElement() {
		if (! hasNext) {
		    throw new NoSuchElementException("intersection");
		}

		Object c = nodes.elementAt(index);
		index++;
		if (index == nodes.size()) {
		    hasNext = false;
		}
		return c;
	    }
	};

	return new IntersectionEnum(h);
    }

    /**
     * Returns a Vector with all Hypercubes that completely contain HyperCube <B>h</B>.
     * The HyperCubes are returned in post order traversing, according to the Nodes where
     * they belong.
     *
     * @param h The given HyperCube.
     * @param root The node where the search should begin.
     * @return A Vector containing the appropriate HyperCubes in the correct order.
     */
    public Vector enclosure(HyperCube h, AbstractNode root) {
	if (h == null || root == null) throw new
	    IllegalArgumentException("Arguments cannot be null.");

	if (h.getDimension() != file.dimension) throw new
	    IllegalArgumentException("HyperCube dimension different than RTree dimension.");

	Vector v = new Vector();

	if (root.getNodeMbb().enclosure(h)) {
	    v.addElement(root);

	    if (!root.isLeaf()) {
		for (int i = 0; i < root.usedSpace; i++) {
		    if (root.data[i].enclosure(h)) {
			Vector a = enclosure(h, ((Index) root).getChild(i));
			for (int j = 0; j < a.size(); j++) {
			    v.addElement(a.elementAt(j));
			}
		    }
		}
	    }
	}
	return v;
    }

    /**
     * Returns an Enumeration with all Hypercubes present in the tree that contain the given
     * HyperCube. The HyperCubes are returned in post order traversing, according to the Nodes where
     * they belong.
     *
     * @param h The given HyperCube.
     * @param root The node where the search should begin.
     * @return An Enumeration containing the appropriate HyperCubes in the correct order.
     */
    public Enumeration enclosure(HyperCube h) {
	class ContainEnum implements Enumeration {
	    private boolean hasNext = true;

	    private Vector cubes;

	    private int index = 0;

	    public ContainEnum(HyperCube hh) {
		cubes = enclosure(hh, file.readNode(0));
		if (cubes.isEmpty()) {
		    hasNext = false;
		}
	    }

	    public boolean hasMoreElements() {
		return hasNext;
	    }
	    
	    public Object nextElement() {
		if (!hasNext) throw new
		    NoSuchElementException("enclosure");

		Object c = cubes.elementAt(index);
		index++;
		if (index == cubes.size()) {
		    hasNext = false;
		}
		return c;
	    }
	};

	return new ContainEnum(h);
    }

    /**
     * Returns a Vector with all Hypercubes that completely contain point <B>p</B>.
     * The HyperCubes are returned in post order traversing, according to the Nodes where
     * they belong.
     *
     * @param p The given point.
     * @param root The node where the search should begin.
     * @return A Vector containing the appropriate HyperCubes in the correct order.
     */
    public Vector enclosure(Point p, AbstractNode root) {
	return enclosure(new HyperCube(p, p), root);
    }

    /**
     * Returns an Enumeration with all Hypercubes present in the tree that contain the given
     * point. The HyperCubes are returned in post order traversing, according to the Nodes where
     * they belong.
     *
     * @param p The query point.
     * @param root The node where the search should begin.
     * @return An Enumeration containing the appropriate HyperCubes in the correct order.
     */
    public Enumeration enclosure(Point p) {
	return enclosure(new HyperCube(p, p));
    }

    /**
     * Returns the nearest HyperCube to the given point.
     * [King Lum Cheung and Ada Wai-chee Fu: Enhanced Nearest Neighbor Search on the R-Tree]
     *
     * @param p The query point.
     * @return A vector containing all the nodes lying in the search path until the nearest hypercube
     *         is found. Elements are instances of AbstractNode and Data classes. The last Data instance
     *         in the vector is the answer to the query.
     */
    public Vector nearestNeighbor(Point p) {
	return nearestNeighborSearch(file.readNode(0), p, Float.POSITIVE_INFINITY);
    }

    /**
     * Used for nearest neighbor recursive search into the RTree structure. <B>n</B> is the current
     * node of the active branch list, searched. <B>p</B> is the query point. <B>nearest</B> is the 
     * distance of <B>p</B> from current nearest hypercube <B>h</B>.
     */
    protected Vector nearestNeighborSearch(AbstractNode n, Point p, float nearest) {
	Vector ret = new Vector();
	HyperCube h;

	if (n.isLeaf()) {
	    for (int i = 0; i < n.usedSpace; i++) {
		float dist = n.data[i].getMinDist(p);
		if (dist < nearest) {
		    h = n.data[i];
		    nearest = dist;
		    ret.addElement(new Data(h, n.branches[i], n.pageNumber, i));
		}
	    }
	    return ret;
	} else {
	    // generate Active Branch List.
	    class ABLNode {
		AbstractNode node;
		float minDist;

		public ABLNode(AbstractNode node, float minDist) {
		    this.node = node;
		    this.minDist = minDist;
		}
	    }

	    ABLNode[] abl = new ABLNode[n.usedSpace];

	    for (int i = 0; i < n.usedSpace; i++) {
		AbstractNode ch = ((Index) n).getChild(i);
		abl[i] = new ABLNode(ch , ch.getNodeMbb().getMinDist(p));
	    }

	    // sort ABL in ascending order of MINDIST from the query point.
	    Sort.mergeSort(
		abl,
		new Comparator() {
			public int compare(Object o1, Object o2) {
			    float f = ((ABLNode) o1).minDist - 
				        ((ABLNode) o2).minDist;

			    // do not round the float here. It is wrong!
			    if (f > 0) return 1;
			    else if (f < 0) return -1;
			    else  return 0;
			}
		}
	    );

	    // traverse all ABL nodes and prune irrelevant nodes according to the MINDIST heuristic.
	    for (int i = 0; i < abl.length; i++) {
		if (abl[i].minDist <= nearest) {
		    // add node in the results vector, if it complies to the MINDIST heuristic.
		    ret.addElement(abl[i].node);
		    // recursively continue the search.
		    Vector v = nearestNeighborSearch(abl[i].node, p, nearest);

		    // find the new nearest distance and add all the nodes accessed, into the current 
		    // results vector.
		    try {
			Object o = v.lastElement();
			if (o instanceof AbstractNode) {
			    for (int j = 0; j < v.size(); j++) {
				ret.addElement(v.elementAt(j));
			    }
			    AbstractNode an = (AbstractNode) o;
			    h = (HyperCube) an.getNodeMbb();
			    nearest = h.getMinDist(p);
			} else if (o instanceof Data) {
			    // if the current node searched was a leaf, than the resulting set definetly
			    // contains just one HyperCube, the nearest to the query point.
			    h = ((Data) o).mbb;
			    nearest = h.getMinDist(p);
			    ret.addElement(o);
			}
		    } catch (NoSuchElementException e) {
			// no nearest node or hypercube was found from this recursion step. Leave nearest
			// distance intact.
		    }
		}
	    }

	    return ret;
	}
    }

    public static void main(String[] args) {
	//PersistantPageFile file = new PersistantPageFile("c:/temp/rtree.dat");
	CachedPersistentPageFile file = new CachedPersistentPageFile("c:/temp/rtree.dat", 3);
	//MemoryPageFile file = new MemoryPageFile();
	RTree r = new RTree(2, 0.4f, 3, file, RTree.RTREE_QUADRATIC);
	//RTree r = new RTree(file);
	float[] f = {10, 20, 40, 70,
		     30, 10, 70, 15,
		     100, 70, 110, 80,
		     0, 50, 30, 55,
		     13, 21, 54, 78,
		     3, 8, 23, 34,
		     200, 29, 202, 50,
		     34, 1, 35, 1,
		     201, 200, 234, 203,
		     56, 69, 58, 70,
		     12, 67, 70, 102,
		     1, 10, 10, 20
	};

	for (int i = 0; i < f.length;) {
	    Point p1 = new Point(new float[] {f[i++],f[i++]});
	    Point p2 = new Point(new float[] {f[i++],f[i++]});
	    final HyperCube h = new HyperCube(p1, p2);
	    r.insert(h, -2);
	}

	for (Enumeration e = r.traverseByLevel(); e.hasMoreElements();) {
	    System.out.println(e.nextElement());
	}

	/*
	HyperCube h = new HyperCube(new Point(new float[] {10, 15}), new Point(new float[] {23, 24}));

	for (Enumeration e = r.intersection(h); e.hasMoreElements();) {
	    System.out.println(e.nextElement());
	}

	Point p = new Point(new float[] {112, 75});
	System.out.print("Nearest to " + p + " is ");
	System.out.println(r.nearestNeighbor(p));
	*/
    }

} // RTree