Anordnung von Quadraten, in Rechtecke zusammenfassen.

  • C#
  • .NET (FX) 4.5–4.8

Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von φConst.

    Anordnung von Quadraten, in Rechtecke zusammenfassen.

    Hallo,
    gegeben sei folgendes Kachel-Feld:



    Wie würdet ihr vorgehen, um am effektivsten die rot markierten Kacheln entsprechend in optimal große Rechtecke zu unterteilen? (Mit anderen Worten: Die Kacheln optimal in Rechtecke zusammenfassen).

    Mir kam ein Ansatz mit genetischen Algorithmus in den Sinn, dessen Fitness-Funktion exemplarisch ANZAHL_KACHELN_IM_RECHTECK/(A*B), wobei jeweils A und B die Seiten des Rechtecks repräsentieren, sein könnte..
    Gäbe es aber vielleicht eine idealere Herangehensweise?

    Danke!
    Und Gott alleine weiß alles am allerbesten und besser.

    ich trau dem genetischen Hype nicht so - ich würde erstma was "konventionelles" versuchen:
    Ich würde alle möglichen grössten Rechtecke ermitteln, dabei Dubletten eliminieren.
    Dann überlappen sich die Rechtecke noch, aber da würdich einen Algo anwenden, der bei Überlappung eines der beiden Rechtecke beschneidet. Beim Beschneiden gibts immer genau 2 sinnvolle Möglichkeiten, und da kann man testen, welche die günstigere ist.
    Ich denke, der Algo müsste ein optimales Ergebnis generieren.

    Spasseshalber kannste mal hier gugge: codeproject.com/Articles/1209269/Not-Levenshtein
    Dort tritt ein entfernt vergleichbares Problem mit Diagonalen auf (Abschnitt "Eliminate overlapping matches"), bei denen auftreten kann, dass nur entweder die eine oder die annere in voller Länge gültig sein kann, und mein Algo sorgt dafür, dass die längere Diagonale bevorzugt wird. Also da tätige ich ähnlich verschrobene Gedankengänge.

    PS: der von mir skizzierte Algo ergäbe aus deim Beispiel eine Aufteilung in 7 Rechtecke - findest du eine bessere Lösung?

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

    @φConst Wenn es vorrangig um die Darstellung geht, gugst Du Region: docs.microsoft.com/de-de/dotne…N&view=netframework-4.7.2
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    @RodFromGermany Was genau meinst du?
    Es geht eher um die strukturelle Partitionierung: Die roten Felder sollen einfach jeweils in Rechtecke zerteilt werden,
    sodass alle Kacheln in Rechtecken zusammengefasst sind.
    Idealerweise sollen aber alle Rechtecke optimal groß sein, das heißt, jedes Rechteck soll optimal viele Kacheln halten.

    Im obigen Beispiel:

    1. Rechteck: 12 Kacheln
    2. Rechteck: 1 Kachel
    3. Rechteck: 1 Kachel
    4. Rechteck: 3 Kacheln
    5. Rechteck: 1 Kachel
    6: Rechteck: 1 Kachel
    7. Rechteck: 1 Kachel

    ErfinderDesRades schrieb:

    PS: der von mir skizzierte Algo ergäbe aus deim Beispiel eine Aufteilung in 7 Rechtecke - findest du eine bessere Lösung?

    Ja, 7 wären optimal.

    Addendum: Ich hatte folgende Idee jetzt:
    Im Grunde betrachtet man die Kacheln-Form, als ein Polygon. Man verbinde alle Ecken jeweils miteinander.
    Existieren zwei schneidende Diagonalen, mit derselben Länge, handelt es sich um ein Rechteck.

    Hättet ihr eine alternative Idee?
    Und Gott alleine weiß alles am allerbesten und besser.

    Dieser Beitrag wurde bereits 4 mal editiert, zuletzt von „φConst“ ()

    φConst schrieb:

    Was genau meinst du?
    So was:
    UserControl mit einer zur Laufzeit anpassbaren Form
    Das ist wahrscheinlich nicht das, wonach Du suchst.
    Vielleicht eine solche Herangehensweise:
    Nimm einen inneren Punkt und finde alle Nachbarn, die ein Rechteck ergeben (etwa eine "Spirale" drum herum legen, jede Seite im eine Reihe / Spalte erweitern).
    Wenn Du am Ende bist, nimmst Du einen nächsten noch nicht erwischten inneren Punkt ...
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hallo φConst,
    du kannst aus deinem Kachel-Feld eine Region erstellen. Jede Region
    wird als eine Liste von Rechtecken gespeichert. Diese Liste kann man
    auslesen. Ich habe sowas vor einigen Jahren mal in VBA programmiert. Hier
    der an dein Kachel-Feld angepasste Code, lauffähig z.B. unter MS-Word:

    Visual Basic-Quellcode

    1. Private Type RECT
    2. Left As Long
    3. Top As Long
    4. Right As Long
    5. Bottom As Long
    6. End Type
    8. Private Const RGN_OR = 2
    10. Private Declare Function CreateRectRgn Lib "gdi32" (ByVal x1 As Long, ByVal y1 As Long, ByVal x2 As Long, ByVal y2 As Long) As Long
    11. Private Declare Function CombineRgn Lib "gdi32" (ByVal hDestRgn As Long, ByVal hSrcRgn1 As Long, ByVal hSrcRgn2 As Long, ByVal nCombineMode As Long) As Long
    12. Private Declare Function DeleteObject Lib "gdi32" (ByVal hObject As Long) As Long
    13. Private Declare Function GetRegionData Lib "gdi32" (ByVal hRgn As Long, ByVal dwCount As Long, lpRgnData As Any) As Long
    15. Private Sub UserForm_Activate()
    17. Dim i As Long, j As Long, Fd(5) As String
    18. Dim Rgn1 As Long, Rgn2 As Long, Rgn3 As Long, Field As Long
    19. Dim x1 As Long, y1 As Long, N1 As Long, N2 As Long, Buffer() As RECT
    20. Dim x2 As Long, y2 As Long, flg1 As Boolean, Out As String
    22. Fd(0) = " ## "
    23. Fd(1) = " ### ## "
    24. Fd(2) = " ## # "
    25. Fd(3) = " ##### "
    26. Fd(4) = " ## "
    27. Fd(5) = " ### "
    29. Field = 20 ' Feldgröße
    30. Rgn1 = CreateRectRgn(0, 0, 0, 0)
    31. Rgn2 = CreateRectRgn(0, 0, 0, 0)
    32. For i = 0 To UBound(Fd)
    33. For j = 0 To Len(Fd(i)) - 1
    34. If Mid$(Fd(i), j + 1, 1) = "#" Then
    35. x1 = j * Field
    36. y1 = i * Field
    37. Rgn3 = CreateRectRgn(x1, y1, x1 + Field, y1 + Field)
    38. Call CombineRgn(Rgn1, Rgn1, Rgn3, RGN_OR)
    39. Call DeleteObject(Rgn3)
    40. Rgn3 = CreateRectRgn(y1, x1, y1 + Field, x1 + Field)
    41. Call CombineRgn(Rgn2, Rgn2, Rgn3, RGN_OR)
    42. Call DeleteObject(Rgn3)
    43. End If
    44. Next j
    45. Next i
    47. N1 = GetRegionData(Rgn1, 0, ByVal 0)
    48. N2 = GetRegionData(Rgn2, 0, ByVal 0)
    49. If N2 < N1 Then
    50. flg1 = True
    51. ReDim Buffer(N2 / 16 - 1)
    52. Call GetRegionData(Rgn2, N2, Buffer(0))
    53. Else
    54. flg1 = False
    55. ReDim Buffer(N1 / 16 - 1)
    56. Call GetRegionData(Rgn1, N1, Buffer(0))
    57. End If
    58. Call DeleteObject(Rgn1)
    59. Call DeleteObject(Rgn2)
    61. Out = CStr(UBound(Buffer) - 1) & " Rechteck(e)" & vbCr & vbCr
    62. For i = 2 To UBound(Buffer)
    63. With Buffer(i)
    64. If flg1 = True Then
    65. x1 = .Top
    66. y1 = .Left
    67. x2 = .Bottom
    68. y2 = .Right
    69. Else
    70. x1 = .Left
    71. y1 = .Top
    72. x2 = .Right
    73. y2 = .Bottom
    74. End If
    75. End With
    76. Out = Out & "Rechteck " & CStr(i - 1) & ": x1=" & CStr(x1) & _
    77. " y1=" & CStr(y1) & " x2=" & CStr(x2) & " y2=" & CStr(y2) & vbCr
    78. Next i
    79. MsgBox Out
    81. End Sub
    Gruss,

    Neptun

    @Neptun Jetzt musst Du da nur noch .NET draus machen. ;)
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!