Search code examples
answer-set-programming

Checking intersection between two rectangles in answer set programming

The rule below checks for intersection.

:- areaCoords(X1,Y1,X2,Y2), areaCoords(XA,YA,XB,YB), XA >= X1, X2 >= XA, YB >= Y1, Y2 >= YA, (X1,Y1,X2,Y2) != (XA,YA,XB,YB).

However it generates symmetric pairs. That is, it checks for intersection(A,B) and intersection(B,A) obviously one of the checks is trivial. I detected it in the grounder. Here is the grounder output.

:-areaCoords(1,1,1,1),areaCoords(1,1,2,2).
:-areaCoords(1,1,2,2),areaCoords(1,1,1,1).

How can I prevent symmetric cases to occure?
In case the problem is somewhere else, I provide the full source that generates these rules.

Edit: I thought the previous version (full source) was very complicated for others to come to a conclution. So I simplified it. This code causes the above problem.

{ areaCoords(1,1,1,1); areaCoords(1,1,2,2) }.

:- areaCoords(X1,Y1,X2,Y2), areaCoords(XA,YA,XB,YB), XA >= X1, X2 >= XA, YB >= Y1, Y2 >= YA, (X1,Y1,X2,Y2) != (XA,YA,XB,YB).
Solution

  • Checking for < instead of inequality should prevent the symmetric constraint:

    { areaCoords(1,1,1,1); areaCoords(1,1,2,2) }.

:- areaCoords(X1,Y1,X2,Y2), areaCoords(XA,YA,XB,YB),
   XA >= X1, X2 >= XA, YB >= Y1, Y2 >= YA,
   (X1,Y1,X2,Y2) < (XA,YA,XB,YB).

    Observe:

    $ gringo --text <<<'{ areaCoords(1,1,1,1); areaCoords(1,1,2,2) }.  :- areaCoords(X1,Y1,X2,Y2), areaCoords(XA,YA,XB,YB), XA >= X1, X2 >= XA, YB >= Y1, Y2 >= YA, (X1,Y1,X2,Y2) < (XA,YA,XB,YB).'
{areaCoords(1,1,1,1);areaCoords(1,1,2,2)}.
:-areaCoords(1,1,2,2),areaCoords(1,1,1,1).

    vs.

    $ gringo --text <<<'{ areaCoords(1,1,1,1); areaCoords(1,1,2,2) }.  :- areaCoords(X1,Y1,X2,Y2), areaCoords(XA,YA,XB,YB), XA >= X1, X2 >= XA, YB >= Y1, Y2 >= YA, (X1,Y1,X2,Y2) != (XA,YA,XB,YB).'
{areaCoords(1,1,1,1);areaCoords(1,1,2,2)}.
:-areaCoords(1,1,1,1),areaCoords(1,1,2,2).
:-areaCoords(1,1,2,2),areaCoords(1,1,1,1).