[ ADV Performance Tunning ] Witch rectangle has the Point ?

Posted 02 September 2012 - 09:02 AM

Hello there. Im new to this forums, this is my first post

Im searching for a way to solve a performance issue i have. Its pretty much like a challenge, and its pretty much simple in terms of 'how it works'.

I have a very huge list of awt.Rectangles, and i need to implement 2 simple methods for it. This it works, on the simplest way:

private List<Zone> set = new ArrayList<Zone>();
    
    public List<Rectangle> getApplicableZones(Point point) {
        List<Rectangle> zones = new ArrayList<Rectangle>();
        for(Rectangle z : set) {
            if(z.contains(point))
                zones.add(z);
        }
        return zones;
    }
    
    public List<Rectange> getIntersections(Rectangle rect) {
        List<Rectangle > list = new ArrayList<Rectangle>();
        for(Rectangle z : set) {
            if(z.intersects(rect))
                list.add(z);
        }
        return list;
    }

But this is not really efficient since i have around 4k Rectangles and its taking too long to process.
Ive tryed to implement a binary tree indexed by X and Y , it got a lil bit better but still not working.

There are some rules to make it simpler:
- You will never have 2 regions close to each other (having one max X = one minimum X)
- Rectangles perimeters NEVER overlaps.
- You will have at most 2 rectangles in a point, you will never have 3 rectangles in the same spot.

This is an image of something it would visually looks like: (attached)

This is for a very big game server im tunning, just cant tell the game