4. Berechnung: Ist der punkt auf dieser Strecke?

Berechnung: Ist der punkt auf dieser Strecke?

  • Y

    Hallo,

    ich habe eine frage an euch:
    Wie kann man berechnen ob ein Punkt X auf einer geraden liegt die bestimmt ist
    durch ihren anfangs und end punkt P und U.

    Die Geraden gleichung besagt ja, dass eine fließkommazahl multipliziert mit dem end Punkt und addiert mit dem anfangspunkt einen punkt auf der linie ergibt:

    g: x = p + s * u (Die Pfeile sollen besagen, dass es Vektoren sind)
    (x, p und u sind vectoren)

    meine erste Frage: Kann man das so umformen?

    s = ( x - p ) / u

    wenn ja frage ich mich wie man aus Vectoren eine fließkommazahl bekommt.

    0
  • M

    nein so kann man das nicht umformen (glaub ich).
    Es geht so:

    X-P=s*U

    Wobei alles Vektoren außer s sind.

    jetzt gehst du folgendermaßen vor:

    X=(x,y,z, ...)
    P=(px,py,pz,....)
    U=(ux,uy,uz,...)

    Es ergibt sich also folgendes überbestimmtes Gleichungssystem:

    x-px=s*ux
y-py=s*uy
z-pz=s*uz
.
.
.

    Aus der ersten Gleichung kannst du s berechnen. JEtzt musst du s in die anderen einsetzen und gucken, ob auch diese Gleichungen erüfllt sind. Wenn ja, liegt der punkt auf der geraden, wenn nicht, dann nicht. 🙂

    0
  • P

    Yazoo schrieb:

    Hallo,
    ich habe eine frage an euch:
    Wie kann man berechnen ob ein Punkt X auf einer geraden liegt die bestimmt ist
    durch ihren anfangs und end punkt P und U.

    Meinst du eine Gerade oder eine Strecke? Geraden haben keine Endpunkte, Strecken schon.

    Die Geraden gleichung besagt ja, dass eine fließkommazahl multipliziert mit dem end Punkt und addiert mit dem anfangspunkt einen punkt auf der linie ergibt:

    Multipliziert mit dem Richtungsvektor, nicht mit dem Endpunkt. Der Richtugnsvektor ist die Differenz zwischen Endpunkt und Anfangspunkt.

    g: x = p + s * u (Die Pfeile sollen besagen, dass es Vektoren sind)
    (x, p und u sind vectoren)

    meine erste Frage: Kann man das so umformen?

    s = ( x - p ) / u

    Nein. Vektoren kann man nicht dividieren.

    Du kannst, wie Maxi beschrieben hat, ein überbestimmtes Gleichungssystem erstellen indem du jede Komponente einzeln betrachtest. Bei mindestens einer der Komponenten/Gleichungen ist der U-Teil von 0 verschieden, die Gleichungen bei denen das der Fall ist kannst du dann benutzen um s zu bestimmen.
    Damit der Punkt auf der Geraden liegt muss der Wert für s aus jeder Gleichung der selbe sein.
    Wenn es sich bei dir um eine Strecke handelt statt um eine Gerade, muss zusätzlich 0 <= s <= 1 gelten.

    0
  • Y

    vielen dank ich glaube das habe ich verstanden.

    lässt sich das so in c++ implementieren?

    bool PointIsOnLine(tbVector3 vLineStart, tbVector3 vLineEnd, tbVector3 vPoint)   // tbVector3 ist eine klasse der TriBase engine die ich zur zeit benutze
{
	float fSX;
	float fSY;
	float fSZ;

	fSX = (vPoint.x - vLineStart.x) / vLineEnd.x;

	if(fSX < 0 || fSX > 1)
		return false;

	fSY = (vPoint.y - vLineStart.y) / vLineEnd.y;

	if(fSY < 0 || fSY > 1)
		return false;

	fSZ = (vPoint.z - vLineStart.z) / vLineEnd.z;

	if(fSZ < 0 || fSZ > 1)
		return false;

	if(fSX == fSY && fSY == fSZ)
		return true;

	return false;
}

    Ich meinte natürlich eine Strecke sorry mein fehler.

    0
  • G

    Mit float nicht, da der Computer implizit nicht darstellbare Ergebnisse rundet, was dazu führt, dass der Vergleich mit == in vielen Fällen (d.h. wenn eine Zahl gerundet wurde) fehlschlägt, selbst wenn das ungerundete Ergebnis tatsächlich gleich wäre. Nur um Anschaulich zu machen wie weit dieses Problem bei Gleitkommazahlen geht: Sogar wenn du nur 0,1 eingibst kann diese Zahl nicht dargestellt werden und muss gerundet werden, da der Computer in einem Stellenwertsystem zur Basis 2 rechnet (nicht zur Basis 10).
    Lösen kann man das Problem ansatzweise indem man eine Differenz definiert, ab der zwei GLeitkommazahlen als "gleich" angesehen werden. Das würde quasi dazu führen, dass auch leich neben der Strecke liegende Punkte angenommen würden. Bringt aber weitere Probleme mit sich...
    In der Form möglich wäre es wohl mit einer Bruch-Klasse. Habe deinen Code aber nicht auf mathematische Richtigkeit über prüft.

    0
  • Y

    geloescht schrieb:

    Mit float nicht, da der Computer implizit nicht darstellbare Ergebnisse rundet, was dazu führt, dass der Vergleich mit == in vielen Fällen (d.h. wenn eine Zahl gerundet wurde) fehlschlägt, selbst wenn das ungerundete Ergebnis tatsächlich gleich wäre. Nur um Anschaulich zu machen wie weit dieses Problem bei Gleitkommazahlen geht: Sogar wenn du nur 0,1 eingibst kann diese Zahl nicht dargestellt werden und muss gerundet werden, da der Computer in einem Stellenwertsystem zur Basis 2 rechnet (nicht zur Basis 10).

    Das ist quatsch! Sonst würde bei folgendem code nicht 0.1 ausgegeben werden:

    float f;

