如何基于坐标和尺寸对等轴测投影中的矩形对象执行正确排序

问题原因 #

你之前使用的比较函数无法得到稳定正确的结果，核心原因有两个：

• 普通排序算法（如JS的Array.sort、Python的sorted）依赖严格弱序的比较规则，你用的边界判断逻辑不满足该要求，排序结果会受初始顺序、算法实现影响，出现随机错误。
• 长矩形容易和多个其他矩形产生遮挡依赖，简单的两两比较无法处理多对象的依赖链路，会出现排序逻辑冲突。

解决方案 #

对于不允许互相穿插的轴对齐矩形，使用拓扑排序是最稳定的方案，步骤如下：

1. 定义遮挡判断规则 #

45度等轴测投影下，矩形r1完全在r2后方（需要先绘制r1，再绘制r2遮挡r1）的判断条件为：

r1.x + r1.width <= r2.x OR r1.y + r1.height <= r2.y

如果两个矩形互不满足上述条件，说明二者投影无遮挡，绘制顺序互不影响。

2. 构建依赖图 #

将每个矩形作为图的节点，对每一对矩形做判断：

• 如果r1需要在r2之前绘制，就添加一条从r1指向r2的边，同时r2的入度加1
• 如果r2需要在r1之前绘制，就添加一条从r2指向r1的边，同时r1的入度加1

3. 拓扑排序得到绘制顺序 #

使用Kahn算法对依赖图做拓扑排序，得到的序列就是正确的前后绘制顺序。如果拓扑排序输出的节点数少于总矩形数，说明存在多个矩形循环穿插的情况，需要把穿插的矩形拆分为更小的矩形后再重复排序流程。

参考代码实现（JavaScript） #

// 矩形类定义
class Rect {
  constructor(x, y, width, height) {
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;
  }
}

// 判断r1是否完全在r2后方，需要先绘制
function isBehind(r1, r2) {
  return (r1.x + r1.width <= r2.x) || (r1.y + r1.height <= r2.y);
}

// 拓扑排序得到正确绘制顺序
function sortIsometricRects(rectList) {
  const count = rectList.length;
  const adjacency = Array.from({length: count}, () => []);
  const inDegree = Array(count).fill(0);

  // 遍历所有矩形对，构建依赖图
  for (let i = 0; i < count; i++) {
    for (let j = i + 1; j < count; j++) {
      const a = rectList[i], b = rectList[j];
      if (isBehind(a, b)) {
        adjacency[i].push(j);
        inDegree[j]++;
      } else if (isBehind(b, a)) {
        adjacency[j].push(i);
        inDegree[i]++;
      }
    }
  }

  // Kahn算法实现拓扑排序
  const queue = [];
  for (let i = 0; i < count; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const sortedResult = [];
  while (queue.length) {
    const current = queue.shift();
    sortedResult.push(rectList[current]);
    for (const next of adjacency[current]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }

  // 检测是否存在循环依赖（穿插矩形）
  if (sortedResult.length !== count) {
    throw new Error('存在穿插矩形，请拆分后再排序');
  }
  return sortedResult;
}

扩展说明 #

如果你的业务场景允许矩形互相穿插，除了拆分矩形的方案外，也可以改用深度缓冲（Z-Buffer）算法，绘制每个像素时记录深度值，直接通过深度判断像素是否需要绘制，不需要提前对矩形做排序。

内容的提问来源于stack exchange，提问作者Katai