# Finding the Rectangle Bounding the Largest Number of Points

Alec Lee

Ranch Hand

Posts: 569

posted 6 years ago

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)

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)

posted 6 years ago

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.

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] [OCP 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

Posts: 684

posted 6 years ago

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.

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

Sheriff

Posts: 8900

5

posted 6 years ago

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?

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