Wenn ich eine beliebige Menge von Punkten, und dann die gleiche Reihe von Punkten um ein gewisses Maß gedreht hat, weiß jemand von Algorithmen zu berechnen/zu schätzen, wo das Zentrum der Rotation ist ? Oder ein Bereich des Studiums, in dem diese Art von Algorithmen benötigt wird? Ich habe Probleme, relevante Informationen zu finden.Suchen Drehpunkt für eine Reihe von Punkten
Dank
Hier können Sie einen Punkt (x, y) sagen haben, das zu (x 'y') bewegt.
Dann muss der Rotationsmittelpunkt auf der Linie liegen, die senkrecht auf (x, y) - (x ', y') steht und die den Mittelpunkt (x, y) - (x ', y') schneidet .
Jetzt nimm einen anderen Punkt, (x2, y2), der sich nach (x'2, y'2) bewegte. Daraus ergibt sich auch eine Linie, auf der sich der Drehpunkt befinden muss.
Jetzt nehmen Sie diese zwei Zeilen und berechnen Sie die Kreuzung. Dort haben Sie das Drehzentrum.
Update: Wenn Sie nicht die Korrespondenz haben, welcher Punkt wo ging, sollte es nicht zu schwer sein, herauszufinden. Hier ist ein Vorschlag von oben: Finde den Schwerpunkt der "Vorher" -Punkte. Ordne die Punkte entsprechend ihrer Entfernung von diesem Punkt. Jetzt mache dasselbe mit den "Nachher" -Punkten. Die Reihenfolge der beiden Sets sollte nun übereinstimmen. (Der Punkt am nächsten zum Zentrum der Massen vor Rotation sollte der Punkt am nächsten an die Mitte der Masse seine nach Rotation.)
Dieser Algorithmus ist gut, wenn er die Beziehung zwischen Punkten kennt. in zwei verschiedenen Artikeln. –
Das ist ein guter Prozess, wenn Sie die Korrelation zwischen den Punkten verstehen, dh wenn sie beschriftet sind, aber wenn sie vorher und nachher willkürlich sind, wird die Frage viel schwieriger (aufgrund des Identitätsproblems; wie identifizieren Sie das? Punkt ist der gleiche vor und nach der Rotation?). –
Wer sagt, er hat nicht? Und selbst wenn er diese Beziehung nicht hat, muss er es herausfinden, bevor er das ganze Problem löst, und von dem Punkt an, an dem er es herausgefunden hat, wird ihm dieser Algorithmus helfen. – aioobe
Sehr interessantes Problem. Mein Wissen darüber ist etwas veraltet, aber soweit ich mich erinnere, gibt es einige Untersuchungen in der Verwendung von Subgraph-Analysen dazu; das heißt, Unterabschnitte des Satzes von Punkten durch die Abstände zwischen den Punkten und den Varianzen darin zu charakterisieren und dann diese Untergraphenanalysen zwischen den Vorher- und Nachher-Drehungen zu korrelieren.
Dies ist natürlich eine sehr komplexe Menge von Punkten mit einer ungleichmäßigen Verteilung angenommen.
Es wäre verrückt Overkill für diese Art von Problem, aber ich denke, die Funktionalität der generalized Hough transform für die Objekterkennung umfasst zumindest, was Sie wollen, auch wenn es nicht ganz für diesen Zweck gedacht ist.
Mit einer beliebigen Form, die aus einer Menge von Punkten und einer anderen beliebigen Menge von Punkten erstellt wurde, wird versucht, die Form in der Menge der Punkte zu finden, obwohl sie gedreht, skaliert und übersetzt wurde. Sie können möglicherweise die Skalierung und Übersetzung herausnehmen und bekommen, was Sie wollen.
Grundsätzlich käme es darauf an, rohe Kräfte zu erzwingen, um mögliche Punkte zu finden, die am besten zu den zweiten Punkten passen.
Sie müssen eine Signatur in Ihrem Datensatz finden, die es ermöglicht, die Punkte aus dem ersten Satz (A) mit denen auf dem zweiten Satz (B) zu identifizieren.
Ein einfacher Weg ist wie folgt:
Für jedes Element E in A, finden die beiden nächsten Punkte (N1, N2) und berechnen den Winkel zwischen N1, E, N2 in drei Werten resultierende: der Winkel und die Abstände von E zu N1 und N2 (ang, d1, d2).
Finden Sie 3 Punkte in A mit eindeutigen Tupeln (ang, d1, d2).
Für jedes Element in B berechnen Sie auch den Abstand zu seinen beiden nächsten Nachbarn und den Winkel. Finden Sie die 3 Punkte, die mit denen von A übereinstimmen.
Die Berechnung der Drehung ist nur eine Frage der geometrischen Analyse.
Update: Sie müssen 3 Punkte die Rotation im 3D-Raum zu bestimmen. In 2D werden zwei tun.
update 2: wie andere andere Beiträge kommentiert haben, kann es Symmetrien in A geben, die Sie daran hindern würden, die 3 einzigartigen Tripletts für (ang, d1, d2) zu finden. In diesem Fall müssen Sie für jeden der drei ausgewählten Punkte in A eine Suche über alle Elemente in B durchführen, die ihren Triplets entsprechen, bis eine Kombination zu einer Drehung führt, die für alle Elemente in A gilt.
Die Erde dreht sich um ihre Achse. Es bewegt sich um die Sonne. Worauf beziehen Sie sich? –
Ist die Übereinstimmung zwischen den Punkten bekannt? – nav
Diese Frage scheint off-topic zu sein, weil es um Mathematik geht, nicht um Programmierung. – bmargulies