间隔重叠的矩形：如何翻译伪代码？

Question

我一直在尝试将一些Mathematica/伪代码从这个答案移植到Python/Blender（问题的条件实际上与我的相同）。 答案有两次编辑，每次编辑都使用相同算法的不同版本。我已经移植了第一个，但正在努力解决第二个。

Python 中的第一个编辑是这样的：

stack = deque()
while any(intersections[r] for r in rectangles):
    rectangles.sort(key=lambda r: intersections[r])
    stack.appendleft(rectangles[0])
    del rectangles[0]

while stack:
    rectangles.insert(0, stack[0])
    stack.popleft()

    rect = rectangles[0]

    g = geometric_centre(points)
    b, d = points[rect]
    m = ((b + d) / 2) - g

    i = 1
    while has_intersections(rect, points):
        x = (-1)**i * i * INCR
        vec = Vector((x, x)) * m
        b += vec
        d += vec
        i += 1

这里

points

是每个矩形到两个 mathutils.vectors 元组的字典，代表其右上角和左下角。

之前/之后：

但是我在从第二次编辑中移植改进的“多角度搜索”伪代码时遇到了麻烦，其中第二个 while 循环现在是：

While stack not empty
    find the geometric center G of the chart (each time!)
    find the PREFERRED movement vector M (from G to rectangle center)
    pop  rectangle from stack 
    With the rectangle
         While there are intersections (list+rectangle)
              For increasing movement modulus
                 For increasing angle (0, Pi/4)
                    rotate vector M expanding the angle alongside M
                    (* angle, -angle, Pi + angle, Pi-angle*)
                    re-position the rectangle accorging to M
    Re-insert modified vector into list

由于答案不包含源代码，我不清楚其含义。这是我失败的尝试：

while stack:
    rectangles.insert(0, stack[0])
    stack.popleft()

    rect = rectangles[0]

    g = geometric_centre(points)
    b, d = points[rect]
    m = ((b + d) / 2) - g
    old_m = m.copy()

    while has_intersections(rect, points):
        for i in range(1, abs(int(m.magnitude))):
            for angle in (15, 30, 36, 45):
                m.rotate(Matrix.Rotation(radians(angle), 2))
                b += old_m - m
                d += old_m - m

如何将伪代码翻译成Python？

Answer 1

我会稍微修改一下该算法，使其更像：

G <- geometric center of all rects
pivot <- rect closest to the center
left <- all rects with centers left of pivot
right <- all rects with centers right of pivot

while {left} not empty:
  newpivot <- last element in {left}
  move newpivot so that:
    - the center of newpivot is to the left of the pivot center, and
    - the distance between centers is (at least) half the sum of their widths
  remove newpivot from {left}
  pivot <- newpivot
  sortLeft

while {right} not empty:
  the mirror of the left code

move all rects by (G - G2)

所以作为可运行的片段：

function sourceCode() {
  let rects = [];

  function setup() {
    setSize(400, 160);
    addSlider(`step`, {
      min: 0,
      max: 6,
      step: 1,
      value: 6,
      transform: v => {
        setupRects();
        return v;
      }
    });
    setupRects();
  }

  // generate a bunch of overlapping rects
  function setupRects() {
    randomSeed(0);
    rects = [];
    for (let i = 0, c = 0; i < 12; i++) {
      c += 20;
      rects.push({
        c: 70 + c,
        w: random(10, 40),
        h: random(20, 100)
      });
    }
  }

  // reposition the rects and then draw them
  function draw() {
    clear();
    translate(25, 20);
    setColor(`black`);
    axes(`x`, 0, width - 30, `y`, 0, height - 25);  
    reposition(); 
    drawRects();
  }

  function drawRects() {
    randomSeed(0);
    rects.forEach(r => {
      setColor(randomColor(0.5));
      rect(r.c - r.w / 2, 60 - r.h / 2, r.w, r.h);
    });
  }

  // repositioning means finding our pivot, then
  // building the left and right lists, and then
  // updating the rects in those lists.
  function reposition() {
    const G = getCenter(); 
    const pivot = rects.reduce((p, r) => {
      const v1 = abs(r.c - G.x);
      const v2 = abs(p.c - G.x);
      return (v1 < v2) ? r : p;
    }, { c: huge });
    const left = rects.filter(r => r.c < pivot.c);
    const right = rects.filter(r => r.c > pivot.c);

    moveRects(pivot, left, right);

    const G2 = getCenter();
    rects.forEach(r => r.c -= (G.x - G2.x));
  }

  // the geometric center is just the average of all centers
  function getCenter() {
    const x = rects.reduce((t, v) => t + v.c, 0) / rects.length;
    setColor(`black`);
    return { x, y: 60 };
  }

  // Our actual algorithm:
  function moveRects(p, left, right) {
    // shift everything in left, one rect at a time
    let n = 0;
    let pivot = p;
    while (left.length > 0 && n++ < step) {
      const newPivot = left.at(-1);
      // the distance between centers
      const d = abs(pivot.c - newPivot.c);
      // the minimum distance we need for there to be no overlap
      const minD = (pivot.w + newPivot.w) / 2;
      // so.. is there an overlap?
      if (d < minD) {
        // if there is, move _all_ rects left by that much,
        // plus a little bit extra to create visual gaps.
        const offset = minD - d;
        left.forEach(r => (r.c -= 5 + offset));
      }
      pivot = left.pop();
    }

    // and then we do the same for right.
    n = 0;
    pivot = p;
    while (right.length > 0 && n++ < step) {
      const newPivot = right[0];
      const d = abs(pivot.c - newPivot.c);
      const minD = (pivot.w + newPivot.w) / 2;
      if (d < minD) {
        const offset = minD - d;
        right.forEach(r => (r.c += 5 + offset));
      }
      pivot = right.shift();
    }
  }

}

customElements.whenDefined(`graphics-element`).then(() => {
  graphics.loadFromFunction(sourceCode);
  graphics.onerror = e => console.error(e.detail);
});

<script type="module" src="https://cdnjs.cloudflare.com/ajax/libs/graphics-element/3.0.0/graphics-element.js" integrity="..." crossorigin="anonymous" referrerpolicy="no-referrer"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/graphics-element/3.0.0/graphics-element.css" integrity="..." crossorigin="anonymous" referrerpolicy="no-referrer" />
<graphics-element title="running through the algorithm" id="graphics"></graphics-element>

（请注意，这段代码采用了一种快捷方式，只是在每一步更新“左侧的所有矩形”/“右侧的所有矩形”。这并不像每次简单地移动一个矩形并添加足够的偏移量以确保新的中心是有效的在

pivot

的正确一侧，但是你可以稍微重写一下——当然，除了在 Python 中实现之外——以使用更高效的算法）