# Interpolation von Datens



## TJava (5. Jan 2013)

Guten Abend,

ich habe es mit Anfangs ca. 1.000.000 Datensätzen zu tun. Diese sollen Interpoliert werden und dann per JavaFx in einer Chart dargestellt werden. 

Die Chart soll die Möglichkeit bieten hineinzuzoomen und dort die Messpunkte bzw. Datensätze detaillierter anzuzeigen.

Gibt es eine Möglichkeit oder welche sind gängige Verfahren um so eine Datenmenge zu interpolieren, damit meine ich aus X Punkten, Y Punkte zu erstellen die den Verlauf darstellen.

Ich weiß nicht ob Interpolation das richtige Verfahren ist. 
Versteht ihr mein Problem und könnt etwas dazu sagen?


----------



## Marco13 (6. Jan 2013)

Ohne von JavaFX wirklich Ahnung zu haben: Bei 1000000 Punkten wird wohl nicht wirklich "interpoliert". Wenn man in einem LineChart 1000 Punkte überhaupt darstellen _kann_ ist das schon viel, sinnvoll gehen vielleicht 100 oder so... Oder ist es genau das, was mit dem Zoomen erreicht werden sollte?


----------



## TJava (6. Jan 2013)

Genau das Problem ist eben das zu viele Punkte vorhanden sind und diese reduziert werden sollen.
Der Anwender öffnet die Software und hat erstmal alle Datenpunkte aus der DB übersichtlich in der Chart.
Nun kann er rein, raus -zoomen.

Soweit ich das sehe, ist eine LineChart sowieso interpoliert?
Oder ist es sinnvoller einfach jeden 10.000 sten-Wert anzuzeigen?


----------



## Marco13 (6. Jan 2013)

Nochmal, ich habe noch nicht intensiv mit JavaFX gearbeitet (mal einen LineChart dargestellt, aber bin noch nicht so "drin") deswegen ist das ganze etwas distanziert: Interpoliert wird natürlich automatisch - dadurch dass Linien zwischen den Datenpunkten gemalt werden. Ich vermute, die Schwierigkeit ist in diesem Fall, die Dynamik des Zoomens reinzubringen. Einerseits die rein technische Frage, wie man immer die richtigen und sich ständig ändernden Daten in den LineChart reinbringt (was sich mit API-Doc-Lesen und ein paar Tutorials sicher lösen läßt). Andererseits die konzeptuelle Frage, wie man entscheidet, bei welcher Zoomstufe welche Punkte angezeigt werden. Man könnte sich sicher irgendwas "pragmatisches" überlegen: Man hat eine "Welt" (d.h. Weltkoordinaten) wo im Bereich [0,1000000] die 1 Million Datenpunkte liegen. Die Totalansicht bewirkt, dass dass der Bereich [0,1000000] auf die Pixel (Screenkoordinaten) [0,1000] abgebildet werden. Dann nimmt man z.B. jeden 10000. Punkt (d.h. stellt 100 Punkte dar). Wenn man dann reinzoomt, so dass ein kleinerer Weltbereich (z.B. [0,100000]) sichtbar ist, muss die Darstellung irgendwann "umspringen", so dass nicht mehr jeder 10000. Punkt, sondern jeder 1000. Punkt dargestellt wird. Da gibt es sicher schon viele Forschungsarbeiten dazu. Auf jeden Fall könnte ich mir vorstellen, dass man es nicht so "locker aus dem Handgelenk" hinschreibt, aber interessant wäre es schon...


----------



## Bernd Hohmann (6. Jan 2013)

TJava hat gesagt.:


> ich habe es mit Anfangs ca. 1.000.000 Datensätzen zu tun. Diese sollen Interpoliert werden und dann per JavaFx in einer Chart dargestellt werden.



Lassen sich die Datensätze in irgendeiner Form über die Zeit strukturieren? Dann würde ich das nämlich in mehrere "Subviews" konsolidieren (also einmalig bei der Konvertierung und dann sporadisch in einer Form des Tagesabschluss).

