www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Punktewolke parametrisieren


Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gegeben sei eine Punktewolke, die durch Streuung zufälliger Punkte einer 
Kurve (parametrisiert durch (x,y)(t)=r(t,a1...an) mit Parameter a1...an 
und unabhängiger Variable t) entsteht. Wie rekonstruiere ich a1...an?

Konkret geht es darum, aus aufgezeichneten GPS-Punkten entlang eines 
Weges (nehmen wir der Einfachheit halber mal als 
(x,y)(t)=(at^2+bt+c,dt^2+et+f) an) die Parameter a...f zu bestimmen.

Gibt es einen einfacheren Ansatz, als zu jedem Punkt den minimalen 
Abstand zur Kurve auszurechen, und die Summe dieser Abstände zu 
minimieren?

Das Problem ist, dass nur die Punkte (x1,y1)...(xm,ym) bekannt sind, 
aber nicht die Variable t in jedem Punkt. Wäre ti bekannt, wäre es ein 
leichtes, den Abstand ||(xi,yi)-r(ti,a1...an)|| zu berechnen. So aber 
muss ich erst das passende ti finden (Suche des absoluten Minimums der 
Abstandsfunktion), was sehr rechenzeitaufwendig ist.

Das beste wäre ein Link zu einer Lösung dieses Problems. Für den Fall, 
dass die Kurve r(t) eine Gerade ist, können die Geradenparameter direkt 
bestimmt werden (Stichwort Ausgleichsgerade). Es bringt also nicht, 
diesen Spezialfall als Vereinfachung zu diskutieren, da es sich nicht 
auf gekrümmte Kurven verallgemeinern läßt.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Handlet es sich nicht um die übliche Suche nach einer Näherungsfunktion 
? Für beliebige Kurven nimmt man soweit ich weiß Splines oder 
Bezierkurven, die zwar keine geschlossene Funktion bilden, aber 
wenigstens stetig.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
http://de.wikipedia.org/wiki/Spline
http://de.wikipedia.org/wiki/B%C3%A9zierkurve
Die Splines würden jeden Punkt der Wolke exakt durchlaufen, Bezier macht 
eine Annäherung, wenn ich das recht sehe.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein. Für Splines und Bezierkurven muss die Reihenfolge der Punkte 
vorgegben sein. Das ist ein völlig anderes Problem.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Noch eine Ergänzung: es geht nicht darum, durch einen einzigen 
aufgezeichneten Track eine glatte Kurve zu legen (dafür sind 
Bezierkurven genau richtig), sondern aus den Punkten von hunderten 
Tracks (die allerdings nur als Punktewolke, also ohne Reihenfolge und 
Zeitangaben vorliegen) die gemittelte Kurve zu bestimmen.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sind nur die xy-Wertepaare in beliebiger Folge bekannt, oder wenigstens 
deren zeitliche Aufeinanderfolge ?
Der exakte Zeitpunkt jeder Messung ist jedenfalls unbekannt. Das würde 
ja nur verhindern, die Geschwindigkeit zu bestimmen, mit der die Kurve 
durchlaufen wurde.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also eher sowas wie das Problem des Handlungsreisenden. Das ist je 
bekanntlich nicht exakt lösbar.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
- Warum speicherst du nicht alles doppelt in ein Array. Es gibt bei 
Zufallsvariablen doch ohnehin kein System.
Also f(x) und gleichzeitig die Umkehrfunktion.

