Projeto

176131.pl

/**     MC346 - Segundo Projeto - Prolog

O código completo está em https://github.com/TiagodePAlves/MC346-prolog com a
documentação mais detalhada em https://tiagodepalves.github.io/MC346-prolog/.

@author João Pedro de Amorim (176131)
@author Tiago de Paula Alves (187679)
*/


:- op(900, xfx, as).
%!  -Result as :Goal.
%
%   Funciona como is/2, aplicando Goal com Result. É útil
%   com funções aritméticas relacionadas a pontos e retas.
%   Em geral, ela só deve funcionar com operações deste módulo.
%
%   A única diferença dessa operação é que a unificação com o
%   valor exato não é necessária, então ela funciona com
%   estruturas além de números e pode funcionar com regras
%   não aritméticas.
Result as Goal :- call(Goal, Result).


%!  norm(++N, +Point, -Result) is det.
%
%   Encontra a norma N de Point. Se N é =inf= ou =infinite=,
%   calcula a norma uniforme.

norm(infinite, Point, Result) :- !,
    norm(inf, Point, Result).
norm(inf, (X, Y), Result) :- !,
    Result is max(abs(X), abs(Y)).
norm(2, (X, Y), Result) :- !,
    Result is sqrt(X*X + Y*Y).
norm(N, (X, Y), Result) :-
    Result is (abs(X)**N + abs(Y)**N)**(1/N).

%!  norm(+Point, -Result) is det.
%
%   Encontra a norma euclidiana de Point. É o mesmo que
%   norm/3, com N = 2.
norm(Point, Result) :- norm(2, Point, Result).



%!  +(+Point, +Point, -Result) is det.
%
%   Soma de pontos, normalmente usada com as/2.
+((X0, Y0), (X1, Y1), (SX, SY)) :-
    SX is X0 + X1, SY is Y0 - Y1.

%!  -(+Point, +Point, -Result) is det.
%
%   Subtração de pontos, normalmente usada com as/2.
-((X0, Y0), (X1, Y1), (DX, DY)) :-
    DX is X0 - X1, DY is Y0 - Y1.


%!  capped(+MinValue, +MaxValue, +Value, -Result) is det.
%!  capped(+MaxValue, +MinValue, +Value, -Result) is det.
%
%   Limita Value para um valor dentro do conjunto
%   [MinValue, MaxValue].
%
%   ==
%   ?- X as capped(0, 1, 0.5).
%   X = 0.5.
%   ?- X as capped(1, 0, 1.5).
%   X = 1.
%   ?- X as capped(0, inf, -15).
%   X = 0.
%   ==
capped(XA, XB, X, Result) :-
    (XA < XB -> Lim = (XA, XB); Lim = (XB, XA)),
    Result as capped(Lim, X).

%!  capped(+Limits:tuple, +Value, -Result) is det.
%
%   Função auxiliar de capped/4. Assume que os
%   limites da tupla estão ordenados, =| Limits
%   = (Xmin, Xmax), Xmin =< Xmax |=.
capped((Xmin, Xmax), X, Result) :-
    X < Xmin -> Result is Xmin;
    X > Xmax -> Result is Xmax;
    Result is X.



%!  distance(++N, +Point, +PointOrLine, -Result) is det.
%
%   Calcula a distância norma N de um ponto à outro ou à
%   uma reta.
%
%   PointOrLine pode ser um ponto =|(X, Y)|= ou um segmento
%   de reta, =|vsegment(X, Ymin, Ymax)|=,
%   =|vsegment(X, Ymax, Ymin)|=, =|hsegment(Y, Xmin, Xmax)|=
%   ou =|hsegment(Y, Xmax, Xmin)|=.
%
%   @see norm/3

distance(N, (X0, Y0), (X1, Y1), Result) :- !,
    Diff as (X0, Y0) - (X1, Y1),
    Result as norm(N, Diff).

distance(_, (X, _), vline(XL), Result) :- !,
    Result is abs(X - XL).
distance(_, (_, Y), hline(YL), Result) :- !,
    Result is abs(Y - YL).

distance(N, (X, Y), vsegment(XL, Ymin, Ymax), Result) :- !,
    YL as capped(Ymin, Ymax, Y),
    Result as distance(N, (X, Y), (XL, YL)).
distance(N, (X, Y), hsegment(YL, Xmin, Xmax), Result) :- !,
    XL as capped(Xmin, Xmax, X),
    Result as distance(N, (X, Y), (XL, YL)).

