• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Finding the Rectangle Bounding the Largest Number of Points

 
Alec Lee
Ranch Hand
Posts: 569
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 34071
331
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 8898
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1263
10
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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....




 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic