# Sort rectangles

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

## Recommended Posts

I have a set of rectangles (non-crossing) on a 2d field. So there's a set of (x, y, w, h). I need to sort them to reach the folowing rule: for every rectangle the previous ones are to the right and up, the next - are right and down, so: x[i-1]+w[i-1]<=x && y[i-1]+h[i-1]<=y x[i+1]>=x+w && y[i+1]>=y+h[i+1] How to sort it quickly?

##### Share on other sites
I assume you mean that the previous one is left and up, not right and up, since the sort order you describe is impossible.

I think you've answered your own question in terms of the comparision you need to do.

Assuming C++, std::sort would be a good place to start unless profiling proves you need a better sort algorithm.

You could either overload operator< for your rectangle class using the formula in your post, or use the second version of std::sort and provide a function object to do the comparison.

class Rect{public:    int X,Y,W,H;    bool operator<(const Rect &R) const { return(X+W<=R.X && Y+H<=R.Y); }}:

I know you say that the rectangles are not overlapping, but what happens in the case that a rectangle is to the right and above another rectangle? Or is that impossible within this particular domain?