長方形の左上隅の座標が変化し、幅/高さが変化する一連の長方形があります。たとえば、固定変数を持つ長方形 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 も接地できます。2 番目の単純化規則でも同じことを行います。Y の値がわかっているが X の値がわからない場合、X の不可能な値をすべて排除しようとします。
これは、四角形 B の左上隅が四角形 A 内にあるかどうかを確認するための多くのコードです。四角形 A が最初に接地されていると仮定して、既に単純化していますが、これは A の左上隅が A の左上隅であるという事実を考慮していません。代わりに、長方形 B 内にある場合があります。長方形の配置とさまざまなオーバーラップの可能性には非常に多くの組み合わせがあるため、幅と高さの伝播を理解しようとすると、事態はさらに複雑になります。考慮しなければならないすべての可能性を考えると、かなり圧倒されます。
長方形を重ならないように配置するためのアルゴリズムを調べてみましたが、多くの人は既に完全な情報を持っていると思い込んでいます。残念ながら、私はすべての根拠のある値を持っているわけではありません。要点は、自分で伝播を実行することです。戦略的な方法でこれに取り組む方法について誰か提案がありますか?