3 ms·
Well if you're willing to sacrifice a bit of speed I think I have a pretty good heuristic algorithm you can use: Step 1: Find a maximal point, by this a mean a
by jdoliner 17y ago
Well if you're willing to sacrifice a bit of speed I think I have a pretty good heuristic algorithm you can use:
Step 1: Find a maximal point, by this a mean a point `p' s.t. no point has x >= p.x and y >= p.y. (such a point clearly exists).
Step 2:
Now it shouldn't be too hard to see that for a rectangle to cover `p' it would have to have `p' as one of its corners, so we set one corner as `p' and then grow the other corner until it runs into walls.
This is just off the top of my head so I'm haven't really done much analysis. You could make it a bit slower and actually get the rectangle that takes up the most area instead of just growing until you hit walls. Not sure how much that actually improves it.
- gruseom 17y agoThis raises the question of exactly how to grow the rectangles, i.e. how to pick out the ones that have adjacent space to consume, what to do with the leftovers after a merge (since the union of two rectangles may not be a rectangle) and so on. It's too slow to examine all the rectangles every time you want to answer one of these questions, so you need a way of arranging them. I've written code that is vaguely similar to what you suggest (but is too slow). It sorts the rectangles in one x-coordinate and then one y-coordinate, which still leaves a lot of searching to do. Perhaps keeping four sorted lists of the rectangles would help, but that's costly too, since as you coalesce rectangles you need to insert and delete from the set.