- In Numerical Recipes (http://www.nr.com/) findest du bestimmt auch 
etwas.

- mit Ausgleichsgeraden (auch kurvilinear) bin ich satt. Die 
Ausgleichsrechnung liefert eine Art Kurvenschlange - mehr nicht. 
Vorraussetzung für brauchbare Ergebnisse ist eine hohe Korrelation.

Beispielsweise die Situation, wenn die Punktewolke durch zwei Geraden im 
45 Grad Winkel genau beschrieben wird, dann lässt sich die ursprüngliche 
Situation über Partialrechnung gar nicht mehr rekonstruieren (Varimax).

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hab ich gerade vor ein paar Tagen gelesen:
http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du eine kurilineare Ausgleichsrechnung suchst, dann empfehle ich 
wegen der linearen Unabhängigkeit die "Legendre Polynome". Quelle s.o.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wir haben zunächst lokale Punktanhäufungen, die irgendwie 
auseinanderdividiert werden müßten, deren Zentrum wären dann die Städte, 
die der Handlungsreisende wahscheinlich auf dem kürzesten Weg 
durchquert hat, genau sagen kann man das nicht mehr.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier sind eindeutig zuviele Frickler unterwegs. Ich hatte nicht gefragt, 
was euch zu meiner Frage durch den Kopf geht, sondern nach einer Lösung. 
Wenn ihr schon die Frage nicht versteht, fragt nach und interpretiert 
sie nicht um.

Ja, und jetzt kommt ... Undankbarkeit ... dbluq war schon hier bevor 
gast laufen konnte ... wir sind alle ganz toll außer gast ... laber blah 
fasel sülz BLUBBB!

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Einen Zusammenhang mit dem Problem des Handlungsreisenden kann ich zwar 
beim besten Willen nicht erkennen, aber dein Gelaber kannst du dir 
schenken, Gast!


> (x,y)(t)=(at^2+bt+c,dt^2+et+f) an) die Parameter a...f zu bestimmen.

Warum eine Modelfunktion abhängig von t, wenn dies die Probleme macht 
und eigentlich auch gar kein sinnvoller Parameter ist?

> Gibt es einen einfacheren Ansatz, als zu jedem Punkt den minimalen
> Abstand zur Kurve auszurechen, und die Summe dieser Abstände zu
> minimieren?

Ja, die Methode der kleinsten Quadrate.


> (Stichwort Ausgleichsgerade).

Ist nur ein Spezialfall oben genannter Methode, welche prima auch für 
nicht-lineare Modellfunktionen anwendbar ist.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So ein Jammer. Eine fertige Lösung wäre natürlich schön, aber eine 
genauere Formulierung des Problems in Zusammenarbeit mit uns Fricklern 
kann ja vielleicht doch irgendwie weiterhelfen.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Einen Zusammenhang mit dem Problem des Handlungsreisenden kann ich zwar
>beim besten Willen nicht erkennen, aber dein Gelaber kannst du dir
>schenken, Gast!
dbluqs krampfhafte Versuche überall was beizutragen nerven einfach. 
sorry


>> (x,y)(t)=(at^2+bt+c,dt^2+et+f) an) die Parameter a...f zu bestimmen.
>
>Warum eine Modelfunktion abhängig von t, wenn dies die Probleme macht
>und eigentlich auch gar kein sinnvoller Parameter ist?
Was wäre denn ein sinnvoller Parameter? x oder y kommen nicht in Frage, 
weil die Kurve keine eindeutige Funktion y(x) oder x(y) sein muss. t ist 
übrigens nicht die Zeit sondern halt eine beliebige unabhängige 
Variable, über die die Kurve läuft. Man könnte t als Weglänge festlegen.


>> Gibt es einen einfacheren Ansatz, als zu jedem Punkt den minimalen
>> Abstand zur Kurve auszurechen, und die Summe dieser Abstände zu
>> minimieren?
>
>Ja, die Methode der kleinsten Quadrate.
Und was sind dann die Quadrate? Die Quadrate der genannten Abstände. Und 
was ist dann die Methode der kleinsten Quadrate? Die Minimierung der 
Summe dieser Abstände. Das meinte ich, habe vergessen, das Quadrieren 
dazuzuschreiben.

>> (Stichwort Ausgleichsgerade).
>
>Ist nur ein Spezialfall oben genannter Methode, welche prima auch für
>nicht-lineare Modellfunktionen anwendbar ist.