f = 0.1f;

std::cout << f;

    die ausgabe sieht so aus:

    0.1

    ...

    Wie dem auch sei, ich habe die funktion verbessert und einen tolleranzbereich hinzugefühgt. Allerdings funktioniert das nicht. Ich glaube das ist ein mathematisches problem.

    hier die funktion:

    bool PointIsOnLine(tbVector3 vLineStart, tbVector3 vLineEnd, tbVector3 vPoint, float fTollerance)
{
	float fSX;
	float fSY;
	float fSZ;

	fSX = (vPoint.x - vLineStart.x) / vLineEnd.x;

	if(fSX < 0 - fTollerance || fSX > 1 + fTollerance)
		return false;

	fSY = (vPoint.y - vLineStart.y) / vLineEnd.y;

	if(fSY < 0 - fTollerance || fSY > 1 + fTollerance)
		return false;

	if(fSX < fSY - fTollerance || fSX > fSY + fTollerance)
		return false;

	fSZ = (vPoint.z - vLineStart.z) / vLineEnd.z;

	if(fSZ < 0 - fTollerance || fSZ > 1 + fTollerance)
		return false;

	if(!(fSY < fSZ - fTollerance || fSY > fSZ + fTollerance))
		return true;

	return false;
}

    beispiel:

    vLineStart = (0, 3, 0)
    vLineEnd = (3, 3, 0)
    vPoint = (1, 3, 0)

    der punkt liegt auf der linie.

    Aber nach der obrigen rechnung nicht, denn:
    fSX = 1/3 aber
    fSY = 0

    Wo liegt das problem???

    0
  • T

    Yazoo schrieb:

    Das ist quatsch! Sonst würde bei folgendem code nicht 0.1 ausgegeben werden:

    Das ist überhaupt kein Quastch. Rate mal, was hier die Ausgabe ist:

    int main()
{
    float x = 0.1;
    float y = 1.0;
    float sum = 0;

    for(int k=0; k != 10; ++k)
            sum += x;    

    if(sum == y)
        std::cout << sum << " == " << y << std::endl;
    else
       std::cout << sum << " != " << y << "; sum-y == " << sum-y << std::endl;

    return 0;
}

    Und dann teste mal zum Vergleich den Code mit x = 1.0 und y = 10.0

    1.0 lässt sich im Binärformat exakt darstellen. 0.1 ist aber in binärer Schreibweise periodisch. Wegen des endlichen Speichers werden nur endlich viele Stellen abgespeichert und Du bekommst sehr lustige Ergenisse. Nur mit der cout-Ausgabe kommst du nicht viel weiter, weil die Ergebnisse gerundet dargestellt werden.

    Offtopic: Ich kann leider gerade keine Quellen angeben, aber wegen genau dieses Problems sind schon Menschen gestorben. Eine Flugabwehrrakete hatte einen Timer auf floating-Point Basis, der die ganze Zeit in 0.1sec-Schritten die Zeit aufsummiert hat. Nach nem Tag oder so waren die Fehler so schlimm, dass der Timer kaputt war. Deswegen stand im Handbuch, man solle die Rakte regelmäßig neu booten. Hat man vergessen (wer liest schon das Handbuch?), die feindliche Rakete ist gekommen und die Abwehrrakete hat sich mit dem falschen Timer verrechnet und ist ins Nirvana geflogen. Die feindliche Rakete hat voll ins Ziel getroffen...
    (Das ist, glaube ich, den Amis im ersten Irakkrieg passiert)

    0
  • W

    Yazoo schrieb:

    geloescht schrieb:

    Mit float nicht, da der Computer implizit nicht darstellbare Ergebnisse rundet, was dazu führt, dass der Vergleich mit == in vielen Fällen (d.h. wenn eine Zahl gerundet wurde) fehlschlägt, selbst wenn das ungerundete Ergebnis tatsächlich gleich wäre. Nur um Anschaulich zu machen wie weit dieses Problem bei Gleitkommazahlen geht: Sogar wenn du nur 0,1 eingibst kann diese Zahl nicht dargestellt werden und muss gerundet werden, da der Computer in einem Stellenwertsystem zur Basis 2 rechnet (nicht zur Basis 10).

    Das ist quatsch!

    kein Quatsch - 'geloescht' hat Recht

    Yazoo schrieb:

    Sonst würde bei folgendem code nicht 0.1 ausgegeben werden:

    float f;

