Hilfe der vorhandenen Information innerhalb des 
Fensters abgeschätzt werden. Dieses kritische 
Problem mit einer gewissen Unsicherheit läßt sich 
durch eine Strategie  Depth-First-Search mit 
Backtracking automatisch lósen: dabei wird ein 
beliebiger Kandidat einfach als der Ausgangspixel 
des Fensters angenommen und die 
anderen Kandidaten werden für das eventuelle 
Backtracking aufbewahrt, damit die Suchvorgänge 
weiter durchführen kónnen. Gleicht die Anzahl 2, 
die kein Ausgangspixel mehr impliziert, so wird 
entweder ein automatisches . Backtracking 
vorgenommen, falls entsprechende Pixeln für 
das Backtracking noch vorhanden sind, oder die 
Suchvorgánge werden gestoppt : ein Vektorobjekt 
ist erstellt. Abb. 3.2 zeigt diese Strategie, wobei 
jede Kante für ein Ausgang steht und jeder Knoten 
für ein Fenster steht. Die Ziffern zeigen die 
Bearbeitungsreihenfolge. 
Kante: Ausgang 
Knoten: Fenster 
  
Abb.3.2 Depth-First-Search mit Backtracking 
Wenn ein Vektorobjekt bereits erzeugt ist, wird es 
überprüft, ob dieses Objekt weiter unterteilt werden 
kann. Beispielsweise wird das Objekt wie in Abb. 
3.3 durch eine Binárbaum-Strategie mit Depth-First- 
Search in 4 Objekte weiter unterteilt. 
Object o 
b o 
(ed) — (b) 
Ged 
Eu A 
Abb. 3.3 ein Binärbaum zur Unterteilung des 
Objektes in 4 Objekte 
Schließlich wird jedes Objekt überprüft, ob es 
andere Objekte enthält. Falls ja, werden die 
164 
enthaltenen Rasterobjekte nacheinander in die 
entsprechenden Vektorobjekte umgewandelt. Dies 
geschieht wiederum durch eine Strategie Depth- 
First-Search mit Backtracking, die in Abb. 3.4 
illustriert wird. Ebenfalls stehen dabei die Ziffern für 
die Bearbeitungsreihenfolge. 
  
Abb. 3.4 Depth-First-Search mit Backtracking zur 
Vektorisierung der enthaltenen Objekte 
4. RASTERISIERUNG 
Bei dieser Transformation wird jeweils ein 
Vektorobjekt in Rasterdaten umgewandelt. Das 
Prinzip einer solchen Transformation läßt sich 
durch Abb. 4.1 erläutern. In Abb.4.1 sei P ein Pixel, 
V sei ein zu rasterisierendes Vektorobjekt, und S 
sei die Anzahl der Schnittpunkte auf V, deren X- 
Koordinaten kleiner als X-Koordinate des Pixels P. 
Ist S gerade, so liegt P außerhalb V. Ist S 
ungerade, so fällt P innerhalb V und Pixel P wird 
der Grauwert von V zugeordnet. 
Y=Yp 
  
YF 
5=2 
  
  
Abb. 4.1 Das Prinzip der Rasterisierung 
Um die Transformation zu beschleunigen, wurden 
bei der Programmierung einige effektive 
Maßnahmen ergriffen, die hier nicht mehr näher 
besprochen werden. Die Wirkung zeigt sich durch 
die Transformationen der Grauwertbilder in dem 
nächsten Abschnitt. 
Falls ein Objekt andere Objekte enthält, werden die 
enthaltenen Objekte zuerst rasterisiert. Ebenfalls 
erfolgt dies durch eine Strategie Depth-First-Search