Also von unten nach oben erst den Mittelwert einer Minute, dann daraus den Mittelwert einer Stunde, ....eines Tages, ...einer Woche und ggf. den Mittelwert eines Monats ermitteln und abspeichern. Je nach Zoomstufe dann die entsprechende Tabelle anzapfen.

Alternativ kann man sowas via rrdjtool (erzeugt auch gleich entsprechende Grafiken) abwickeln. Letztendlich macht RRD nichts anderes als oben beschrieben. Ich habe aber vollstes Verständnis dafür, wenn Du das selber für eine bestehenden Datenbasis machen willst - bis man rrdjtool verstanden hat und nur 5% seiner Funktionalität braucht hat man es auch selber geschrieben.

Bernd

psMarco: Ich befürchte, Du denkst zu kompliziert


----------



## bERt0r (7. Jan 2013)

Also, wenn das ganze ein Line-Chart ist, würde ich so vorgehen, wenn ich das selber Zeichnen soll (von JavaFX und einer LineChart Klasse hab ich keine Ahnung).
Ich habe einen fixen Ausschnitt des Graphen, weis mein x-min und mein x-max sowie meinen Zeichenbereich in Pixel. Jetzt frag ich einfach für jeden Pixel ab, ob auf dem ein Wert liegt, wenn nicht nehme ich das mittel der zwei umliegenden Werte. 
Das heist, egal ob ich ganz rauszoome oder ganz rein, ich sehe immer nur so viele echte Datenpunkte wie mein Ausschnitt breit ist.


----------



## Bleiglanz (7. Jan 2013)

Interpolation ist wohl das falsche Wort. Du meinst ja eher sowas wie Reduktion.

Sagen wir mal in deiner Startansicht hast du Platz für 1000 Pixel.

Dann kannst du

a) zufällig tausend Werte nehmen und diese entsprechend anzeigen

b) jeden tausendsten nehmen (könnte aber die Ansicht total verfälschen)

c) 1000 Blöcke bilden, von diesen die Mittelwerte bilden und diese anzeigen (würde Ansicht "glätten", rechenintensiv)

d) ...

Es hängt auch davon ab, wie stark die einzelnen Meßwerte "streuen" bzw. ob eine Glättung erwünscht oder akzeptiert wird usw.


----------



## Harry Kane (7. Jan 2013)

@TE:
Du kannst due Anzahl Zeichenoperation einschränken, wenn du von einem Startpunkt nur dann eine Linie zeichnest, wenn der Endpunkt in x oder y Richtung mindestens eine gewisse Pixelanzahl (min. 1, max. würde ich sagen 3) entfernt ist. Dadurch vermeidest du dass Zeichenoperationen unnötigerweise an derselben Position mehrfach durchgeführt werden.
Interpoliert werden muss da mMn gar nix.


----------



## Melfis (7. Jan 2013)

Ich würde dir eine Baumstruktur empfehlen. Die Zahlen sind die Leafs und die Nodes enthalten dann den mittelwert, max, min, etc der Kinder. Einmal ein Beispiel im kleinen: 

Folgende Messwerte sind gegeben:

3;2;5;9;3,2;4;6;6

Begrenzung der Leafs auf 3:
              Mittelwert              Min              Max
Root               4.44                  2                 9       
  Node1:         3.33                  2                 5
    3;
    2;
    5;
  Node2:         4.66                  2                 9
    9;
    3;
    2;
  Node3:         5.33                  4                 6
    4;
    6;
    6;

Je nach Zoomtiefe kann eine andere Ebene zur darstellung gewählt werden. Bei 1.000.000 und einer beschränkung von 10 Zahlen pro Node komme ich auf 6 Ebenen bzw. 6 "Level-of-Detail" zwischen denen man schalten kann.


----------



## TJava (10. Jan 2013)

Bleiglanz hat gesagt.:


> Interpolation ist wohl das falsche Wort. Du meinst ja eher sowas wie Reduktion.
> 
> Sagen wir mal in deiner Startansicht hast du Platz für 1000 Pixel.
> 
> ...



Hallo, genau das ist die richtige Richtung. Ich habe die Werte und will sie mit etwas wie Bezierkurven darstellen. Die Kurven soll so geglättet bzw. gesmooth werden.

