source: trunk/Geometry.pas

unit Geometry;

interface

uses
  Classes, SysUtils, Math;

type
  { TGPoint }

  TGPoint<T> = record
  public
    X: T;
    Y: T;
    constructor Create(const X, Y: T);
    class operator Add(const A, B: TGPoint<T>): TGPoint<T>;
    class operator Subtract(const A, B: TGPoint<T>): TGPoint<T>;
    class operator GreaterThan(const A, B: TGPoint<T>): Boolean;
    class operator GreaterThanOrEqual(const A, B: TGPoint<T>): Boolean;
    class operator LessThan(const A, B: TGPoint<T>): Boolean;
    class operator LessThanOrEqual(const A, B: TGPoint<T>): Boolean;
    class operator Equal(const A, B: TGPoint<T>): Boolean;
    class operator Multiply(const A, B: TGPoint<T>): TGPoint<T>;
    //class operator Divide(const A, B: TGPoint<T>): TGPoint<T>;
    //class operator Modulus(A: TGPoint<T>; B: TGPoint<T>): TGPoint<T>;
    class function Min(const A, B: TGPoint<T>): TGPoint<T>; static;
    class function Max(const A, B: TGPoint<T>): TGPoint<T>; static;
    procedure Rotate(Base: TGPoint<T>; Angle: Double);
  end;

  { TGPoint3D }

  TGPoint3D<T> = record
  public
    X: T;
    Y: T;
    Z: T;
    constructor Create(const X, Y, Z: T);
  end;

  { TGRect }

  TGRect<T> = record
  private
    function GetEmpty: Boolean;
    function GetSize: T;
    procedure SetSize(AValue: T);
  public
    P1: T;
    P2: T;
    function IsPointInside(const P: T): Boolean;
    function Center: T;
    procedure SetEmpty;
    procedure Normalize;
    procedure Move(P: T);
    class operator Equal(const A, B: TGRect<T>): Boolean;
    constructor Create(const P1, P2: T);
    constructor CreateBounds(const Origin, Size: T);
    property Size: T read GetSize write SetSize;
    property Empty: Boolean read GetEmpty;
  end;

  { TGLine }

  TGLine<T> = record
  private
    function GetDistance: Double;
    procedure SetDistance(AValue: Double);
  public
    P1: T;
    P2: T;
    constructor Create(const P1, P2: T);
    function GetMiddle: T;
    function GetAngle: Double;
    function GetSize: T;
    function ToRect: TGRect<T>;
    function DotProduct: Double;
    class function LineIntersect(const LineA, LineB: TGLine<T>; out Intersection: T): Boolean; static;
    procedure Rotate(const Angle: Double);
    class operator Equal(const A, B: TGLine<T>): Boolean;
    property Distance: Double read GetDistance write SetDistance;
  end;

  { TGPolygon }

  TGPolygon<T> = record
  private
    function GetPoint(const Index: Integer): T; inline;
    procedure SetPoint(const Index: Integer; const AValue: T); inline;
  public
    type
      TPointArray = array of T;
    var
    Points: TPointArray;
    function IsPointInside(const P: T): Boolean;
    constructor Create(const Points: TPointArray); overload;
    constructor Create(const Rect: TGRect<T>); overload;
    function Compare(Polygon: TGPolygon<T>): Boolean;
    procedure Move(P: T);
    function GetRect: TGRect<T>;
    function EdgeDistance(Polygon: TGPolygon<T>): Double;
    function GetCenter: T;
    procedure AddPoint(const P: T);
    procedure Clear;
    procedure CutLine(Vector: TGLine<T>; const PointInside: T);
    property Items[Index: Integer]: T read GetPoint write SetPoint; default;
  end;

  // Integer
  TPoint = TGPoint<Integer>;
  TPoint3D = TGPoint3D<Integer>;
  TLine = TGLine<TPoint>;
  TRect = TGRect<TPoint>;
  TPolygon = TGPolygon<TPoint>;

  // FLoating
  TPointF = TGPoint<Single>;
  TPoint3DF = TGPoint3D<Single>;
  TRectF = TGRect<TPointF>;
  TLineF = TGLine<TPointF>;
  TPolygonF = TGPolygon<TPointF>;

function TypedMod(Numerator, Denominator: Integer): Integer; overload;
//function TypedMod(Numerator, Denominator: Single): Single; overload;
function TypedDivide(Divident, Divisor: Integer): Integer; overload;
function TypedDivide(Divident, Divisor: Single): Single; overload;
function TypedRound(Value: Double): Integer; overload;
function TypedRound(Value: Double): Double; overload;
function StdPointToPoint(Value: Classes.TPoint): TPoint;
function PointToStdPoint(Value: TPoint): Classes.TPoint;
function ModNeg(A, B: Integer): Integer;


