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

[Gausi]

Zitat von Stevie:

Zu diesem Schluss war ich in den ersten beiden Sätzen meiner Anmerkungen auch gekommen.

Ups, sorry, das habe ich anscheinend überlesen.

Aber vielleicht als Ergänzung: Das haut natürlich besonders stark in dieser Zeile des Originalcodes rein, wenn AStartIdx = 0 ist.
RotateList(LTmpList, (LTmpList.Count - 1) - AStartIdx); Dann wird die Liste mit 1000 Einträgen 1000 mal im Speicher hin und her kopiert, bevor mit der Überprüfung auf Gleichheit der beiden Listen begonnen wird.

Das mit der Index-Rechnerei mag zwar aufwändiger erscheinen, ist es aber nicht. Schon alleine deswegen, weil bei ungleichen Polygonen es sehr schnell zu einem Abbruch kommen wird, während sich die Rotation grade erst warmgelaufen hat.

[Blup]

Bitte für das Formular eine eigene Unit.
Damit kannst du dir eine Bibliothek schreiben, die wenger Abhängigkeiten hat.
Das erleichtert auch die Implementation von Testfällen.

Mal ein erster Ansatz:

Delphi-Quellcode:

unit CadVec3;

interface

uses
  Generics.Collections;

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

  TCadVec3List = TList<TCadVec3>;

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

  function IsListItemEqual(AItem1, AItem2: TCadVec3): Boolean;
  function IsListEqual(AList1, AList2: TCadVec3List; AOffset: Integer): Boolean;

  function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List): Boolean; overload;
  function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean; overload;
  function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List): Boolean; overload;
  function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean; overload;

  function CompareBothLists(AFirstList, ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;

implementation


function CompareBothLists(AFirstList, ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;
var
  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.
  if (AFirstList = nil) or (ASecondList = nil) then
    Exit(False);

  LFirstTmpList := TCadVec3List.Create;
  LSecondTmpList := TCadVec3List.Create;
  try
    LFirstTmpList.AddRange(AFirstList);
    LSecondTmpList.AddRange(ASecondList);
    RemoveIdenticalFromList(LFirstTmpList, AFirstListOpen);
    RemoveIdenticalFromList(LSecondTmpList, ASecondListOpen);

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

      Result := CompareOpenPolygons(LFirstTmpList, LSecondTmpList, ADirectional)
    end
    else
    begin
      if AFirstListOpen then
      begin
        if not IsListItemEqual(LFirstTmpList.First, LFirstTmpList.Last) then
          Exit(False);

        LFirstTmpList.Delete(LFirstTmpList.Count - 1);
      end
      else if ASecondListOpen then
      begin
        if not IsListItemEqual(LSecondTmpList.First, LSecondTmpList.Last) then
          Exit(False);

        LSecondTmpList.Delete(LSecondTmpList.Count - 1);
      end
      else // if not AFirstListOpen and not ASecondListOpen then
      begin
        if LFirstTmpList.Count <> LSecondTmpList.Count then
          Exit(False);
      end;

      Result := CompareClosedPolygon(LFirstTmpList, LSecondTmpList, ADirectional);
    end;
  finally
    LSecondTmpList.Free;
    LFirstTmpList.Free;
  end;
end;

function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List): Boolean;
var
  i: Integer;
begin
  // Vergleich von geschlossenen Polygonen bzw. einem offenen und einem geschlossenen Polygon.
  for i := 0 to ASecondList.Count - 1 do
  begin
    if IsListItemEqual(AFirstList[0], ASecondList[i]) then
    begin
      if IsListEqual(AFirstList, ASecondList, i) then
        Exit(True);
    end;
  end;
  Result := False;
end;

function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean;
begin
  Result := CompareClosedPolygon(AFirstList, ASecondList);
  if (not Result) and ADirectional then
  begin
    ASecondList.Reverse;
    Result := CompareClosedPolygon(AFirstList, ASecondList);
    ASecondList.Reverse;
  end;
end;

function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List): Boolean;
begin
// Vegleich von zwei offenen Polygonen.
  Result := IsListEqual(AFirstList, ASecondList, 0);
end;

function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List;
  ADirectional: Boolean): Boolean;
begin
  Result := CompareOpenPolygons(AFirstList, ASecondList);
  if (not Result) and ADirectional then
  begin
    ASecondList.Reverse;
    Result := CompareOpenPolygons(AFirstList, ASecondList);
    ASecondList.Reverse;
  end;
end;

function IsListEqual(AList1, AList2: TCadVec3List; AOffset: Integer): Boolean;
var
  i1, i2, iCount: Integer;
begin
// AOffset .. StartIndex in List2,
  iCount := AList2.Count;
  i2     := AOffset;
  for i1 := 0 to AList1.Count - 1 do
  begin
    if not IsListItemEqual(AList1[i1], AList2[i2]) then
      Exit(False);

    i2 := (i2 + 1) mod iCount;
  end;
  Result := True;
end;

function IsListItemEqual(AItem1, AItem2: TCadVec3): Boolean;
begin
  Result := (AItem1.x = AItem2.x) and (AItem1.y = AItem2.y) and (AItem1.z = AItem2.z);
end;

procedure RemoveIdenticalFromList(AList: TCadVec3List; AOpen: Boolean);
var
  i: Integer;
begin
// Entferne doppelte, aufeinander Folgende Eintr�ge bzw. Elemente.
  for i := AList.Count - 1 downto 1 do
  begin
    if IsListItemEqual(AList[i], AList[i - 1]) then
      AList.Delete(i);
  end;

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

end.