Also aus 100 Punkten keine lineare Verbindung sonder eine Bezier' 
Was gibt es da für Möglichkeiten und kann mir jemand erklären, wie genau das funktioniert?


Danke schon mal für eure Antworten.


----------



## TJava (10. Jan 2013)

Das ganze soll in gneauso funktionieren wie hier:

Highstock Demo Gallery - 52,000 points with data grouping

MfG


----------



## dauzhsdh (10. Jan 2013)

Na dann mach das doch wie dort. Man erkennt an den Knickstellen das dort zwischen zwei Punkten nur linear interpoliert wird.


----------



## Bleiglanz (10. Jan 2013)

TJava hat gesagt.:


> Das ganze soll in gneauso funktionieren wie hier:
> 
> Highstock Demo Gallery - 52,000 points with data grouping
> 
> MfG


In diesem Beispiel wird dadurch geglättet, dass man auf jeder Skala den Durchschnitt nimmt, interpoliert wird da gar nichts - schon gar nicht per Bezier.

Auf der Höchsten Stufe wird die Temperatur stündlich angezeigt und dazwischen eine Gerade genommen.


----------



## TJava (10. Jan 2013)

> a dann mach das doch wie dort. Man erkennt an den Knickstellen das dort zwischen zwei Punkten nur linear interpoliert wird.


Das ist auch  okay, nur soellen nicht einfach Punkte, weggelassen werden. 
der Informationsgehalt bleibt erhalten bzw. die Form des Graphen.

Was meinst du mit auf jeder Skala?




> In diesem Beispiel wird dadurch geglättet, dass man auf jeder Skala den Durchschnitt nimmt, interpoliert wird da gar nichts - schon gar nicht per Bezier.
> 
> Auf der Höchsten Stufe wird die Temperatur stündlich angezeigt und dazwischen eine Gerade genommen.



Was meinst du mit Skala?


----------



## dauzhsdh (10. Jan 2013)

TJava hat gesagt.:


> Das ist auch  okay, nur soellen nicht einfach Punkte, weggelassen werden.
> der Informationsgehalt bleibt erhalten bzw. die Form des Graphen.



Ja dann mach das doch so.  In der Beispielapplikation werden ab t > 1w Werte wegelassen. Alles darunter ist stündlich aufgelöst. Und so wie das aussieht werden da nur stumpf Liniensegmente zwischen den Punkten gezeichnet, was dir IMHO die API zum Zeichen schon abnimmt wenn du zwei Punkte angibst. Wenn du nun alle Punkte in den großen Zeitdarstellungen benötigst, zeichne eben alle.


----------



## bERt0r (10. Jan 2013)

Du kannst doch sowieso nur eine Auflösung von einem Punkt pro Pixel haben. Wenn du z.B pro sekunde einen Wert kriegst, die Skalierung der Zeit Achse ist aber auf 1 Minute, dann bleibt dir nix anderes über, als ein Mittel von je 60 Werten auszurechnen und dann jeweils einen Punkt machen. Oder, wenn das deine Anwendung zulässt und die Werte nicht extrem schwanken, nimmst du einfach immer den Wert der 1. Sekunde einer Minute und gut is.
Wenn du dann hineinzoomst und die Skalierung z.B auf eine Sekunde machst, siehst du alle Werte.


----------



## Spacerat (10. Jan 2013)

Schon mal 'ne AudioSkopie programmiert? Da gibt es 2 Darstellungsarten und in beiden findet eine Reduktion der Daten statt (siehe Bleiglanz Beitrag). Je nach Darstellungsart muss man die Blöcke auf verschiedene Weise erstellen...
1.
"wandernde Welle"

```
frameSize = Anzahl Samples / Anzahl Blöcke
Durchschnittswerte für / von:
1. Block Samples 0 bis frameSize
2. Block Samples frameSize bis 2 * frameSize

n. Block Samples (n - 1) * frameSize bis n * frameSize
```

2.
"stehende Welle"

