Abschlussprojekt FIAE (Optimierung von Algorithmen) -> Vergleich von Polygonen

[Gyrospeter]

Guten Abend werte Delphi-Gemeinde,

nun ist es für mich auch soweit, ich befinde mich gerade in den Vorbereitungen meines Abschlussprojektes und dabei geht es um Umgestaltung bzw. das effizienter Gestalten eines schon vorhandenen bzw. schon vorhandener Algorithmen.
Hierbei wird Wert auf die Laufzeit-, Speichereffizienz und kognitive Effizienz als drei Hauptkriterien gelegt.
Vorab, die Algorithmen die verbessert werden sollen hinlänglich der Effizienz, habe ich vor längerer Zeit selbst geschrieben.
In der Praxis hat sich herausgestellt, dass diese Algorithmen leider sehr langsam arbeiten und bei großen Listen auch ziemlich viel Speicher fressen.
Problem dabei ist, dass ich auf den ersten Blick nicht wirklich erkennen kann, wo Verbesserungspotential ist (außer z.B. auf die Listen als Feldvariablen zu verzichten und diese eben lokal zu erstellen und wieder wegzuräumen).
Ich möchte hier keine 1:1 Lösung angeboten bekommen, aber einige Tipps wo ich was verbessern könnte bzw. wo welche Stellen ich mir noch anschauen sollte, bei denen Verbesserungspotential herrscht

Kurzum was mein Code macht:
Es gibt 2 generische Listen die aus Records bestehen, vielleicht wären hier sogar generische Listen aus Vektoren besser diese Listen beinhalten Vektoren (Koordinaten) aus denen sich dann ein Polygon zeichnen lässt. Diese Polygone sollen nun verglichen werden. Es gibt Fälle in denen der Startpunkt bei Polygon 1 der Endpunkt bei Polygon 2 und umgekehrt ist, dann sind die Polygone dennoch gleich. Nur eben in der Liste von den umgedreht, diese wird dann durch eine Funktion rotiert. Weiterhin gibt es die Möglichkeit geschlossene oder offene Polygone als Parameter in die Listen zu übergeben. Auch auf doppelte Einträge wird geachtet und diese aus der Liste entfernt.

Als einen guten Lösungsansatz zur Vorbereitung fand ich:
https://stackoverflow.com/questions/...lygons-is-same

Und hier der Code:

Delphi-Quellcode:

type
  TCadVec3 = record
    x: Integer;
    y: Integer;
    z: Integer;
  end;

  TCadVec3List = TList<TCadVec3>;

  TCADVecListHelperMainFrm = class(TForm)
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    { Private-Deklarationen }
    FFirstCADList: TCadVec3List;
    FSecondCADList: TCadVec3List;
  public
    { Public-Deklarationen }
  end;

var
  CADVecListHelperMainFrm: TCADVecListHelperMainFrm;

//  Globale Methoden.
  procedure RotateList(AList: TCadVec3List; AIndex: Integer);
  procedure RemoveIdenticalFromList(AList: TCadVec3List; AOpen: Boolean);

  function IsListItemEqual(AFirstRecord, ASecondRecord: TCadVec3): Boolean;
  function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean;
  function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; AStartIdx: Integer; ADirectional: Boolean): Boolean;
  function CompareBothLists(AFirstList, ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;

implementation


{$R *.dfm}

function CompareBothLists(AFirstList,
  ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;
var
  i: Integer;
  LFirstTmpList,LSecondTmpList: TCadVec3List;
begin
//  Vergleich der Listen bzw. der Polygone und ob diese geometrisch gleich, oder ungleich sind.
//  Hierbei werden verschiedene Rahmenbedingungen und Szenarien aufgeführt -> geschlossene Polygone, offene Polygone, geschlossenes/offenes Polygon.
  LFirstTmpList := TCadVec3List.Create;
  LSecondTmpList := TCadVec3List.Create;

  try
    Result := False;

    if (AFirstList = nil) or (ASecondList = nil) then
      Exit;

    LFirstTmpList.AddRange(AFirstList);
    LSecondTmpList.AddRange(ASecondList);
    RemoveIdenticalFromList(LFirstTmpList, AFirstListOpen);
    RemoveIdenticalFromList(LSecondTmpList, ASecondListOpen);

    if (AFirstListOpen = ASecondListOpen) and (LFirstTmpList.Count <> LSecondTmpList.Count) then
      Exit;

    if not AFirstListOpen and not ASecondListOpen then
    begin
      for i := 0 to LSecondTmpList.Count - 1 do
      begin
        if IsListItemEqual(LFirstTmpList[0], LSecondTmpList[i]) then
        begin
          Result := CompareClosedPolygon(LFirstTmpList, LSecondTmpList, i, ADirectional);

          if Result then
            Break;
        end;
      end;
      Exit;
    end
    else if AFirstListOpen and ASecondListOpen then
      Result := CompareOpenPolygons(LFirstTmpList, LSecondTmpList, ADirectional)
    else if AFirstListOpen and not ASecondListOpen then
    begin
      if IsListItemEqual(LFirstTmpList.First, LFirstTmpList.Last) then
      begin
        LFirstTmpList.Delete(LFirstTmpList.Count - 1);

        for i := 0 to LSecondTmpList.Count - 1 do
        begin
          if IsListItemEqual(LFirstTmpList[0], LSecondTmpList[i]) then
          begin
            Result := CompareClosedPolygon(LFirstTmpList, LSecondTmpList, i, ADirectional);

            if Result then
              Break;
          end;
        end;
        Exit;
      end
      else
        Exit;
    end
    else
    begin
      if IsListItemEqual(LSecondTmpList.First, LSecondTmpList.Last) then
      begin
        LSecondTmpList.Delete(LSecondTmpList.Count - 1);

        for i := 0 to LFirstTmpList.Count - 1 do
        begin
          if IsListItemEqual(LSecondTmpList[0], LFirstTmpList[i]) then
          begin
            Result := CompareClosedPolygon(LSecondTmpList, LFirstTmpList, i, ADirectional);

            if Result then
              Break;
          end;
        end;
        Exit;
      end
      else
        Exit;
    end;
  finally
    LSecondTmpList.Free;
    LFirstTmpList.Free;
  end;
end;

function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; AStartIdx: Integer; ADirectional: Boolean): Boolean;
var
  i: Integer;
  LEqual: Boolean;
  LTmpList: TCadVec3List;
begin
//  Vergleich von geschlossenen Polygonen bzw. einem offenen und einem geschlossenen Polygon.
  LTmpList := TCadVec3List.Create;

  try
    LEqual := True;
    LTmpList.AddRange(ASecondList);
    RotateList(LTmpList, AStartIdx);

    for i := 0 to AFirstList.Count - 1 do
    begin
      if not IsListItemEqual(AFirstList[i], LTmpList[i]) then
      begin
        LEqual := False;
        Break;
      end;
    end;

    if not LEqual and not ADirectional then
    begin
      LEqual := True;
      LTmpList.Clear;
      LTmpList.AddRange(ASecondList);
      LTmpList.Reverse;
      RotateList(LTmpList, (LTmpList.Count - 1) - AStartIdx);

      for i := 0  to AFirstList.Count - 1 do
      begin
        if not IsListItemEqual(AFirstList[i], LTmpList[i]) then
        begin
          LEqual := False;
          Break;
        end;
      end;
    end;
    Result := LEqual;
  finally
    LTmpList.Free;
  end;
end;

function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List;
  ADirectional: Boolean): Boolean;
