Changeset 165 for trunk/UMap.pas

Timestamp:

Nov 22, 2017, 4:48:33 PM (7 years ago)

Author:

chronos

Message:

• Added: Optimization phase for voronoi map generation.

File:

• trunk/UMap.pas (modified) (4 diffs)

trunk/UMap.pas

@@ -271 +271 @@
   Intersection: TPoint;
   CellDistance: TCellsDistance;
-  R1, R2: TRect;
   Cell: TCell;
-  CellsAngle: TObjectList; // TObjecTList<TCellsDistance>
-  CellAngle: TCellsDistance;
-  NextCellAngle: TCellsDistance;
   L1, L2: TLine;
   MP: TPoint;
   LinkLine: TLine;
   Polygon: TPolygon;
+  //LeftLink: TCellsDistance;
+  //CenterLink: TCellsDistance;
+  //RightLink: TCellsDistance;
+  LeftClosingLine1: TLine;
+  LeftClosingLine2: TLine;
+  RightClosingLine1: TLine;
+  RightClosingLine2: TLine;
+  CurrentAngle: Double;
+  LeftAngle: Double;
+  RightAngle: Double;
+  CenterCell: TCell;
+  LeftCell: TCell;
+  RightCell: TCell;
+  LeftIndex: Integer;
+  RightIndex: Integer;
+  LeftCenterCell: TCell;
+  RightCenterCell: TCell;
+  ChangesCount: Integer;
+  LeftCellCommon: TCell;
+  RightCellCommon: TCell;
+  LeftText: string;
+  RightText: string;
 begin
   Clear;
-
-  // Allocate and init new
+  RandSeed := 1234;
+
+  // Allocate and init new cells
   Cells.Count := Size.Y * Size.X;
   for Y := 0 to Size.Y - 1 do
@@ -325 +344 @@
         TCellsDistance(SelectedCells[J]).Cell2.PosPx);
       if LineIntersect(L1, L2, Intersection) then begin
-          R1 := PointsToRect(TCellsDistance(CellsDistance[I]).Cell1.PosPx,
-            TCellsDistance(CellsDistance[I]).Cell2.PosPx);
-          R2 := PointsToRect(TCellsDistance(SelectedCells[J]).Cell1.PosPx,
-            TCellsDistance(SelectedCells[J]).Cell2.PosPx);
-          if PointInRect(Intersection, R1) and PointInRect(Intersection, R2) then begin
-            Intersected := True;
-            Break;
-          end;
+        if PointInRect(Intersection, L1.ToRect) and
+        PointInRect(Intersection, L2.ToRect) then begin
+          Intersected := True;
+          Break;
         end;
+      end;
     end;
     if not Intersected then SelectedCells.Add(CellsDistance[I]);
@@ -348 +364 @@
   FreeAndNil(SelectedCells);
   FreeAndNil(CellsDistance);
