Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Finding the Rectangle Bounding the Largest Number of Points

Alec Lee
Ranch Hand
Posts: 569
This is more a general computer science question than java question. But the solution is to be implemented in java, so I post it here.

Given a set of points (x1,y1), (x2,y2), .., (xn,yn) (well represented as List<java.awt.Point> to make it java related) , how do we find a bounding rectangle (well again represented by java.awt.Rectangle to make it java related) of fixed size that contains the largest number of points. The coordinates are all integers and from a fixed range e.g. say 0 - 100

My current solution is to generate rectangles around the proximity of each point and count the number of points each generated rectangle is bounding. Is there a better solution?

(btw, it is a game related program, not my assignment. I need to find the point where my character can attack the largest number of monsters)

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 35095
380
Alec,
Did you know we have a forum on game development? I think this fits in that forum better than Java in General so I'll move it for you.

Fred Hamilton
Ranch Hand
Posts: 684
It's an interesting question. I assume the points are randomly distributed? Then I can't really imagine a special algorithm, just a lot of brute force calculations.

There are statistical formulas for this sort of thing. You might try iterating through your array, and for each point calculating the sum of the distances from that point to each of the other points. There should be one point for which that calculation is minimized.

You might also try some kind of recursive algorithm, where you start ny dividing your screen into sections, then choosing the section that has the most points and repeating the process.

Just a couple of ideas that might work

The formula for the distance between two points is based on Pythagorus Theorum.

But I'm a little puzzled. Are you not in control of your shooter? In which case I can't see how you can beat quick visual scrutiny followed by a well placed mouse click.

Bert Bates
author
Sheriff
Posts: 8900
5
I had a similar problem. This idea probably isn't the best, but it was good enough for my application...

- Put all the points into a 2d array (probably sparsely filled). This array represents a cartesian graph of the occupied points.
- Iterate thru the array doing this:
- whenever an occupied point is found, increment its value by, say 10, and increment the values of all the points within, say, 5 points (in all directions), of the found point by 10.

- If you were then to do a 3d graph of your 2d array, you'd see "hills" and "valleys" in the array, and presumably the highest hill would be in the center of the the greatest concentration of occupied points...

Does that make sense?

salvin francis
Bartender
Posts: 1320
10
It looks like a clustering algorithm to me except for the fact that the shape of the cluster is not circular...

here is one that I had recalled from my college days....