Picking a Collection and Design for querying 1G Point objects

Hi everyone, any chance I could get some design tips?

I have one million Point objects where the x and y values are floats with 2 decimal places. These points exist somewhere between a top left corner of (0,0) and a bottom right corner(400,200).

When the user specifies a top left and bottom right Point(for a rectangle) (no slanted diaganol lines), I have to return all of my Point objects that are inside of the Rectangle specified by the user - in less than a second.

I tried making 2 TreeSets -- one ordered by X and one ordered by Y, where they both use the same Point objects, (I'm avoiding instantiating double the points). The 1st treeset is instantiated without problems, but when my application attempts instantiating the 2nd TreeSet, I get an out-of Heap memory exception. If that were to have worked correctly instead, I was planning on using the "subset" method in TreeSet to get all the Point objects in the user's selected X range, .. and then vice-versa on the "Y" treeset for the points matching the user's specified Y rectangle values,.. and then I could take the intersection of those two result lists to arrive at a list with the points inside the user's specified rectangle.

Tweaking the JVM memory is Not going to be an option.

Is there a different design I should be using?

Thanks so much

Using an array can be an efficient solution with memory and performance

See the code below which uses both Treeset and array.

import java.awt.Point;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Date;

import java.util.HashSet;

import java.util.Iterator;

import java.util.Random;

import java.util.Set;

import java.util.SortedSet;

import java.util.StringTokenizer;

import java.util.TreeSet;

class ABC {

public static final int TT_EOL = 10;

}

class TestSwitch {

public static void main(String args[]) {

System.out.println("Treeset *************");

treeSetOper();

System.out.println("Arry *************");

arrayOper();

}

public static void treeSetOper(){

TreeSet<Point> parray1 = new TreeSet<Point>(new XComparator());

TreeSet<Point> parray2 = new TreeSet<Point>(new YComparator());

for(int i = 0 ; i < 1000000 ; i++){

Random r1 = new Random();

Point p = new Point(r1.nextInt(40000),r1.nextInt(20000));

parray1.add(p);

}

Iterator<Point> i = parray1.iterator();

while(i.hasNext()){

Point p = i.next();

parray2.add(p);

}

Point inputTop = new Point(19980,9980);

Point inputBottom = new Point(20020,10020);

long before = System.currentTimeMillis();

SortedSet<Point> subsetx = parray1.subSet(new Point(19980,0), new Point(20020,20000));

SortedSet<Point> subsety = parray2.subSet(new Point(0,9980), new Point(40000,10020));

Set<Point> intersection = new HashSet<Point>(subsetx);

intersection.retainAll(subsety);

long after = System.currentTimeMillis();

System.out.println("Size : " + intersection.size());

System.out.println("Time : " + (after-before));

}

public static void arrayOper(){

long before = System.currentTimeMillis();

Point[] parray1 = new Point[1000000];

//Point[] parray2 = new Point[1000000];

for(int i = 0 ; i < 1000000 ; i++){

Random r1 = new Random();

Point p = new Point(r1.nextInt(40000),r1.nextInt(20000));

//Point p = new Point(1,1);

parray1[i]=p;

//parray2[i]=p;

}

//Arrays.sort(parray1,new XComparator());

//Arrays.sort(parray2,new YComparator());

Point inputTop = new Point(19980,9980);

Point inputBottom = new Point(20020,10020);

ArrayList<Point> intersection = new ArrayList<Point>();

for(int i = 0 ; i < 1000000 ; i++){

Point p = parray1[i];

if((p.x >=19980 && p.x <= 20020) && (p.y >=9980 && p.y <= 10020)){

intersection.add(p);

}

}

long after = System.currentTimeMillis();

System.out.println("Size : " + intersection.size());

System.out.println("Time : " + (after-before));

}

}

class XComparator implements Comparator<Point>{

public int compare(Point o1, Point o2) {

int retval = 0;

int x = o1.x-o2.x;

if(x < 0){

return -1;

}else if(x==0){

}else if(x>0){

return +1;

}

int y = o1.y-o2.y;

if(y < 0){

return -1;

}else if(y==0){

}else if(y>0){

return +1;

}

return retval;

}

}

class YComparator implements Comparator<Point>{

public int compare(Point o1, Point o2) {

int retval = 0;

int y = o1.y-o2.y;

if(y < 0){

return -1;

}else if(y==0){

}else if(y>0){

return +1;

}

int x = o1.x-o2.x;

if(x < 0){

return -1;

}else if(x==0){

}else if(x>0){

return +1;

}

return retval;

}

}