File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Game Development and the fly likes Finding the Rectangle Bounding the Largest Number of Points Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Game Development
Bookmark "Finding the Rectangle Bounding the Largest Number of Points" Watch "Finding the Rectangle Bounding the Largest Number of Points" New topic

Finding the Rectangle Bounding the Largest Number of Points

Alec Lee
Ranch Hand

Joined: Jan 28, 2004
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

Joined: May 26, 2003
Posts: 33102

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.

[OCA 8 book] [Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
Fred Hamilton
Ranch Hand

Joined: May 13, 2009
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

Joined: Oct 14, 2002
Posts: 8898
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?

Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
salvin francis
Ranch Hand

Joined: Jan 12, 2009
Posts: 1108

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....

I agree. Here's the better link:

I agree. Here's the link:
subject: Finding the Rectangle Bounding the Largest Number of Points
It's not a secret anymore!