Wie berechnet sich der Spiegel Punkt entlang einer Linie?

Wenn Dinge wie, dass in computer-Programme, eines der Themen, die Sie vielleicht zu tun haben, ist die Durchführung dieser Berechnungen mit integer-Arithmetik nur (oder soviel wie möglich), vorausgesetzt, die Eingabe in ganzen zahlen. Dies zu tun, in ganzen zahlen, so viel wie möglich, ist eine separate Frage, die ich nicht abdecken hier.

Folgende ist eine "mathematische" Lösung, die umgesetzt werden, wenn buchstäblich benötigen floating-point-Berechnungen. Ich weiß nicht, ob dies akzeptabel ist, in Ihrem Fall. Optimieren Sie es nach Ihrem Geschmack selbst.

(1) Vertreten Ihre Linie L durch

A * x + B * y + C = 0

Gleichung. Beachten Sie, dass Vektor (A, B) ist der Normalenvektor dieser Linie.

Zum Beispiel, wenn die Linie wird durch zwei Punkte definiert X1(x1, y1) und X2(x2, y2), dann

A = y2 - y1
B = -(x2 - x1)
C = -A * x1 - B * y1

(2) Normalisieren die Gleichung durch Division aller Koeffizienten, die durch die Länge des Vektors (A, B). I. e. berechnen Sie die Länge

M = sqrt(A * A + B * B)

und dann die Werte berechnen

A' = A /M
B' = B /M
C' = C /M

Die Gleichung

A' * x + B' * y + C' = 0

ist noch eine äquivalente Gleichung der Linie L außer, dass jetzt der Normalenvektor (A', B') ist ein Einheitsvektor.

(3) Nehmen Sie Ihre Punkt P(px, py) und berechnen Sie den Wert

D = A' * px + B' * py + C'

Dies gibt Ihnen die unterzeichnet Entfernung D aus Ihrer Sicht P Ihrer Linie L. In anderen Worten, dies ist der Abstand von P zu dem nächsten Punkt auf L (die wir nicht wirklich über den nächsten Punkt selbst, wir müssen nur den Abstand).

Sagt die Zeichen, die Seite der Linie L den Punkt P liegt. Wenn P liegt auf der gleichen Seite der Vektor (A', B') verweist ("positiv" - Seite), ist der Abstand positiv ist. Wenn P liegt auf der anderen Seite ("negativ" - Seite), ist der Abstand negativ.

(4), um zu finden, Ihre Spiegel zeigen P'(px', py') Sie brauchen, um Ihren Punkt P durch die absolute Distanz |2 * D| über die Linie L auf die andere Seite.

"Across the line" wirklich bedeutet, dass, wenn der Punkt P lag auf der "positiven" Seite der L, dann haben wir ihn zu bewegen, gegen die Richtung des Vektors (A', B') auf die "negative" Seite. Und Umgekehrt, wenn der Punkt P lag auf der "negativen" Seite der L, dann müssen wir es verschieben in Richtung des Vektors (A', B') auf die "positive" Seite.

Diese können einfach ausgedrückt werden als verschieben des Punktes die Entfernung von -2 * D (beachten Sie das Minuszeichen) in Richtung des Vektors (A', B').

Das bedeutet, dass

px' = px - 2 * A' * D
py' = py - 2 * B' * D

gibt Ihnen Ihre Spiegel zeigen P'(px', py').

Alternativ können Sie verwenden einen Ansatz, der auf die Feststellung der tatsächlichen am nächsten Punkt N on line L und dann was den Punkt P mit Bezug auf N. Dies ist schon in anderen Antworten, werde ich nur beschreiben, wie ich es tun würde.

(1) eine Formel Erstellen

A*x + B*y + C = 0

für Ihre Linie L genau wie in Schritt 1 beschrieben vor. Es gibt keine Notwendigkeit zu normalisieren dieser Gleichung.

(2) Bauen Sie eine Gleichung für die senkrechte Linie, die durchläuft P. Lassen Sie uns sagen, dass die senkrechte Linie ist vertreten durch

D*x + E*y + F = 0

Den D und E Koeffizienten bekannt sind, sofort

D = B
E = -A

während F berechnet werden kann durch ersetzen des Punktes P in die Gleichung

F = -D*px - E*py

(3) Finden, den Schnittpunkt dieser beiden Linien durch die Lösung des Systems von zwei linearen Gleichungen

A*x + B*y = -C
D*x + E*y = -F

