C/C++ Einem Pfad Folgen....

[DanDanger]

Hallo,

ich habe folgendes Problem :

Durch 6 Punkte (p0, p1, p2,.....,p5) ist ein beliebiger Pfad gegeben, der aus Geradenstücken zusammengesetzt ist.

Also : (p0, p1) bilden Gerade 1, (p1, p2) bilden Gerade 2, (p2, p3) bilden Gerade 3, usw.....



(Übelstes ASCII-Art) Beispiel eines Pfades :

p1*___*p2
\
\
p3 *---------*p4
\
\
p5*-------*p6





Nun möchte ich, das ein Punkt diesem Pfad folgt.
Ausserdem möchte ich, dass der Punkt in der Lage ist, eine Bestimmte Teilstrecke des Pfades abzulaufen : z.B. Wenn ich sage : Laufe 75% des Pfades entlang, dann soll der Punkt halt den Pfad zu 75% entlanglaufen.

Leider habe ich keine Idee, wie ich das Lösen kann (ist das Überhaupt Möglich??).


Hat jemand von Euch ne' Idee (oder zumindest einen Lösungsansatz??) ???

Neugierige Grüsse
DanDanger

[Boron]

Bisschen wenig Infos!

Gehe ich richtig in der Annahme, dass du so etwas grafisch auf dem Bildschirm ausgeben möchtest?
Wenn richtig, mit welchem Toolkit willst du das machen; Qt, GTK ...?

Ein Pfad, wie du ihn dir vorstellst, nennt man allgemein "Polygonzug".

Ansonsten musst du deine Geometriekenntnisse zu Rate ziehen.
Gesamtlänge des Pfades = Summe der Längen aller Teilstücke usw.

Wenn du weißt, wie der mathematische Algorithmus der Lösung deines Problems ist, dann ist die Implemetierung (Programmierung) das kleinere Problem.

[DanDanger]

Hi,

das ganze soll in OpenGL implementiert werden, dass Problem bei Sache ist halt : Mir fehlt der Mathematische Algorithmus zur Berechnung der "Punktposition" (das Berechnen der Gesamtlänge des "Polygonzug's" is das kleinere Problem ;-) ).

Na, wenn mir jemand da Mathematisch ein bisschen unter die Arme greifen könnte, währe das schon toll:D


Neugierige Grüsse
DanDanger

[sixfriends]

Falls du die Koordinaten dieser Punkte hast, dann ist die Länge der Strecke zwischen p0 = (x0,y0) und p1 = (x1,y1):

p0p1 = Wurzel( (x1-x0)^2 + (y1-y0)^2 )

oder anders ausgedrückt: a^2 + b^2 = c^2

Hoffe, das hilft dir weiter.

[DanDanger]

Hi,
erstmal: Danke für die Antwort.

Die Betragsformel zur Längenbestimmung habe ich schon implementiert (trotzdem : DANKE :-) ).

Hast Du vieleicht noch ne' Idee, wie ich das mit dem "Pfad-Folgen" hinkriege? Das schwierigste scheint ja zu sein, den Pfad in eine Art "Geradengleichung" reinzuquetschen........


Neugierige Grüsse
DanDanger

[kehj]

Moin,

ich denke mal, das ganze sollte nicht so schwierig sein. Die Implementation in GL kriegst du hin?

Der mathematische Algo ist ziemlich einfach würde ich sagen. Der Punkt läuft die Geraden entlang, indem du folgende Gleichung anwendest (lineare Algebra):

p(t) = p0 + t * (p1 - p0)

p(t): aktuelle Position des Punktes in Abhängigkeit von der Zeit, t im Interwall 0..1 laufen lassen.
Du mußt das ganze für die x, y und z-Komponente einzelnd berechnen. Das machst du jeweils pro Teilstrecke, d.h. wenn du bei 1 angekommen bist, fängst du auf der nächsten bei 0 an...

Um 75% des Weges abzulaufen, würde ich erstmal die Gesamtstrecke des Pfades berechnen und davon 75% nehmen. Dann kannst du ja auch berechnen auf welchem Pfad du wie weit gehen mußt, um die 75% der Gesamtstrecke zu kriegen.

[BLUESCREEN3D]

