Sign in to follow this  
lephyrius

Algorithm for covering as much dots a as possible?

Recommended Posts

If I have a rectangle of random size and it has random dots in it.( = Rectangle A)

I want to take a rectangle that's inside A to cover as many dots as possible.

 

Is there any possible way of doing this without going bruteforce: iterating through all the dots and use them as a corner of the rectangle only saving the one with most dots in it?

Edited by lephyrius

Share this post


Link to post
Share on other sites

I want to take a rectangle that's inside A to cover as many dots as possible.

 

Wouldn't by any chance be a homework assignment? If so, that's greatly discouraged. If not, you may get better answers if you describe how the rectangle will be used.

 

In any case, you haven't provided enough information. Must the rect vertices be comprised of the given dots? The smallest rect that covers all the dots? Any rect that covers some of the dots?

 

The answer to the problem as you've stated it: the original rectangle reduced by an arbitrarily small delta. That covers all the dots, which is "as many dots as possible."

Edited by Buckeye

Share this post


Link to post
Share on other sites

1.) How looks the constraint for "rectangle B inside rectangle A"?

2.) What co-ordinates are used (integer, floating point)?

3.) Are the points allowed to be located on the boundary of a rectangle or do they need to be located really inside?

4.) What does "as many as possible" mean exactly?

 

EDIT: Err, yes: Too few details given ;)

Edited by haegarr

Share this post


Link to post
Share on other sites

If I have a rectangle of random size and it has random dots in it.( = Rectangle A)

I want to take a rectangle that's inside A to cover as many dots as possible.


Then rectangle A will be a rectangle that's inside A and also covers as many dots as possible.
Are you thinking about bounding boxes? In that case, it's easy:
 
ptMin = vec2.uniform(float::max)
ptMax = vec2.uniform(float::min)

for pt in pts
  ptMin = min(ptMin, pt)
  ptMax = max(ptMax, pt)
Edited by fastcall22

Share this post


Link to post
Share on other sites




Wouldn't by any chance be a homework assignment? If so, that's greatly discouraged. If not, you may get better answers if you describe how the rectangle will be used.

 

I want to have thumbnails of screenshots from moments in the game. First I thought that I could just resize them but then it looks kinda ugly and a bit distorted.

So then I just crop it in the middle after that.

The problem is that I don't think it looks cool enough. So what I'm thinking is that I could mark the explosions, bullets and magic with "relevance" dots or run the image through a "Feature Detection" like a SURF or SIFT to mark the images with interesting stuff. I'm thinking of doing a collage/toplist of cool(= gives out most score) stuff when the level is complete. The problem is that it's really slow to do brute force and I want it the instant the level is complete. What I want is a function that basically given an width/height and an image gives me back the cropped version of the most intense place in the image.

 



Then rectangle A will be a rectangle that's inside A and also covers as many dots as possible.
Are you thinking about bounding boxes? In that case, it's easy:

 

Nope I want a specific size of the rectangle.

Share this post


Link to post
Share on other sites
Convex hull might cover it, and the bounding box is just an easy alternate form. Several greedy algorithms could help finding a good boundary, constructing rectangle options based on what gives good results quickly. You could also go for a correct-but-expensive route of testing all viable solutions.

What you specifically do will depend on your exact problem to solve.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this