```
frameSize = Anzahl Samples / Anzahl Blöcke
Durchschnittswerte für / von:
1. Block frameSize Samples im Abstand "Anzahl Blöcke"
2. Block frameSize Samples im Abstand "Anzahl Blöcke" + 1

n. Block frameSize Samples im Abstand "Anzahl Blöcke" + n
```

Glätten kann man bei Reduktion im übrigen überhaupt nicht.
Und weil das mit der "stehenden Welle" so unverständlich war, hier noch bissl' Beispielcode:

```
int w = getWidth();
			int w2 = w - 2;
			int h = getHeight();
			int b = h / 2;
			double ampHeight = b * 0.9;
			g.setColor(getBackground());
			g.fillRect(0, 0, w, h);
			g.setColor(getForeground());
			if(buffer == null || buffer[channel] == null) {
				g.drawLine(1, b, w - 1, b);
				return;
			}
			double amp;
			double cAmp = 0.0;
			double ol = Double.NEGATIVE_INFINITY;
			double ul = Double.POSITIVE_INFINITY;
			int x = 1;
			int y = 0;
			int l = buffer[channel].limit();
			int c, y2, p;
 			for(int n = 0; n < w2; n++) {
				c = 0;
				cAmp = 0.0;
				for(int step = n; step < frameSize; step += w2) {
					p = (frameCounter * frameSize + step + n) % l;
					amp = buffer[channel].get(p);
					if(ol < amp) {
						ol = amp;
					}
					if(ul > amp) {
						ul = amp;
					}
					cAmp += amp;
					c++;
				}
				cAmp /= c;
				y2 = (int) (cAmp * ampHeight);
				switch(mode) {
				case DOTTED:
					g.drawLine(x, b - y2, x, b - y2);
					break;
				case FILLED:
					g.drawLine(x, b, x, b - y2);
					break;
				case LINE:
				default:
					if(x == 1) {
						g.drawLine(x, b - y2, x, b - y2);
					} else {
						g.drawLine(x, b - y, x + 1, b - y2);
					}
					break;
				
				}
				x++;
				y = y2;
			}
```
Leider vermute ich, dass er dir für deinen Anwendungsfall nicht viel bringt, denn ich geh mal davon aus, dass du eher Fall 1 benötigst. Ich kann ja mal versuchen, ob ich den so auf die Schnelle hinbekomme.


----------



## Spacerat (11. Jan 2013)

...in einer Stunde hat's leider nicht geklappt, den Programmabschnitt zu suchen, aber hier ist er.

```
int w = getWidth();
int w2 = w - 2;
int h = getHeight();
int b = h / 2;
double ampHeight = b * 0.9;
g.setColor(getBackground());
g.fillRect(0, 0, w, h);
g.setColor(getForeground());
if(buffer == null || buffer[channel] == null) {
	g.drawLine(1, b, w - 1, b);
	return;
}
double amp;
double cAmp = 0.0;
double ol = Double.NEGATIVE_INFINITY;
double ul = Double.POSITIVE_INFINITY;
double inc = frameSize / (double) w2;
int x = 1;
int y = 0;
int l = buffer[channel].limit();
int y2, p;
	for(int n = 0; n < w2; n++) {
	cAmp = 0.0;
	for(int step = 0; step < inc; step++) {
		p = (int) (frameCounter * frameSize + n * inc + step) % l;
		amp = buffer[channel].get(p);
		if(ol < amp) {
			ol = amp;
		}
		if(ul > amp) {
			ul = amp;
		}
		cAmp += amp;
	}
	cAmp /= inc;
	y2 = (int) (cAmp * ampHeight);
	switch(mode) {
	case DOTTED:
		g.drawLine(x, b - y2, x, b - y2);
		break;
	case FILLED:
		g.drawLine(x, b, x, b - y2);
		break;
	case LINE:
	default:
		if(x == 1) {
			g.drawLine(x, b - y2, x, b - y2);
		} else {
			g.drawLine(x, b - y, x + 1, b - y2);
		}
		break;
	
	}
	x++;
	y = y2;
}
```
Eigentlich unterscheiden sich die beiden Teile nur in den Zeilen 24 bis 35, aber der Rest gehört nunmal dazu. 
"ol" und "ul" werden in beiden Fällen für die Reduzierung auch nicht benötigt. Die dienen nur zum feststellen der Spitzenwerte.


