# Algorithm for covering as much dots a as possible?

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

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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634061
• Total Posts
3015301
×