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