----------



## TJava (11. Jan 2013)

Leider verstehe ich den Code nicht.





> Du kannst doch sowieso nur eine Auflösung von einem Punkt pro Pixel haben. Wenn du z.B pro sekunde einen Wert kriegst, die Skalierung der Zeit Achse ist aber auf 1 Minute, dann bleibt dir nix anderes über, als ein Mittel von je 60 Werten auszurechnen und dann jeweils einen Punkt machen. Oder, wenn das deine Anwendung zulässt und die Werte nicht extrem schwanken, nimmst du einfach immer den Wert der 1. Sekunde einer Minute und gut is.
> Wenn du dann hineinzoomst und die Skalierung z.B auf eine Sekunde machst, siehst du alle Werte.



Durch Mittelwertbildung, werden allerdings die Werte wieder verfälscht. Wenn es ein Sinus  ist z.B.
würde sich ja ein Mittelwert bilden, der gegen Null geht.

mmhh ich bin echt ratlos...


----------



## TJava (11. Jan 2013)

Hallo meint ihr das solch eine Aufgabe durch eine Graphenbibliothek übernommen wird.

Also man gibt 10000 Punkte ein und diese werden auf z.B. 640 Pixel vernünftig gezeichnet?


----------



## Spacerat (11. Jan 2013)

TJava hat gesagt.:


> Leider verstehe ich den Code nicht.
> ...
> Durch Mittelwertbildung, werden allerdings die Werte wieder verfälscht. Wenn es ein Sinus  ist z.B.
> würde sich ja ein Mittelwert bilden, der gegen Null geht.
> ...


Der Code ist auch nicht jedermanns Sache. In meinem ersten Post sind aber auch zwei kurze Abschnitte, in denen die beiden Verfahren erklärt werden. Für Charts kommt natürlich nur die "wandernde" Welle in Frage, weil dieses die Abschnitte kontinuierlich reduziert, d.h. bei z.B. für die Reduktion eines Sinus von 10000 (a) Werten auf 640 (b) Werte werden pro reduziertem Wert (n) [c]a / b[/c] (m) ab Stelle [c]n * m[/c] aus [c]a[/c] addiert, durch [c]m[/c] geteilt und an Stelle [c]n[/c] der reduzierten Werte geschrieben.
Daraus folgt, dass niemals der Mittelwert des gesamten Sinus errechnet wird, welcher deswegen auch nicht 0 werden kann. Allerdings, wenn man nun den Mittelwert der Reduzierten Werte errechnet, dürfte dieser auch wieder gen 0 gehen.
Aber wenn der JavaFX-Chart das ohnehin automatisch macht (entzieht sich meiner Kenntnis) braucht man sich ja selber nicht mehr um diese Reduktion kümmern.


----------



## TJava (17. Jan 2013)

Hallo, 

danke für diese Erklärung.
Ich übergebe JavaFx teilweise 3000 Punkte und daraus entsteht ein Punktebrei.
Das heißt JavaFx macht es nicht von selbst oder sehe ich das Falsch?


----------



## Spacerat (17. Jan 2013)

TJava hat gesagt.:


> Ich übergebe JavaFx teilweise 3000 Punkte und daraus entsteht ein Punktebrei.
> Das heißt JavaFx macht es nicht von selbst oder sehe ich das Falsch?


Ich weis es wirklich nicht... Hast evtl. mal'n paar Screenshots (Ausschnitt Original und ChartView)? Es wäre zumindest recht unlogisch, wenn es die Chart nicht selber machen würde, weil wozu bräuchte man sie denn, wenn man diese Berechnung nebst Anzeige auf jedem Panel mitels "paintComponent()" selber implementieren kann.
[OT]Ehrlich gesagt halte ich auch nicht viel von JavaFX, ist auch nur 'ne Lib, die den kardinalsten Fehler wiederholt und dass nur, weil's anscheinend nicht anders geht. Betrifft: Dateitypen.[/OT]


----------

