Editing Chase-san/RangeBucket2D

Robo Home | Changes | Preferences | AllPages

I developed this to increase the preformance of my traditional pattern matcher Pytko. It is not yet used (I have to retrieve its source). Basically this is the same as searching linearly however it culls off entirely unused sections like a grid. Its not as complex as a kd-tree or quadtree and doesn't have thier flair, but its simple and most of all, decently small (assuming you cull unused portions).

This code is free to use.

<pre>
package chase.util;

import java.awt.geom.*;
import java.util.*;

public class RangeBucket2D<K extends Point2D> {
	List<K> tree[][];
	double bucketX;
	double bucketY;
	Rectangle2D area;
	
	public RangeBucket2D(Rectangle2D range, int xbucket, int ybucket) {
		area = (Rectangle2D)range.clone();
		bucketX = range.getWidth()/(double)xbucket;
		bucketY = range.getHeight()/(double)ybucket;
		
		tree = new List[xbucket][ybucket];
	}
	
	private List<K> getNode(K p) {
		int x = (int)((p.getX()-area.getMinX())/bucketX);
		int y = (int)((p.getY()-area.getMinY())/bucketY);
		if(tree[x][y] == null) tree[x][y] = new ArrayList<K>();
		//System.out.println("["+x+","+y+"]");
		return tree[x][y];
	}
	
	public void add(K p) {
		if(area.contains(p)) {
			//System.out.print("(" + p.getX()+", "+p.getY()+") = ");
			getNode(p).add(p);
		}
		else System.out.println("Out of range");
	}
	
	public boolean contains(K p) {
		if(area.contains(p))
			return getNode(p).contains(p);
		return false;
	}
	
	public void remove(K p) {
		if(area.contains(p))
			getNode(p).remove(p);
	}
	
	public List<K> range(Rectangle2D range) {
		if(!area.contains(range)) return null;
		
		//top left node
		int xMin = (int)((range.getMinX()-area.getMinX())/bucketX);
		int yMin = (int)((range.getMinY()-area.getMinY())/bucketY);
		int xMax = (int)((range.getMaxX()-area.getMinX())/bucketX)+1;
		int yMax = (int)((range.getMaxY()-area.getMinY())/bucketY)+1;
		List<K> out = new ArrayList<K>();
		
		for(int x = xMin; x < xMax; x++) {
			for(int y = yMin; y < yMax; y++) {
				List<K> tmp = tree[x][y];
				for(int i=0; tmp != null && i < tmp.size(); i++) {
					K p = tmp.get(i);
					if(range.contains(p)) out.add(p);
				}
			}
		}
		return out;
	}
}
</pre>

Summary:
Consciousness check: 6 + 4 =
This change is a minor edit. Send email notification that Chase-san/RangeBucket2D has been changed.
(Visit Preferences to set your user name.)

View other revisions
Robo Home | Chase-san | Changes | Preferences | AllPages