How can I order objects on an isometric projection, based on coordinates and size?

Question

I've tried to figure it out on my own, but nothing I tried really worked completely. I'm not sure if this is a math question (since it's language-independent), but I'll ask here first.

I have a set of rectangular shapes: x, y, width, height. I want to be able to sort these objects, so that they are "behind each other" when projected isometrically.

Edit: the x and y coordinates represent the "bottom left" corner of each rectangle.

Here is an example of a failed attempt:

Here is what I'm looking for:

Here is an example of an object with: x=0, y=0, width=2, height=1

The objects can be rectangles of any size (not just those shown in my example). The angle isn't really important either, let's just say 45°.

I've tried to look into Cavalier Projection and similar topics - but information about how to actually sort these objects eluded me.

What kind of sorting algorithm can I use to sort these objects and get the correct order?

Edit 1: Using @Stef's suggestion (and changing "<" to "<=" works for most cases, but as soon as more objects are added, this starts to happen:

// Stef's suggestion, slightly modified
compareRectangles(r1, r2):
return ((r1.x + r1.width <= r2.x) OR (r1.y+r1.height <= r2.y))

I've encountered this issue previously, in my own attempts. Adding or removing other boxes, can change the result. I'm not sure if this is an issue with sort(), or if it's related to objects being too "distant" from each other (so the sorting suddenly doesn't work any longer when "long" objects cut each other).

Generally, the more "square" the objects are, the less faults appear. But I'm trying to find a solution that works even with long rectangles.

Edit 2: Here are the coordinates of the failing above example. Sadly, this constellation is kind of fragile... adding more boxes just causes the fault to appear in a different random place. The total constellation seems to affect the result, not each single comparison.

x, y, width, height
===================
0, 4, 4, 4
0, 8, 8, 1
4, 4, 4, 2
8, 4, 1, 7
6, 6, 1, 1
5, 6, 1, 1
4, 6, 1, 1
8, 11, 1, 1
0, 2, 9, 1
0, 1, 9, 1
0, 0, 9, 1
11, 7, 1, 1
11, 8, 1, 1
11, 9, 1, 1
11, 10, 1, 1
11, 11, 1, 1
0, 10, 1, 1
0, 11, 1, 1
1, 10, 1, 1
1, 11, 1, 1
2, 10, 1, 1
2, 11, 1, 1

0, 3, 11, 1 // long box above failing box

9, 1, 1, 1 // failing box

user_3080723 · Answer

For two rectangles A and B, there are three possible situations:

A must be drawn before B;
B must be drawn before A;
It doesn't matter which is drawn first.

The third case is important; if you try to mix it in by defaulting to one of the first two cases in your comparison function, then the comparison will not be a transitive relation. In other words, you could end up with conflicting triplets A, B, C, where A must be drawn before B, B before C, and C before A.

Classical sorting algorithms operate with the assumption that the relation is both transitive (no conflicting triplets), and total (for every pair A,B, you can say which one must be drawn first).

A sorting algorithm that doesn't require the relation to be total is called a topological sort, and is usually described as a sort of the vertices of a directed graph. Here the vertices are the rectangles, and there is an edge from A to B if A must be drawn before A.

Hence, build your graph, and call a topological sort function on this graph.

I think the conditions for the edges are the following. For two rectangles A and B:

if ((A.x_max <= B.x_min) AND (B.y_max <= A.y_min)) OR ((B.x_max <= A.x_min) AND (A.y_max <= B.y_min)), then it doesn't matter which rectangle is drawn first;
else if ((A.x_max <= B.x_min) OR (A.y_max <= B.y_min)), then B should be drawn before A;
else if ((B.x_max <= A.x_min) OR (B.y_max <= A.y_min)), then A should be drawn before B.

Note that compared to your notations, I used x_min = x, x_max = x+width, y_min = y, y_max = y + height.

How can I order objects on an isometric projection, based on coordinates and size?

1 Answers