implementation

function ModNeg(A, B: Integer): Integer;
begin
  if A < 0 then A := A + Ceil(-A / B) * B;
  Result := A mod B;
end;

function TypedMod(Numerator, Denominator: Integer): Integer; overload;
begin
  Result := Numerator mod Denominator;
end;

{function TypedMod(Numerator, Denominator: Single): Single; overload;
begin
  //Result := FMod(Numerator, Denominator);
end;}

function TypedDivide(Divident, Divisor: Integer): Integer;
begin
  Result := Divident div Divisor;
end;

function TypedDivide(Divident, Divisor: Single): Single;
begin
  Result := Divident / Divisor;
end;

function TypedRound(Value: Double): Integer;
begin
  Result := Round(Value);
end;

function TypedRound(Value: Double): Double;
begin
  Result := Value;
end;

function StdPointToPoint(Value: Classes.TPoint): TPoint;
begin
  Result.X := Value.X;
  Result.Y := Value.Y;
end;

function PointToStdPoint(Value: TPoint): Classes.TPoint;
begin
  Result.X := Value.X;
  Result.Y := Value.Y;
end;

{ TGPolygon }

function TGPolygon<T>.GetPoint(const Index: Integer): T;
begin
  Result := Points[Index];
end;

function TGPolygon<T>.GetCenter: T;
var
  I: Integer;
begin
  Result := T.Create(0, 0);
  for I := 0 to Length(Points) - 1 do
    Result := Result + Points[I];
  Result.X := TypedRound(Result.X / Length(Points));
  Result.Y := TypedRound(Result.Y / Length(Points));
end;

procedure TGPolygon<T>.SetPoint(const Index: Integer; const AValue: T);
begin
  Points[Index] := AValue;
end;

function TGPolygon<T>.IsPointInside(const P: T): Boolean;
var
  I, J: Integer;
begin
  Result := False;
  J := High(Points);
  for I := Low(Points) to High(Points) do begin
    if ((Points[I].Y <= P.Y) and (P.Y < Points[J].Y)) or
      ((Points[J].Y <= P.Y) and (P.Y < Points[I].Y)) then
      begin
      if (P.X < (Points[J].X - Points[I].X) *
         (P.Y - Points[I].Y) /
         (Points[J].Y - Points[I].Y) + Points[I].X) then
          Result := not Result;
      end;
    J := I;
  end;
end;

constructor TGPolygon<T>.Create(const Points: TPointArray);
var
  I: Integer;
begin
  SetLength(Self.Points, Length(Points));
  for I := 0 to Length(Points) - 1 do
    Self.Points[I] := Points[I];
end;

constructor TGPolygon<T>.Create(const Rect: TGRect<T>);
begin
  SetLength(Self.Points, 4);
  Self.Points[0] := Rect.P1;
  Self.Points[1] := T.Create(Rect.P2.X, Rect.P1.Y);
  Self.Points[2] := Rect.P2;
  Self.Points[3] := T.Create(Rect.P1.X, Rect.P2.Y);
end;

function TGPolygon<T>.Compare(Polygon: TGPolygon<T>): Boolean;
var
  I: Integer;
begin
  Result := Length(Points) = Length(Polygon.Points);
  if not Result then Exit;
  for I := 0 to Length(Points) - 1 do
    if Points[I] <> Polygon.Points[I] then begin
      Result := False;
      Break;
    end;
end;

function TGPolygon<T>.GetRect: TGRect<T>;
var
  I: Integer;
begin
  if Length(Points) = 0 then
    Result.Empty
  else begin
    Result := TGRect<T>.Create(Points[0], Points[0]);
    for I := 1 to Length(Points) - 1 do
    with Points[I] do begin
      Result.P1 := Points[I].Min(Result.P1, Points[I]);
      Result.P2 := Points[I].Max(Result.P2, Points[I]);
    end;
  end;
end;

procedure TGPolygon<T>.AddPoint(const P: T);
begin
  SetLength(Points, Length(Points) + 1);
  Points[Length(Points) - 1] := P;
end;

procedure TGPolygon<T>.Clear;
begin
  SetLength(Points, 0);
end;

procedure TGPolygon<T>.CutLine(Vector: TGLine<T>; const PointInside: T);
var
  I: Integer;
  PointsChecked: Integer;
  L1, L2: TGLine<T>;
  Intersection: T;
  NewPoly: TGPolygon<T>;
  NewPolygonStarted: Boolean;
  Success: Boolean;