%!  distance(+Point, +PointOrLine, -Result) is det.
%
%   Calcula a distância euclidiana de um ponto à outro ou à
%   uma reta. Similar a distance/4 com N = 2.
distance(A, B, Result) :- distance(2, A, B, Result).


:- op(800, xfx, intersect_with).
%!  intersect_with(+Shape, +Shape) is det.
%
%   Verdade se as formas geométricas
%   bidimensionais têm intersecção não vazia.
%
%   As únicas formas implementadas são círculo,
%   definido por =|circle(Center, Radius)|=, e
%   quadrado, =|square(Center, SideLength)|=.

circle(C0, R0) intersect_with circle(C1, R1) :- !,
    % intersecção de círculos ocorre quando a
    % distância entre eles é menor ou igual a
    % soma dos raios
    Dist as distance(C0, C1),
    Dist =< R0 + R1.

square(C0, L0) intersect_with square(C1, L1) :- !,
    % quadrados são como círculos em norma infinita,
    % em que o raio é metade do lado, então a regra
    % de intersecção é parecida com a de círculos
    Dist as distance(inf, C0, C1),
    Dist =< (L0 + L1)/2.

circle(CC, R) intersect_with square(CQ, L) :-
    % intersecção círculo e quadrado pode ser
    % quando o círculo está dentro do quadrado
    % e distância uniforme entre eles é menor
    % ou igual a metado do lado
    Dist as distance(inf, CC, CQ),
    Dist =< L/2, !
    ; !,
    % ou quando a distância do centro do
    % círculo para qualquer um dos lados
    % do quadrado é menor que o raio
    square_side(L/2, CQ, Line),
    Dist as distance(CC, Line),
    Dist =< R, !.

square(CQ, L) intersect_with circle(CC, R) :- !,
    circle(CC, R) intersect_with square(CQ, L).


%!  square_side(+HalfSide, +Center, -Segment) is multi.
%
%   Verdade se Segment é um dos lados do quadrado
%   definido por Center e metade do lado, HalfSide.
%
%   Usado para descobrir os quatros lados de um
%   quadrado.
square_side(HL, (X, Y), vsegment(X-HL, Y-HL, Y+HL)).
square_side(HL, (X, Y), vsegment(X+HL, Y-HL, Y+HL)).
square_side(HL, (X, Y), hsegment(Y-HL, X-HL, X+HL)).
square_side(HL, (X, Y), hsegment(Y+HL, X-HL, X+HL)).


%!  shape(+Name, +Shape) is det.
%
%   Verdade se existe uma figura Shape associada
%   a Name.
:- dynamic(shape/2, [thread(local)]).

%!  insert_shape(+Name, +Shape) is det.
%
%   Insere a figura no banco de dados e suas intersecções.
insert_shape(NewName, NewShape) :-
    asserta(shape(NewName, NewShape)).

%!  insert_shape(+NamedShape) is det.
%
%   Funciona como insert_shape/2, mas quebra o NamedShape antes.
insert_shape(circ(Name, X, Y, R)) :-
    insert_shape(Name, circle((X, Y), R)).
insert_shape(quad(Name, X, Y, R)) :-
    insert_shape(Name, square((X, Y), R)).


%!  intersection(?NameA, ?NameB) is det.
%
%   Verdade se existe uma figura com nome NameA e
%   outra com NameB, sendo NameA lexicograficamente
%   menor que NameB e elas têm intersecção não vazia.
intersection(A, B) :-
    shape(A, ShapeA), shape(B, ShapeB), A @< B,
    ShapeA intersect_with ShapeB.



%!  topo is det.
%
%   Resolve o problema com a entrada e saída atual.
topo :-
    read(Figures),
    % insere as figuras como fatos
    maplist(insert_shape, Figures),
    % compilar o predicado dinâmico pode otimizar as queries,
    % mas principalmente ele protege de n
    compile_predicates([shape/2]),

    % conta o número de soluções
    aggregate_all(count, intersection(X, Y), Length),
    writeln(Length),

    % e imprime as soluçoes
    foreach(intersection(X, Y), (
        format("~w ~w", [X, Y]), nl
    )).

% OBS: o aggregate_all/3 e foreach/2 fazem a mesma operação
% de encontrar as intersecções, então o código poderia ser
% 2 vezes mais rápido fazendo o operação e guardando as
% intersecções em uma lista, mas isso não foi usado aqui para
% manter a consistência com o estilo de uso de fatos dinâmicos
% do banco de dados de Prolog.