f = 0.1f;

std::cout << f;

    die ausgabe sieht so aus:

    0.1

    Die Ausgabe (zumal im Dezimalsystem) ist nicht identisch mit der internen Darstellung, sondern 'nur' eine auf eine bestimmte (Default ist z.B.6) Anzahl von Stellen gerundete Näherung.

    Ein PC speichert eine 0,1 i.A. nicht exakt, da keine endliche Summe rationaler Zahlen mit Nennern von 2^n (n ist eine ganze Zahl) existiert, die identisch 0,1 ist.

    Yazoo schrieb:

    Ich glaube das ist ein mathematisches problem.

    hier die funktion:

    bool PointIsOnLine(tbVector3 vLineStart, tbVector3 vLineEnd, tbVector3 vPoint, float fTollerance)
{
	float fSX;
	float fSY;
	float fSZ;

	fSX = (vPoint.x - vLineStart.x) / vLineEnd.x;

    es ist eher ein Problem der korrekten Umsetzung der Antworten von Maxi und pumuckl in Code.

    Maxi schrieb:

    Es geht so:

    X-P=s*U

    wobei U wohl U = vLineEnd - vLineStart , P = vLineStart ist und X = vPoint ist, wenn ich nicht irre. Dann wäre hier korrekt:

    fSX = (vPoint.x - vLineStart.x) / (vLineEnd.x - vLineStart.x);

    und genauso für fsY.

    Gruß
    Werner

    0
  • W

    Werner Salomon schrieb:

    Dann wäre hier korrekt:

    fSX = (vPoint.x - vLineStart.x) / (vLineEnd.x - vLineStart.x);

    und genauso für fsY.

    .. wobei dass vielleicht mathematisch korrekt, aber numerisch instabil ist, wie Dein Zahlenbeispiel Dir zeigen wird, da hier bereits vLineEnd.y-vLineStart.y==0 ist!

    Ich würde Dir hier ein anderes Verfahren vorschlagen:
    Bezogen auf Dein anfängliches Posting ist die Gerade g gegeben mit

    g := P + s*U

    der Punkt von dem man wissen will, ob er auf g liegt sei X. Der Punkt F sei ein Punkt auf dieser Geraden, so dass die Verbindung FX senkrecht auf U steht. D.h. F ist der Fußpunkt des Lotes von X auf g. Und damit auch der Punkt auf g, der am nächsten an X liegt; evt. auch selber X ist.
    Dann ist für den Vektor FX

    FX = X - (P + s*U)     (1)

    Da FX senkrecht auf U steht, gilt auch

    FX*U = 0  (2)

    multipliziere (1) mit U

    FX*U = X*U - P*U - s*U^2    (3)

    mit Berücksichtigung von (2) gilt dann

    s*U^2 = (X - P)*U    (4)

    bzw.:

    s = ((X - P)*U) / U^2    (5)

    solange |U|>0 ist, erhält man immer eine Lösung für s. Jetzt muss man nur noch den Betrag von FX bestimmen (FX folgt aus (1)) und schauen, ob der Wert eine Mindesttoleranz nicht überschreitet. Also in C++:

    bool PointIsOnLine( const tbVector3& vLineStart, const tbVector3& vLineEnd, const tbVector3& vPoint, float fTolerance )
{
    tbVector3 u = vLineEnd - vLineStart;
    float s = ((vPoint - vLineStart) * u) / (u*u);  // Glg.(5)
    tbVector3 f = vLineStart + s * u;   // Fusspunkt F
    return abs( vPoint - f ) <= fTolerance;
}

    .. funktioniert auch unabhängig von der Anzahl der Dimensionen von tbVector3

    :xmas2: Werner

    0
  • Y

    erstmal vielen dank für deine hilfe,
    leider lässt sich der code nicht compilliren.

    Werner Salomon schrieb:

    float s = ((vPoint - vLineStart) * u) / (u*u);  // Glg.(5)

    hier sagt mein kompiler:

    error C2440: 'Initialisierung': 'tbVector3' kann nicht in 'float' konvertiert werden

    muss ich das hier nicht wieder in die einzelnen bestandteile aufteilen?
    Also

    float sX = ((vPoint.x - vLineStart.x) * u.x) / (u.x*u.x);
float sY = ((vPoint.y - vLineStart.y) * u.y) / (u.y*u.y);
float sZ = ((vPoint.z - vLineStart.z) * u.z) / (u.z*u.z);

    ???

    Oder liegt das an der tbVector3 Klasse liegen?

    auserdem sagt mein kompiler hier:

    return abs( vPoint - f ) <= fTolerance;

    ,dass abs nur int, long, double und long double übernehmen kann.

    muss ich das ebenfalls wie oben in die einzelnen X, Y, Z aufteilen???

    0
  • ?

    Beim ersten Fehler versuchst du einem Float einen Vektor zuzuweisen, beim zweiten gehst du davon aus, dass abs (Die C++-Funktion) für Vektoren definiert ist. Du könntest sie natürlich dafür überladen.

    Oder meinst du eigentlich in Wirklichkeit eine Strecke?

    PS: Na meine Mathematik überarbeite ich gerade noch einmal 😉

    0
  • Y

    ich meinte eine strecke, sry mit den namen habe ich es nicht so

    0
  • W

    Yazoo schrieb:

    erstmal vielen dank für deine hilfe,
    leider lässt sich der code nicht compilliren.

    Werner Salomon schrieb:

    float s = ((vPoint - vLineStart) * u) / (u*u);  // Glg.(5)

    hier sagt mein kompiler:

    error C2440: 'Initialisierung': 'tbVector3' kann nicht in 'float' konvertiert werden

    das wird daran liegen, dass 'tbVector3' keinen binären Operator* unterstützt. Leider habe ich weder auf der Seite von David Scherfgen noch sonst wo die Schnittstelle von 'tbVector3' gefunden. In der Beschreibung heißt es, dass Kreuz- und Punktprodukt unterstützt werden. Mit dem Punktprodukt ist wohl das Skalar- oder innere Produkt eines Vektors gemeint.
    Also musst Du den operator* nur gegen das Punktprodukt austauschen - wie immer dies auch heißen mag.

    Yazoo schrieb:

    muss ich das hier nicht wieder in die einzelnen bestandteile aufteilen?
    Also

    float sX = ((vPoint.x - vLineStart.x) * u.x) / (u.x*u.x);
float sY = ((vPoint.y - vLineStart.y) * u.y) / (u.y*u.y);
float sZ = ((vPoint.z - vLineStart.z) * u.z) / (u.z*u.z);

    nein - wie es richtig geht siehe bei Skalarprodukt oder bei dieser Vektorklasse.

    Yazoo schrieb:

    auserdem sagt mein kompiler hier:

    return abs( vPoint - f ) <= fTolerance;

    ,dass abs nur int, long, double und long double übernehmen kann.

    das gleiche Problem wie oben für den Betrag eines Vektors. Hier musst Du abs gegen das austauschen, was Tribase für den Betrag vorgesehen hat.

    :xmas2: Werner

    0
  • Y

    erstmal vielen dank für deine hilfe.

    Muss ich hier den betrag bilden, es handelt sich schließlich um eine Strecke.

    und liefert abs dann nicht einen vector zurück??

    reicht es nicht S zu haben und dan zu prüfen ob es zwischen 0 und 1 liegt??

    0
  • W

    Yazoo schrieb:

    Muss ich hier den betrag bilden, es handelt sich schließlich um eine Strecke.

    Ja - wenn Du Dir oben alles genau durchgelesen hast, so wirst Du vielleicht gemerkt haben, dass 'f' der Fußpunkt von 'vPoint' alias X auf g ist. Demzufolge ist |vPoint-f| der (seitliche) Abstand von 'vPoint' zu der Geraden g.

    Yazoo schrieb:

    reicht es nicht S zu haben und dan zu prüfen ob es zwischen 0 und 1 liegt??

    Nein, da der (seitliche) Abstand noch beliebig groß sein kann (s.o.). Die zusätzliche (!) Prüfung ob s im Intervall [0,1] liegt sagt dann aus, ob X alias 'vPoint' auch auf der Strecke vLineStart-vLineEnd liegt.

    Yazoo schrieb:

    und liefert abs dann nicht einen vector zurück??

    abs liefert den Betrag zurück, und der ist immer eine skalare Größe - also z.B. ein double in C++.

    :xmas2: Werner

    0
  • Y

    tut mir leid, dass ich immer mindestens 2 fragen auf einmal habe:

    1. Der Betrag eines Vektors ist die Länge, richtig?

    2. Da die Berechnung des Betrags eine Wurzel beinhaltet ist das nicht sehr performance freundlich. Kann ich auch das quadrat des Betrages nehmen und dann prüfen ob es kleiner ober gleich dem Quadrat von fTolerance ist, also:

    |vPoint - f| <= fTolerance * fTolerance

    Falls die Fragen richtig sind sähe das in code so aus:

    bool PointIsOnLine(tbVector3 const& vLineStart, tbVector3 const& vLineEnd, tbVector3 const& vPoint, float const& fTolerance)
{
	tbVector3 vU = vLineEnd - vLineStart;
	float fS = tbVector3Dot((vPoint - vLineStart), vU) / tbVector3Dot(vU, vU);       // tbVector3Dot ist die Funktion für das Punktprodukt

	if(fS < 0.0f - fTolerance || fS > 1.0 + fTolerance)
		return false;

	tbVector3 vF = vLineStart + fS * vU;

	return tbVector3LengthSq(vPoint - vF) <= (fTolerance * fTolerance);        // tbVector3LengthSq ist zum berechnen des Quadrates der Länge
}

    nochmal entschuldigung wegen meines fehlenden wissen über vektoren, ich bin erst in der 10. Klasse und mein einziges (sehr beschrenktes) Wissen über Vektoren habe ich aus einem Buch für 3D Programmierung.

    0
  • W

    Yazoo schrieb:

    1. Der Betrag eines Vektors ist die Länge, richtig?

    Ja

    Yazoo schrieb:

    2. Da die Berechnung des Betrags eine Wurzel beinhaltet ist das nicht sehr performance freundlich. Kann ich auch das quadrat des Betrages nehmen und dann prüfen ob es kleiner ober gleich dem Quadrat von fTolerance ist ..

    Ja, das kannst Du machen. Der Code sollte so ok sein.

    Aber so als Tipp: in erster Linie sollte Dein Code so aussehen, dass Du ihn selber auch verstehst. Das gilt umso mehr, umso unsicherer Du noch mit der Domäne (hier Vektorrechnung) bist.
    Sollte sich dann irgendwann herausstellen, dass Deine Laufzeit(en) länger sind als gewünscht oder erwartet, so versuche die Ursachen durch Messungen oder auch durch Ausprobieren herauszubekommen. Dann kannst Du gezielt an diesen Stellen Änderungen vornehmen.
    Vorzeitige Optimierungen haben nach meiner Erfahrung im Mittel mehr schädliche als positive Effekte.

    Yazoo schrieb:

    nochmal entschuldigung wegen meines fehlenden wissen über vektoren, ich bin erst in der 10. Klasse und mein einziges (sehr beschrenktes) Wissen über Vektoren habe ich aus einem Buch für 3D Programmierung.

    das ist schon ok, dafür ist das Forum da.

    :xmas2: Werner

    0
  • Y

    vielen dank für eure hilfe!
    Ohne euch wäre ich aufgeschmissen.

    Die Funktion klappt nun.

    Vielen dank und guten rutsch ins neue Jahr!

    0
Anmelden zum Antworten