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

[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.