# A simple problem: Growing a square in a cloud of points

This topic is 2483 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've encountered a problem in a 2d game I'm working on right now that seems super simple, but I can't seem to find an optimal solution for it. I want to have a box that's as large as possible, which contains a single point (let's assume the middle) but does not contain any other points. A drawing here

I need the solution to keep it a square, and while I don't need global optimality, I do need the edge to go right up to the points. Any thoughts? I haven't had much sleep..so maybe my brain just isn't working and it's actually a really easy problem...

##### Share on other sites
And in case you're curious, here's the dev blog for the game.

##### Share on other sites
Does the box need to be axis-aligned or oriented?

-Josh

##### Share on other sites
Get the farthest point relative to the center point on both x and y axis and resize the rectangle to those values?

##### Share on other sites

Does the box need to be axis-aligned or oriented?

Yes, it needs to be axis-aligned. Not sure if oriented would be any easier...?

Get the farthest point relative to the center point on both x and y axis and resize the rectangle to those values?

I need the square to NOT contain any of the points (except for the center one, to avoid the trivial solution where you just put the square outside the point cloud).

##### Share on other sites
Then just get the closest one on both x and y axis

##### Share on other sites

[quote name='jjd' timestamp='1328793072' post='4911282']
Does the box need to be axis-aligned or oriented?

Yes, it needs to be axis-aligned. Not sure if oriented would be any easier...?

[/quote]

Oriented would be harder. You can get at axis-aligned solution by just finding the point with the minimum distance in the x or y direction from your central point. This will define the half-width of the square.

-Josh

##### Share on other sites
I don't need the square to actually be centered about the central point. So it should be allowed to move around, as long as it still contains the central point.

Furthermore, unless I'm misunderstanding your suggestion, I don't see how that would work for my drawing here: http://www.makeitsha...om/drawing/8753 The minimum distance point from the red center would be the black point furthest to the right - it is closest to the center in the Y direction, and using that distance would make the square too small. I also assume you don't mean the Euclidian distance, as that would make the square too big. Am I misunderstanding?

EDIT: Hmm I think for the fixed-center case, you can split up the points into 4 regions delineated by the 2 diagonals of the square. So all points in the "top" and "bottom" regions, you consider their "grow distance" to be the Y distance to the center, and for the "left" and "right" region you consider it the X distance. Then, you can find the point with the minimum "grow distance" and use that as your half-width.

Still thinking about the movable case..perhaps applying this iteratively would work...

Thanks for taking the time to reply!

##### Share on other sites
After some digging, it is similar although not quite this problem here: http://chaoxuprime.com/2011/02/an-open-problem-axis-aligned-rectangle-packing-density

Humm...I hope this doesn't end up being some NP-complete or high-order polynomial algorithm where I have to brute force it (ie. try placing edges at every point and enumerating..??)...

##### Share on other sites
I can only think of a way to make centered square. Not sure how correct it'll be.

1. Loop through all points and find lowest distance between center point and other points;
2. Create centered square in such way that the closest point would be on the line;
3. Test whether you have any extra points inside (extra test), and make square smaller by penetration distance.

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633654
• Total Posts
3013168
×