Jump to content
  • Advertisement
Sign in to follow this  
stevesan

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!