Ja? Wie genau verallgemeinerst du die Methode, um den Abstand eines 
Punkte (xi,yi) von einer unendl. oft diffbaren Kurve zu berechnen, von 
der nichts bekannt ist ausser ihrer Parametrisierung?

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe so allmählich die Aufgabe verstanden:
Wir haben eine Ebene, die in kartesischen x- und y-Koordinaten vermessen 
wird, und darauf schlängelt sich eine Straße, auf der viele Fahrzeuge 
entlangfahren, jedes liefert zu unbekannten Zeitpunkten XY-Wertepaare 
eines GPS-Empfängers ab. Leider wird auch die Reihenfolge nicht 
aufgezeichnet. Am Ende hat man in der Umgebung der Straße viele 
Koordinatenpunkte und soll daraus den wahrscheinlichsten Verlauf der 
Straße als Funktion der Zeit t ausgeben, in der man sie entlangfährt. 
Konstante Geschwindigkeit wäre dann vorausgesetzt, sonst wird es noch 
komplizierter.
Ist das so korrekt?

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
9 von 10 Punkten!!

> und soll daraus den wahrscheinlichsten Verlauf der Straße als Funktion der > 
Zeit t ausgeben,

nein: richtig wäre

...und soll daraus den wahrscheinlichsten Verlauf der Straße als 
Funktion der Weglänge t ausgeben,

wobei du Weglänge und Zeit als äquivalent betrachten darfst, wenn du mit 
konstanter Geschwindigkeit fährst.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sorry, aber deine Verallgemeinerung der Methode der kleinsten Quadrate 
hört sich schwer nach einer Schleifenkonstruktion an.

Im NR steht was von einer "Downhill Simplex Method". Ist sicher eine 
stupide Rechnerei aber vielleicht genau das was du hier brauchst. Sowas 
kann nicht befriedigend funktionieren. Aber dafür gibts ja schließlich 
Computer.

Andernfalls müsstest Du jetzt genauer spezifizieren was du willst...



Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Andernfalls müsstest Du jetzt genauer spezifizieren was du willst...

Dieser Satz ist hier im Forum gleichbedeutend mit "Ich habe keine 
Ahnung, bin mir aber zu fein, es zuzugeben."

Was ist hieran ungenau, wenn ich hinzufüge, dass r(t,a1...an) unednl. 
oft diffbar ist:

>Gegeben sei eine Punktewolke, die durch Streuung zufälliger Punkte einer
>Kurve (parametrisiert durch (x,y)(t)=r(t,a1...an) mit Parameter a1...an
>und unabhängiger Variable t) entsteht. Wie rekonstruiere ich a1...an?

>Im NR steht was von einer "Downhill Simplex Method".