var
  i: Integer;
  LEqual: Boolean;
  LTmpList: TCadVec3List;
begin
//  Vegleich von zwei offenen Polygonen.
  LTmpList := TCadVec3List.Create;

  try
    LEqual := True;
    LTmpList.AddRange(ASecondList);

    for i := 0 to AFirstList.Count - 1 do
    begin
      if not IsListItemEqual(AFirstList.Items[i], LTmpList.Items[i]) then
      begin
        LEqual := False;
        Break;
      end;
    end;

    if not LEqual and not ADirectional then
    begin
      LEqual := True;
      LTmpList.Clear;
      LTmpList.AddRange(ASecondList);
      LTmpList.Reverse;

      for i := 0 to AFirstList.Count - 1 do
      begin
        if not IsListItemEqual(AFirstList.Items[i], LTmpList.Items[i]) then
        begin
          LEqual := False;
          Break;
        end;
      end;
    end;
    Result := LEqual;
  finally
    LTmpList.Free;
  end;
end;

procedure TCADVecListHelperMainFrm.FormCreate(Sender: TObject);
begin
//  Instanzen erzeugen.
  FFirstCADList := TList<TCadVec3>.Create;
  FSecondCADList := TList<TCadVec3>.Create;
end;

procedure TCADVecListHelperMainFrm.FormDestroy(Sender: TObject);
begin
//  Instanzen freigeben.
  FSecondCADList.Free;
  FFirstCADList.Free;
end;

procedure RotateList(AList: TCadVec3List; AIndex: Integer);
var
  i: Integer;
begin
//  Rotation der Liste zum vorgegebenen Startindex bzw. Startpunkt.
  if (AList = nil) or (AIndex < 0) or (AIndex > AList.Count - 1) then
    Exit;

  for i := 0 to AIndex  - 1 do
  begin
    AList.Move(0, AList.Count - 1);
  end;
end;

function IsListItemEqual(AFirstRecord, ASecondRecord: TCadVec3): Boolean;
begin
//  Vergleich der Elemente in der Liste.
  if (AFirstRecord.x = ASecondRecord.x) and (AFirstRecord.y = ASecondRecord.y) and (AFirstRecord.z = ASecondRecord.z) then
    Result := True
  else
    Result := False;
end;

procedure RemoveIdenticalFromList(AList: TCadVec3List; AOpen: Boolean);
var
  i: Integer;
  LCadActualItem,LCadNextItem: TCadVec3;
begin
//  Entferne doppelte, aufeinander Folgende Einträge bzw. Elemente.
  for i := AList.Count - 1 downto 1 do
  begin
    LCadActualItem := AList.Items[i];
    LCadNextItem := AList.Items[i - 1];

    if IsListItemEqual(LCadActualItem, LCadNextItem) then
      AList.Delete(i - 1);
  end;

  if not AOpen then
  begin
    if IsListItemEqual(AList.First, AList.Last) then
      AList.Delete(AList.Count - 1);
  end;
  AList.TrimExcess;
end;