Position auf Linie ermitteln

Hi,

ich habe ein kleines Problem, bei dem ich einen besonders schnellen Algorithmus suche:

Ich habe eine Linie durch den Raum, die durch die Anfangs- und Endkoordinaten X1,Y1,Z1 und X2,Y2,Z2 definiert ist. Jetzt bekomme ich eine weitere Koordinate X,Y,Z und möchte wissen, ob diese sich auf der Linie befindet. Da das für die Selektierung einer Vektorgrafik gedacht ist und Rundungsfehler in einem gewissen Rahmen ignoriert werden müssen, hat der Punkt X,Y,Z eine gewisse Toleranz. D.h. wenn dier Punkt nicht exakt auf der Linie sitzt, sich aber dennoch im Rahmen der vorgegebenen Toleranz mit dieser schneidet, dann soll das auch OK sein.

Wie mache ich sowas am effizientesten? Momentan fehlt mir noch jeglicher Ansatz...

Wopp

antialias

Definier dein zulässiges Epsilon (wie weit der Punkt von der Gerade enfernt sein kann und noch als 'darauf liegend' gelten soll) und nimm die normale Gleichung für Abstand Punkt-Gerade (findet man über google). Mathematische Formeln für so Zeugs lassen sich nicht weiter optimieren.

Je nach Anwendung findest du natürlich auch einen Quick-Hack: (z.B. wenn der Vektor auf dem Bildschirm dargestellt wird kannst du einfach schaun ob der Pixel an den du den Punkt plotten willst bereits die Farbe des Vektors hat.)

icarus2

Angenommen du hast eine Vektorgleichung (x, y, z ) = (1, 2, 3) + t * (-3, 4, 2) und du willst überprüfen, ob der Punkt P(1 / 8 / 2) auf der Geraden liegt, dann stellst du die Gleichungen auf:

1 = 1 - 3t ==> t = ...
8 = 2 + 4t ==> t = ...
2 = 3 + 2t ==> t = ...

Wenn du bei allen drei Gleichungen ein gleiches t bekommst, dann liegt der Punkt auf der Geraden, sonst nicht.

Du kannst dann wenn es nicht ganz exakt sein muss eine gewisse Abweichung tolerieren. Wie hoch dabei die Toleranzgrenze sein muss müsstest du selber berechnen oder ausprobieren.