Ähnlichkeit zweier Polygone bestimmen

  • VB.NET
  • .NET (FX) 4.5–4.8

Es gibt 50 Antworten in diesem Thema. Der letzte Beitrag () ist von Mokki.

    Eine Idee mit Strecken und Winkel für einfache Polygone:
    1. Zuerst muss die Größe angeglichen werden. Man setzt die längste oder kürzeste Seite der beiden Polygone gleich und skaliert alle anderen Kanten entsprechend (Dreisatz).
    2. Dann nimmt man jeweils einen beliebigen Knoten jedes Polygons & setzt den in den Ursprung, die erste Gerade ist parallel zur x-Achse, alle anderen Punkte ergeben sich daraus.
    3. Man errechnet die Differenzen in x- & y-Richtung jedes Knotenpaars und erhält die Summe der Differenzen.
    4. Das wiederholt man mit allen Knotenpaaren. Bei dem Ergebnis mit der geringsten Differenz sind beide Polygone bestmöglich ausgerichtet.
    5. Man bestimmt einen Schwellwert der Differenz, der unterschritten werden muss, damit zwei Polygone als gleich gelten.
    Die Lösung funktioniert nur bei Polygonen mit gleicher Knotenanzahl und der Rechenaufwand steigt stark mit zunehmender Komplexität. Allerdings könnte man ein iteratives Verfahren nutzen, bei dem Teillösungen bewertet werden und nicht alle Kombinationen durchgerechnet werden müssen.

    Das mit dem Prozentwert ist so eine Sache. Man müsste überhaupt erst einmal ein Maß für die Ähnlichkeit bestimmen, mit dem man dann die Ähnlichkeit in % berechnet.
    Einfach nur irgendein Wert hat keinerlei Aussagekraft.
    Option strict = on

    If it's stupid and it works it ain't stupid.

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

    Genau. Neben der Ähnlichkeit kannst du auch prüfen, ob ein Polygon in mehr als einer Ausrichtung übereinstimmt & man kann auf Teilübereinstimmungen prüfen.
    Es kann ja beispielsweise sein, dass die Hälfte der beiden Polygone fast deckungsgleich ist und die andere stark variiert. Da könnte man sogar recht einfach ein %-Wert berechnen.
    Beispielsweise bis zu 60% des Umrisses ist deckungsgleich.

    Es dürfe auch recht leicht sein, Mehrkern-CPUs zu nutzen, da ja die gleiche Berechnung in einer Schleife läuft und die Ergebnisse anschließend verglichen werden. Da kann man die Ausgangspunkte auf die Threads aufteilen.
    Option strict = on

    If it's stupid and it works it ain't stupid.

    ob ein Polygon in mehr als einer Ausrichtung übereinstimmt

    Wie meinst du das genau? Das mit Teilübereinstimmung kann ich später noch optimieren. Denkst du es wäre besser mit Längen zu arbeiten oder mit Punkten?

    EDIT: Habe noch das hier gefunden: en.wikipedia.org/wiki/Cosine_similarity
    Das sieht mir auch sehr hilfreich aus, könnte man daraus etwas machen?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „xd-franky-5“ ()

    Es gibt rotationssymmetrische Polygone. Wenn du beispielsweise zwei Polygone hast, bei denen jeweils alle Strecken gleich lang sind und die Eckpunkte auf einem Kreis liegen, sind alle Lösungen aus dem oben genannten Algorithmus optimal.

    Ich würde übrigens die Koordinaten der Eckpunkte berechnen. Wenn du die hast sind Strecken und Winkel egal.

    Ps: Auch wenn ich recht optimistisch bin, dass man mit der Methode ein Ergebnis erreichen kann, gibt es bestimmt deutlich effizientere Wege.
    Option strict = on

    If it's stupid and it works it ain't stupid.

    @Nils_Kr Ah okay, verstehe. Ich habe die Koordinaten bereits, ich müsste halt davon die Strecken berechnen um sie gleichzusetzen und daraus dann wieder Koordinaten.
    Okay ich kann's ja später mal so probieren und beide auf Effizienz prüfen, kommt immer gut in Ausarbeitungen :D

    Im Endeffekt wird es am effizientesten sein die Koordinaten selbst zu transformieren. Man setzt eine Koordinate in den Ursprung und die nächste auf die x-Achse, alle anderen Koordinaten werden dann entsprechend transformiert.

    Aber aus dem stehgreif kann ich dir nicht sagen, wie man das macht, dafür ist Mathe zu lange her bei mir.
    Option strict = on

    If it's stupid and it works it ain't stupid.

    Ich habe die ersten 2 Schritte mal so verwirklicht, aber noch nicht getestet:

    VB.NET-Quellcode

    1. Dim first As Integer = CInt(Console.ReadLine.ToString)
    2. Dim second As Integer = CInt(Console.ReadLine.ToString)
    4. Dim comppols As List(Of Polygon) = {polygons(first), polygons(second)}.ToList
    5. Dim shortest As Integer = 0
    6. For Each pol In comppols
    7. Dim ds As Double = 0
    8. For i = 0 To pol.Points.Count - 2 Step 2
    9. Dim p1 As Point = pol.Points(i)
    10. Dim p2 As Point = pol.Points(i + 1)
    11. Dim d As Double = Math.Sqrt((p2.Y - p1.Y) ^ 2 + (p2.X - p1.X) ^ 2)
    12. If d < ds Or ds = 0 Then
    13. ds = d
    14. shortest = i
    15. End If
    16. Next
    17. Next
    19. polygons(first) = SetPolygonToOrigin(polygons(first), shortest)
    20. polygons(first) = RotatePolygonToPoint(polygons(first), shortest)
    22. Dim difference As Double = 0
    23. For i = shortest To polygons(second).Points.Count + shortest - 1
    24. Dim index As Integer = i Mod polygons(second).Points.Count
    25. polygons(second) = SetPolygonToOrigin(polygons(second), index)
    26. polygons(second) = RotatePolygonToPoint(polygons(second), index)
    28. Dim diff As Double = 0
    29. For k = 0 To polygons(first).Points.Count - 1
    30. Dim p1 As Point = polygons(first).Points(k)
    31. Dim p2 As Point = polygons(second).Points(k)
    32. diff += Math.Sqrt((p2.Y - p1.Y) ^ 2 + (p2.X - p1.X) ^ 2)
    33. Next
    34. If diff < difference Or difference = 0 Then difference = diff
    35. Next
    37. Console.WriteLine(difference)
    38. Console.ReadLine()


    In der ersten schleife ermittle ich die kürzeste Kante, in der zweite setze ich alle an den Ursprung(mit Fokus auf die Kürzeste Kante) und in der Dritten rotiere ich alle Punkte passend. Siehe de.wikipedia.org/wiki/Koordinatentransformation

    EDIT: der Code war nicht ganz richtig, aber er scheint nun zu funktionieren. Also wenn ich 2 identische Polygone miteinander vergleiche kommt 0 raus.
    EDIT: Okay jetzt ist er fertig, mal schauen wie er sich so tut.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „xd-franky-5“ ()

Facebook
Telefonspende