Da habe ich schon effizientere Algorithmen. Es geht aber um einen 
intelligenteren Ansatz, der die verschachtelte Schleife (1. Minimierung 
der Quadrate, 2. Suche nach kleinstem Abstand) umgeht, nicht um eine 
schnelle Implementierung dieser beiden Schleifen.

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da du ja n-mal klüger bist als wir alle zusammen, lös' dein Problem doch 
einfach selbst und lass uns Deppen hier zufrieden, statt ständig deinen 
überlegenen Intellekt zur Schau zu stellen.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die parametrische Darstellung der Straße ist zum Beispiel nötig, wenn 
sie ein Autobahnkleeblatt enthält, wo das Durchfahren der Schleife zu 
zwei Zeit- oder Wegpunkten dieselben XY-Koordinaten ergibt. ( "nicht 
eindeutig" wie oben schon gesagt).

Ist die Fitfunktion vorgegeben? Die genannten quadratischen Gleichungen 
waren doch nur ein Beispiel, fitten mit der Methode der kleinsten 
Quadrate setzt zunächst mal diese Vorgabe voraus oder sehe ich das 
falsch?

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> lös' dein Problem doch einfach selbst und lass uns Deppen hier zufrieden,

Schon recht, Christoph.
Ich antworte nur den Deppen, die danach fragen.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Interessantes Problem. Ich habe wirklich auch keine Ahnung.

Ich glaube ich habe es jetzt auch langsam begriffen. Leider muss ich bei 
meiner ursprünglichen Aussage bleiben:
Brauchbare Ergebnisse gibt es nur bei einer hohen Korrelation.

Also wenn die Strasse Kurven hat und nur wenige Punkte vorliegen kann 
man gar nichts mit anfangen.

Wenn man viele Punkte hat kann man sie in x,y Richtung anordnen 
(sortieren) und bekommt eine Vorstellung vom Verlauf der Strasse. Dann 
ist auch alles kein Problem mehr. Zunächst über Clusterbildung der 
Punkte und dann iterativ durch Verfeinerung der Granulation. Solange bis 
die Korrelation nicht mehr wesentlich besser wird.

Und dazwischen liegt nun die Realität für die du eine Lösung suchst. Die 
soll natürlich dank Kollege Computer besser sein als der Augenschein.

Also ich kenne das als Clusteranalyse. Vielleicht bringt dir das etwas. 
Es handelt sich um ein multivariates Verfahren für Probleme dieser Art.

Gruss



Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ist die Fitfunktion vorgegeben?

Das fällt unter meinen Kommentar zu:

> Andernfalls müsstest Du jetzt genauer spezifizieren was du willst...

Wenn du weißt wie es fürs Beispiel der quadratischen Funktionen geht, 
dann heraus damit. Wenn nicht, wird es auch nicht weiterhelfen, wenn ich 
dir sage, dass ich stückweise kubische Polynome stetig differenzierbar 
verkette, oder doch?

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Und dazwischen liegt nun die Realität für die du eine Lösung suchst. Die
>soll natürlich dank Kollege Computer besser sein als der Augenschein.

Nein, überhaupt nicht. Eine Kurve, die ich per Augenmaß zeichnen würde, 
wäre die perfekte Lösung. Dir scheint nicht bewußt zu sein, dass 
Computer sich mit Augenmaß sehr schwer tun.

>Also ich kenne das als Clusteranalyse. Vielleicht bringt dir das etwas.
>Es handelt sich um ein multivariates Verfahren für Probleme dieser Art.

Ich kenne Clusteranalyse als etwas anderes. multivariates ist auch ein 
schönes Wort.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und das ist keine Spline-Funktion? Es hört sich in der Wikipedia 
zumindest genauso an: aus Stücken zusammmengesetzt und stetig 
differenzierbar

"Ein Spline n-ten Grades ist eine Funktion, die stückweise aus Polynomen 
mit maximalem Grad n zusammengesetzt ist. Dabei werden an den Stellen, 
an denen zwei Polynomstücke zusammenstoßen (man spricht auch von Knoten) 
bestimmte Bedingungen gestellt, etwa dass der Spline (n-1) mal stetig 
differenzierbar ist."

Das Stichwort "Clusteranalyse" klingt wirklich vielversprechend:
http://de.wikipedia.org/wiki/Clusteranalyse

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Clusteranalyse

Trotzdem. So funktioniert es und nicht anders. Wenn du weniger 
Dimensionen hast umso besser...

Also Clustern und dann die Granulation verkleinern.

Ist aber alles PI mal Daumen versteht sich.

Das Problem mit dem man am Schluss konfrontiert wird nennt sich 
Schwellenwertverfahren und die sind mit natürlicher Intelligenz leicht 
zu verarbeiten, wie du eben auch richtig angemerkt hast.







Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Natürlich ist das eine Splinefunktion, wenn du es so betrachtest. Aber 
die Methode der Berechnung des Splines aus Stützstellen ist hier völlig 
unbrauchbar, wenn du mal drüber nachdenkst.

>Das Stichwort "Clusteranalyse" klingt wirklich vielversprechend:
ja, das Stichwort "Mathematik" klingt auch vielversprechend

Leute, es war nett mit euch. Ihr müsst euch nun leider alleine weiter 
mit dem Problem vergnügen, weil ich eine Lösung brauche und keine Zeit 
mehr habe darauf hinzuweisen, warum der eine oder andere (oder jeder) 
Geistesblitz zu nichts führt.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich würde eine quadratische B-Spline Funktion ansetzen, die nicht so 
stark oszilliert.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Immer wenn ich "Zeit ist Geld" höre, weiss ich das ist eine Ausrede.

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ich würde eine quadratische B-Spline Funktion ansetzen, die nicht so
>stark oszilliert.

Ich denke nicht, dass man von vornherein Annahmen über die Anzahl von 
Wendepunkten machen sollte.

Kennst du die "Most curvy street of the world"?
http://maps.google.com/maps?f=q&hl=en&q=lombard+st...

Die würde dann als schöne Gerade interpoliert. Wohl nicht ganz im Sinne 
des Erfinders.

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hier wendet sich der Gast mit Grausen, so kann ich hier nicht ferner 
hausen...

Ich sehe das ganze wie eine Fotobearbeitung am Computer, Kontrast 
anheben, Schärfen oder weichzeichnen, Auflösung verringern usw. Am 
Schluß soll eine saubere Linie rauskommen.
"Clustern und dann die Granulation verkleinern" wäre so ein Rezept.
Meine Formulierung "lokale Punktanhäufungen irgendwie 
auseinanderdividieren (und anschließend eine kürzeste Verbindungslinie 
ermitteln)" geht in die gleiche Betrachtungsweise. Die Autobahnschleife 
wäre ein Test für die Güte des Vorgehens, die darf nicht rausgemittelt 
werden.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man sollte schon mit quadratischen B-Splines arbeiten (Bsp. TrueType) 
aus vielen Segmenten zusammengesetzt alles andere ist doch noch mehr 
Kaffesatz.
Damit gibt es keine Unstetigkeiten. Also es reicht aus und noch mehr 
Parameter lassen sich nicht rechtfertigen. Der Algorithmus soll ja nur 
in eine Richtung konvergieren.





Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Gast,

Das Grausen ist berechtigt.

Was hast du denn erwartet. Man erwartet vom Computer, dass er 
intelligenter ist als der Mensch und verrechnen darf er sich nicht.

Wenn der Mensch nach Augenmass eine Linie einzeichnet, was ist davon zu 
halten. Über solche Linien sind doch schon unzählige Köpfe gerollt.


Du bist dem Problem KI-Forschung nähergerückt - einer Utopie.


Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jorge, ich glaube du solltest Politiker werden, wenn du es nicht schon 
bist. Deine Fähigkeit, Zusammenhänge aus der Luft zu greifen, wo keine 
sind, und dir in einem Satz gleichzeitig selbst zu widersprechen und 
diesen Widerspruch scheinbar in eine frühere Aussage eines anderen zu 
platzieren, ist phänomenal.

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"Jorge, ich glaube du solltest Politiker werden, wenn du es nicht schon
bist. Deine Fähigkeit, Zusammenhänge aus der Luft zu greifen, wo keine
sind, und dir in einem Satz gleichzeitig selbst zu widersprechen und
diesen Widerspruch scheinbar in eine frühere Aussage eines anderen zu
platzieren, ist phänomenal."

Das ist ja genial...

Autor: Holger K. (hkrueger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wirf mal einen Blick in dieses Paper:
http://www.springerlink.com/content/c434qb8l038qeu1b/

Soll angeblich ein effizienter Algorithmus für das Orthogonal Distance 
Fitting (ODF) von Kurven und Flächen sein. Basiert allerdings auch auf 
der Kleinste-Quadrate Methode.

Hab gerade gemerkt, daß da nicht jeder drauf zugreifen kann ohne 
entsprechend zu zahlen. Hier ist noch ne Pressemeldung von 2004 über das 
Verfahren:

http://www.innovations-report.de/html/berichte/inf...

Der Autor des Verfahrens hat auch ein Buch darüber veröffentlicht, daß 
man bei Amazon erstehen kann:
http://www.amazon.de/Squares-Orthogonal-Distance-S...

Ansonsten vielleicht einfach mal in ner Universitätsbibliothek in der 
Nähe danach suchen. Meistens steht da auch irgendwo nen Kopierer rum, 
wenn man keine Lust hat extra nen Ausweis zu beantragen.

Autor: Thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sehr sinnig einen Link auf ein Dokument im Nutzerbeschränkten Bereich 
anzugeben.

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Soll angeblich ein effizienter Algorithmus für das Orthogonal Distance
>Fitting (ODF) von Kurven und Flächen sein

Dank dir Holger, ODF reicht völlig als Stichwort, damit komme ich 
weiter.

Autor: Jorge (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ODF ist tatsächlich das Schlagwort für die hilflosen Versuche sowas in 
den Griff zu bekommen.

http://www.innovations-report.de/html/berichte/inf...

Jetzt wünsche ich Gast weiterhin viel Vergnügen mit der Lösung seines 
speziellen Problems.

Ich persönlich bin weiterhin skeptisch. Damit habe ich aber schon 
verraten, dass ich in der Opposition bin :-))...

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>ODF ist tatsächlich das Schlagwort für die hilflosen Versuche sowas in
>den Griff zu bekommen.
>
>http://www.innovations-report.de/html/berichte/inf...

Schön, dass du das nochmal wiederholt hast, Jorge.

Holger, leider musste ich feststellen, dass ODF nichts anderes ist als 
die von mir umrissene Idee. Die Projektion jedes Punktes auf die Kurve 
wird mittels Newtonverfahren o.ä. gemacht, wodurch wieder das Problem 
der verschachtelten Schleifen vorliegt (das Newtonverfahren an sich ist 
nicht das Problem, sondern die Anzahl der zu testenden Startwerte um 
nicht bloss ein lokales Minimum zu finden).

Autor: RT (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was bisher vergessen wurde, ist dass das Problem eine Groessenskala 
besitzt. Dh es ist nicht variabel in der Groesse, noch kann 
Selbstaehnlichkeit vorkommen. Irgendwo kommt die Breite der Strasse und 
deren minimaler Kruemmungsradius rein. Sonst ist das Problem 
unterbstimmt.

RT

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Was bisher vergessen wurde, ist dass das Problem eine Groessenskala
> besitzt.

Und du könntest Jorge in seiner Politikerkarriere, vor allem in der 
Opposition, beraten. Immer schön alle Probleme verkomplizieren, auch 
wenn noch nicht mal eine Lösung für den einfachen Fall existiert.

Autor: RT (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nicht ganz. Wenn die Strasse unendlich duenn ist und ein Kurvenradius 
gegen Null zulaessig ist, dann kriegt man durch jede Punktwolke eine 
sich beliebig windende Gebirgsstrasse. Nein ?

RT

Autor: Oberpolitiker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bau doch einfach nen Schneemann

Autor: Johann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Holger-Hhhh, ich weiß ja nicht von wo du schreibst, aber in Deutschland 
ist dein Zeug bestimmt nicht legal.

Autor: Holger Harten (holger-h-hennef) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das Problem ist, dass nur die Punkte (x1,y1)...(xm,ym) bekannt sind,
aber nicht die Variable t in jedem Punkt. Wäre ti bekannt, wäre es ein
leichtes, den Abstand ||(xi,yi)-r(ti,a1...an)|| zu berechnen. So aber
muss ich erst das passende ti finden (Suche des absoluten Minimums der
Abstandsfunktion), was sehr rechenzeitaufwendig ist.

Das must nicht so eng sehen.
Schau mal was da schon gemacht ist um Polis zu tracen.

Datenparalleler Software-Ray-Tracer
Die bisher vorhandenen COVISE-Module zur Grafikausgabe basieren alle auf 
der Programmierschnittstelle OpenGL für Hardware-beschleunigte 
3D-Grafik. Am Rechenzentrum steht jedoch ein großes Cluster (128 Knoten) 
aus Shared Memory-System (je 2 CPUs) mit einem schnellen 
Verbindungsnetzwerk (Infiniband, fast 1 Gigabyte/s bei einer Latenz von 
5 Mikrosekunden) zur Verfügung, das nicht über die dafür notwendigen 
Grafikkarten verfügt. Damit die in Simulationen auf diesem Cluster 
gewonnenen enormen Datenmengen effizient - insbesondere ohne sie über 
langsame Verbindungen umzukopieren - visualisiert werden können, soll 
ein datenparalleler Software-Ray-Tracer (d.h. es wird mittels 
Strahl-Rückverfolgung ermittelt, welche Farbe einem Bildpunkt zugeordnet 
wird) implementiert werden, der die schon vorhandene verteilte Struktur 
der Daten respektiert. Insbesondere sollen Polygone zusammen mit 
volumetrischen Daten auf unstrukturierten Gittern dargestellt werden 
können.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.