1

我有一组矩形，矩形的左上角坐标不同，宽度/高度也不同。例如，让我们取一个带有固定变量的矩形 A：X 坐标（左上角）为 1，Y 坐标为 2，宽度为 1，高度为 2。现在矩形 B 的变量并非全部接地：X 为 1，Y 为 [1,2]，宽度为 2，高度为 [1,2]。

基于此信息，我们应该能够判断 2 是 Y 的不可能值，因为它会导致两个矩形的左上角相同，因此它们会重叠。然后 Y 将接地为 1。高度也是如此：如果高度为 2，则矩形 B 的左下角将与矩形 A 重叠，因此只允许 1。有了这些信息，我们就能够通过传播将矩形 B 接地。但对我来说问题是我有很多矩形要考虑，并且有很多可用的选项。

我在 SWI-Prolog 中使用 CHR 来实现。目前我有这样的东西（它只是这里实现的非重叠矩形约束的一小部分）：

% verify top left corner
rect(_,c(X,Y),s(W,H))\rect(Hint,c(_X,_Y),S)<=>
  number(X),number(Y),number(W),number(H),number(_X),\+ number(_Y),
  _X >= X, _X < X+W, Z is Y+H-1, numlist(Y,Z,NY), subtract(_Y,NY,NewY), \+ permutation(NewY,_Y) |
  rect(Hint,c(_X,NewY),S).
rect(_,c(X,Y),s(W,H))\rect(Hint,c(_X,_Y),S)<=>
  number(X),number(Y),number(W),number(H),\+ number(_X),number(_Y),
  _Y >= Y, _Y < Y+H, Z is X+W-1, numlist(X,Z,NX), subtract(_X,NX,NewX), \+ permutation(NewX,_X) |
  rect(Hint,c(NewX,_Y),S).

% better version of equals
permutation([], []).
permutation([H|T], R) :-
   permutation(T, X),
   delete(H, R, X).
permutation(X, Y) :- % in case of numbers instead of lists
   X == Y.

标题左侧的矩形是矩形 A，我简化的是矩形 B。如果 X 坐标接地（它是一个数字）但 Y 没有接地（它是一个列表），那么我尝试删除所有列表中 Y 的不可能值。最好的情况是只剩下 1 个元素，我们也可以将 Y 接地。在第二个 simpagation 规则中，我做同样的事情：如果我们知道 Y 的值但不知道 X 的值，我们会尝试消除 X 的所有不可能值。

这是用于验证矩形 B 的左上角是否在矩形 A 内的大量代码。我什至已经通过假设矩形 A 先接地而简化了事情，这并没有考虑到 A 的左上角的事实可能在矩形 B 内。当我试图弄清楚宽度和高度的传播时，事情变得更加复杂，因为矩形放置和不同的重叠可能性有很多组合。想到我必须考虑的所有可能性，我感到非常不知所措。

我尝试查找非重叠矩形放置的算法，但许多人认为我已经拥有完整的信息。不幸的是，我没有所有扎根的价值观，重点是我自己进行传播。有没有人对如何以战略方式解决这个问题提出建议？

4

0 回答 0