begin
  NewPoly.Clear;
  Success := False;
  NewPolygonStarted := False;
  I := 0;
  PointsChecked := 0;
  L1 := Vector;
  L1.Rotate(Pi / 2);
  if Length(Points) > 0 then
  while True do begin
    L2 := TGLine<T>.Create(Points[I], Points[(I + 1) mod Length(Points)]);
    if TGLine<T>.LineIntersect(L1, L2, Intersection) then
    if L2.ToRect.IsPointInside(Intersection) then begin
      if not NewPolygonStarted then begin
        // Crossing line, start new polygon
        NewPoly.Clear;
        NewPoly.AddPoint(Intersection);
        NewPolygonStarted := True;
      end else begin
        // Crossing line, end polygon. If point NewPolygonStarted, the use polygon as result
        NewPoly.AddPoint(Points[I]);
        NewPoly.AddPoint(Intersection);
        if NewPoly.IsPointInside(PointInside) then begin
          Success := True;
          Break;
        end else begin
          NewPoly.Clear;
          NewPoly.AddPoint(Intersection);
          NewPolygonStarted := True;
        end;
      end;
    end else
      NewPoly.AddPoint(Points[I]);
    I := (I + 1) mod Length(Points);
    Inc(PointsChecked);
    if PointsChecked > 2 * Length(Points) then Break;
  end;
  if Success then Points := NewPoly.Points;
end;

function TGPolygon<T>.EdgeDistance(Polygon: TGPolygon<T>): Double;
var
  I, J: Integer;
  Dist: Double;
begin
  Result := Infinity;
  for I := 0 to Length(Points) - 1 do
  for J := 0 to Length(Polygon.Points) - 1 do begin
    Dist := TGLine<T>.Create(Points[I], Polygon.Points[J]).Distance;
    if Dist < Result then Result := Dist;
  end;
end;

procedure TGPolygon<T>.Move(P: T);
var
  I: Integer;
begin
  for I := 0 to Length(Points) - 1 do
    Points[I] := Points[I] + P;
end;

{ TGLine }

function TGLine<T>.GetDistance: Double;
begin
  Result := Sqrt(Sqr(P2.X - P1.X) + Sqr(P2.Y - P1.Y));
end;

procedure TGLine<T>.SetDistance(AValue: Double);
var
  Angle: Double;
begin
  Angle := GetAngle;
  P2 := T.Create(Round(P1.X + Cos(Angle) * AValue),
    Round(P1.Y + Sin(Angle) * AValue));
end;

constructor TGLine<T>.Create(const P1, P2: T);
begin
  Self.P1 := P1;
  Self.P2 := P2;
end;

function TGLine<T>.GetMiddle: T;
begin
  Result := T.Create(P1.X + TypedDivide((P2.X - P1.X), 2), P1.Y + TypedDivide((P2.Y - P1.Y), 2));
end;

function TGLine<T>.GetAngle: Double;
begin
  Result := ArcTan2(P2.Y - P1.Y, P2.X - P1.X);
end;

function TGLine<T>.GetSize: T;
begin
  Result := P2 - P1;
end;

function TGLine<T>.ToRect: TGRect<T>;
begin
  Result := TGRect<T>.Create(P1, P2);
end;

function TGLine<T>.DotProduct: Double;
begin
  Result := P1.X * P2.X + P1.Y * P2.Y;
end;

procedure TGLine<T>.Rotate(const Angle: Double);
begin
  P2.Rotate(P1, Angle);
end;

class operator TGLine<T>.Equal(const A, B: TGLine<T>): Boolean;
begin
  Result := (A.P1 = B.P1) and (A.P2 = B.P2);
end;

class function TGLine<T>.LineIntersect(const LineA, LineB: TGLine<T>; out
  Intersection: T): Boolean;
Var
  LDetLineA, LDetLineB, LDetDivInv: Double;
  LDiffLA, LDiffLB: T;
  D: Double;
begin
  if (LineA.P1 = LineA.P2) or (LineB.P1 = LineB.P2) then begin
    Result := False;
    Exit;
  end;
  LDetLineA := LineA.P1.X * LineA.P2.Y - LineA.P1.Y * LineA.P2.X;
  LDetLineB := LineB.P1.X * LineB.P2.Y - LineB.P1.Y * LineB.P2.X;

  LDiffLA := LineA.P1 - LineA.P2;
  LDiffLB := LineB.P1 - LineB.P2;

  D := (LDiffLA.X * LDiffLB.Y) - (LDiffLA.Y * LDiffLB.X);
  if D = 0 then begin
    // Parallel lines without intersection
    Result := False;
    Exit;
  end;
  LDetDivInv := 1 / D;

  Intersection.X := TypedRound(((LDetLineA * LDiffLB.X) - (LDiffLA.X * LDetLineB)) * LDetDivInv);
  Intersection.Y := TypedRound(((LDetLineA * LDiffLB.Y) - (LDiffLA.Y * LDetLineB)) * LDetDivInv);
  Result := True;
end;

{ TGPoint3D }

