überprüfen Sie, ob der Punkt liegt auf der Linie segment

Ich bin verwirrend, ich möchte prüfen, ob ein Punkt liegt auf der Linie a-segment.
Ich google es, aber ich erhalte im Prinzip zwei verschiedene Antworten.

http://en.wikipedia.org/wiki/Line_segment

und

http://www.softwareandfinance.com/Turbo_C/Check_Point_Lies_line_Segment.html

Was ist die richtige Antwort? ich möchte diesen Algorithmus (in C-Sprache ist besser) für die geometrie-Programme wie die postgis.

  • Er hat zwei verschiedene Antworten auf das gleiche problem bedeutet nicht, dass man falsch ist.
  • Von dem, was ich sehen, verwenden Sie zwei verschiedene Repräsentationen ein Linien-segment. Eine Zeit begin und Ende Koordinaten (C-Algorithmus). Und eine Zeit begin und Richtung/Länge vector (Wikipedia).
  • Aber was ist der Unterschied? wenn ich die wikipedia-Lösung und einer anderen?
  • Gleiche Sache, aber Anfang/Ende ist wahrscheinlich einfacher zu Programmieren als die Grad/die Länge von Vektoren. begin/vector wird wahrscheinlich mindestens 1 Schritt mehr.
InformationsquelleAutor Anderson Carniel | 2013-02-24
  1. 8

    Floating-point Arithmetik nicht speichern kann jede Zahl, die Sie Sie zu wünschen. Irgendwann, es muss ungefähr. Nun, ich vermute, der Algorithmus, die Sie von Wikipedia ist, sagen Sie:

    y=mx+b

    Wissen Sie m Sie wissen b jetzt plug-in und stellen Sie sicher, dass die Gleichung gilt. Die großen Werke für die Mathematik. (Quadratwurzel von 2 ) Quadrat ist gleich der Quadratwurzel von 4.

    Aber nun Stell dir vor, Sie tun, auf einem computer. Die Quadratwurzel aus 4 wird kommen, genau wie 2, denn Computer sind toll zu halten, kleine integer-zahlen. Jedoch der rechten Seite, die Quadratwurzel von 2, ist ein bisschen off. Sie hatte abgeschnitten einige der Ziffern, also, wenn Sie quadriert, könnte es sein 1.999998 oder so ähnlich. Um Platz für dieses, müssen Sie überprüfen, dass y is approx. mx+b so:

    tolerance = .01
x,y
rhs = m*x + b //right hand side
dif = abs(rhs - y)
if dif < tolerance //the point is approximately on the segment

    Dann haben Sie zu prüfen, die bounding-box für Sie (find max x,y, min x,y)

    Natürlich, diese Methoden sind nicht perfekt ( http://xkcd.com/217/ ), aber für die meisten praktischen Anwendungen, die Sie halten wird, wahr genug. Wenn Sie WIRKLICH brauchen genaue zahlen, ich würde vorschlagen, mit Wolfram Alpha (ich höre, es gibt einige API oder sowas) oder einfach nur schreiben Sie Ihre eigenen genauen Anzahl-Bibliothek.

    • Danke, jetzt verstehe ich. =)
    • +1 für xkcd. 🙂
    InformationsquelleAutor Ryan Amos
  2. 2

    Bevor Sie fortfahren, wäre es hilfreich zu wissen, wenn Sie nur eine grafische Darstellung der Linie irgendwie oder wenn Sie tatsächlich haben, die Formel, die die Zeile erstellt hat. Da Sie sagte "line" und nicht "plane" ich nehme an wir sprechen über eine 2D-Linie.

    Wenn Sie die Formel für die Zeile, dann die Antwort ist einfach, ersetzen Sie die Punkte x,y-Wert in die Formel ein, und wenn die Formel gültig ist, dann ist der Punkt auf der Linie.

    Zum Beispiel, wenn die Linie y = 2x + 1,5 und Ihr Punkt (1,1)

    1 = 1(1) + 1.5
    1 = 3,5 ist false, so dass der Punkt nicht auf der Strecke liegen

    Das gleiche funktioniert auch für jede Zeile die Formel in 2D-oder 3D-unabhängig von der Anzahl der Variablen oder die form der Linie..

    x + 2y = 0
    1,5 x + 12y - 4z = 84

    Nur pop in dem Punkt, mit dem Sie arbeiten und, wenn beide Seiten der Gleichung sind gleich, dann ist der Punkt auf der Linie (oder Ebene).

    Wenn Sie auf der Suche nach einer grafischen Lösung, wie zum Beispiel eine bitmap, einen Fahrplan oder so etwas und wollen wissen, ob der Ort, wo jemand geklickt "auf der Linie der Straße", dann ist das ein völlig anderes problem.

    InformationsquelleAutor David Toth
  3. 1

    Beide Recht.

    Nur im Hinterkopf behalten, dass Turbo C ist furchtbar alt und jetzt außerhalb der Norm. void main() zum Beispiel sollte nicht verwendet werden (es ist int main() statt)

    Auch nicht verwenden, Vergleiche (==) in floating point, in C, weil floating point ist unpräzise, das ist, warum Sie das Turbo C-code < 0.001 %% > 0.001 Stil.

    InformationsquelleAutor speeder
Schreibe einen Kommentar