Forum: Digitale Signalverarbeitung / DSP / Machine Learning Punktewolke parametrisieren


von Gast (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


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.

von Gast (Gast)


Lesenswert?

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

von Gast (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


Lesenswert?

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

von Jorge (Gast)


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).

von Christoph Kessler (db1uq) (Gast)


Lesenswert?

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

von Jorge (Gast)


Lesenswert?

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

von Christoph Kessler (db1uq) (Gast)


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.

von Gast (Gast)


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!

von Thomas (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


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.

von Gast (Gast)


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?

von Christoph Kessler (db1uq) (Gast)


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?

von Gast (Gast)


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.

von Jorge (Gast)


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...



von Gast (Gast)


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.

von Thomas (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


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?

von Gast (Gast)


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.

von Jorge (Gast)


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



von Gast (Gast)


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?

von Gast (Gast)


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.

von Christoph Kessler (db1uq) (Gast)


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

von Jorge (Gast)


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.







von Gast (Gast)


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.

von Jorge (Gast)


Lesenswert?

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

von Jorge (Gast)


Lesenswert?

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

von Thomas (Gast)


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,+san+francisco&ie=UTF8&z=17&ll=37.802112,-122.417779&spn=0.007019,0.016952&t=h&om=1&iwloc=addr

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

von Christoph Kessler (db1uq) (Gast)


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.

von Jorge (Gast)


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.





von Jorge (Gast)


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.


von Thomas (Gast)


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.

von Matthias (Gast)


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...

von Holger K. (hkrueger)


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/informationstechnologie/bericht-26319.html

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-Surfaces-Computer/dp/3540239669

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.

von Thomas (Gast)


Lesenswert?

Sehr sinnig einen Link auf ein Dokument im Nutzerbeschränkten Bereich 
anzugeben.

von Gast (Gast)


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.

von Jorge (Gast)


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/informationstechnologie/bericht-26319.html

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 :-))...

von Gast (Gast)


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).

von RT (Gast)


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

von Gast (Gast)


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.

von RT (Gast)


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

von Oberpolitiker (Gast)


Lesenswert?

Bau doch einfach nen Schneemann

von Johann (Gast)


Lesenswert?

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

von Holger H. (holger-h-hennef) Benutzerseite


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.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.