“脏区域”相交时如何优化列表？

Question

我有一个“脏区域”列表（用于纹理）。其中的矩形可能会相互重叠。我想优化这个列表，这样就不会出现重叠。因此，当我使用这个列表时，数据不会在相交区域被复制两次。

有某种算法可以解决这个问题吗？我的想法似乎不是最理想的。

Answer 1

实现此目的的一种方法是基于水平扫描，您可以在图像上画线，计算通过的边缘以确定您是否在矩形内，如this fiddle中所示。它产生以下输出，其中填充的矩形是输入，描边的矩形是输出：

它首先找到扫描结果可能发生变化的所有位置，即矩形的顶部和底部，然后对它们进行排序和过滤以获得唯一值。

for (let rect of rects) {
    yCoordiantes.push(rect.starty, rect.endy);
}

然后我们评估在这些 y 坐标之间交叉的扫描线：

for (let i = 0; i < yCoordiantes.length - 1; i++) {
  let y = (yCoordiantes[i] + yCoordiantes[i+1]) / 2;

沿着该线找到矩形的所有左侧或右侧：

  for (let rect of rects) {
    if (rect.endy < y || rect.starty > y) {
        continue;
    }
    xStarts.push(rect.startx);
    xEnds.push(rect.endx);
  }
  let allXs = [...xStarts, ...xEnds];

然后，对于每个 x 坐标，我们通过计算是否经过的矩形起点多于终点来确定是否在矩形内：

  for (let k = 0; k < allXs.length; k++) {
    let insideCount = xStarts.filter(x => x <= allXs[k]).length
                    - xEnds.filter(x => x <= allXs[k]).length;

每当计数达到 0 时创建一个输出矩形：

if (insideCount === 0 && inside) {
    output.push({
    starty: yCoordiantes[i],
    endy: yCoordiantes[i + 1],
    startx: start,
    endx: allXs[k]
  });
}
if (insideCount > 0 && !inside) {
    start = allXs[k];
}
inside = insideCount > 0;

这可以优化，但它演示了这个想法。