Wie man einen Punkt auf einem verzogenen Raster zur Karte

Question

Angenommen, Sie haben eine Sammlung von Punkten mit Koordinaten auf einem kartesischen Koordinatensystem.

Sie möchten einen weiteren Punkt zeichnen, und Sie wissen, seine Koordinaten in der gleichen kartesischen Koordinatensystem.

Doch die Handlung Sie zeichnen auf aus dem Original verzerrt. Stellen Sie sich das Original ende Flugzeug, das Drucken auf einem Gummiblatt und Stretching es an einigen Stellen und Kneifen es in anderen, in einer asymmetrischen Art und Weise (keine Überlappung oder etwas komplexe).

( Quelle )

Sie kennen die gestreckt und ungereckten Koordinaten jedes Ihrer Menge von Punkten, aber nicht die zugrunde liegende Strecke Funktion. Sie kennen die ungereckten Koordinaten eines neuen Punktes.

Wie kann man abschätzen, wo den neuen Punkt in den gestreckten Koordinaten auf den gestreckten Positionen von nahen Punkten basierend plotten? Es muss nicht exakt sein muß, da Sie die aktuelle Strecke Funktion aus einer Menge von neu zugeordneten Punkten nicht feststellen können, wenn Sie mehr Informationen haben.

andere mögliche Suchbegriffe: verzogen verzerrt Gitternetz-Koordinatenebene Verzerrung rückgängig

Answer 1

Ok, so klingt wie Imagewarping. Dies ist, was Sie tun sollten:

1. Erstellen Sie eine Delaunay-Triangulation Ihres unwarped Raster und verwenden Sie Ihr Wissen über die Korrespondenzen zwischen den verzogenen und unverzerrten Gittern der Triangulierung des verzogenen Raster zu erstellen. Jetzt kennen Sie die entsprechenden Dreiecken in jedem Bild, und da es keine Überlappung ist, sollten Sie in der Lage, den nächsten Schritt ohne große Schwierigkeiten durchzuführen.

2. Nun, den entsprechenden Punkt A zu finden, in dem verzerrten Bild:

   1. Finden Sie das Dreieck A liegt in und um die Transformation zwischen dem Dreieck in dem unwarped Gitter verwenden und das verzerrte Raster, um die neue Position zu verstehen.

Dies erklärt sich im Einzelnen noch explizit hier .

Weitere (viel komplizierter) Methode ist die Thin Plate Spline (was auch erklärt in den Folien oben).

Answer 2

ich verstand, dass Sie eine Eins-zu-Eins-Entsprechung zwischen den verpackten und unverpackten Gitterpunkten. Und ich nehme an, dass die Verformung nicht so extrem ist, dass man sich schneidenden Gitterlinien haben könnten (wie das Bild, das Sie zeigen).

Die Strategie ist genau das, was Jacob schlägt vor: Triangulate die beiden Gitter, so daß es eine Eins-zu-Eins-Entsprechung zwischen Dreiecke, suchen den Punkt in der Triangulation abgebildet wird und dann baryzentrischen Koordinaten in dem entsprechenden Dreieck verwenden die berechnen neue Punktposition.

Preprocess

1. Erstellen Sie den Delaunay-Triangulation der Punkte des Gitters eingewickelt, nennen wir es WT.
2. Für jedes Dreieck in WT ein Dreieck zwischen den entsprechenden Scheiteln im ungeöffneten grid hinzuzufügen. Daraus ergibt sich eine Triangulation UWT der ungeöffneten Punkte.

Karte einen Punkt p in das ummantelte Gitter

1. Finden Sie das Dreieck T(p1,p2,p3) im UWT die p enthält.
2. Berechnen Sie die baryzentrischen Koordinaten (b1,b2,b3) von p in T(p1,p2,p3)
3. Lassen Sie Tw(q1,q2,q3) das Dreieck in WT sein entsprechend T(p1,p2,p3). Die neue Position ist
   b1 * q1 + b2 * q2 + b3 * q3.

Bemerkungen Daraus ergibt sich eine Funktion wie eine Deformation rel="nofollow lineare Splines. Für glattere Verhalten könnte man die gleiche Triangulation verwenden, aber höhere Ordnung Annäherung tun, was ein bisschen komplizierte Berechnung anstelle der baryzentrischen Koordinaten führen würde.

Answer 3

Die anderen Antworten sind groß. Das einzige, was ich noch hinzufügen möchte, ist, dass Sie einen Blick auf nehmen möchten Freiform-Deformation als eine Möglichkeit, die Verformungen der Beschreibung.

Wenn das nützlich ist, dann ist es durchaus möglich, eine Verformung Raster / Gitter zu Ihrem bekannten Paar zu passen, und dann haben Sie eine sehr schnelle Methode der zukünftigen Punkte zu verformen.

Answer 4

Viel hängt davon ab, wie viele bestehende Punkte, die Sie haben. Wenn Sie nur einen haben, gibt es nicht wirklich viel kann man damit machen - den zweiten Punkt um den gleichen Betrag in der gleichen Richtung versetzt, aber Sie haben nicht genug Daten, um wirklich besser zu machen als die

Wenn Sie eine angemessene Anzahl von vorhandenen Punkte haben, können Sie eine Oberfläche fit durch diese Punkte tun, und verwenden Sie, dass die richtige Position des neuen Punktes anzunähern. Gegeben N Punkte, können Sie immer eine perfekte Passform erhalten einen Auftrag N Polynom, aber Sie wollen nur selten, das zu tun - stattdessen Sie in der Regel vermuten, dass die Strecke Funktion ist eine ziemlich niedrige Ordnung Funktion (zB quadratisch oder kubisch) und fit eine Oberfläche, auf die Punkte auf dieser Basis. Sie legen Sie dann Ihren neuen Punkt auf der Grundlage der Funktion für Ihre angepasste Oberfläche.