+  SortNeighborsByAngle;
+
+  while True do begin
+  ChangesCount := 0;
+  // Optimize link lines for lower angle
+  for Cell in Cells do begin
+    // Change link if lower angle can be achieved
+    for I := 0 to Cell.Neighbors.Count - 1 do begin
+      LeftCell := Cell.Neighbors[I];
+      RightCell := Cell.Neighbors[(I + 1) mod Cell.Neighbors.Count];
+      LeftText := LeftCell.Neighbors.ToString;
+      RightText := RightCell.Neighbors.ToString;
+      LeftIndex := LeftCell.Neighbors.IndexOf(Cell);
+      RightIndex := RightCell.Neighbors.IndexOf(Cell);
+      LeftCellCommon := LeftCell.Neighbors[(LeftIndex + LeftCell.Neighbors.Count - 1) mod LeftCell.Neighbors.Count];
+      RightCellCommon := RightCell.Neighbors[(RightIndex + 1) mod RightCell.Neighbors.Count];
+      if (LeftCellCommon = RightCell) and
+      (RightCellCommon = LeftCell) then begin
+        LeftCenterCell := LeftCell.Neighbors[(LeftIndex + LeftCell.Neighbors.Count - 2) mod LeftCell.Neighbors.Count];
+        RightCenterCell := RightCell.Neighbors[(RightIndex + 2) mod RightCell.Neighbors.Count];
+
+        if LeftCenterCell = RightCenterCell then begin
+          CenterCell := LeftCenterCell;
+
+          LeftClosingLine1 := TLine.Create(LeftCell.PosPx, Cell.PosPx);
+          LeftClosingLine2 := TLine.Create(LeftCell.PosPx,
+            CenterCell.PosPx);
+          LeftAngle := SubAngle(LeftClosingLine1.GetAngle,
+            LeftClosingLine2.GetAngle);
+
+          RightClosingLine1 := TLine.Create(RightCell.PosPx, Cell.PosPx);
+          RightClosingLine2 := TLine.Create(RightCell.PosPx,
+            CenterCell.PosPx);
+          RightAngle := SubAngle(RightClosingLine2.GetAngle,
+            RightClosingLine1.GetAngle);
+
+          LeftClosingLine1 := TLine.Create(Cell.PosPx, LeftCell.PosPx);
+          RightClosingLine1 := TLine.Create(Cell.PosPx, RightCell.PosPx);
+          CurrentAngle := SubAngle(RightClosingLine1.GetAngle,
+            LeftClosingLine1.GetAngle);
+          if (CurrentAngle > LeftAngle) and (CurrentAngle > RightAngle) then begin
+            LeftCell.DisconnectFrom(RightCell);
+            Cell.ConnectTo(CenterCell);
+            SortNeighborsByAngle;
+            Inc(ChangesCount);
+          end;
+        end;
+        //end;
+      end;
+    end;
+  end;
+  if ChangesCount = 0 then Break;
+  end;
 
   // Compute polygon around cells with sequence sorted by link angle
   for Cell in Cells do begin
-    CellsAngle := TObjectList.Create;
-    for I := 0 to Cell.Neighbors.Count - 1 do begin
-      CellAngle := TCellsDistance.Create;
-      CellAngle.Cell1 := Cell;
-      CellAngle.Cell2 := TCell(Cell.Neighbors[I]);
-      CellAngle.Distance := ArcTan2Point(Point(
-        CellAngle.Cell2.PosPx.X - CellAngle.Cell1.PosPx.X,
-        CellAngle.Cell2.PosPx.Y - CellAngle.Cell1.PosPx.Y));
-      CellsAngle.Add(CellAngle);
-    end;
-    CellsAngle.Sort(CompareDistance);
-
     // Use whole map first for cell polygon
-    if CellsAngle.Count > 0 then begin
+    if Cell.Neighbors.Count > 0 then begin
       Polygon := TPolygon.Create(Rect(0, 0,
         Size.X * DefaultCellSize.X, Size.Y * DefaultCellSize.Y));
-      for I := 0 to CellsAngle.Count - 1 do begin
-        CellAngle := TCellsDistance(CellsAngle[I]);
-        LinkLine := TLine.Create(CellAngle.Cell1.PosPx,
-          CellAngle.Cell2.PosPx);
+      for I := 0 to Cell.Neighbors.Count - 1 do begin
+        LinkLine := TLine.Create(Cell.PosPx,
+          Cell.Neighbors[I].PosPx);
+        LinkLine.Distance := LinkLine.Distance - 4;
         MP := LinkLine.GetMiddle;
         // Create half plane vector
-        L1 := TLine.Create(MP, Point(MP.X + LinkLine.GetSize.X, MP.Y + LinkLine.GetSize.Y));
+        L1 := TLine.Create(MP, Point(MP.X + LinkLine.GetSize.X,
+          MP.Y + LinkLine.GetSize.Y));
 
         Polygon.CutLine(L1, Cell.PosPx);
@@ -379 +437 @@
       Cell.Polygon := Polygon.Points;
     end else SetLength(Cell.Polygon, 0);
-
-    FreeAndNil(CellsAngle);
   end;