{$MODE OBJFPC}
{$MODESWITCH AUTODEREF}
unit dminkowski;

interface

uses
  dmath,
  dvector2i,
  dvector2f,
  dintersect;

procedure MinkowskiDiff2f(const A, B: TRect2f; out C: TRect2f); overload;
procedure MinkowskiDiff2f(const A, B: TCircle2f; out C: TCircle2f); overload;
procedure MinkowskiDiff2f(const A, B: TConvexPolygon2f; out C: TConvexPolygon2f); overload;

implementation

procedure MinkowskiDiff2f(const A, B: TRect2f; out C: TRect2f);
begin
  C.P := A.P - (B.P + B.D);
  C.D := A.D + B.D;
end;

procedure MinkowskiDiff2f(const A, B: TCircle2f; out C: TCircle2f);
begin
  C.P := A.P - B.P;
  C.R := A.R + B.R;
end;

procedure MinkowskiDiff2f(const A, B: TConvexPolygon2f; out C: TConvexPolygon2f);
var
  Base, I, J, Count: LongInt;
  AEdge, BEdge: TVec2f;
begin
  C.Init(Length(A.V) + Length(B.V));
  Base := 2 * Length(B.V); // чтобы не делить отрицательные числа с остатком
  AEdge := A.GetEdge(0);
  BEdge := B.GetEdge(Base);
  while Clockwise2f(AEdge, BEdge) do begin
    Inc(Base);
    BEdge := B.GetInvEdge(Base);
  end;
  while not Clockwise2f(AEdge, BEdge) do begin
    Inc(Base);
    BEdge := B.GetInvEdge(Base);
  end;
  I := 0;
  J := Base;
  Count := 1;
  C.V[0] := A.V[0] - B.V[Base mod Length(B.V)];
  while Count < Length(A.V) + Length(B.V) do begin
    if Clockwise2f(AEdge, BEdge) then begin
      C.V[Count] := C.V[Count - 1] + AEdge;
      Inc(I);
      AEdge := A.GetEdge(I);
    end else begin
      C.V[Count] := C.V[Count - 1] + BEdge;
      Inc(J);
      BEdge := B.GetInvEdge(J);
    end;
    Inc(Count);
  end;
end;

end.
