Transformiertes Rechteck/GraphicsPath auf Kollision prüfen

  • Allgemein

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von Gonger96.

    Transformiertes Rechteck/GraphicsPath auf Kollision prüfen

    Hey,ich sitze im Moment an einem kleinen Problem. Ich habe entweder ein Rechteck oder einen GraphicsPath und eine Matrix:
    Spoiler anzeigen

    Das Rechteck/Graphicspath wird darüber transformiert gezeichnet und ich würde gerne Wissen, wie ich prüfen kann ob ein Punkt sich darin befindet. Ich hatte gedacht, ich könnte einfach den Punkt mit der Inversen multiplizieren und dann per Rectangle.Contains() bzw. GraphicsPath.IsVisible() testen. Dass klappt auch, nur wenn es gescaled wird oder x & y geskewed/gesheared werden, schlägt's fehl. Rotation, Spiegelung, Scherung (x oder y) etc. laufen. Sogar Skewing (also Neigen) klappt für x oder y, nur beide zusammen klappt nicht, so ists auch beim Scheren von x & y und Skalieren allgemein. Da scheint's irgendwie verschoben zu sein. Gibt es eine andere Möglichkeit dort möglichst schnell auf Kollision zu prüfen?

    Grüße

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Gonger96“ ()

    Gonger96 schrieb:

    ob ein Punkt sich darin befindet.
    prüfst Du, indem Du diesen Punkt genau so transformierst (z.B. als alle 4 Ecken eines Rechtecks) und dann mit Contains oder so rangehst.
    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!

    Also ich hab vor einer Weile nen Snippet gefunden womits ging (hatte nen ähnliches prob.):

    VB.NET-Quellcode

    1. Public Function Collide(pBody As Rectangle) As Boolean
    2. Using MRegion As New Region(_graPath) '_graPath = Path der auf Kollision geprüft werden soll
    3. Using MPath As New GraphicsPath
    4. MPath.AddRectangle(pBody)
    5. Using PlayerRegion As New Region(MPath)
    6. PlayerRegion.Intersect(MRegion)
    7. Return PlayerRegion.GetRegionScans(New Matrix(1, 0, 0, 1, 0, 0)).Length > 0
    8. End Using
    9. End Using
    10. End Using
    11. End Function

    Das dürfte garnicht klappen. Tut es auch nicht. Wenn ich den Punkt aber mit der invertierten Matrix transformiere, dann klappt es für die meisten Transformationen. Nur Skalierung, Scherung und Neigung von X und Y schlägt fehl.

    @RushDen
    Das ist viel zu langsam und prüft ausserdem n ganzes Rechteck, ich brauche ja nur einen Punkt.

    Gonger96 schrieb:

    Nur Skalierung, Scherung und Neigung von X und Y schlägt fehl.
    Ein Punkt hat nun mal keine Neigung und kein Volumen.
    Fehlt bei Deiner Problembeschreibung irgendetwas?
    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!

    Ich versuchs nochmal zu erklären. Man hat bspw. ein Rechteck, dass um 45° rotiert ist (dafür Matrix m). Jetzt möchte ich wissen ob ein Punkt in diesem Rechteck ist. Ich habe den Punkt mit der Inversen zu m multipliziert und dann per Rectangle.Contains(TransformierterPunkt) getestet. Das klappt.

    Man kann das Rechteck aber auch Scheren um die X und die Y-Achse, ist nur um eine der beiden Achsen geschert, stimmt die Prüfung noch. Ist um X und Y-Achse geschert oder auch geneigt klappt es nicht mehr. Wenn das Rechteck skaliert ist funktioniert dies garnicht.

    Gonger96 schrieb:

    klappt es nicht mehr
    Dann ist da irgendwo ein Fehler.
    Stell mal Deine Trafo grafisch dar und gib die Parameter über ein paar Slider vor.
    Mach eine xy, xz und yz-Darstellung.
    Überzeuge Dich, dass das dann so aussieht, wie es aussehen soll.
    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!

    Es verhält sich so wie oben beschrieben. Man könnte ggf. auch die vier Eckpunkte des Rechtecks transformieren und als Polygon behandeln. Dafür müsste man dann irgendwie prüfen, ob der Punkt im Polygon liegt.

    Trotzdem verstehe ich nicht wieso dass mit dem transformierten Punkt bei 90% aller transformationen klappt nur bei 3 Spezialfällen nicht. Ich mache mal kurz ein Beispiel fertig.

    /Edit:
    Anscheinend ist meine Invert()-Methode der Matrix fehlerhaft. :/

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Gonger96“ ()

    Gonger96 schrieb:

    Anscheinend ist meine Invert()-Methode der Matrix fehlerhaft.

    Das wollte ich grad anmerken. Es gibt ein paar Invertierungs-Algorithmen im Netz, die "dummerweise" alle davon ausgehen, dass die Matrix, die invertiert werden soll, orthogonal ist. Dann braucht man nämlich nur Zeilen und Spalten zu vertauschen. Ist aber noch Scherung oder nicht-proportionale Skalierung mit im Spiel, muss man das anders berechnen. Hab den Algo grad nicht parat, aber in meiner Erinnerung spielen da noch die Determinanten der Sub-Matrizen eine Rolle...
    Weltherrschaft erlangen: 1%
    Ist dein Problem erledigt? -> Dann markiere das Thema bitte entsprechend.
    Waren Beiträge dieser Diskussion dabei hilfreich? -> Dann klick dort jeweils auf den Hilfreich-Button.
    Danke.

    Diese Matrixklasse hab ich nicht zur verfügung, sonst hätt' ichs in einem anderen Unterforum gepostet. Zuvor hatte ich die Matrix so invertiert
    A-1=1/|A| *
    [d -b]
    [-c a]
    Und das Offset einfach negiert. Genau dieses Offset wird falsch berechnet. Ich hab mir gedacht ich erweiter einfach die Matrix zu
    [a b 0]
    [c d 0]
    [e f 1] und invertiere diese.
    Spoiler anzeigen

    Ich hoffe das gibt mir dann die richtigen Ergebnisse.

    Gonger96 schrieb:

    und invertiere diese.
    Für 3-Reihige Matrizen gibt es doch geschlossene Algorithmen.
    Auf jeden Fall kannst Du ja mal per Zufallstzahlen eine Reihe von Matrizen invertieren, das FResultat mit der Ausgangsmatrix multiplizieren und auf Einheitsmatrix testen.
    Für den Fall der Singularität solltest Du noch die Determinante bestimmen, aber auch das ist elementar.
    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!

    Es scheint nun zu klappen, ich teste mal etliche Zufällige durch wie du gesagt hast. Momentan sieht's so aus

    C-Quellcode

    1. void matrix::invert()
    2. {
    3. if(get_determinant() == 0)
    4. throw logic_error("Matrix not invertible");
    5. float det = 1/get_determinant();
    6. *this = matrix(determinant(m22, 0, m32, 1)*det, determinant(0, m12, 1, m32)*det, determinant(0, m21, 1, m31)*det, determinant(m11, 0, m31, 1)*det, determinant(m21, m22, m31, m32)*det, determinant(m12, m11, m32, m31)*det);
    7. }

    Für die Matrix
    [m11 m12]
    [m21 m22]
    [m31 m32]

    Ja, ist sie. Direct2D und GDI+ benutzen intern auch eine 3x3 Matrix bzw. eine 2x2 Matrix + Offsetvektor. Die dritte Spalte kommt nur dazu damit ich die multiplizieren kann und jetzt auch zum Invertieren, fürs transformieren wird diese ignoriert und die dritte Zeile wird einfach als Vektor addiert. Es scheint aber jetzt zu funktionieren, bis auf ein paar Rundungsfehler ( 0.9999898 anstatt 1) und ein paar seltsame Ausreißer sieht's ganz gut aus.

Facebook