constructor TGPoint3D<T>.Create(const X, Y, Z: T);
begin
  Self.X := X;
  Self.Y := Y;
  Self.Z := Z;
end;

{ TGPoint }

constructor TGPoint<T>.Create(const X, Y: T);
begin
  Self.X := X;
  Self.Y := Y;
end;

class operator TGPoint<T>.Equal(const A, B: TGPoint<T>): Boolean;
begin
  Result := (A.X = B.X) and (A.Y = B.Y);
end;

class operator TGPoint<T>.Add(const A, B: TGPoint<T>): TGPoint<T>;
begin
  Result.X := A.X + B.X;
  Result.Y := A.Y + B.Y;
end;

class operator TGPoint<T>.Subtract(const A, B: TGPoint<T>): TGPoint<T>;
begin
  Result.X := A.X - B.X;
  Result.Y := A.Y - B.Y;
end;

class operator TGPoint<T>.Multiply(const A, B: TGPoint<T>): TGPoint<T>;
begin
  Result.X := A.X * B.X;
  Result.Y := A.Y * B.Y;
end;

{class operator TGPoint<T>.Divide(const A, B: TGPoint<T>): TGPoint<T>;
begin
  Result.X := TypedDivide(A.X, B.X);
  Result.Y := TypedDivide(A.Y, B.Y);
end;

class operator TGPoint<T>.Modulus(A: TGPoint<T>; B: TGPoint<T>): TGPoint<T>;
begin
  Result.X := TypedMod(A.X, B.X);
  Result.Y := TypedMod(A.Y, B.Y);
end;
}

class operator TGPoint<T>.GreaterThan(const A, B: TGPoint<T>): Boolean;
begin
  Result := (A.X > B.X) and (A.Y > B.Y);
end;

class operator TGPoint<T>.GreaterThanOrEqual(const A, B: TGPoint<T>): Boolean;
begin
  Result := (A.X >= B.X) and (A.Y >= B.Y);
end;

class operator TGPoint<T>.LessThan(const A, B: TGPoint<T>): Boolean;
begin
  Result := (A.X < B.X) and (A.Y < B.Y);
end;

class operator TGPoint<T>.LessThanOrEqual(const A, B: TGPoint<T>): Boolean;
begin
  Result := (A.X <= B.X) and (A.Y <= B.Y);
end;

class function TGPoint<T>.Min(const A, B: TGPoint<T>): TGPoint<T>;
begin
  if A.X < B.X then Result.X := A.X else Result.X := B.X;
  if A.Y < B.Y then Result.Y := A.Y else Result.Y := B.Y;
end;

class function TGPoint<T>.Max(const A, B: TGPoint<T>): TGPoint<T>;
begin
  if A.X > B.X then Result.X := A.X else Result.X := B.X;
  if A.Y > B.Y then Result.Y := A.Y else Result.Y := B.Y;
end;

procedure TGPoint<T>.Rotate(Base: TGPoint<T>; Angle: Double);
var
  D: TGPoint<T>;
begin
  D := Self - Base;
  X := Base.X + TypedRound(D.X * Cos(Angle) - D.Y * Sin(Angle));
  Y := Base.Y + TypedRound(D.X * Sin(Angle) + D.Y * Cos(Angle));
end;

{ TGRect }

function TGRect<T>.IsPointInside(const P: T): Boolean;
begin
  Result := (P >= P1) and (P <= P2);
end;

function TGRect<T>.GetEmpty: Boolean;
begin
  Result := P1 = P2;
end;

procedure TGRect<T>.SetEmpty;
begin
  P2 := P1;
end;

procedure TGRect<T>.Normalize;
var
  NewP1: T;
  NewP2: T;
begin
  NewP1 := P1.Min(P1, P2);
  NewP2 := P1.Max(P1, P2);
  P1 := NewP1;
  P2 := NewP2;
end;

function TGRect<T>.Center: T;
begin
  Result.X := TypedDivide(P2.X - P1.X, 2);
  Result.Y := TypedDivide(P2.Y - P1.Y, 2);
end;

function TGRect<T>.GetSize: T;
begin
  Result := P2 - P1;
end;

procedure TGRect<T>.SetSize(AValue: T);
begin
  P2 := P1 + AValue;
end;

procedure TGRect<T>.Move(P: T);
begin
  P1 := P1 + P;
  P2 := P2 + P;
end;

constructor TGRect<T>.Create(const P1, P2: T);
begin
  Self.P1 := P1;
  Self.P2 := P2;
  Normalize;
end;

constructor TGRect<T>.CreateBounds(const Origin, Size: T);
begin
  Self.P1 := Origin;
  Self.P2 := Origin + Size;
end;

class operator TGRect<T>.Equal(const A, B: TGRect<T>): Boolean;
begin
  Result := (A.P1 = B.P1) and (A.P2 = B.P2);
end;

end.