prev up inhalt next


3.1 Koordinatensysteme

Die Angabe eines Punktes geschieht meistens durch kartesische Koordinaten x,y .

Eine Folge von Punkten kann absolut oder relativ spezifiziert werden:

Absolut:
Jeder Punkt der Folge wird durch seine kartesischen Koordinaten beschrieben.
Relativ:
Jeder Punkt der Folge wird unter Verwendung einer Windrose (Abbildung 3.1 ) relativ zum Vorgänger der Folge beschrieben, entweder mit absoluten Richtungscodes oder mit relativen Richtungscodes.


Windrose

Eine Verwendung von absoluten Richtungscodes ergibt für die Figur in Abbildung 3.2 die Folge 0,2,1,2,2,0, - 2, - 2, - 1, - 2 . Der relative Richtungscode legt nach jedem Schritt die momentane Richtung als ``0'' fest. Es ergibt sich für die Figur in Abbildung 3.2 die Folge 0,2, - 1,1,0, - 2, - 2,0,1, - 1 .

Zur Platzeinsparung werden die ``wahrscheinlicheren'' Richtungsänderungen mit weniger Bits codiert. Tabelle 3.1 zeigt eine mögliche Codierung, basierend auf den Wahrscheinlichkeiten in Spalte 1. Der zu diesen Wahrscheinlichkeiten konstruierte Huffman-Code wird mit Hilfe des Baumes in Abbildung 3.3 ermittelt. Für die Figur in Abbildung 3.2 entstehen dann statt (10 × 3) = 30 Bits nur noch 26 Bits.


Beispiel für Streckenzug

% Richtung Code Bit-Länge
28 0 00 2
26 1 01 2
24 -1 10 2
7 2 1100 4
6 -2 1101 4
4 3 1110 4
3 -3 11100 5
2 -4 11111 5
Tabelle 3.1: Relative Richtungscodes


Code-Baum basierend auf Wahrscheinlichkeiten


prev up inhalt next