ablaufen einer linie, z.b. von punkt anfang zu punkt ende:




//laenge der linie muss hier erstmal berechnet werden - hast du ja schon...

for(aktuelle_position=0;aktuelle_position<=laenge_der_linie;aktuelle_position++)
{
aktuelle_koordinaten.x=(ende.x-anfang.x)/laenge_der_linie*aktuelle_position;
aktuelle_koordinaten.y=(ende.y-anfang.y)/laenge_der_linie*aktuelle_position;
//hier dann eben den pixel (aktuelle_koordinaten.x,aktuelle_koordinaten) anzeigen
}

/*

um noch das ablaufen eines teilstueckes der gesamtstrecke zu ermoeglichen musst du wie schon gesagt berechnen:
-die gesamtlaenge
-die abzulaufende gesamtlaenge (z.b. gesamtlaenge*0.75 für 75%)
dann musst du nurnoch:
-die bisher von der oben beschriebenen for-schleife abgelaufene strecke zwischenspeichern und die endbedingung der schelife erweitern:

for(aktuelle_position=0;aktuelle_position<=laenge_der_linie && aktuelle_gesamtposition<=abzulaufende_gesamtlaenge;aktuelle_position++,akt uelle_gesamtposition++)

*/



ps: da das anscheinend ziemlich einfacher opengl-code ist (nur 2d mit pixeln und linien) wäre ich daran interessiert, um ein bisschen opengl zu lernen :D - kannst du mir den schicken? e-mail-addresse würde ich dir dann per pn geben...

lol, mir fällt gerade auf, dass der thread schon einen monat alt ist... :rolleyes:

[DanDanger]

lol, mir fällt gerade auf, dass der thread schon einen monat alt ist... :rolleyes:


Macht nicht's,
wenn's einem interessiert : Hier ist mein Code zum Linien-Folgen (Im Grunde BLUESCREEN3D's Ansatz) :



double t = 0 ;
GLfloat x = 0 ;
GLfloat y = 0 ;

GLfloat GesamtLaenge = 0 ;
GLfloat ZuFahren = 0 ;
GLfloat GefahreneStrecke = 0 ;

int i ;
int ZaehlX = 0 ;
int ZaehlY = 0 ;


/* Brerechne zunaechst : Gesamtlaenge des Weges : Wurzel( (x1-x0)^2 + (y1-y0)^2 ) */
for(int j=0; j < p_NumPoints-1; j++)
{
GesamtLaenge += sqrt( pow((PX[j+1]-PX[j]),2) + pow((PY[j+1]-PY[j]),2) ) ;
}

/*
Berechene nun : Strecke die Zurueckgelegt werden muss, um der Uebergebenen
Prozentzahl (ProzentPosition) zu entsprechen
*/
ZuFahren = (GesamtLaenge/100) * ProzentPosition ;

/*
Zum Schluss : Solange den Weg entlangfahren, wie die zurueckgelegte Strecke < Zu Fahrende Strecke */
do
{
t += SPEED ;
/*
Durch den Integer Cast schneidet man alles hinterm Komma ab
z.B. (int)3.1415 = 3 oder (int)0.112312 = 0
*/
i = (int)t;
/*
Was hier passiert ist der eigentliche Algorithmus:
Es wird hier die parameterform der Geraden benutzt.
px[i] ist der x-Wert des sog. Aufpunkt
(px[i+1] - px[i]) ist der x-Wert des sog. Richtungsvektors
(t-i) ist der Parameter
F: Warum nicht t alleine sondern (t-i)?
A: Weil der wert von t für jedes Teilintervall zwischen 0 und 1 liegen muss
Nimmt man nur t, geht der Parameter aber schon im zweiten Interval bei 1 los.
*/
x = PX[i] + (PX[i+1] - PX[i]) * (t - i) ;
y = PY[i] + (PY[i+1] - PY[i]) * (t - i) ;

GefahreneStrecke = glfAbsolute((PX[0] - x)) + glfAbsolute((PY[0] - y)) ;


}while(GefahreneStrecke < ZuFahren) ;


*NeuX = x ;
*NeuY = y ;
}



DANKE an alle die geholfen haben :D

Gruss
DanDanger