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?
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."
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 ;)
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.
ptMin = vec2.uniform(float::max)
ptMax = vec2.uniform(float::min)
for pt in pts
ptMin = min(ptMin, pt)
ptMax = max(ptMax, pt)
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.