Cramer ' s rule funktioniert sehr gut in diesem Fall. Die angegebene Formel in Line Kreuzung Artikel in der Wikipedia sind nichts anderes als eine Anwendung von cramers Regel zu diesem system.

Die Lösung bietet Ihnen den am nächsten gelegenen Punkt N(nx, ny) wir waren auf der Suche für.

(4) Jetzt einfach berechnen

px' = nx + (nx - px)
py' = ny + (ny - py)

finden Sie Ihre Punkt P'(px', py').

Beachten Sie, dass dieser Ansatz fast vollständig umgesetzt in zahlen. Der einzige Schritt, der möglicherweise verlieren Präzision ist die division innerhalb der Cramer-Regel, die bei Schritt 3. Natürlich, wie üblich, der Preis, den Sie zu bezahlen haben, für "fast integral" - Lösung ist die Notwendigkeit für große-zahlen-Arithmetik. Auch Koeffizienten C und F können überlaufen, auch nicht zu erwähnen, Berechnungen innerhalb Cramer ' s Regel-Formeln.

InformationsquelleAutor AnT

Berechne den nächsten Punkt auf der Linie zu dem Punkt in Frage. Dann kehren Sie die Richtung des Vektors zwischen diesen Punkten und fügen Sie es zu dem nächsten Punkt auf der Linie. Voilà, Sie haben gefunden, dass der Spiegel zeigen.

InformationsquelleAutor Anteru

Habe ich gemacht, genau dies für ein anderes system, das ich gebaut habe.. Es ist viel mehr als das in meinem code; also ich hoffe, ich habe extrahiert alle notwendigen bits... Line.ClosestPoint(Point pt) ist die Methode, die Sie wollen...

Der Algorithmus basiert auf der Idee, dass die Steigung der Linie perpindicular für jede gegebene Zeile wird die negative multiplikative Kehrwert der Steigung der gegebenen Linie. d.h., wenn eine Linie hat die Steigung m, dann die andere Linie hat die Steigung -1/m. So alle Sie tun müssen ist, bilden eine Linie durch den Punkt mit Steigung gleich -1/m und finden Sie den Schnittpunkt dieser Linie mit der ursprünglichen Linie.

public class Line
{
    protected const double epsilon = 1.0e-8;

    public Point Anchor { get; set; }

    public double Slope { get; set; }

    public virtual Point ClosestPoint(Point pt)
    { return Intersection(Make(pt, -1 /Slope)); }

    protected Line(Point anchor, double slope)
    {
        Anchor = anchor;
        Slope = slope;
    }

    public static Line Make(Point anchor, double slope)
    { return new Line(anchor, slope); }

    public virtual Point Intersection(Line line)
    {
        if (lib.Within(line.Slope, Slope, epsilon))              
            if( lib.Within(line.YIntcpt, YIntcpt, epsilon))
                //code for NoInterceptException not included
                throw new NoInterceptException(
                    "The two lines overlap.");
            else return Point.NullPoint;
        //----------------------------------------
        double tm = Slope, om = line.Slope,
            tx = Anchor.X, ty = Anchor.Y,
            ox = line.Anchor.X, oy = line.Anchor.Y;

        var x = double.IsInfinity(tm) ? tx :
                double.IsInfinity(om) ? ox :
                   (tm * tx - om * ox + oy - ty) /
                          (tm - om);

        var y = double.IsInfinity(tm) ?
               om * (x - ox) + oy :
               tm * (x - tx) + ty;

        return Point.Make(x, y);
    }
}

public struct Point
{
    const double epsilon = 1.0e-12;
    private readonly bool isDef;
    private readonly double y;
    private readonly double x;
    public bool HasValue { get { return isDef; } }
    public bool IsNull { get { return !isDef; } }

    private Point(double xValue, double yValue)
    { x = xValue; y = yValue; isDef = true; }
    public static Point Make(double x, double y)
    { return new Point(x, y); }

    public double X 
    {
        get
        {
                  //code for AlgebraicException not included
            if (IsNull) throw new AlgebraicException("Null Point Object"); 
            return x;
        }
    }
    public double Y
    {
        get
        {
                  //code for AlgebraicException not included
            if (IsNull) throw new AlgebraicException("Null Point Object");
            return y;
        }
    }

    public static Point NullPoint { get { return new Point();}}

    // Other functionality

} 

InformationsquelleAutor Charles Bretana