Home

Visualisierung geometrischer Datenstrukturen

1. 126 8 4 8 Animationen zum Priorit tssuchbaum 127 8 4 9 Demos zum Prort tssuchbaum 132 9 5 40 00 4292 135 9 1 TESTSZUM2 D BAUM 220004 keins keller 136 9 2 TESTS ZUM PRIORIT TSSUCHBAUM 2 ndeso Er EEE ES seuas ESES EE EE SEEE EEs ENEE 143 10 BEDIENUNGSANLEITUNG DES PROGRAMMS VISUALGEOM zussssossssonsssnnsssnssssosssnnnesnnnsnnnne 152 10 1 SYSTEMVORAUSSETZUNGEN sar Ene sehn lebe ansehe lin 152 10 2 2006 154 10 3 155 10 4 STARTEN DER ANWENDUNG ED ECSS 156 10 5 DASSTARTME Rh Sa VEETEE EDEIS 158 Inhaltsverzeichnis 10 6 DER 2 D BAUM ege Ra EIERN ENDE ED a ie 159 10 6 1 Interpretation der Ausgaben zum 2 4 161 10 6 2 Das Menu Datei zum 2 4 164 10 6 3 Das Men Bearbeiten
2. em em em gefundene Punkte Vorg nge im Baum darstellen PUNKTDARSTELLUNG aan a nu BAUMDARSTELLUNG 1 I 1 I I I I 1 I I I 1 I i i markieren I I 1 I I I Abbildung 28 Aktivit tsdiagramm Anfragerechteck Mit diesen transformierten Werten f hrt das Programm im aktuellen 2 d Baum eine Bereichsanfrage durch Die berlegungen f hren zu dem Aktivit tsdiagramm in Abbildung 28 55 Zur Erl uterung der Symbole siehe Tabelle A9 39 Elaboration Systemanalyse und Entwurf Visualisieren der Bereichsanfrage Als Visualisierung des Anfragealgorithmus wird ausschlie lich die farbliche Kennzeichnung der angefassten Knoten und der ausgew hlten Bl tter verwendet Dies erscheint uns ausreichend da im Eingabebereich gleichzeitig erkennbar ist welche Punkte im Anfragerechteck liegen und welche Splitbereiche von dem Anfragerechteck geschnitten werden Wie Abbildung 29 zeigt werden die dabei besuchten Pfade und die gefundenen Punkte gr n hervorgehoben 216 1 22 3 18 615 8 13 519 721 Abbildung 29 Beispielskizze zum Anfragerechteck 7 4 3 5 Aufbau des allgemeinen 2 d Baums Mit dem allgemeinen 2 d Baum liegt ein tern rer Suchbaum vor F r diesen ist der Algorithmus f r das sch ner Zeichnen von Kapitel 8 2 2 nicht unmittelbar verwendbar Damit verbleiben un
3. Rein ker Use Cases z m 27d BIU E Ed 7 4 3 Analyse mit Aktivit tsdiagrammen 7 4 3 1 Punkt in den dynamischen 2 d Baum 7 4 3 2 Punkt aus dem dynamischen 2 d Baum l schen 7 4 3 3 Punkte in den ausgeglichenen 2 d Baum einf gen 7 4 3 4 Rechteckanfrage durchf hren u 7 4 3 5 Aufbau des allgemeinen 2 d Baums 7 4 3 6 Demo TAST Spezielles 2 EES 7 5 ELABORATION DES PRIORIT TSSUCHBAUMS 1 7 5 1 E ben in Eisler serien ST 5 5020 7 5 1 2 semidynamische Priorit tssuchbaum 7 5 1 3 Der dynamische Dor tssuchbaum 7 5 1 4 balancierte dynamische Priort tseuchbaum 1 5 2 Use Cases zum Priorit tssuchbaum Inhaltsverzeichnis 1 5 3 Analyse mit Aktivit tsdiagrammen eessseeseseesreesrreriessrssrtsrestrtstrestresressrersresseseresteese 68 7 5 3 1 Punkt in dynamischen Priorit tssuchbaum einf gen
4. 69 7 5 3 2 Visualisieren des Bnft ecvorgange 71 7 5 3 3 Punkt aus dem dynamischen Priorit tssuchbaum l schen 75 7 5 3 4 Visualisieren des L schvorgangs u Niinon asi EEE EEE EE EA ERREA 75 T 5 3 5 gt Bereichsanfrase durchf hren eet ENEE deed Eeer 78 Ar EE AE 80 7 5 3 7 Spezielles Men system zum Pr ortt tssuchbaum 80 1 6 NORL UFIGE KLASSENBILDUNG 2212 Asa ee e 81 8 CONSTRUCTION ERZEUGUNG 22uusss0ssssossssossesonnsssnnssnnsssnnsssnnnnsnnnnssnnnssnnsssnnnnsnnnnsnnnnssnnnssnnnnsnnnnenen 85 8 1 ITERATIVE UND INKREMENTELLE 85 8 2 ENTWICKLUNG DER GEMEINSAMEN 85 8 2 1 Entwicklung der Benutzeroberfl che nen 86 8 2 2 Algorithmus zum sch nen Zeichnen der Suchb ume 92 8 2 3 eet eege eege Ee 95 8 2 4 Drucken 20 97 8 2 5 Speichern und Laden der 98 8 2 6 Auswahl des Grafikformates sssneseeeesseeeeeerseeeessetesseetesseresssrressteressterssstreesseresssteessteeessesssteesstt 98 8 227 DasJava HilfesysteM senhe E a A E A AEEA 99
5. TreeCanvasToTernaerAdapter VmouseClickedd _listModel X InputAreaToStatuslineAdapter Pointlist PointlistToviewAdapter EH _model_1 stateChanged0 view Abbildung 64 Klassendiagramm zum tern ren 2 d Baum 9 Zur Erl uterung der Symbole siehe Tabelle A10 Zum Frstellen des Diagramms wurde die Demoversion des Programms Rational Rose 98 eingesetzt 115 Construction Erzeugung 8 3 7 Animierter Aufbau des 2 d Baums Im Kapitel 7 4 haben wir als Designentscheidung festgelegt dass wir beim Einf gen von Punkten in den 2 d Baum auf eine Animation per Bewegung verzichten Die Visualiserung soll aus schlie lich ber den Farbeinsatz erfolgen Insofern ist der Name Animation beim 2 d Baum teilweise unpassend Wegen einer einheitlichen Men oberfl che haben wir uns allerdings daf r entschieden wie beim Priorit tssuchbaum den Men punkt animiert zu verwenden Animiertes Einf gen im dynamischen 2 d Baum Die vom Algorithmus eingeschlagenen Wege im Baum werden rot eingezeichnet Die beiden Punkte die f r die aktuelle Berechnung des neuen Splitwertes verwendet werden erscheinen ebenfalls in rot Dazu muss die Methode insertPoint aus der Klasse DrawableKdTree so erweitert werden dass in allen beim Einf gen angefassten Knoten das Flag _marked auf true gesetzt wird Die paint Methode
6. 2 2 2 00000200000000000000000040 00000 0 BEDEUTUNG DER DREI BUTTONS BEIM PpRIORIrtATSSUCHRBAUNM PRIO MEN PUNKTE DES DATEI MEN S TEIL IN PRIO MEN PUNKTE DES DATEI MEN S TEIL 2 2 0 PRIO MEN PUNKTE DES BEARBETTEN MewOs PRIO MEN PUNKTE DES MEN S STRUKTURVARIANTE TEIL In PRIO MEN PUNKTE DES MEN S STRUKTURVARIANTE TEIL 2 PRIO MEN PUNKTE DES MEN S OGTIONEN PRIO MEN PUNKTE DES 058 002 0002200000000000000 000040000 0 Einleitung Tell me and I forget Teach me and I remember Involve me and I learn Benjamin Franklin RICH89 1 Aufgabenstellung Mit dieser Diplomarbeit haben wir vom Lehrgebiet Praktische Informatik VI den Auftrag erhal ten ein Java Programm zur Visualisierung der geometrischen Datenstrukturen 2 dimensionaler Suchbaum und Priorit tssuchbaum zu erstellen Beide B ume sind Beispiele f r Datenstrukturen die in der algorithmischen Geometrie genutzt werden um effizient Punkte in der Ebene zu spei chern Sie unterst tzen die Suche nach einzelnen Punkten und Bereichsanfragen Der 2 dimensionale Suchbaum Der 2 dimensionale Suchbaum 2 d Baum stellt eine Erweiterung des eindimensionalen Such baums dar Auf jeder Ebene des Suchbaums wird die nach der jeweiligen Koordinate sortierte Punktmenge zyklisch nach einer der beiden Koordinaten aufgeteilt Di
7. Nach dem Entfernen der Punkte auf allgemeine 2 d Baum Datei Bearbeiten Strukturvariante Optionen Hilfe der Splitgeraden bleibt nur noch ein Anfrage l schen Baum zeichnen Punkt bri unkt brig Damit ist eine Teilpunktliste leer die andere enth lt nur einen Punkt Dieser Punkt muss rechts oder links am Splitknoten angeh ngt werden Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Abbildung 59 Restpunktliste mit einem Punkt Nach dem Entfernen aller Punkte auf der Splitgeraden enth lt die Restpunktliste nur noch zwei Punkte Hierbei sind zwei weitere F lle zu unterscheiden e Der eine Punkt liegt rechts und der andere links von der Splitgeraden Abbildung 60 e Beide Punkte liegen rechts oder links von der Splitgeraden Abbildung 60 Der allgemeine 2 d Baum oj xi Datei Bearbeiten Strukturvariante Optionen Hilfe Der allgemeine 2 d Baum ol Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Anfrage l schen Baum zeichnen 24 Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Abbildung 60 Restpunktliste mit zwei Punkten Nach dem Entfernen aller Punkte auf der Splitgeraden enth lt die Restpunktliste nur noch drei Punkte Hierbei sind zwei weitere F lle zu unterscheiden
8. Knoten beim 2 d Baum Knoten beim tern ren 2 d Baum 0 1 1 1 2 3 2 4 8 3 8 27 4 16 48 5 32 128 Tabelle 1 7 4 3 6 Demo aufrufen Maximale Knotenanzahl des allgemeinen 2 d Baums Es werden Demos zum dynamischen und zum ausgeglichenen 2 d Baum angeboten Nutzt der Benutzer eines der Demos wird ihm in einer Sequenz gezeigt wie die Algorithmen zum Einf gen 61 Elaboration Systemanalyse und Entwurf und L schen von Punkten ablaufen und wie dabei die Splitgeraden im Eingabebereich eingezeichnet werden Abschlie end werden ein Anfragerechteck im Eingabebereich eingezeich net und alle angefassten bzw im Rechteck enthaltenen Punkte im Baum markiert Nach jeder Ak tion soll f r den Benutzer die M glichkeit bestehen das Demo ber eine Schaltfl che zu beenden W hrend ein Demo abl uft muss dem Benutzer durch einen erkl renden Text im Eingabebereich verdeutlicht werden ob ein Punkt gerade eingef gt oder gel scht oder eine Anfrage durchgef hrt wird 7 4 3 7 Spezielles Men system Dem Benutzer sollen die verschiedenen Baumvarianten die Einstelloptionen f r die Darstel lungsart des Baumes und die Auswahl der Demos ber ein Men system angeboten werden Deshalb wird f r den 2 d Baum zun chst das Men system aus Abbildung 30 geplant Es ber cksichtigt auch bereits Men punkte die erst sp ter bei der Erweiterung des Programms aufgegriffen werden sollen Die Bedeutung der einzelnen Men punkte
9. Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Abbildung 62 Restpunktliste mit mehr als drei Punkten 113 Construction Erzeugung Kennzeichnen der Knoten an denen 1 d B ume h ngen Die paint Methode in KdTreeCanvas ber cksichtigt ob sich am gerade zu zeichnenden Splitknoten ein 1 d Baum befindet Ist dies der Fal wird durch die Methode _drawReferenceLeafSearchTree eine blaue Markierung als Hinweis auf den 1 d Baum eingezeichnet Einbinden separater Fenster f r die 1 d B ume F r die Reaktion auf Mausaktionen in der Baumzeichenfl che musste ein zus tzlicher Controller beim KdTreeCanvas angemeldet werden Dadurch kann der Benutzer jetzt einen Knoten im 2 d Baum anklicken um dessen mittleren Blattsuchbaum zu betrachten Dieser Controller ermittelt den x und y Wert des angeklickten Punktes in der Zeichenfl che Damit durchsucht er den DrawableKdTree um den angeklickten Knoten zu ermitteln Abbildung 63 zeigt dass in Sonderf llen ein unausgeglichenen 2 d Baum entsteht Der allgemeine 2 d Baum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen 12 14 1 3 15 13 0 Zum Anzeigen der mittleren B ume auf einen Abbildung 63 unausgeglichene Form des 2 d Baums Weil es im unausgewogenen Baum m glich ist dass ein Knoten im linke
10. i Abbildung 77 Interaktionsdiagramm zum Zusammenspiel der Threads Erl uterungen zum Interaktionsdiagramm von Abbildung 77 Der zun chst gestartete Demo Thread _demo3 setzt die Variable more in PrioTreeGUI auf false ruft dann das Einf gen des ersten Punktes in die Punktliste und den Baum auf Am Ende der Modell nderungen werden die ChangeListener verst ndigt 8 Zur Erl uterung der Symbole siehe Tabelle All 133 Construction Erzeugung Das Zeichnen des Punkteinf gens in den Baum geschieht durch den Thread _points Der ChangelListener bergibt ihm daf r ein BufferedImage der Zeichenfl che Jedes ver nderte Bild schickt der Zeichenthread zum Anzeigen an die Instanz von PrioTreeCanvas Am Ende der run Methode setzt points die Variable more auf true damit der n chste Einf gevorgang beginnen kann Nach Abschluss der run Methode wird die Zeichenthread instanz automatisch gel scht Der Demo Thread _demo3 hat gewartet bis more den Wert true aufweist Jetzt kann er mit dem Einf gen des n chsten Punktes fortfahren 134 Programmtest 9 Programmtest Nach dem Rational Unified Process endet jede Iteration mit einer Ergebnispr fung dem Review Wir m ssen also Testsituationen Testf lle und Testdaten aufstellen mit denen sich das jeweilige Iterationsziel m glichst genau berpr fen l sst Um den Anforderungen der analytischen Qualit tssicherung zumindest ansatzweise
11. Beispiel 1 Test des Aufbaus eines leeren Baums 136 Programmtest Erwartetes Ergebnis Verhalten des Programms Beim Bet tigen des Buttons Baum zeichnen muss der Wurzelknoten als Blatt im Ausgabebereich erschei nen und an ihm der Punktwert aus gegeben werden Es existiert noch keine Splitgerade Der ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Test des Aufbaus des Baums mit einem Knoten Beispiel 2 Erwartetes Ergebnis Verhalten des Programms Beim Bet tigen des Buttons Baum zeichnen muss der Splitwert als Mittelwert der beiden x Koordinaten berechnet der Knoten mit dem Split wert und die beiden Bl tter mit den Punktwerten im Ausgabebereich dar gestellt werden Im Eingabebereich ist mit dem Splitwert eine senkrechte Gerade einzuzeichnen Der ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Test des Aufbaus des Baums mit zwei Knoten Beispiel 3 Erwartetes Ergebnis Verhalten des Programms Auch nach dem Speichern einer leeren Punktliste soll das Laden ohne Fehlermeldung m glich sein Dem Benutzer ist mitzuteilen dass die ge ladene Punktliste leer ist und deshalb kein Baumaufbau erfolgt Der ausgegliche
12. Bereichsanfrage mit Anfragerechteck Benutzer Abbildung 13 Use Case Diagramm F r die drei verschiedenen Arten von 2 d B umen lassen sich die F lle Punkt im 2 d Baum einf gen und Punkt aus 2 d Baum l schen in Unterf lle aufteilen Dies wird im weiteren exem plarisch beschrieben Auch die F lle Bereichsanfrage mit Anfragerechteck und Demo starten werden genauer betrachtet 2 Zur Erl uterung der Symbole siehe Tabelle A8 40 Elaboration Systemanalyse und Entwurf Use Case Punkt in den dynamischen 2 d Baum einf gen Der Benutzer klickt mit der linken Maustaste einen Punkt im 1 Quadranten der Ebene an Dabei werden nur Punkte mit ganzzahligen Koordinatenwerten zuge lassen Der Punkt wird in den Eingabebereich eingezeichnet Die Einf geposition des Punktes im 2 d Baum wird bestimmt Die Splitkoordinate und der Splitwert werden ermittelt Der Knoten mit dem neuen Splitwert wird in den 2 d Baum eingef gt Das Blatt mit dem neuen Punkt wird in den Baum eingef gt Die Splitgerade wird in der Ebene dargestellt Im Ausgabebereich wird der 2 d Baum auf unterschiedliche Weise gezeichnet Der Baum mit dem neu eingef gten Punkt wird sofort angezeigt Der Weg beim Einf gen wird dem Benutzer durch eine farblich hervorge hobene Kennzeichnung aller angefassten Punkte veranschaulicht Use Case Punkt aus dem dynamischen 2 d Baum l schen Der Benutzer kl
13. 2 A 2 1 Anleitung zum Erstellen der Hilfedateien an einem Beispiel Allgemeine Hinweise Zur besseren bersichtlichkeit ist es empfehlenswert das Hilfesystem in ein eigenes Unterver zeichnis zu packen Dies sollte f r die Images und die Hilfedateien ebenfalls erfolgen Abbildung 1 glkdHelp Laus ausgabe einaus eingabe ay hg_see af toplevel u alltree ip distree CH structure mouse GJlstructure u dversion ip sversion kdHelp kdstart kdHelpindex EkdHelpTOC html html html gif gif gif gif gif html html html html html html html html html html hs html ihm Beispiel f r die Aufteilung der Verzeichnisse Anleitung zum Erstellen der Hilfedateien an einem Beispiel Zun chst werden mit einem geeigneten Editor 7 Netscape Composer Frontpage die HTML Dateien mit den Hilfetexten erstellt Diese werden um die bersichtlichkeit sicherzustellen geeignet in verschiedenen Unterverzeichnissen abgelegt Abbildung A1 Sind diese Dateien fertig m ssen sie mit dem Hilfesystem verkn pft werden Wie der Quellcode in Abbildung 54 zeigt wird der Applikation der Name der HelpSet Datei bekannt gegeben Dies ist erforderlich da eine Applikation verschiedene HelpSet Dateien nutzen kann Es m s
14. Elaboration Systemanalyse und Entwurf 7 5 2 Use Cases zum Priorit tssuchbaum Nach den berlegungen zur darzustellenden Datenstruktur werden jetzt exemplarische Anwen dungsf lle zur groben Abstimmung dessen erarbeitet was das zuk nftige Programm f r das Ar beiten mit dem Priorit tssuchbaum anbieten soll Der Benutzer soll zu verschiedenen Varianten des Priorit tssuchbaums Punkte einf gen und ent fernen und eine Bereichsanfrage durch Festlegen eines Anfragehalbstreifens starten k nnen Nach allen Aktionen erfolgt ein Neuzeichnen des aktuellen Priorit tssuchbaums Einf hrende animierte Demonstrationen sollen dem Benutzer das Arbeiten erleichtern Dies f hrt zu dem allgemeinen Use Case Diagramm von Abbildung 31 Punkt im Priorit ts suchbaum einf gen Punkt aus Priorit tssuchbaum l schen Bereichsanfrage mit Anfragehalbstreifen Abbildung 31 Use Case Diagramm Benutzer F r die vier verschiedenen Arten des Priorit tssuchbaums lassen sich die F lle Punkt in Priori t tssuchbaum einf gen und Punkt aus Priorit tssuchbaum l schen in Unterf lle aufteilen Nachfolgend werden beispielhaft diese Anwendungsf lle zum dynamischen Priorit tssuchbaum aufgef hrt 61 Zur Erl uterung der Symbole siehe Tabelle A8 66 Elaboration Systemanalyse und Entwurf Use Case Punkt in den dynamischen Priorit tssuchbaum einf gen Der Benutzer klickt einen Punk
15. T mouseClicked changeListeners i EventListenerList Point2D M 422i Double i N insertTest point T showOpti onDidl og 4 Di logfenster Splitrichtung i gt splitdirection showInputDialog t Dial ogfenster Splitwert litvalue 4 sp insertPoint point splitvalue getListenerLi st i listeners stateChanged Changed _treelvlodel Abbildung 55 Interaktionsdiagramm zum dynamisch interaktiven 2 d Baum Zur Erl uterung der Symbole siehe Tabelle All 105 Construction Erzeugung Hinweis zum Zeichenbereich Der Zeichenbereich f r die B ume ist beschr nkt auf 1400 Bildpunkte in x und 550 in y Richtung Dabei liegen die Knotenebenen im y Ab stand von 50 Bildpunkten Der ge ringste Abstand in x Richtung be tr gt 40 Gerade beim dynamischen 2 d Baum kann dieser Zeichenbereich schnell verlassen werden Deshalb haben wir die Methode controlDrawing in der Klasse DrawableKdTree implementiert Sie kontrolliert ob der zu zeichnende Blattknoten noch innerhalb des darstellbaren Bereiches liegt und liefert den gefundenen Abbildung 56 Knoten nicht im Zeichenbereich Zustand als booleschen Wert zur ck Der boolesche Wert ist false wenn die Anzahl der Ebenen gr er als 10 oder der x Wert des zu zeichnenden Blattes au erhalb des Inte
16. als Gruppenarbeit erstellt Die Ab grenzung der Themen in der Arbeit und der Programmteile zwischen Ingrid und Klaus Dieter Schumacher erfolgte gem der nachfolgenden Tabelle Ingrid Schumacher Klaus Dieter Schumacher Programmcode Priorit tssuchbaum ohne Drucken Dateiverwaltung und Hilfesystem Benutzeroberfl che e Men klassen Implementation als Applet Blattsuchbaum Implementierung des Algorithmus f r das sch ner Zeichnen 2 d Baum ohne Men klassen Applet Blattsuchbaum und den Algorithmus f r das sch ner Zeichnen Methoden zum Laden und Speichern der Punktliste e Methoden zum Drucken von Eingabe und Ausgabebereich e Methoden zum Speichern von Eingabe und Ausgabebereich als JPEG Datei e Methoden zum Hilfesystem hs Index und Hilfedateien Kapitel der Diplomarbeit 1 2 7 5 8 2 1 8 2 2 8 4 9 2 10 7 3 4 5 7 4 8 2 4 bis 8 2 7 8 3 9 1 10 6 A2 Alle nicht genannten Kapitel der Diplomarbeit und des erstellten Programmcodes lassen sich nicht unmittelbar einem von uns beiden zuordnen 180 Erkl rung Erkl rung Hiermit versichern wir dass wir die Diplomarbeit selbst ndig mit der unter Aufteilung der Gruppenarbeit genannten Abgrenzung verfasst haben Auch haben wir keine anderen als die angegebenen Quellen und Hilfsmittel benutzt Zitate sind als solche in der Arbeit kenntlich gemacht worden Stockelsd
17. 1 2 1_03 zu folgender Fehlermeldung Exception occured during event dispatching java lang IllegalArgumentException NumComponents not in sync with COLOR_ID at com sun codec jpeg JPEGCoder getDefaultJPEGEncoderParam Diese Fehlermeldung konnte auch durch eine Ausnahmenbehandlung nicht abgefangen werden Aktuell ist auch die Internetnutzung nur eingeschr nkt m glich da f r das Starten des Applets mit dem Netscape Communicator oder dem Internet Explorer zun chst das JRE2 vom SUN Server gezogen und installiert werden muss Des weiteren existiert immer noch kein hierf r erfor derliches Plug In unter Linux Auch muss die HTML Startseite mit dem HTML Converter von SUN f r die Nutzung des Plug Ins vorbereitet werden Das Ergebnis diese Aufbereitung ist allerdings auch dass eine derart aufbereitete HTML Seite nicht mehr mit dem appletviewer geladen werden kann Auch hier lie sich die Fehlermeldung nicht behandeln Wird VisualGeom als Applet mit dem appletviewer genutzt so ergibt sich bei dem Versuch der Nutzung von JavaHelp die Fehlermeldung dass javax help HelpSet nicht gefunden w rde Mit dem Einbinden der Helpset jar Datei mittels archive in den applet Tag der HTML Datei konnten wir zwar diesen Fehler beseitigen Daf r lie en sich dann die Hilfe dateien nicht laden Da Applets in einer Sandbox ablaufen sind ohne Signieren Datei und Druckoperationen nicht zugelassen Dies muss aber getrennt f r jeden Browser vorgenommen we
18. Dieses auf der Lebenslinie platzierte Symbol kennzeichnet den Steuerungsfokus Er gibt an welches Objekt aktuell aktiv ist p gt Die waagerechten Pfeile visualisieren Nachrichten zwischen t den durch die Lebenslinien symbolisierten Objekten Auf einem Pfeil wird die jeweilige Nachricht notiert R Mit diesem Symbol ber einem Steuerungsfokus ver deutlichen wir dass das Ausl sen der betreffenden Nachricht durch den Akteur verursacht wurde Tabelle 11 Verwendete Interaktionsdiagrammsymbole A 17 Anmerkungen zur Plattformunabh ngigkeit 4 Anmerkungen zur Plattformunabh ngigkeit Zum Thema Plattformunabh ngigkeit von Java stellt HOLU98 fest Unfortunately Java s promise of platform independence falls flat on is face in the threads arena This isn t really Java s fault it s almost impossible to write a truly platform independed threading system Dies mussten wir leider wiederholt bei den Programmtests feststellen Anfangs war Lauf zeitverhalten der Animationen unter Windows 95 98 Linux und Solaris recht unterschiedlich Es wurden diverse Klimmz ge erforderlich um ann hernd vergleichbares Verhalten zu erzielen Unter Windows liefen die Animationen bereits bei unseren ersten Programmierversuchen recht fl ssig ab w hrend sie unter Linux und Solaris nicht vertretbar langsam waren Zu bedenken bleibt dabei dass Java 10 Priorit tsebenen f r Threads unterst tzt w hrend S
19. Wir k nnen also nur ein grunds tzliches Verst ndnis ber B ume und deren Aufbau voraussetzen Einf gen L schen und Balancieren sind bekannte Begriffe jedoch nicht so pr sent dass fl ssig und verst ndig mit ihnen gearbeitet werden kann Die Studenten ben tigen deshalb animierte Visualisierungen beim Aufbauen Einf gen und L schen der beiden Suchb ume Des weiteren sollen sie m glichst erfahren was das Entarten von B umen bedeutet und wie sich damit das Laufzeitverhalten ver ndert Dabei ist die wesentliche mit dem Programm zu verfolgende Intention dass die Studenten die im Kurstext beschriebenen beiden Suchb ume interaktiv erleben k nnen Geeignete Ausf hrungen zur Evaluation von Software finden sich unter FU4763 Seite 86 bis 110 Eingangsvoraussetzungen der Adressaten Des weiteren setzen wir bei den Benutzern grundlegende F higkeiten und Fertigkeiten im Um gang mit Tastatur Maus Bildschirm und Anwendungssoftware voraus Dies schlie t auch die F higkeit ein unser Programm einschlie lich dem Java Runtime Environment JRE2 oder dem Java Development Kit JDK2 gem einer Anleitung auf der Festplatte zu installieren Als zus tzliche Rahmenbedingung wollen wir ber cksichtigen dass die Studenten bis zu diesem Zeitpunkt ihres Studiums zumeist nur Erfahrungen im Umgang mit Microsoft Oberfl chen gemacht haben Deshalb wollen wir uns bei der Gestaltung des Men systems daran orientieren S
20. angefasste Knoten umgeh ngter Knoten neu eingef gter Punkt und Knoten neu eingef gter Splitknoten und neue Splitgerade Wird ein Anfragerechteck einge zeichnet werden alle bei der Anfra ge angefassten Knoten durch gr ne Kreise gekennzeichnet Liegt ein Punkt im Anfragerechteck wird zus tzlich der Punktwert gr n dar gestellt angefasster innerer Knoten angefasstes Blatt Punkte in Anfragerechteck Anfragerechteck 161 Bedienungsanleitung des Programms VisualGeom ausgeglichene 2 d Baum mit disjunkten Koordinaten Zun chst werden die Punkte eingege Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen FTE ben Das Bet tigen des Buttons zeichnen bewirkt die Durchf hrung des ersten Schrittes Die Punktemenge wird zun chst nach der x Koordinate sortiert Dann wird als arithmetisches Mittel der benachbarten x Koordinaten 8 und 9 der Splitwert 8 5 berechnet Die Punktmenge wird in zwei gleich m chtige oder sich um maximal 1 unter scheidende Teilmengen aufgeteilt Diese h Koordinat iert Abbildung 83 Schrittweiser Aufbau des aus WER geglichenen 2 d Baums und sind in rot dargestellt allgemeine 2 d Baum ioj x Datei Bearbeiten Strukturvariante Optionen Hilfe Aus dem Eingabebereich von Abbildung 84 wird ersichtlich dass vier Punkte mit Anfrage l schen Baum zeichnen iden
21. 119 INTERAKTIONSDIAGRAMM EINF GEN IM SEMIDYNAMISCHEN BAUM TEIL 2 120 BEREICHSANFRAGE IM SEMIDYNAMISCHEN 5 2 2 L SCHEN EINES PUNKTES IM DYNAMISCHEN 5 2 2 24 LINKSVOLLST NDIGE BAOMSKELETTE BEISPIEL ZUM PUNKTEINF GEN DEN DYNAMISCH BALANCIERTEN BAUM ERWEITERUNG DES ALTEN BAUMS EINF GEN EINES NEUEN EINF GEN EINES NEUEN DUNKTES ANIMIERTES EINF GEN MIT VERDR NGEN EINES PUNKTES ANIMIERTES L SCHEN IM DYNAMISCHEN PRIORIT TSSUCHBAUM 9 INTERAKTIONSDIAGRAMM ZUM ZUSAMMENSPIEL DER STARTMEN DER APPLIKATION VON VISUALGEOM STARTMEN DES APPLETS VON VISUALGEOM uueeeessssennnenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn STARTFENSTER DES 2 p BaAUwMS ANIMIERTER DYNAMISCHER Z p BaAUM ANFRAGE DURCHFORHREN SCHRITTWEISER AUFBAU DES AUSGEGLICHENEN 2 D BAUMS ALLGEMEINER 2 D BAUM TEIL 1 2 ATLLEGEMEINER Z B BAUM in antenne anlegen ee EE eege STARTFENSTER DES ANIMIERTER AUFBAU BEIM SEMIDYNAMISCH STATISCHEN
22. 2 A 52 Na A GE AR 2 AR 1 Schritt Ausgangssituation 2 Schritt Suchpfad zum Punkt markieren Punkt 2 4 l schen Punkt l schen Suchpfad entfernen 4 2 AAA 3 Schritt L cke f llen durch Punkt mit 4 Schritt L schvorgang abgeschlossen kleinerem y Koordinatenwert Abbildung 38 Animiertes L schen im semidynamischen Priorit tssuchbaum 76 Elaboration Systemanalyse und Entwurf Dynamische dynamisch balancierte Variante Beim dynamischen Priorit tssuchbaum unterscheidet sich das eigentliche L schen der Punkte nicht von den Vorg ngen im semidynamischen Fall Hier m ssen jedoch zus tzlich im zugrunde liegenden Skelettbaum die Knoten mit dem x Koordinatenwert des gel schten Punktes entfernt werden Zun chst wird der Suchpfad bis zum Vaterknoten des zu l schenden Blattes markiert im markierten Endknoten vorhandener Punkt wird in den verbleibenden Teilbaum verlagert In rot wird die neue Kante vom Vorg nger des markierten Endknotens zum verbleiben den Nachfolger eingezeichnet Das umgangene Knotenpaar ist zusammen mit den Split werten und den alten Kanten gel scht Der Splitwert im inneren L schknoten wird mit dem Nachfolgewert berschrieben Nach kurzer Pause ist der Ergebnisbaum mit korrigierten Knotenpositionen zu zeichnen Abbildung 39 zeigt das L schen des Punktes 214 im Baum aus Abbildung 37 fa e 1 5 Punkt 2 4 wi
23. Ein neuer Punkt wandert in rot auf dem Weg zum Blatt mit seinem x Koordinatenwert von der Wurzel aus in den Baum hinein Trifft der neue Punkt im Knoten auf einen Punkt mit gr erem y Wert als er selbst aufweist so verdr ngt er diesen Punkt d h der neue Punkt wird blau in den Knoten ein gef gt und der verdr ngte Punkt wandert daf r in Rot weiter in den Baum hinein jetzt je doch auf dem Pfad zu seinem x Koordinatenwert Abbildung 34 zeigt das Einf gen des Punk RAAS STEE 1 Schritt Ausgangssituation 2 Schritt Punkt 2 2 wird eingef gt Punkt 4 3 bereits eingef gt Einf gepfad markiert a A D o 0 3 Schritt Punkt 2 2 verdr ngt Punkt 4 3 4 Schritt Einf gen Punkt 2 2 beendet dessen Einf gepfad wird sichtbar nachdem auch 4 3 eingef gt Abbildung 34 Animiertes Einf gen eines Punktes 72 Elaboration Systemanalyse und Entwurf e Dynamisch dynamisch balanciert Beim dynamischen Priorit tssuchbaum unterscheidet sich das eigentliche Einf gen der Punkte nicht von den Vorg ngen im semidynamischen Fall Hier wird jedoch der zugrunde liegende Skelettbaum erst um ein Blatt mit dem neuen x Ko ordinatenwert erweitert Dazu muss zun chst der Ansatzknoten f r das neue Blatt gesucht werden In roter Farbe wird gezeigt wie der Suchpfad langsam w chst bis der Ansatzknoten erreicht ist Dann soll zuerst der linke Sohn mit dem kleineren x Wert aus dem Ansatzknoten he
24. Sonderf llen sind stets umfangreichere Operationen beim L schen eines Punktes erforderlich Ab dem gel schten Punkt muss der betreffende Teilbaum neu aufgebaut werden Dabei wird der Neuaufbau um so signifikanter je n her der zu l schende Punkt in der N he der Wurzel liegt Damit erscheint es uns m glich im Rahmen der Diplomarbeit den gew nschten L schalgorithmus f r den dynamischen 2 d Baum zu implementieren 54 Elaboration Systemanalyse und Entwurf 7 4 3 3 Punkte in den ausgeglichenen 2 d Baum einf gen Abbildung 23 Aufbau eines ausgeglichenen 2 d Baums Teil 1 Der ausgeglichene 2 d Baum wird erst dann aufgebaut wenn alle Punkte ausgew hlt wurden siehe Abbildung 23 Die Punkte werden nach ihrer x Koordinate sortiert in die Punktliste eingef gt Abbildung 24 Aufbau eines ausgeglichenen 2 d Baums Teil 2 55 Elaboration Systemanalyse und Entwurf Der erste Splitwert ergibt sich als arithmetisches Mittel der beiden x Koordinaten der mittleren Punkte in der sortierten Punktliste Hier ist es x 4 5 Dann wird die Punktliste in zwei gleich gro e nach der y Koordinate sortierte Punktlisten aufgeteilt Abbildung 24 Mit diesen nach den y Koordinaten sortierten Punktlisten wird analog verfahren Nur werden jetzt f r die Ermittlung der Splitwerte die entsprechenden y Koordinaten verwendet Es ergibt sich der Teilbaum von Abbildung 25 An den Splitknoten sind nun die aufget
25. _inputAred 1 1 myl PointV ectorToV Lem A dapter 1 1 1 add Changelistener mol stateChanged 1 1 H 1 1 addChangeListener _m41 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 changed _points Abbildung 49 Interaktionsdiagramm zum Anmelden eines ChangeListeners 82 2 Algorithmus zum sch nen Zeichnen der Suchb ume Ein weiteres gemeinsames Problem ist die Entscheidung wie die Suchb ume in der Baumzeichen fl che dargestellt werden Die B ume sollen stets gleichm ig aussehen auch wenn dynamisch Ver nderungen am Baummodell vorgenommen werden Dies bedeutet dass die B ume in der Zeichenfl che aktualisiert werden m ssen Wir haben uns f r die Verwendung des Algorithmus von Reingold und Tilford aus deren Artikel Tidier Drawings of Trees REINS1 entschieden 1 Zur Erl uterung der Symbole siehe Tabelle All 92 Construction Erzeugung Die Grundlage f r das Zeichnen ist eine stets aktuelle Zuordnung von x und y Koordinaten zu jedem Knoten des Baumes Damit kann der Baum in einem Preorder Baumdurchlauf jederzeit sch n in die Ausgabefl che gezeichnet werden Was genau hei t sch n zeichnen Reingold und Tilford greifen in ihrem Artikel zun chst auf Anforderungen an das sch ne Zeich nen zur ck die bereits von Wetherell amp Shannon WETH79 aufgestellt wurden e Die Knoten e
26. das Ende der Liste angeh ngt 103 Construction Erzeugung F r das Einf gen eines Punktes in den dynamischen 2 d Baum wurde der Einf gealgorithmus mit der Methode insertPoint in der Klasse KdTree aufgenommen Der Algorithmus be stimmt zun chst mittels _searchInsertPosition rekursiv die Einf geposition Ist diese gefunden wird mit der Methode _pointInsert der Splitwert berechnet ein neuer Split knoten mit Splitwert und Splitrichtung erzeugt und ein neues Blatt mit dem Punkt in den 2 d Baum eingef gt Beide Knoten sind Instanzen der Klasse KdNode Nachdem das Einf gen erfolgreich getestet wurde haben wir diese Methoden in den Draw ableKdTree und den DrawableKdNode aufgenommen insertPoint wurde dabei um Methoden f r die Zeicheninformationen und den Aufruf des ChangelListeners erg nzt Da im Ein gabebereich neben den Punkten zus tzlich auch die Splitgeraden gezeichnet werden sollen haben wir in der Klasse DrawableKdNode zus tzlich das Attribut _ line und Methoden f r den Zu griff auf dieses Objekt aufgenommen um in jedem Splitknoten Start und Endpunkt der zu geordneten Splitgeraden zu speichern Mit der Eingabe eines Punktes erfolgt auch der Aufruf des Changelisteners f r die Punktmenge Hierdurch wird der neue Punkt im Eingabebereich eingezeichnet Danach erfolgt ein Preorder durchlauf durch den dynamischen 2 d Baum Dabei wird auf die in den Bl ttern befindlichen In formationen f r die Splitgera
27. das compilierte Paket com sun image codec jpeg Solaris e JDK2 oder JRE2 JavaHelp oder die Datei jhall jar aus dem JavaHelp System e das compilierte Paket com sun image codec jpeg Tabelle 3 F r die Applikation ben tigte Software 152 Bedienungsanleitung des Programms VisualGeom F r die Nutzung des Programms als Applet gelten die Rahmenbedingungen von Tabelle 4 Betriebssystem Erforderliche Software Windows 95 Bei Einsatz des Netscape Communicators ab Version 4 x oder des Internet Windows 98 Explorers ab Version 4 x Windows NT JRE2 einschlie lich Plug In e aus JavaHelp die Datei jhall jar e abh ngig von der jeweiligen JDK2 Version ggf das compilierte Paket com sun image codec jpeg Bei Einsatz des appletviewer der Firma SUN das Programm appletviewer aus 2 e e aus JavaHelp die Datei jhall jar e abh ngig von der jeweiligen JDK2 Version ggf das compilierte Paket com sun image codec jpeg Linux JRE2 e aus JavaHelp die Datei jhall jar e das compilierte Paket com sun image codec jpeg Hinweis Das Plug In f r den Netscape Communicator befindet sich zur Zeit noch in der Entwicklung Der aktuelle Stand ist unter http www blackdown org erfahrbar Deshalb ist die Nutzung als Applet ausschlie lich mit dem im JDK2 enthaltenen Programm appletviewer m glich Solaris JRE2 e Plug In f r JRE2 e aus JavaHelp die Datei jhall jar e das compilierte
28. die Formulierung vision rer Anforderungen und die Festlegung der verwendeten Architekturmuster bzw des Architektur stils Dabei werden die wichtigsten Anwendungsf lle im Detail spezifiziert und die System architektur entworfen Das Ergebnis ist die Architektur als Sicht aller Modelle des Systems Abbildung 6 Mit dem Ende dieser Phase sollen nach den Autoren die kritischen Anwendungsf lle und die grundlegende Architektur realisiert sein 26 Objektorientierte Softwareentwicklung Die entscheidende Frage f r die Elaboration Phase stellt sich laut 99 S 12 mit Are the use cases architecture and plans stable enough and are the risks under sufficent control to be able to commit to the whole development work in a contract Das Kapitel 7 enth lt Ausf hrungen zu dieser Phase bei der Entwicklung unseres Programms VisualGeom Construction Erzeugung Das Softwareprodukt wird erstellt indem die Anwendungsprogrammierer alle Anwendungs f lle nacheinander implementieren Am Ende dieser Phase ist das Softwareprodukt zwar vollst ndig befindet sich aber ggf noch in einem Alpha Stadium Entscheidend f r diese Phase ist nach BOOC99 S 12 die Frage Does the product meet users needs sufficiently for some customers to take early delivery Die Kapitel 8 und 9 enthalten Ausf hrungen zu dieser Phase bei der Entwicklung unseres Programms VisualGeom e Transition Einf hrung In dieser P
29. glichen Eingaben f r die Splitwerte OTTM93 Ohne diesen Spezialknoten lie e sich beim L schen nicht immer ein Knotenpaar im Blattsuchbaum finden sondern der gr te Knotenwert w re nur einzeln vorhanden Dadurch entst nde ein Son derfall der immer abgepr ft werden muss Mit dem zus tzlichen Startknoten ist diese Problematik ausger umt Im semidynamischen Fall wird ein ausgewogener Skelettbaum mit der bergebenen Anzahl an Bl ttern aufgebaut Beide Konstruktoren greifen beim Baumaufbau auf die Methode insert zu die einen neuen Knoten in den Skelettbaum einf gt Das iterative Umsetzen der Anwendungsf lle zum Priorit tssuchbaum erfolgte in nachstehender Reihenfolge 1 Einf gen von Punkten in einen semidynamischen Baum mit sofortiger Anzeige Einf gen von Punkten in einen dynamischen Baum mit sofortiger Anzeige Bereichssuche im semidynamischen Baum L schen von Punkten semidynamisch und dynamisch Der semidynamisch statische Baum Der balancierte dynamische Baum Erweiterungen f r die allgemeine Punktmenge 097 St e 97 Animationen e f r das Einf gen von Punkten e f r das L schen von Punkten e f r die Bereichssuche 9 Demos Jeder Iterationsschritt endete mit gezielten Tests Exemplarische Testbeispiele sind im Kapitel 9 2 beschrieben 117 Construction Erzeugung 8 4 1 Einf gen von Punkten im semidynamischen Baum F r das Einf gen von Punkten in den zeichenbaren Bau
30. gt werden ben tigen wir f r das Einf gen und L schen im semidynamischen Fall nur die Anpassung der vorhandenen Methoden pointIn SkeletonInsert und pointFromSkeletonDelete f r das Verhalten im Blatt knoten e Einf gen Ist der Blattknoten besetzt muss in die Liste eingef gt werden L schen Ist im Blatt der Punkt nicht gefunden muss in der Liste gel scht werden Wird der Blattknoten frei muss der erste Wert der Liste in den Blattknoten bernommen und in der Liste gel scht werden Im dynamischen Fall ist zus tzlich zu ber cksichtigen ob im Ansatzknoten Blatt f r einen neu einzuf genden Knoten eine nichtleere Liste existiert Ist dies der Fall so muss die Liste in den zugeh rigen Nachfolgeknoten umgeh ngt werden nachdem der erste Listeneintrag gel scht und dieser Punkt in den neuen Blattknoten eingef gt wurde Die ben tigten nderungen wurden in der Methode insert vorgenommen Da die ben tigte sortierte Punktliste den Knoten zuzurechnen ist haben wir sie als weiteres At tribut zusammen mit den notwendigen Methoden in der Klasse PrioNode erg nzt 8 4 8 Animationen zum Priorit tssuchbaum Die Animation der Abl ufe in den Methoden zum Einf gen L schen und der Bereichsanfrage muss durch zus tzliche Threads erfolgen damit der Benutzer die Option beh lt w hrend der Animation auf die Benutzeroberfl che zuzugreifen und sei es nur um die Animation zu stoppen Da das Visualisieren der Alg
31. hlt so werden Punktliste Punkte und Suchbaum gel scht Welche Strukturvariante gerade ausgew hlt ist kann der Titelleiste entnommen werden 165 Bedienungsanleitung des Programms VisualGeom dynamischer 2 d Baum Nach der Eingabe eines Punktes erfolgt unmittelbar der Aufbau des aktualisierten Suchbaums im Ausgabebereich und Einzeichnen der Split geraden im Eingabebereich Der Splitwert wird daf r als arithmetisches Mittel aus den Koordinaten der beiden im gleichen Splitrechteck be findlichen Punkte berechnet Das L schen eines Punktes f hrt zum Entfernen des zugeordneten Blattes aus dem Baum und der Splitgeraden aus dem Eingabebereich Bei Durchf hren einer Anfrage werden alle angefassten Knoten mar kiert Die ausgew hlten Blattknoten werden gesondert gekennzeichnet dynamisch interaktiver 2 d Baum Ist bereits ein Punkt eingef gt so wird nach der Eingabe jedes weiteren Punktes zun chst gefragt nach welcher Koordinate x oder y der Splitbereich geteilt werden soll Anschlie end muss ein konkreter Splitwert eingegeben werden Nach erfolgreicher Kontrolle werden die Erg nzungen vorgenommen Das L schen eines Punktes f hrt zum Entfernen des zugeordneten Blattes aus dem Baum und der Splitgeraden aus dem Eingabebereich Bei Durchf hren einer Anfrage werden alle angefassten Knoten mar kiert Die ausgew hlten Blattknoten werden gesondert gekennzeichnet Die Men punkte ffnen und Speichern sind deakt
32. ohne den y Heap zu verletzen Je L5 Abbildung 37 Balancieren im Priorit tssuchbaum Teil 2 Bei einer Doppelrotation werden die beschriebenen Abl ufe f r jede einzelne Rotation ben tigt 74 Elaboration Systemanalyse und Entwurf 7 5 3 3 Punkt aus dem dynamischen Priorit tssuchbaum l schen Die detaillierteren Ausf hrungen zum L schen eines Punktes unterscheiden sich vom Einf gen eines Punktes nur unwesentlich In der Eingabefl che klickt der Benutzer den zu l schenden Punkt mit der rechten Maustaste an Auch in diesem Fall muss der Punkt berpr ft werden Kommt er in der aktuellen Punktliste vor so muss er sowohl aus dem Baum als auch aus der Punktmenge gel scht werden Der aktu alisierte Baum und die neue Punktmenge sind am Bildschirm neu darzustellen Da sich das Aktivit tsdiagramm zum L schen nur durch die verwendete Methode vom Einf gen unterscheidet wird hier auf seine Darstellung verzichtet 7 5 3 4 Visualisieren des L schvorgangs Wie beim Einf gen siehe Seite 71 erfolgt die Unterscheidung zwischen Sofortmodus und Animation Sofortmodus e _Semidynamisch statische Variante Nach jeder Ver nderung an der aktuellen Punktmenge muss der Benutzer den Baum kom plett neu aufbauen und zeichnen lassen Deshalb werden hier keine farblichen Hervorhe bungen ben tigt e _Semidynamische Variante Beim L schen werden die Punkte rot hervorgehoben die nach dem L schen eines Pun
33. ssen alle Knoten angefasst werden f r die der Durchschnitt aus zugeordnetem Splitbereich und Anfragerechteck nicht leer ist Die bei der Suche aufgefundenen Punkte und alle besuchten Knoten werden farblich gekennzeichnet in den 2 d Baum eingezeichnet 43 Elaboration Systemanalyse und Entwurf Use Case Demo aufrufen Der Benutzer w hlt im Hilfemen eine der beiden angebotenen Demos zum dy namischen oder ausgeglichenen 2 d Baum Das Programm zeigt schrittweise den Baumaufbau beim Einf gen von Punkten Im dynamischen Fall wird ein Punkt gel scht Es wird ein Anfragerechteck im Eingabebereich eingezeichnet Dann erfolgt die Markierung aller angefassten und aller im Anfragerechteck enthaltenen Punkte ber eine Schaltfl che kann das Demo jederzeit vom Benutzer definiert abge brochen werden 7 4 3 Verfeinerte Analyse mit Aktivit tsdiagrammen Einen ersten bergang von der Analyse also dem Was soll gemacht werden zum Entwurf also dem Wie soll dies geschehen bieten Aktivit tsdiagramme Sie stellen verfeinerte Abl ufe der in den Use Cases aufgef hrten Aktionen dar und bringen M glichkeiten ins Spiel wie diese Forderungen erf llt werden k nnen Dies soll hier f r die Anwendungsf lle von Kapitel 7 4 2 betrachtet werden Dabei erfolgen auch berlegungen wie die Visualisierung der Baumalgorithmen durchgef hrt werden sollte 7 4 3 1 Punkt in den dynamischen 2 d Baum einf
34. usr lib java codec jar export CLASSPATH Alternativ kann dieser Eintrag in der benutzerspezifischen Einstellungsdatei profile im Benutzerheimatverzeichnis vorgenommen werden F r JDK2 unter Solaris sind abh ngig vom Verzeichnis in das JDK2 installiert wurde ent sprechende Einstellung wie unter Linux durchzuf hren 154 Bedienungsanleitung des Programms VisualGeom Die VisualGeom Programmdateien sind mit der vorhandenen Verzeichnisstruktur in ein belie biges Verzeichnis auf der Festplatte zu entpacken Dabei wird zun chst das Unterverzeichnis VisualGeom angelegt In dieses werden dann alle Verzeichnisse und Dateien f r die Benutzung als Applikation und Applet kopiert Windows95 98 NT Entpacken Sie mit WinZip oder einem anderem Programm das ZIP Dateien mit langen Dateinamen entpacken kann die Datei VisualGeom zip in das von Ihnen ausgew hlte Verzeichnis Alternativ besteht die M glichkeit das Programm VisualGeom exe aufzurufen Es entpackt als ausf hrbares ZIP Archiv selbst ndig die Programmdateien in das von Ihnen aus gew hlte Verzeichnis Linux und Solaris Mounten Sie die CD z B in das Verzeichnis cdrom Kopieren Sie die Datei VisualGeom tgz in das Verzeichnis in das Sie VisualGeom installieren wollen z home kirk Entpacken Sie mit tar die Datei VisualGeom tgz in das von Ihnen aus gew hlte Verzeichnis cp R cdrom VisualGeom VisualGeom VisualGeom tgr tar xvf VisualGeom tgz Beachten
35. 8 3 CONSTRUCTION DES 2 DBAUMS 2605 103 8 3 1 Einf gen von Punkten im dynamischen 2 4 103 8 3 2 Bereichssuche im dynamischen 2 4 107 8 3 3 L schen von Punkten im dynamischen 2 4 107 8 3 4 ausgeglichene 2 4 108 8 35 Schrittweiser Aufbau des ausgeglichenen 2 4 109 8 3 6 2 0 OEN 110 8 3 7 Aufbau des 2 d Baums 116 8 3 8 2 4 116 8 4 CONSTRUCTION DES 55 5 0 117 8 4 1 Einf gen von Punkten im semidynamischen Baum 118 8 4 2 Einf gen von Punkten im dynamischen Baum 120 8 4 3 Bereichssuche im semidynamischen Baum 121 8 4 4 L schen im semidynamischen und dynamischen Baum 122 8 4 5 Der semidynamisch statische Baum 123 8 4 6 Der balancierte dynamische 125 8 4 7 Erweiterung f r die allgemeine
36. Deshalb wird nur nach der oberen Grenze auf der x Achse gefragt 8 16 32 oder beliebig aber maximal 32 7 5 1 3 Der dynamische Priorit tssuchbaum Der Einsatz ma geschneiderter Techniken f r das Einf gen und L schen erlaubt auch eine effi ziente dynamische Variante des Priorit tssuchbaumes Wir entscheiden uns f r die volldynamische Variante aus OTTM93 mit einem von der Reihen folge der Punkte abh ngigen nat rlichen Blattsuchbaum als Suchstruktur e anfangs leere Baum besteht aus einem Knoten mit einem fiktiven Splitwert der gr er als alle m glichen x Koordinaten ist Ein neuer Punkt wird in zwei Phasen eingef gt Zun chst wird die x Koordinate des Punktes verwendet um den Blattsuchbaum um den entsprechenden Knoten zu erweitern In den erweiterten Baum wird anschlie end der Punkt wie blich eingef gt 7 5 1 4 Der balancierte dynamische Priorit tssuchbaum Die Effizienz der dynamischen Variante ist nur gew hrleistet wenn der Baum ausgeglichen bleibt Deshalb betrachten wir abschlie end die balancierte dynamische Variante Bei dieser erfolgt das Einf gen wie bei der dynamischen Ist das AVL Kriterium verletzt so wird der zugrunde liegende Baum nach dem Einf gen eines neuen Punktes balanciert Beim Balancieren ist besonders darauf zu achten dass der y Heap nicht verletzt wird Es sind bei jeder Rotation entsprechende Vorkehrungen zu treffen 9 Siehe Kapitel 7 5 1 4 65
37. Die Prozesssicht beschreibt die Nebenl ufigkeit und Synchronisation f r die aktiven Klassen Es erfolgt die Visualisierung der Anwendungsf lle mittels Aktivit tsdiagrammen Des weiteren werden Objekte und ihre Beziehungen einschlie lich der zeitlichen Ordnung ihres Nachrichtenaustausches mit Sequenzdiagrammen veranschaulicht posium in 1999 45 Dieses Abbildung entstand nach Folien der Firma Rational Software vom Rational Worldwide Software Sym 29 Objektorientierte Softwareentwicklung Implementation View Implementierungssicht Sie enth lt die Komponenten mit ihren Klassen und Paketen einschlie lich der Beziehungen zwischen den Komponenten Deployment View Einsatzsicht Die Einsatzsicht wird mittels Verteilungsdiagrammen veranschaulicht Diese verdeutlichen welche Komponenten und Objekte auf welchen Prozessen oder Computern lauff hig sind Dabei wird beschrieben wie diese konfiguriert sind und welche Kommunikationsbeziehungen zwischen ihnen bestehen Bei der Anwendung des Modells RUP ergibt sich f r uns als Konsequenz zun chst im Rahmen des Requirements alle Anwendungsf lle zu ermitteln Analyse und Designentscheidungen zu treffen und dann die Anwendungsf lle iterativ und inkrementell zu implementieren 30 Elaboration Systemanalyse und Entwurf 7 Elaboration Systemanalyse und Entwurf F r unser kleines Programm lehnen wir uns nun an das in Kapitel 6 beschriebene Prinzip an i
38. M glichkeit der experimentellen Auseinandersetzung mit den beiden Suchb umen Dabei lassen sich Aufbau Abbau und Bereichsanfragen visualisieren und animieren Durch das Programm werden die Datenstrukturen somit in klarerer Art und Weise dargestellt als es in der Fachliteratur m glich ist da diese nur Momentanaufnahmen in einzelnen Bildern festhalten kann Inhaltsverzeichnis INHALTSVERZEICHNIS EINGANGSVORAUSSETZUNGEN DER ADRESSATEN RAHMENBEDINGUNGEN F R DIE SOFTWAREENTWICKLUNG eessen LERNPSYCHOLOGISCHE ASPEKTE 20200s20000s0n00sonssssnsnnsnsenonssssnsonsnsensnssnsnsonsnssssonsnsessnssnsssensnsenee L SOFTWAREERGONOMISCHE ASPEKTE cscossssssonssssnsossssenonssssnsonsnsensnssnsnsonsnssnsonsnsessnssssnsonsnsense L7 OBJEKTORIENTIERTE SOFTWAREENTWICKLUNG 2 1 1 24 ELABORATION SYSTEMANALYSE UND 21 RE Ee EE BC NC RE 7 2 ARCHITEKTUR DES PROGRAMMS srren nis ls ken 7 3 GESTALTUNG DER BENUTZERORERPL ACHEN TA ELABORATION DES2 D BAUMS EE ele E NEE RE E 7 4 1 1 Der ausgeglichene 2 4 724 1 2 2 herein 7 4 1 3 Der dynamische 2 42
39. Punkte aus der Punktliste werden in der Eingabereihenfolge nacheinander in einen neuen 2 d Baum eingef gt Im worst case f hrt dieser Neuaufbau des dynamischen 2 d Baums zu einer Liste Damit er gibt sich O n f r die Laufzeit dieses L schalgorithmus V d SE EH EAEkE 3 ZA a DR Vi Abbildung 21 L schen in einem beliebigen 2 d Baum Im Fall von Abbildung 21 kann einer von insgesamt acht Punkten gel scht werden Dabei ent spricht das L schen der Punkte 814 916 6 13 7114 411 und 3112 dem in Abbildung 19 behandelten Fall 53 Elaboration Systemanalyse und Entwurf Wird der Punkt 1017 gel scht so f hrt dies dazu dass der linke Teilbaum am Splitknoten y 8 ohne den gel schten Punkt komplett neu aufgebaut werden muss Dies bedeutet dass die verbleibenden Punkte im linken Teilbaum also 814 und 916 zun chst in einer Punktliste als Hilfsdatenstruktur zu sichern sind 17 8 613 714 84 185 Abbildung 22 2 d Baum nach L schen des Punktes 1017 Das L schen des Punktes 519 aus Abbildung 21 bewirkt dass die Punkte 814 916 und 1017 aus dem Baum entfernt und in einer Punktliste zwischengespeichert werden m ssen Am Knoten mit dem Splitwert x 11 kann dann der neue Teilbaum aufgebaut werden Entsprechende berlegungen gelten auch f r das L schen des Punktes 1718 Abgesehen von den in der Abbildung 18 und der Abbildung 19 dargestellten
40. Sie besteht aber nicht aus Punkten die sich in allen Koordinaten voneinander unterscheiden In diesem Fall ist der Aufbau eines erweiterten 2 d Baums erforderlich Dieser ist tern r Es handelt sich wieder um eine statische Variante des 2 d Baums e Die zu betrachtende Punktmenge ist noch nicht vorgegeben Der 2 d Baum soll dynamisch aufgebaut werden Pro auftretendem Punkt ist der 2 d Baum um einen Knoten zu erweitern Dazu muss zwischen dem neuen Punkt und dem benachbarten Punkt der Splitwert ermittelt und das Blatt mit dem neuen Punkt erg nzt werden Der Splitwert kann als arithmetisches Mittel der zugeordneten Punktkoordinaten berechnet oder als Wert aus dem Intervall der zu geordneten Punktkoordinaten festgelegt werden 7 4 1 1 Der ausgeglichene 2 d Baum Die Menge der zu speichernden Punkte wird zun chst in einer Punktliste nach den x Koordinaten aufsteigend sortiert Diese Punktliste wird in der Mitte in zwei Punktlisten aufgeteilt Sie unter scheiden sich in der Anzahl der Elemente um maximal 1 Aus den x Koordinaten der beiden Punkte in der wird der Splitwert als arithmetisches Mittel berechnet Des Vorgang wird rekursiv abwechselnd mit x oder y als Splitkoordinate durchgef hrt bis nur noch jeweils ein Punkt in der Menge verbleibt 7 4 1 2 Der allgemeine 2 d Baum Die Menge der zu speichernden Punkte wird in einer Punktliste nach den x Koordinaten auf steigend sortiert Existieren Punkte mit identischer x Koordina
41. Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen 5 13 1 10 2 14 4 12 6 11 Beispiel 10 Anfragerechteck nur in den Splitberei chen der enthaltenen Punkte Erwartetes Ergebnis Verhalten des Programms Die zu den Punkten im Anfrage rechteck geh renden Bl tter sind in gr n als angefasst zu kennzeichnen Auch deren eingetragene Punkte m ssen gr n dargestellt werden Alle Pfade zu diesen Bl ttern m ssen ebenfalls markiert sein Die Bl tter zu den Splitbereichen die geschnitten werden ohne dass ihre Punkte innerhalb des Anfrage rechtecks liegen werden als besucht gekennzeichnet Die dort gespeicher ten Punkte bleiben jedoch schwarz ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Beispiel 11 Anfragerechteck auch Splitberei chen ohne deren Punkte einzuschlie en 142 Programmtest 9 2 Tests zum Priorit tssuchbaum Beispiele f r den Test spezieller Werte Typische Testf lle hierzu ergeben sich beim berpr fen der leeren Datenstrukturen beim Laden und Speichern einer leeren Punktliste siehe hierzu Kapitel 9 1 und beim Wechsel zwischen dem semidynamisch statischen Priorit tssuchbaum und den anderen Strukturvarianten Erwartetes Ergebnis Verhalten des Programms Bei der
42. Strukturvariante zu r ckgesetzt Die Men punkte unter Optionen werden ebenfalls auf die Startwerte zu r ckgesetzt In der Titelleiste erscheint die Meldung Der 2 dimensionale Such baum Alle in diesem Modus nicht nutzbaren Men punkte und alle Buttons werden deaktiviert ffnen Beim ersten Mal wird das Dateiverzeichnis VisualGeom ge ffnet sonst das aktuell eingestellte Die ausgew hlte Strukturvariante bestimmt den Filter f r die Datei anzeige kd Dateien mit Punkten die sich in allen Koordinaten voneinander unterscheiden kda Dateien mit allgemeiner Punktmenge Speichern Die abgespeicherte Punktmenge wird aktualisiert Speichern unter Der Benutzer hat die M glichkeit die Punktliste als Textdatei auf der Festplatte in einem ausw hlbaren Verzeichnis zu sichern Bei erstmaligem Speichern wird hier das Verzeichnis Visualgeom ge ffnet sonst das aktuell eingestellte Verzeichnis Die Dateiendung kd bzw kda wird automatisch als Suffix an den Dateinamen angeh ngt Drucken Der Inhalt von Ein und Ausgabefenster wird auf einem Drucker ausgegeben Schlie en Die Bearbeitung des Suchbaums wird beendet und die Fenster geschlossen Wurde der 2 d Baum aus dem Startmen aufgerufen so wird dieses angezeigt Andernfalls wird die Applikation oder das Applet beendet Beenden Das Arbeiten mit dem Programm VisualGeom wird beendet Tabelle 7 2 d Men punkte des Dat
43. den Betriebssystemen e Windows in den Versionen 95 98 und NT Linux Solaris und e MAC OS Programme in Sprachen wie C m ssen nach der Portierung auf ein anderes Betriebssystem neu compiliert und ggf an betriebssystemspezifische Besonderheiten angepasst werden Die von der Firma SUN entwickelte Programmiersprache Java bersetzt beim Compilieren Quellcode in Bytecode Dieser ist mit dem im JRE bzw dem JDK enthaltenen Interpreter ohne nderungen auf den oben genannten Betriebssystemen lauff hig F r uns ergibt sich damit zwangsl ufig das Programm in der Sprache Java zu implementieren Nur mit dieser objektorientierten Programmiersprache ist die betriebssystemspezifische Platt formunabh ngigkeit realisierbar Damit verbleibt aktuell nur noch die Auswahl zwischen den Versionen 1 und JDK2 Auf Wunsch des Lehrgebietes und um die unter JDK2 bereits integrierten Swing Klassen und das Java 2D API nutzen zu k nnen entschieden wir uns f r JDK2 Hierdurch ergaben sich w hrend der Programmentwicklung allerdings diverse Schwierigkeiten Zu Beginn der Diplomarbeit existierte nur eine Beta Release von JDK2 unter Windows und unter Solaris Die erste Pre Release f r Linux erschien erst im Fr hjahr 1999 Sie setzt allerdings die Verwendung der glibc Bibliotheken voraus Erst ab der Version 6 0 sind diese ein Bestandteil der SuSE Distribution Eine MAC OS Version von JDK2 existiert nach unserem Kenntnisstand immer noch
44. einer GIF oder JPEG Datei Tabelle 5 Tags in der TOC Datei Teil 1 A 12 Anleitung zum Erstellen der Hilfedateien an einem Beispiel lt tocitem gt ein Verzeichniseintrag mit dem unter text festgelegten Namen wird definiert Dieser Name wird bei der Auswahl des Eintrags angezeigt Dieser Eintrag dient als bergeordneter Gliederungs punkt Zusammenfassung von Hilfedateien s oben text Men s Beim Anklicken wird das Men auf bzw zugeklappt lt tocitem target gt Es wird ein Verzeichniseintrag mit dem unter text festgelegten Namen definiert Dieser Name wird bei der Auswahl des Eintrags angezeigt Mit target wird die ID einer Datei zugeordnet die bei Auswahl dieses Men punktes angezeigt werden soll Tabelle Tags in der TOC Datei Teil 2 A 2 4 Die Datei kdHelpIndex xml Der nachfolgende Auszug verdeutlicht den grunds tzlichen Aufbau einer HelpIndex Datei lt xml version 1 0 encoding ISO 8859 1 gt lt DOCTYPE index gt lt index version 1 0 gt lt indexitem text Ausgabebereich gt lt indexitem text Ausgabebereich target einaus aus gt lt indexitem text Ein Ausgabebereich target einaus einaus gt lt indexitem gt lt indexitem text Eingabebereich target einaus ein gt lt index gt Abbildung 5 Auszug aus der Datei kdHelpIndex xml A 13 Anleitung zum Erstellen der Hilfed
45. eingegeben oder gel scht und Anfragerechtecke aufgezogen werden Dabei gelten folgende Zu ordnungen e Linke Maustaste im Eingabebereich Das Klicken mit der linken Maustaste bewirkt dass ein Punkt eingegeben wird Ist dieser Punkt bereits vorhanden oder handelt es sich bei den 2 d B umen um solche bei denen sich die Punkte in allen Koordinaten voneinander unterscheiden m ssen erfolgt die Ausgabe einer Fehlermeldung in der Statuszeile Die gilt f r den dynamischen den dynamisch interaktiven und den ausgeglichenen 2 d Baum Nur der allge meine 2 d Baum kann Punkte mit identischer Koordinate verwalten 159 Bedienungsanleitung des Programms VisualGeom e Linke Maustaste im Ausgabebereich Wird im Ausgabebereich ein allgemeiner 2 d Baum angezeigt der innere Knoten mit einer zus tzlichen blauen Markierung enth lt so deutet dies auf vorhandene 1 d B ume hin Diese k nnen durch Anklicken der betreffenden Knoten in eigenen Fenstern betrachtet werden Rechte Maustaste im Eingabebereich Das Anklicken eines Punktes mit der rechten Maustaste bewirkt das L schen des Punktes im Eingabebereich und im Baum Ziehen der Maus mit gedr ckter linker Maustaste im Eingabebereich Dies f hrt zum Platzieren und ffnen eines Anfragerechtecks Die Buttons in der Buttonleiste sind abh ngig vom jeweiligen Programmmodus aktiviert oder de aktiviert Ihre Bedeutung kann der Tabelle 6 entnommen werden Button Bedeu
46. erreicht Beispiel 17 L schen im dynamischen Baum 2 147 Programmtest Erwartetes Ergebnis Verhalten des Programms Im Beispiel wird der Punkt 7113 gel scht Der Blattknoten 7 und der innere Knoten 7 bilden ein zusam menh ngendes Knotenpaar Als Spe zialfall weist der innere Knoten als Baumwurzel aber keinen Vorg nger auf Deshalb muss der rechte Nach folgerknoten der Wurzel zum neuen Wurzelknoten werden Der Punkt 919 muss vor dem L schen des Wurzelknotens in den rechten Nachfolgerknoten 9 verscho ben werden dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Punkt 7 13 erreicht Der dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Punkt 7 13 erreicht Beispiel 18 L schen im dynamischen Baum 3 148 Programmtest Nachdem wir bereits verschiedene L schvorg nge betrachtet und dabei darauf hingewiesen haben dass fter Punkte vor dem L schen von Knoten an eine neue Position verschoben werden m ssen soll ein letzter spezieller L schvorgang getestet werden Im dynamisch balancierten Baum muss besonders darauf geachtet werden dass beim L schen die Ordnung im y Heap nicht verletzt wird Beispiel 15 Erwartetes Ergebnis Verhalten des Programms Der Punkt 515 wird gel scht Das zusammenh ngende Knotenp
47. gen Wenn der Benutzer einen Punkt im 1 Quadranten der Ebene mit der Maus angeklickt hat muss der Punkt von den Bildschirmkoordinaten in die Weltkoordinaten umgerechnet werden Dabei ist das jeweils eingestellte Raster zu ber cksichtigen Den Zusammenhang zeigt Abbildung 14 S Sinngem nach OEST98 44 Elaboration Systemanalyse und Entwurf 0 0 oben links Bildschirm mit 1 Quadrant Fensterkoordinaten Abbildung 14 Koordinatentransformation Bevor der ermittelte Punkt in den dynamischen 2 d Baum eingef gt werden kann muss gekl rt werden ob es sich bei diesem um einen f r die ausgew hlte Strukturvariante zul ssigen Punkt handelt Folgende Rahmenbedingungen stellen die Voraussetzungen f r die bernahme in den Baum dar e Der Punkt ist noch nicht im 2 d Baum eingetragen Der Punkt unterscheidet sich von den bereits eingetragenen Punkten in beiden Koordinaten Da auch der erneute Aufbau des 2 d Baumes mit VisualGeom m glich sein soll wird als Hilfsdatenstruktur eine Punktliste genutzt Diese soll alle bereits im 2 d Baum enthaltenen Punkte in der Eingabereihenfolge festhalten Damit ergibt sich eine einfache M glichkeit diese Liste zur Kontrolle der Voraussetzungen f r das Eintragen des neuen Punktes zu durchsuchen Handelt es sich bei dem angeklickten Punkt um einen der nicht den Voraussetzungen gen gt soll eine Fehlermeldung den Benutzer auf die Falscheingabe hinweisen Andernfalls erfolgt d
48. glichkeit auch mit den entarteten Suchb umen arbeiten zu k nnen wird dem Benutzer in Ans tzen ein Einblick in ihr Laufzeitverhalten erm glicht Gleichzeitig erf hrt er anschaulich worin der Vorteil der in FU1840 Seiten 118 bis 125 und 130 bis 135 beschriebenen ausgeglichenen Datenstrukturen besteht 22 Siehe auch Kapitel 7 23 Siehe Ausf hrungen zum dynamischer 2 d Baum den Kapiteln 7 4 3 1 und 7 4 3 2 16 Softwareergonomische Aspekte 5 Softwareergonomische Aspekte In diesem Kapitel wollen wir im Rahmen der Inception Phase Grunds tze f r den Aufbau der Benutzeroberfl che und die Programminteraktionen entwickeln Hierzu stellen wir uns folgende Frage Welche Aspekte der Software Ergonomie sind im Rahmen der Entwicklung des Programms VisualGeom wichtig Dazu m ssen wir zun chst kl ren was unter Software Ergonomie zu verstehen ist und welche Intentionen mit der Software Ergonomie vertreten werden Hierzu findet sich in DU DESS Seite 218 Die Software Ergonomie entwickelt Kriterien und Methoden zur Gestaltung inter aktiver Programmsysteme die den menschlichen Bed rfnissen der Benutzer nach einer ausgeglichenen Verteilung der geistigen k rperlichen und sozialen Belastung weitgehend entgegenkommt Das Ziel der Software Ergonomie besteht danach darin eine effiziente Ausf hrung der beschrie benen Aufgabe zu gew hrleisten Dabei m ssen m gliche negative physische und psy
49. gter Punkt Knoten 24 Punkt 9 6 erreicht dynamischen Priorit tssuchbaum wird zun chst die Erweiterung des Skelett baums visualisiert Dabei wird der Suchpfad zum Ansatzknoten mar kiert Erst wird der neue linke und dann der neue rechte Nachfolgerkno ten erzeugt Ggf wird der Splitwert im Ansatzknoten korrigiert Nach der neu eingef gte Erweiterung des Skelettbaums wird der neue Punkt wie im semidynami schen Fall eingef gt Abbildung 89 Animierter Aufbau beim dynami schen Priorit tssuchbaum Suchpfad zum Ansatzknoten 171 Bedienungsanleitung des Programms VisualGeom semidynamische Priorit tssuchbaum Wird ein Punkt aus dem Eingabe Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage isschen bereich entfernt so wird zun chst der Suchpfad zum Punkt rot einge zeichnet und der Punkt gel scht Die entstandene L cke wird durch Hochziehen von Nachfolgepunk ten geschlossen nachfolgender Punkte wandert eine Ebene h her gel schter Punkt Punkt 2 14 erreicht Abbildung 90 Animiertes L schen eines Punktes dynamische Priorit tssuchbaum iol Nach dem L schen des Punktes wie Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen im semidynamische Fall muss im dy Suchpfad namischen Baum zus tzlich das L 2 schen der zugeh rigen Knoten
50. ihm beim 2 d Baum und Priorit tssuchbaum die Auswahl zwischen dynamischem und statischem Aufbau und die Auswahl zwischen den Arten unmittelbar animiert und schrittweise erm glicht 23 Objektorientierte Softwareentwicklung 6 Objektorientierte Softwareentwicklung Aus den Ausf hrungen im Kapitel 3 Rahmenbedingungen f r die Softwareentwicklung folgt das Programm in einer objektorientierten Sprache zu implementieren Als logische Konsequenz ergibt sich auch f r die Softwareentwicklung ein geeignetes objektorientiertes Vorgehensmodell einzu setzen Hierf r bieten sich verschiedene Modelle an Abbildung 4 vermittelt einen berblick ber die Entwicklung der verschiedenen objektorientierten Vorgehensmodelle Danach kann der Softwareentwickler aktuell f r seine objektorientierte Soft wareentwicklung zwischen sieben verschiedenen Vorgehensmodellen ausw hlen I 00A A Generation i na Fusion 72 OPEN Fusion2 0 AA Perspective 95 Broch 96 3 Generation AE Modell ohjekioriendiert os BE Lemmer H Al Prozess Abbildung 4 Entwicklung objektorientierter Vorgehensmodelle Aufgrund der in der Praxis inzwischen recht guten Akzeptanz des Rational Unified Process BOOC99 der auch als RUP bezeichnet wird und der vorhandenen Unterst tzungs
51. kd und prio importiert Zur Realisierung des MVC Konzeptes m ssen den ereignisliefernden Komponenten der Benutzer oberfl che nun noch Controller zugeordnet werden um die Benutzeraktionen zu registrieren und die geforderten Aktionen im jeweiligen Modell auszul sen Abbildung 48 zeigt das Zusammen spiel der Klassen am Beispiel des 2 d Baums 89 Construction Erzeugung Der Eingabefl che wird ein MouseListener zur Registrierung von Mausklicks und ein Mouse MotionListener zur Kontrolle von Mausbewegungen hinzugef gt Dies geschieht ber separate Controller Klassen Sie werten die ausgel sten Maus Events aus und rufen die ben tigten Metho den in den Modell Klassen auf Der Controller f r die Men aktionen wird in die zentrale Klasse GUI aufgenommen in der das Zusammenstellen aller Komponenten erfolgt Die Modelle Baum und Punktliste ihrerseits werden von weiteren Controllern berwacht die nach jeder Modell nderung daf r sorgen dass die Ansichten View neu gezeichnet werden Da alle Controller als Vermittler zwischen Oberfl che und Modell auftreten verwenden wir die Bezeichnung Adapter in ihren Klassennamen Folgende Adapter Klassen werden realisiert _Adapterklasse zwischen Eingabefl che und Modellen zur Umsetzung der MouseEvents InputAreaToTreeAndPointsAdapter _Adapterklasse zwischen Eingabefl che und Statuszeile zur Kommentierung von MouseEvents InputAreaToStatuslineAdapter _Adapterklassen zwis
52. konnten 8 3 4 Der ausgeglichene 2 d Baum F r den ausgeglichenen 2 d Baum war die bereits implementierte Methode zum Einf gen eines Punktes nicht verwendbar Wie der Algorithmus aus Kapitel 7 4 3 3 verdeutlicht muss die Punktliste sukzessive sortiert geteilt und erneut sortiert werden Hierzu war es erforderlich in der Klasse Pointlist zun chst die Methode addSortedXPoint f r das nach der x Koordinate sortierte Einf gen eines Punktes in die Punktliste zu erg nzen In der Klasse DrawableKdTree wurde die Methode insertPointList aufgenommen die aus der nach x Koordinaten sortierten Punktliste den Baum aufbaut Diese Methode ruft dazu eine private Methode auf die den Splitwert berechnet die Splitrichtung festlegt die Koordinaten der zuge ordneten Splitgeraden bestimmt den Splitknoten erzeugt und die Punktliste in zwei Teillisten auf teilt Hatte die Ausgangsliste mehr als drei Elemente so werden die Teillisten nach der zweiten Koor dinate sortiert und die Methode erneut aufgerufen Bestand die Ausgangsliste nur noch aus zwei Punkten werden Blattknoten gebildet und die Punkte in diese Knoten eingetragen Bestand die Ausgangsliste aus 3 Punkten so befindet sich in einer der beiden Teillisten nur ein Punkt Hierf r wird sofort der zugeordnete Blattknoten erzeugt die anderen Teilliste nach der zweiten Koordinate sortiert und dann die Methode erneut aufgerufen 108 Construction Erzeugung 8 3 5 Schrittweiser Aufba
53. links Bildschirm mit 1 Quadrant Fensterkoordinaten Abbildung 32 Koordinatentransformation Bevor der ermittelte Punkt in den Priorit tssuchbaum eingef gt werden kann muss gekl rt wer den ob dieser Punkt im Rahmen der Einstellungen erlaubt ist e der Punkt bereits vor so darf er kein zweites Mal eingef gt werden e Sind nur Punkte mit disjunkten x Koordinaten erlaubt so wird der neue Punkt nicht ein gef gt wenn bereits ein Punkt mit diesem x Koordinatenwert vorkommt e Liegt der Punkt im semidynamischen Fall au erhalb des eingestellten Universums muss er abgewiesen werden All diese Tests ben tigen eine aktuelle Punktmenge Es ist deshalb erforderlich auch die Punkt menge in einer Datenstruktur festzuhalten Da dem Benutzer die Wiederholungsm glichkeit des Baumaufbaus angeboten werden soll eignet sich daf r eine Liste die die eingegebenen Punkte in der Eingabereihenfolge festh lt Zum Testen wird auf diese Punktliste zugegriffen Ist der Punkt zugelassen wird er an die aktu elle Punktliste angeh ngt und in den Priorit tssuchbaum eingef gt 69 Elaboration Systemanalyse und Entwurf Der akzeptierte neue Punkt wird im 1 Quadranten eingezeichnet Der aktualisierte Baum wird in der Zeichenfl che neu angezeigt Dabei m ssen die vorgenommenen Ver nderungen f r den Be nutzer deutlich werden siehe Gedanken zum Visualisieren auf Seite 71 Als Ergebnis dieser detaillierteren berle
54. muss der Split wert des inneren Knotens mit dem des verbleibenden Nachfolgeknotens berschrieben werden Abbildung 69 zeigt das L schen des Punktes 415 Der rote Pfeil verdeutlicht die neue Ver zeigerung Der Splitwert des inneren Knotens 4 wird mit dem Wert 3 des verbleibenden Blatt knotens berschrieben 122 Construction Erzeugung 3 7 5 4 2 7 Abbildung 69 L schen eines Punktes im dynamischen Priorit tssuchbaum 8 4 5 Der semidynamisch statische Baum Der Aufbau des statischen Baumes erfolgt erst nach der Eingabe aller Punkte Der Baum soll ein ausgewogener Blattsuchbaum sein der alle x Werte der Punkte in den Blattknoten aufweist Aus gewogen bedeutet dass bis auf die unterste Ebene alle Ebenen vollst ndig besetzt sind Es gibt nun verschiedene M glichkeiten einen solchen Baum zu erzeugen Wir beschlossen ihn links vollst ndig darzustellen Die Besetzung der untersten Ebene soll ohne freie Pl tze zwischen den Blattknoten von links nach rechts zunehmen Dies ergibt ein regelm iges Aussehen der B ume siehe Abbildung 70 Abbildung 70 Linksvollst ndige Baumskelette 123 Construction Erzeugung F r den statischen Skelettbaum entwerfen wir einen weiteren Konstruktor in der Klasse Draw ablePrioTree an den eine nach x aufsteigend sortierte Punktliste bergeben wird Der Kon struktor ruft die Methode _staticTree2 auf die folgende Algorithmus Idee imp
55. nicht Hierbei handelt es sich um eine Erweiterung des Abstract Window Toolkit Hiermit stellt Java Grafikfunktionen f r Text Grafik und Bilddarstellungen zur Verf gung die au erdem unabh ngig von den physikalischen Ger ten Drucker und Bildschirm sind SuSE GmbH Schanz ckerstr 10 D 90443 N rnberg http www suse de Rahmenbedingung f r die Softwareentwicklung Auch unterst tzen die verf gbaren Browser JDK2 Applets nicht Dies soll sich mit einer dem n chst erscheinenden Version des Netscape Communicators ndern Daf r ist z Z ein Plug In f r den Netscape Communicator und den Internet Explorer Bestandteil der Windows Version von JRE Auch unter Solaris lassen sich seit August 1999 JDK2 Applets mit einem Plug In nutzen Zus tzlich ist aber f r 2 ein umfangreicherer Betriebssystempatch erforderlich F r Linux existiert weiterhin kein Plug In Hier verbleibt nur die Nutzung des in JDK2 enthaltenen Programms appletviewer F r die Nutzung des Applets mit einem Browser muss die HTML Seite aus der das Applet auf gerufen wird unter Verwendung einer speziellen Java Applikation aufbereitet werden Erst dann kann der Browser unter Nutzung des JRE das Applet starten Mit der so modifizierten HTML Seite l sst sich das Applet allerdings nicht mit dem appletviewer aufrufen Als Fazit dieser Ausf hrungen bleibt dass gegenw rtig bei der Nutzung als Applet zus tzlicher Aufwand notwendig ist Dies stellt e
56. r die erste Komponente verwendet Punkte die im Baum keinen Platz finden werden im Blattknoten in einer gleicherma en sor tierten Liste abgelegt 7 5 1 1 Der statische Priorit tssuchbaum Die Menge der zu speichernden Punkte wird in einer Liste nach den x Koordinaten aufsteigend sortiert Mit Hilfe dieser Liste erfolgt der Aufbau eines linksvollst ndigen Blattsuchbaums f r die x Koordinaten der Punkte In diesen Skelettbaum werden die Punkte nach den Kriterien des Priorit tssuchbaumes eingef gt Dazu sind die Punkte nach ihren y Koordinaten aufsteigend zu sortieren und in dieser Reihenfolge in das Baumger st einzuf gen Wegen der Sortierung der Punkte kann es dabei nicht zu einem Verdr ngen bereits eingef gter Punkte kommen 7 5 1 2 Der semidynamische Priorit tssuchbaum F r die semidynamische Variante wird der Blattsuchbaum f r das zugrunde liegende Universum erstellt Dazu erfolgt das Abdecken des Bereichs zwischen der kleinsten und der gr ten x Koordinate im ganzzahligen Bereich Auftretende Punkte werden dynamisch in den Blattsuchbaum eingef gt Um den y Heap zu erhalten kann es dabei zum Verdr ngen bereits vorhandener Punkte kommen 59 Hierbei handelt es sich um den Kurs Datenstrukturen Kursnummer 01663 der Fernuniversit t Hagen 64 Elaboration Systemanalyse und Entwurf Hinweis Vereinfachend soll als Universum das mit 1 beginnende x Intervall f r die Skelett b ume betrachtet werden
57. selbst sagt 30 von dem 90 von dem was was wir sehen man selbst tut Abbildung 1 Analyse des Battelle Instituts 15 Battelle Institut eV Am R merhof 35 60486 Frankfurt 11 Lernpsychologische Aspekte Das lernpsychologische Modell fu t auf der These dass der handelnde Mensch in besonderer Weise in der Lage ist zu lernen Diese These wird zus tzlich von einer Analyse des Battelle Insti tutes Abbildung 1 gest tzt Danach behalten wir 90 von dem was wir selbst tun Wir k nnen aber nur 10 von dem behalten was wir ausschlie lich lesen Das Studieren an der FernUniversit t auch oft noch an der virtuellen FernUniversit t ist im we sentlichen auf das Lesen der Kursunterlagen und das L sen der Einsendeaufgaben beschr nkt Hier kann das Programm einen weiteren Eingangskanal anbieten und dadurch folgendes erm glichen e _Experimentelles Vorgehen e Entdeckendes Lernen e ben und Verfestigen des betreffenden Kurstextteils von FU 1840 e L sen von Einsendeaufgaben Mit dem Programm wird zus tzlich bei den Benutzern der visuelle Eingangskanal angesprochen Dies erscheint uns besonders wichtig denn e Je mehr Arten der Erkl rung angeboten werden je mehr Kan le der Wahrnehmung genutzt werden desto fester wird Wissen gespeichert desto vielf ltiger wird es verankert und auch verstanden desto mehr Sch ler werden den Wissensstoff begreifen und ihn sp ter auch er innern VES
58. wollen wir unter anderem mit der Aufteilung der Zei chenfl che in den Eingabebereich und den Ausgabebereich erreichen Die Steuerbarkeit soll durch einstellbare Geschwindigkeit beim Aufbau von 2 d Baum und Priorit tssuchbaum erreicht werden Hierzu werden wir im Men f r die Art des Zeichnens abh ngig von der jeweiligen Strukturvariante die Auswahl zwischen unmit telbar animiert und schrittweise anbieten Siehe auch 94 Seiten 73 bis 77 Hierbei denken wir an Textverarbeitungsprogramme wie WinWord von Microsoft oder das Officepaket der Firma Star Division Hiermit meinen wir die geplante Auswahl beim 2 d Baum zwischen dynamisch dynamisch interaktiv ausgewogen und allgemein und beim Priorit tssuchbaum zwischen semidynamisch statisch semidyna misch dynamisch und dynamisch balanciert Siehe auch Kapitel 7 8 und 10 Siehe hierzu auch FU4763 S 89 20 Softwareergonomische Aspekte Der Dialog beim interaktiven dynamischen 2 d Baum soll so aufgebaut werden dass zu n chst die Splitkoordinate und erst dann der Splitwert abgefragt werden Damit wollen wir beim Benutzer das Gef hl der Konsistenz des Systems und Berechenbarkeit des Sys temverhaltens erreichen und damit m glichst ihrer Erwartungskonformit t entsprechen Um bersichtlichkeit zu gew hrleisten muss eine geeignete Darstellung und Anordnung der Informationen auf dem Bildsc
59. zum 2 4 Baum 165 10 6 4 Das Men Strukturvariante zum 2 4 2 165 10 6 5 Das Men Optionen zum 2 d Baum 167 10 6 6 Das Men Hilfe zum 2 4 168 10 7 DER PRIORIT TSSUCHBA E 169 10 7 1 Interpretation der Ausgaben zum Priorit tssuchbaum 170 10 7 2 Das Menu Datei zum Priorit tssuchbaum eeeeeeeeeeeeessssennnnnnnnnnnnnnnnnnnnnnnnnnnnen nenn 173 10 7 3 Das Men Bearbeiten zum Priorit tssuchbaum 22 0 00 1111 174 10 7 4 Das Men Strukturvariante zum Priorit tssuchbaum eeeeeeeeeesesessensnnnnnnnnnnnnnnnnnnnnn 175 10 7 5 Das Men Optionen zum Priorit tssuchbaum 176 10 7 6 Das Men Hilfe zum Priorit tssuchbaum 2222 2 1 2 011110000000 177 11 SCHLUSSFOLGERUNGEN UND AUSBLICK 220sss20000000000002 2220000000000 02 220000000000 000020000000 178 AUFTEILUNG DER GRUPPENARBEIT 0s 20000000000000 2220000000000 22200000000000002200000000000 000000000000 000 000 180 ERKT RUNG ee een 181 III Tabellen und Abbildungen ABBILDUNG 1 ABBILDUNG 2 ABBILDUNG 3 ABBILDUNG 4 ABBILDUNG ABBILDUNG 6 ABBILDUNG 7 ABBILDUNG 8 ABBILDUNG 9 ABBILDUNG 10 ABBILDUNG 11 ABBILDUNG 12 ABBILDUNG 13 ABBILDUNG 14 ABBILDUNG 15 ABBILDUNG 16 ABBILDUNG 17 ABBILDUNG 18 ABBILDUNG 19 ABBILDUNG 20 ABBILDUNG 21 ABBILDUNG 22 ABBILD
60. 0 Noack J und Schienmann B Objektorientierte Vorgehensmodelle im Vergleich in Informatik Spektrum Band 22 Heft 3 Juni 1999 Seite 166 bis 179 Koch M u a Software Ergonomie Springer Wien 1991 Mehlhorn K Data Structures and Algorithms 1 Sorting and Searching Springer Verlag Berlin 1984 Mehlhorn K Data Structures and Algorithms 3 Multi dimensional Searching and Computational Geometry Springer Verlag Berlin 1984 Literaturverzeichnis OEST98 OPPE94 OTTM93 REINS1 RICH89 ROWE98 RUMB94 SELLE97 Oesterreich Bernd Objektorientierte Softwareentwicklung Oldenburg Verlag M nchen 1998 4 Auflage Opperman R u Einf hrung in die Software Ergonomie in Eberleh H u a Software ergonomische Evaluation deGruyter 1994 Ottmann Thomas und Widmayer Peter Algorithmen und Datenstrukturen B I Mannheim 1993 2 Auflage Reingold E M und Tilford J S Tidier Drawings of Trees In IEEE Transactions on Software Engineering Vol SE 7 No 2 March 1981 Page 223ff Richards Jack und Rogers Theodore Approaches and Methods in Language Teaching Seite 100 Cambridge 1989 Rowe G W An Indruction to Data Structures and Algorithms with Java Prentice Hall Europe Munich 1998 Rumbaugh J Objektorientiertes Modellieren und Entwerfen Hanser M nchen 1994 Selle Norbert JavaAnimation Style Guides Version 1 1 vom 10 08 1997 Internes Dokumen
61. 2 d Baum entfernt werden Dies bedeutet aber dass der zugeordnete Splitknoten auch nicht mehr erforderlich ist und damit auch die zugeordnete Splitgerade zu l schen ist Wegen des Wechsels der Splitkoordinate zwischen und A von Baumebene zu Baumebene l sst sich der L schvorgang nicht auf das L schen eines Blattes in einem bin ren Suchbaum zur ckf hren Deshalb folgen hier nun grunds tzliche berlegungen zu einem m glichen L schalgorithmus Nur so k nnen wir die Design Entscheidung treffen ob das L schen im Rahmen unserer Software Entwicklung berhaupt implementierbar ist der Literatur fanden wir bis auf das schwache Entfernen FU1840 Seite 122 keinen Hinweis ber einen L schalgorithmus f r einen 2 d Baum Dieses schwache Verfahren verbietet sich hier allerdings Der Knoten im Baum lie e sich ohne Probleme geeignet kennzeichnen Im Rahmen der Visualisierung soll aber nicht nur die Datenstruktur sondern auch der 1 Quadrant mit den Punkten und den Splitgeraden dargestellt werden Beim schwachen Entfernen w rde es dort zu un blichen Darstellungen kommen Der betroffene Bereich w re durch das Entfernen des Punktes und der zugeordneten Splitgeraden i Allg kein Rechteck mehr Um eine Idee zum zu entwickelnden L schalgorithmus zu erhalten werden nachfolgend zun chst einige m gliche L schf lle betrachtet Im Fall von Abbildung 17 existiert noch kein Splitwert und damit auch noch keine Splitgerade In
62. 3 ABBILDUNG 74 ABBILDUNG 75 ABBILDUNG 76 ABBILDUNG 77 ABBILDUNG 78 ABBILDUNG 79 ABBILDUNG 80 ABBILDUNG 81 ABBILDUNG 82 ABBILDUNG 83 ABBILDUNG 84 ABBILDUNG 85 ABBILDUNG 86 ABBILDUNG 87 ABBILDUNG 88 ABBILDUNG 89 ABBILDUNG 90 ABBILDUNG 91 ABBILDUNG 92 KLASSENDIAGRAMM DER IMPLEMENTIERTEN 55 96 DRUCKBEREICH EINES DIN A4 BLATTES 0 002 2 60000000 000000005500 GRUNDS TZLICHER AUFBAU DES HILFESYSTEMS M NUTZEN DES HELPSET AUS EINER ANWENDUNG INTERAKTIONSDIAGRAMM ZUM DYNAMISCH INTERAKTIVEN Z D BAONM 105 KNOTEN NICHT IM ZEICHENBEREICH ceeeessssssesssesseneennnnnnssnnnnnnnnnnnnnnnnnnsennnnnnnnsnnnnsnnnnssnnsnnnenennnn 106 SCHRITTWEISER AUFBAU DES AUSGEGLICHENEN 2 0000000 109 ERERE RESTPUNKTLISTE a essen nme sn 111 RESTPUNKTLISTE MIT EINEM DUNKT 00000469200 112 RESTPUNKTLISTE MIT ZWEI PUNKTEN 112 RESTPUNKTLISTE MIT DREI PUNKTEN 1033 113 RESTPUNKTLISTE MEHR ALS DREI DUNKTEN 113 UNAUSGEGLICHENE FORM DES 2 114 KLASSENDIAGRAMM ZUM TERN REN 2 222222000 0222000000000000000005 0000 00 115 EINF GEN VON PUNKTEN SEMIDYNAMISCHEN PRIORIT TSSUCHBAUM ssesssseseeeterererreeeeree 118 INTERAKTIONSDIAGRAMM EINF GEN SEMIDYNAMISCHEN BAUM TEIL 1 22 1
63. 44 Vorl ufiges Klassendiagramm zum Priorit tssuchbaum Ein Blick auf die beiden Klassendiagramme zeigt offensichtliche bereinstimmungen Im Kapitel 8 werden wir deshalb als Verfeinerung gemeinsam nutzbare Klassen und eine Baumhierarchie festlegen 67 Zur Erl uterung der Symbole siehe Tabelle 10 84 Construction Erzeugung 8 Construction Erzeugung Aufbauend auf den Ergebnissen der Analysephase geht es hier um die Verfeinerung der Entw rfe und deren Implementation in Java Dabei wird die Vorgehensweise in dieser Phase exemplarisch beschrieben und nur auf besondere Einzelprobleme eingegangen 8 1 Iterative und inkrementelle Vorgehensweise Die in dieser Phase durchzuf hrenden Arbeiten erfolgen iterativ Dies bedeutet dass wir uns je weils zun chst einen geeigneten Anwendungsfall heraussuchen und diesen einschlie lich der erforderlichen Tests komplett fertig stellen Danach erarbeiten wir nach und nach die anderen An wendungsf lle bis das gesamte Programm zur Verf gung steht Der Umfang des fertigen Pro gramms nimmt durch die Iterationen stetig zu Es w chst inkrementell Dies gilt nicht unbedingt in gleichem Ma e f r den Codeumfang da beim Ausf hren weiterer Anwendungsf lle bereits fertige Klassen wiederverwendet werden k nnen und Gemeinsamkeiten erkannt werden Diese f hren nachtr glich zur Bildung von Superklassen so dass der Programmcode bei dieser iterativen Vor gehensweise st ndig berar
64. 7 5 3 2 beschrieben soll der einzuf gende Punkt dabei langsam auf seinem Einf ge pfad in den Baum hineinwandern Wird durch ihn ein anderer Punkt verdr ngt sollen beide Punk te den Platz tauschen Der verdr ngte Punkt muss weiter in den Baum hineinlaufen Die in der Methode pointInSkeletonInsert erstellte Informationsliste enth lt daf r in den Ein zeleintr gen den Punkt im aktuellen Knoten den neuen Punkt und ob getauscht wird oder nicht Aus den Knoteninformationen berechnen Methoden aus der Klasse AnimInfo die Anzahl der Zwischenschritte und die tempor ren Positionen f r das Gleiten der Punkte Pro Zwischenschritt wird im Animation Thread ein Image gezeichnet das dann zur Anzeige an die Klasse Prio TreeCanvas gesandt wird Diese blendet nur noch das gesamte Image mit der paint Me thode in die Baumzeichenfl che ein Beispiele sind in Abbildung 74 und Abbildung 75 zu sehen 129 Construction Erzeugung Abbildung 74 Animiertes Einf gen eines neuen Punktes Abbildung 75 Animiertes Einf gen mit Verdr ngen eines Punktes Beim animierten L schen im dynamischen Fall siehe Abbildung 76 sind wir in unserem Drehbuch den berlegungen aus Kapitel 7 5 3 4 gefolgt 1 2 3 Es wird ein L schpfad zu dem Knoten eingezeichnet der den zu l schenden Punkt enth lt Der Punkt wird gel scht der L schpfad entfernt die L cke animiert geschlossen Der Suchpfad zum zu l schenden Knoten wird eingezeichnet Di
65. Anzahl Anfrage l schen Baum zeichnen k der Punkte 2 betr gt Also sind als Eingabe Punktmengen mit 4 8 16 32 usw Punkten zu be trachten Hier werden 8 Punkte aus gew hlt Es muss sich ein Baum mit 8 Bl ttern in der dritten Ebene er geben Beispiel 5 Ausgeglichener Baum f r 8 Punkte 138 Programmtest Erwartetes Ergebnis Verhalten des Programms Ein ausgeglichener 2 d Baum hat in der untersten Ebene genau dann 2 Bl tter wenn die Anzahl k der Punk te um 1 gr er ist als beim Baum von Beispiel 5 Es gilt also k 2 1 Dabei m ssen aufgrund des imple mentierten Algorithmus diese beiden Bl tter am u ersten rechten Knoten angeheftet sein ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen 4 1 7 2 58 0 712 85 6 2124 8 6 8 7 10 Beispiel 6 Ausgeglichener Baum f r 9 Punkte Erwartetes Ergebnis Verhalten des Programms Ein ausgeglichener 2 d Baum hat in der untersten Ebene genau dann 2 Bl tter weniger als maximal m glich wenn die Anzahl k der Punkte um 1 kleiner ist als beim Baum von Bei spiel 5 also k 2 1 Der ausgeglichene 2 d Baum mit disjunkten Koordinaten E3 Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichn
66. Auswahl der Struktur variante semidynamisch oder nach dem L schen aller Punkte muss der leere Skelettbaum aufgebaut wer den Gleiches gilt f r die Auswahl des Men punktes Neuzeichnen bei leerer Punktliste Der semidynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Alle Punkte l schen bn Anzahl Bl tter Beispiel 12 Test des Aufbaus eines leeren semidyna mischen Baums Erwartetes Ergebnis Verhalten des Programms Bei Auswahl der Strukturvarianten dynamisch dynamisch balan ciert oder nach dem L schen aller Punkte muss der initiale Knoten des dynamischen Priorit tssuch baumes mit dem speziellen Split wert im Ausgabebereich darge stellt werden ES Der dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Punkt 11 5 erreicht Beispiel 13 Test des Aufbaus eines leeren dynami schen Baums 143 Programmtest Erwartetes Ergebnis Verhalten des Programms Hat der Benutzer im semi dynamisch statischen Fall Punkte eingegeben aber den Baum ber die Schaltfl che Baum zeichnen noch nicht aufbauen lassen so muss der Wechsel in die anderen Strukturvarianten trotzdem unge st rt ablaufen auch wenn beim statischen Fall der Baumcontroller leer ist solange noch kein Baum e
67. Baum appletviewer PrioApplet html f r den Priorit tssuchbaum Alternativ kann KdAppletPlugIn html oder PrioAppletPlugIn html mit dem Netscape Communicator oder dem Internet Explorer geladen werden 157 Bedienungsanleitung des Programms VisualGeom 10 5 Das Startmen Das Startmen stellt drei Buttons zur Verf gung Angeboten werden der 2 d Baum der Priori t tssuchbaum und das Beenden der Applikation bzw das Schlie en des Applets Visualisierung geometrischer Datenstrukturen Pi EZ Priorit tssuchbaum 2 dimensionaler Suchbaum Programmende Bitte einen Baumtyp ausw hlen Abbildung 78 Startmen der Applikation von VisualGeom Visualisierung geometrischer Datenstrukturen Priorit tssuchbaum 2 dimensionaler Suchbaum Schliessen Bitte eine Baumtyp ausw hlen Applet window Abbildung 79 Startmen des Applets von VisualGeom 158 Bedienungsanleitung des Programms VisualGeom 10 6 Der 2 d Baum Der k dimensionale Suchbaum Titelleiste mit aktueller Datei Strukturvariante Hilfe Baumbezeichnun g Startmen zur Zeit deaktivier te Buttonleiste Eingabebereich f r die Punkte Ausgabebereich f r die verschie denen Suchb ume Punkt 14 11 erreicht Statuszeile Abbildung 80 Startfenster des 2 d Baums Erst nach der Auswahl einer Strukturvarianten k nnen mit der Maus Punkte im Eingabebereich
68. E 10 TABELLE All Verzeichnis der Abbildungen BEISPIEL F R DIE AUFTEILUNG DER 155 00 7 EDERT nee ee 9 DIE DATELMAB IHM ni 11 AUSZUGAUSEINER FOE DATEL 12 AUSZUG AUS DER DATEI KDHELPINDEX Mt 13 Verzeichnis der Tabellen LISTE DER DOWNLOAD WWW ADRESSEN TEIL 5 LISTE DER DOWNLOAD WWW ADRESSEN 2 2102 2 2 2 2 1000 00000000000000000000000444 6 TAGS IN DER HELPSET DATEI HELP pe 10 BEDEUTUNG DER TAGS IN DER Map Damgt 11 TAGS IN DER TOC Darerfenri1i 12 TAGS N DER TOC DATEI 2 2 02020020224 44400 00 0 00000000000000 13 TAGS IN DER DATEI 14 VERWENDETE Ugp Casgp DLAGRAMMSYMBOLE 8 15 VERWENDETE AKTIVIT TSDIAGRAMMSYMBOLE 16 VERWENDETE 16 VERWENDETE INTERAKTIONSDLAGRAMMSYMBOLR 17 Literaturverzeichnis Literaturverzeichnis 1 1 B cher und Zeitschriften BOOC9Y9 Booch Jacobson Rumbaugh The Unified Software Development Process Addison Wesley Bonn 1999 BOOC9Y9a Booch Jacobson Rumbaugh Das UML Benutzerhand
69. E2 f r e Windows 95 Windows 98 e Windows NT http java sun com products jdk 1 2 jre download windows html Hinweis Dieses Produkt schlie t das Plug In f r die Browser Net scape Communicator und Internet Explorer unter Windows ein 2 f r Linux http www blackdown org java linux mirrors html JRE2 f r Linux http www blackdown org java linux mirrors html 2 f r Solaris http www sun com solaris jdk download 1 2 1_03 JRE2 f r Solaris http www sun com software solaris jre index html JRE2 Plug In f r Solaris http www sun com solaris netscape jpis index html Tabelle 1 Liste der Download WWW Adressen Teil 1 Literaturverzeichnis Produkt Internetquelle JavaHelp http java sun com products javahelp index html HTMLCONF 12 ZIP http java sun com products plugin 1 2 jinstall 12 win32 cab Hinweis Dies ist das Java Programm um JDK2 Applets durch Anpas sen der HTML Startseite mit dem Netscape Communicator oder dem Internet Explorer starten zu k nnen Kawa http www tek tools com kawa Hinweis Integrierte Entwicklungsumgebung unter Windows Rational Rose http www rational com rose Hinweis BOOC99 liegt ein Bestellzettel f r eine CD mit der kosten losen Evaluation Version dieses Produktes bei Tabelle A2 Liste Download WWW Adressen Teil 2 Anleitung zum Erstellen der Hilfedateien an einem Beispiel
70. FernUniversit t Gesamthochschule Hagen Fachbereich Informatik Diplomarbeit Zur Erlangung des Grades eines Diplom Informatikers November 1999 Visualisierung Geometrischer Datenstrukturen unter Ber cksichtigung softwareergonomischer und lernpsychologischer Gesichtspunkte gepr ft von Prof Dr Rolf Klein Lehrgebiet Praktische Informatik VI verfasst von Ingrid Schumacher und Klaus Dieter Schumacher Zusammenfassung Zusammenfassung Diese Diplomarbeit beschreibt unsere Intentionen f r das entwickelte Programm und die Rahmen bedingungen f r unsere objektorientierte Softwareentwicklung Die Softwareentwicklung erfolgt angelehnt an den Unified Software Development Process von Booch Jacobson und Rumbaugh BOOC99 Dabei setzen wir als Modellierungswerkzeug UML die Unified Modeling Language ein Die Beschreibung einiger Schwierigkeiten bei der Implementation in Java und ein Ausblick schlie en die Arbeit ab Das mit unserer Diplomarbeit entwickelte Softwareprodukt richtet sich vor allem an die Stu dierenden des Kurses Algorithmische Geometrie an der FernUniversit t Hagen FU1840 Die im Kurs vorgestellten Datenstrukturen 2 dimensionaler Suchbaum und Priorit tssuchbaum werden mit dem Programm visualisiert So wird den Studierenden die M glichkeit er ffnet die Datenstrukturen durch Beobachtungen und selbst ndigen Aufbau zu analysieren und zu reflektieren Dies geschieht durch das Nutzen der Demos und die
71. NAMISCHEN ANIMIERTES L SCHEN IM DYNAMISCHEN AKTIVIT TSDIAGRAMM BEREICHSANPRACE 8 BEISPIELSKIZZE ZUR 11 12 1 444 000000000000000 00004600 0 33 SPEZIELLES MEN SYSTEM ZUM PRIORIT TSSUCHBAUM VORL UFIGES KLASSENDIAGRAMM ZUM Z D BAOM VORL UFIGES KLASSENDIAGRAMM ZUM B SISFENSTER F R DIE SUCHB UME au ed KLASSENDIAGRAMM ZUR ZUSAMMENSTELLEN DER 2 ZUSAMMENSPIEL DER KLASSEN NACH DEM MNC Ppmzm INTERAKTIONSDIAGRAMM ZUM ANMELDEN EINES 5 65 22 2 2 22 SCH NES ZEICHNEN MIT RELATIVEM OFFSET UND BERECHNETEM X WERT IV Tabellen und Abbildungen ABBILDUNG 51 ABBILDUNG 52 ABBILDUNG 53 ABBILDUNG 54 ABBILDUNG 55 ABBILDUNG 56 ABBILDUNG 57 ABBILDUNG 58 ABBILDUNG 59 ABBILDUNG 60 ABBILDUNG 61 ABBILDUNG 62 ABBILDUNG 63 ABBILDUNG 64 ABBILDUNG 65 ABBILDUNG 66 ABBILDUNG 67 ABBILDUNG 68 ABBILDUNG 69 ABBILDUNG 70 ABBILDUNG 71 ABBILDUNG 72 ABBILDUNG 7
72. P zwischen Phasen Phases und Arbeits abl ufen Workflows unterschieden wird Sie teilen den Gesamtprozess zeitlich horizontal und vertikal auf Jeder Phase sind die verschiedenen Arbeitsabl ufe mit unterschiedlicher Intensit t er kennbar an der H he der einzelnen Graphen zugeordnet Im Rational Unified Process werden die Phasen unterteilt in Voruntersuchung Es werden schwerpunktm ig die Arbeitsabl ufe aus der Gesch ftsmodellierung und der Anforderungsanalyse Requirement gem Abbildung 5 durchgef hrt Dabei sind nach 99 S 12 die entscheidenden Fragen in der Inception Phase What is the system primarily going to do for each of its major users What could an architecture for that system look like What is the plan and what will it cost to develop the product Die f r die Entwicklung von VisualGeom erforderlichen Elemente der Inception Phase ha ben wir bereits in den Kapiteln 2 3 4 und 5 durchgef hrt Dort wurden die Eingangsvoraus setzungen der Benutzer beschrieben die Rahmenbedingungen f r die Softwareentwicklung und Grundelemente des u eren Aufbaus von VisualGeom entworfen Aussagen ber die Kosten der Softwareentwicklung sind nur bezogen auf den zeitlichen Rahmen m glich der sich aus der Bearbeitungsdauer f r die Diplomarbeit von insgesamt sechs Monaten ergibt Elaboration Systemanalyse und Entwurf In dieser Phase erfolgt u a die berpr fung der Machbarkeit
73. PRIORIT TSSUCHBAUM 170 PUNKT EINF GEN IN DEN SEMIDYNAMISCHEN 171 ANIMIERTER AUFBAU BEIM DYNAMISCHEN DRIORTTATSSUCHBAUM 171 L SCHEN EINES DUNKTES 172 L SCHEN IM DYNAMISCHEN 55 2 172 ANFRAGE DURCHPORHREN 173 Tabellen und Abbildungen TABELLE 1 TABELLE 2 TABELLE 3 TABELLE 4 TABELLE 5 TABELLE 6 TABELLE 7 TABELLE 8 TABELLE 9 TABELLE 10 TABELLE 11 TABELLE 12 TABELLE 13 TABELLE 14 TABELLE 15 TABELLE 16 TABELLE 17 TABELLE 18 TABELLE 19 TABELLE 20 Verzeichnis der Tabellen MAXIMALE KNOTENANZAHL DES ALLGEMEINEN 2 D BAUMS 22221 KLASSEN AUS DEM PAKET COMMON F R DIE APPLIKATION BEN TIGTE 8 F R DAS APPLET BEN TIGTE BOETWARE AUFRUF VON VISUALGEOM ALS APPLET BEDEUTUNG DER VIER BUTTONS BEIM 2 0 2 D MEN PUNKTE DES 2 D MEN PUNKTE DES 6 2 D MEN PUNKTE DES MEN S STRUKTURVARIANTE TEIL 1 2 D MEN PUNKTE DES MEN S STRUKTURVARIANTE TEIL 2 2 2001 2 D MEN PUNKTE DES MEN S 00 2 D MEN PUNKTE DES 08
74. Paket com sun image codec jpeg e Netscape der Version 4 x oder h her Tabelle 4 F r das Applet ben tigte Software 153 Bedienungsanleitung des Programms VisualGeom 10 2 Installation Die CD aus Kapitel 4 des Anhangs enth lt neben VisualGeom f r Solaris Windows und Linux auch JDK2 und JRE2 einschlie lich der aktuell verf gbaren Plug Ins f r diese drei Betriebs systeme Des weiteren sind folgende Dateien vorhanden jhall jar Sie enth lt die f r V isualGeom ben tigten Klassen des Java Hilfesystems codec jar Diese Datei enth lt die f r VisualGeom ben tigten compilierten Klassen des zu JDK2 geh renden Paketes com sun image codec jpeg Nach der Installation von JDK2 bzw JRE2 sind jhall jar und codec jar in das Ver zeichnis von JDK bzw das unter JRE befindliche lib Verzeichnis zu kopieren Anschlie end m ssen sie in den Klassenpfad mit Hilfe der Umgebungsvariablen CLASSPATH aufgenommen werden Mit JDK2 unter Windows im Verzeichnis JDK2 lautet der Eintrag in der Datei AUTOEXEC BAT SET CLASSPATH C JDK2 src jar C JDK2 codec jar C JDK2 jhall jar Unter Linux ergibt sich mit JDK2 jhall jar und codec jar im Verzeichnis usr lib java z folgender Eintrag in der Datei etc profile CLASSPATH usr lib java src jar usr lib java lib dt jar CLASSPATH CLASSPATH usr lib java lib tools jar CLASSPATH CLASSPATH usr lib java jhall jar CLASSPATH CLASSPATH
75. PrioTreeGUI die Methode _lookhelp von Abbildung 54 ausgef hrt Variablen fuer die Verwendung von JavaHelp Variable fuer das Objekt das die die Kommunikation zwischen der Applikation und dem HelpSet herstellen soll private HelpBroker _helpbroker Variable fuer die URL private URL _helpURL Variable fuer das Objekt fuer das Herstellen einer Verbindung zum Hilfesystem private HelpSet _helpSet Angabe des Verzeichnisses und Namens der HelpSet Datei relativ zum Programmverzeichnis private String _helpSetName apps geodast kdHelp kdHelp hs Aufruf des Hilfesystems private void _lookHelp Kontrolle ob eine Verbindung zum Hilfessystem besteht if _helpSet null try Aufbau einer Zeichenkette die aus dem absoluten Dateiverzeichnisses des Hilfesystems und dem Dateinamen der Hilfedatei besteht String _helpURL file System getProperty user dir _helpSetName Konvertierung der Zeichenkette in eine absolute URL URL url new URL _helpURL Koppelung des Objektes mit den Daten des Hilfesystems _helpSet new HelpSet null url catch Exception ex System out println _helpSetName ist nicht korrekt oder nicht auffindbar return if Erzeugen eines Helpbrokers der den Standardnavigator nutzt _helpbroker _helpSet createHelpBroker Darstellen des Helpbrokers _helpbro
76. RMATION AKTIVIT TSDIAGRAMM PUNKT IN DYNAMISCHEN 2 D BAUM EINPOOGENT 46 BEISPIELSKIZZEN ZUM EINF GEN DES PUNKTES Oo 48 2 D BAUM MIT EINEM BLATT enna a T a E E E E a E T SS 50 2 D BAUM MIT ZWEI BL TTERN 50 2 D BAUM MIT ZWEI BL TTERN AN EINEM SPLITKNOTEN 51 2 D BAUM MIT EINEN BLATT MWURZELENOTEN L SCHEN IN EINEM BELIEBIGEN 2 D BAUM uueenneeeeeeeeennsnssssnnnnennnnsnsssnnennnnnnnnnnnnnnnennnnnnnennnnnnennenn 2 D BAUM NACH L SCHEN DES PUNKTES 1017 9992 AUFBAU EINES AUSGEGLICHENEN 2 D BAUMS TEIL 1 AUFBAU EINES AUSGEGLICHENEN 2 D BAUMS TEIL 2 AUFBAU EINES AUSGEGLICHENEN 2 D BAUMS 3 2 2 AUFBAU EINES AUSGEGLICHENEN 2 D BAUMS TEIL An AUFBAU EINES AUSGEGLICHENEN 2 D BAUMS TEIL ai AKTIVIT TSDIAGRAMM ANPRAGER CHTECK 000500111 BEISPIELSKIZZE ZUM ANFRAGERECHTECK 00000000000 MEN SYSTEM ZUM 2 0 USE CASE DIAGRAMM KOORDINATENTRANSFORMATION 0 0 AKTIVIT TSDIAGRAMM PUNKT IN PRIORIT TSSUCHBAUM EINF GEN EINES DUNKTES BEISPIELSKIZZEN ZUM ANIMIERTEN EINF GEN IN DEN DYNAMISCHEN BAUM BALANCIEREN IM PRIORIT TSSUCHBAUM TEIL 1 BALANCIEREN IM PRIORIT TSSUCHBAUM TEIL 2 9928 ANIMIERTES L SCHEN IM SEMIDY
77. Sie bitte dass Sie ggf die Rechte und Benutzeridentifikationen anpassen m ssen 10 3 Einschr nkungen Einschr nkungen ergeben sich aktuell f r die Applikation bei folgenden Punkten Die Zeit f r die Durchf hrung der Druckmethode ist bedingt durch die spezifische Art der Implementation der Firma SUN unvertretbar langsam Der zeichenbare Bereich wurde von uns wegen der Gr e des Ausgabefensters auf maximal 10 Ebenen und maximal 32 Baumknoten in der Ebene 5 beschr nkt Bei ungeeigneter Lage 155 Bedienungsanleitung des Programms VisualGeom der Knoten k nnen in den tiefer liegenden Ebenen abh ngig von der Art des sch ner Zeich nens auch weniger Knoten sichtbar sein Mit einer Fehlermeldung wird darauf hingewiesen wenn ein Knoten nicht mehr im sichtbaren Bereich liegt Die Eingabe ist allerdings nicht ge sperrt e Das Speichern von JPEG Dateien unter Solaris f hrt zu einer Fehlermeldung Bei Anwendung von VisualGeom als Applet gelten wegen des Betriebs in der Sandbox folgende weitere Einschr nkungen e Speichern und Laden von Punktdateien ist nicht m glich e Speichern von Eingabe und Ausgabebereich als JPEG Datei ist nicht m glich Das Drucken aus einem Applet heraus ist nicht m glich e Die Nutzung des Java Hilfesystems bereitet beim Aufruf des Applets mit dem applet viewer Schwierigkeiten 10 4 Starten der Anwendung F r das Starten als Applikation und als Applet ist in da
78. T78 Seite 42 Unterricht besteht darin dem Sch ler Schritt f r Schritt durch Formulierungen und Neufor mulierungen eines Problems oder Wissensbereiches einen Weg zu weisen STAMS84 5 63 16 25 Die mit dem entdeckenden Lernen vertretene Hauptthese lautet dass das Lernen um so wirkungsvoller ist als es durch eigene aktive Erfahrungen erfolgt und dabei auf selbst ndigen entdeckerischen T tigkeiten beruht Vester VEST78 unterscheidet zwischen vier Eingangskan len auditiv Das Verstehen erfolgt durch Kommunikation visuell Das Lernen erfolgt durch das Auge durch Beobachtung haptisch Das Erfahren erfolgt durch F hlen und Anfassen intellekt Das Lernen erfolgt anhand abstrakter Formeln 12 Lernpsychologische Aspekte Auch wenn sich diese Zitate auf Schule beziehen lassen sie sich nach unserer Erfahrung als Studenten und Referenten in der Erwachsenenbildung sinngem auch auf Studenten der Infor matik bertragen Symbolische Repr sentation Enaktive Ikonische Repr sentation Enaktivienen Repr sentation Thonisigten Abbildung 2 Repr sentationen nach Bruner Beim Bearbeiten und Erfassen des 2 d Baums und des Priorit tssuchbaums aus dem Kurs Algo rithmische Geometrie FU1840 Seiten 118 bis 125 und 130 bis 135 werden die Benutzer be sonders bez glich des Begriffslernens und des Probleml sens gefordert Beim Begriffslernen 8 Wir sind b
79. Thread Threading wird durch das Betriebssystem realisiert Dies macht hier eigent lich nur Sinn wenn mehrere Prozessoren zur Verf gung stehen JIT Es wird der Just In Time Compiler verwendet NOJIT Es wird der Just In Time Compiler nicht verwendet Auch existiert JDK2 auf den drei Betriebssystemplattformen WindowsXX Solaris und Linux im mer noch nicht in der gleichen Version Auch hierdurch ergaben sich Implementationsprobleme Diverse kleinere Bugs die die Versionen 1 2 und 1 2 1 enthalten wurden mit der Version 1 2 2 unter Windows beseitigt Der aktuelle Versionsstand Ende Oktober 1999 ist e Windows JDK2 in der Version 1 2 2 JDK2 in der Version 1 3beta e Solaris JDK2 in der Version 1 2 1_03 Linux 2 Pre Release 2 f r die Version 1 2 F r MAC OS existiert weiterhin keine JDK2 Version Also kann unser Programm weiterhin nicht auf dieser Plattform genutzt werden Da wir neben Swing Komponenten in unserem Programm auch Komponenten des 2D API genutzt haben ist das Compilieren unter 1 trotz einer f r diese Version verf gbaren Swing Variante nicht m glich 85 EN Saba 2 Dieser Hinweis stammt aus einem Artikel au einer der englischen Java News Groups A 19 Anmerkungen zur Plattformunabh ngigkeit W hrend mit VisualGeom als Applikation das Speichern eines Image als JPEG Datei unter Windows und Linux problemlos m glich war kam es unter Solaris trotz der JDK2 Version
80. UNG 23 ABBILDUNG 24 ABBILDUNG 25 ABBILDUNG 26 ABBILDUNG 27 ABBILDUNG 28 ABBILDUNG 29 ABBILDUNG 30 ABBILDUNG 31 ABBILDUNG 32 ABBILDUNG 33 ABBILDUNG 34 ABBILDUNG 35 ABBILDUNG 36 ABBILDUNG 37 ABBILDUNG 38 ABBILDUNG 39 ABBILDUNG 40 ABBILDUNG 41 ABBILDUNG 42 ABBILDUNG 43 ABBILDUNG 44 ABBILDUNG 45 ABBILDUNG 46 ABBILDUNG 47 ABBILDUNG 48 ABBILDUNG 49 ABBILDUNG 50 Verzeichnis der Abbildungen ANALYSE DES BATTELLE INSTITUTS 00 000000000000000000000000000 ETTE 11 REPR SENTATIONEN NACH BRUNER eeeeeeeeeeeeererererrererrrrrrrereee DER SOFTWARE ERGONOMIE ZUZUORDNENDE 18 ENTWICKLUNG OBJEKTORIENTIERTER VORGEHENSMODELLE 24 DER RATIONAL UNIFIED 5 25 AZrl SICHTEN BEISPIEL F R DIE BAUMDARSTELLUNG 1 31 BEISPIEL F R DIE BAUMDARSTELLUNG TEIL 2 2 02 0 0000000000 000000000 00 00000114 32 BEISPIEL F R DIE BAUMDARSTELLUNG TEIL 3 992 32 BEISPIEL F R DIE BAUMDARSTELLUNG TEIL 4 33 STARTBILDSCHIRM eis in 35 AUFTEILUNG DES ARBEITSFENSTERS BEREICHE 1 220022 1 4660 00000000000000000050 000 36 USE CASE DIAGRAMM KOORDINATENTRANSFO
81. aar mit dem Blattknoten 5 und dem inneren Knoten 5 wird wie im dynamischen Fall blich gel scht Dadurch verla gern sich der Punkt 1718 in den Wurzelknoten und der Punkt 15115 in den inneren Knoten 15 Im Wurzelknoten ist das AVL Kriterium verletzt Der Baum muss balanciert werden Bei der erforder lichen Einfachrotation nach links muss die Ordnung im y Heap erhal ten bleiben Vor dem Rotieren ist der Punkt 15115 ins Blatt 15 zu ver schieben um die neue Wurzel frei zumachen Nach dem Rotieren mit dem Umh ngen des Blattes 15 m s sen die Punkte 1718 und 10110 nach oben verschoben werden Die entstandenen L cken werden ge schlossen balancierte dynamische Priorit tssuchbaum Datei Bearbeiten Strukturwariante Optionen Hilfe Anfrage l schen 15 15 1 Punkt 5 5 erreicht balancierte dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Punkt 5 5 erreicht Beispiel 15 Baum L schen im dynamisch balancierten 149 Programmtest F r die Tests zu den Bereichsanfragen im semidynamischen Priorit tssuchbaum wird eine Aufteilung in folgende Eingabe quivalenzklassen vorgenommen e Es befindet sich kein Punkt im Anfragehalbstreifen s Beispiel 21 Es liegen alle Punkte im Anfragehalbstreifen s Beispiel 22 e liegen einzelne Punkte im Anfragehalbstreifen Be
82. ariante Optionen Hilfe Anfrage l schen Abbildung 87 Animierter Aufbau beim semi dynamisch statischen Priorit ts suchbaum Zun chst erfolgt die Eingabe aller Punkte Nach Bet tigen des Buttons Baum zeichnen wird der linksvoll st ndige Skelettbaum im Ausgabebe reich dargestellt Die nach der y Koor dinate aufsteigend sortierten Punkte werden nacheinander in den Baum ein gef gt Einf gen des Punktes 6 12 in den Priorit tssuchbaum bereits im Baum eingef gte Punkte noch nicht eingef gter Punkt 170 Bedienungsanleitung des Programms VisualGeom Der semidynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Punkt 2 14 erreicht Abbildung 88 Animiertes Punkt Einf gen in den semi dynamischen Priorit tssuchbaum In den st ndig vorhandenen Skelettbaum wird dynamisch jeder neu angeklickte Punkt eingef gt Dabei l sst sich der Einf gepfad des neuen Punk tes bis zu seinem Speicher knoten verfolgen Verdr ngt der neue Punkt einen bereits eingef gten Punkt so wird auch der Verdr ngungsvor gang animiert dargestellt verdr ngter Punkt der tiefer im Baum einge f gt wird neu eingef gter Punkt dynamische Priorit tssuchbaum iof x Beim Einf gen eines Punktes in den Datei Bearbeiten Strukturvariante Optionen Hilfe neu einge f
83. as Anzeigen des Punktes das Anh ngen an das Ende der Punktliste das Ermitteln des Splitwertes sein Einf gen in den dynamischen 2 d Baum die Ermittlung von Anfangs und Endpunkt der neuen Splitgeraden und die Darstellung der Splitgeraden Dem Benutzer muss dabei deutlich werden welche nderungen am 2 d Baum vorgenommen werden Das Ergebnis unserer berlegungen zeigt das Aktivit tsdiagramm von Abbildung 15 Der Splitwert kann als arithmetisches Mittel berechnet oder durch Benutzereingabe bestimmt werden 55 Siehe hierzu auch berlegungen zur Visualisierung beim Einf gen eines Punktes auf der Seite 47 45 Elaboration Systemanalyse und Entwurf Knoten Punkt in Baum einf gen e an nn nn nn mn mg PUNKTEINGABE angeklickten Punkt ermitteln falscher Punkt Punkt in Punktmenge einf gen aktualisierten Baum zeichnen Splitgerade in Ebene einzeichnen Punkt in Ebene einzeichnen DARSTELLUNG DER EINGABEFL CHE BAUMDARSTELLUNG 56 Abbildung 15 Aktivit tsdiagramm Punkt in dynamischen 2 d Baum einf gen Allgemeine berlegungen zur Baumdarstellung Der 2 d Baum wird nach dem Einf gen eines weiteren Punktes in seiner neuen Form angezeigt Dabei sind im Ausgabebereich die Kanten die Knoten die Splitwerte und die Punkte in schwarz darzustellen Im Eingabebereich werden die Punkte als kleine
84. assen von JavaHelp und das com pilierte Paket com sun image codec jpeg genutzt Unter Verwendung der zus tzlichen Klassen werden die von uns programmierten Klassen als Applikation unter Solaris mit JDK1 2 und unter Linux mit JDK1 2prel getestet e Die Applets werden unter Windows mit dem Netscape Communicator 4 5 und dem Internet Explorer in der Version 4 und unter Solaris und Linux mit dem appletviewer getestet 2 Dies ist eine integrierte unter http www tek tools com kawa erh ltliche Entwicklungsumgebung Lernpsychologische Aspekte 4 Lernpsychologische Aspekte Dieses Kapitel besitzt f r uns eine doppelte Bedeutung e Als Reflexion ber Lerntypen Lernkan le und Darstellungsarten repr sentiert es f r uns eine wesentliche Voraussetzung f r die Entwicklung des geplanten Softwareproduktes und die Formulierung der Anforderungen an das fertige Produkt e Es zeigt auf welche Einsatzm glichkeiten wir f r unser Programm sehen Damit f hren wir hier und in den Kapiteln 2 3 und 5 auch eine Voruntersuchung durch Sowohl die Theorie als auch die Praxis des Lehrens und Lernens ist ein wesentlicher Bestandteil unserer menschlichen Lebensweise Dabei spielt das Bild das wir uns vom Menschen machen eine besondere Bedeutung Die jeweiligen Ans tze der Lernpsychologie ergeben sich deshalb aus dem jeweils zugrunde gelegten Menschenbild Ausgehend vom betreffenden Menschenbild bietet die Psychologie verschied
85. atei Bestandteil von VisualGeom 21 Softwareergonomische Aspekte Hierdurch hoffen wir Zeigefehler durch physiologisches Rauschen minimieren zu k nnen Aus gleichem Grunde wollen wir beim interaktiven dynamischen 2 d Baum auf eine Mauseingabe der Splitgeraden verzichten Bereits bei einem Rasterabstand von 10 Bildpunkten erwies sich das Platzieren einer Splitgeraden als schwierig Bei einem Rasterabstand von 2 Bildpunkten wurde es unm glich Deshalb wird nur die gezielte Eingabe per Abfrage zugelassen Schlussfolgerungen f r VisualGeom zur Wahrnehmungspsychologie Wir wollen eine m glichst erwartungskonforme Gestaltung der Men s vornehmen Der Einsatz von Farben soll unter Ber cksichtigung der Farbempfindlichkeit des mensch lichen Auges 4 5 56 57 und der psychologischen Wirkungen von Farben erreicht werden Dies wollen wir bei e der Visualisierung von Zust nden und Zustands nderungen e Unterscheiden von Zust nden e dem Lenken der Aufmerksamkeit auf wichtige Bildschirminhalte Markieren selektierter Bildschirmobjekte und e Herstellen von Informationsbeziehungen ber cksichtigen Farben sollen gezielt und sparsam verwendet und mit fester Bedeutung durchg ngig f r den 2 d Baum und den Priorit tssuchbaum benutzt werden Besonders denken wir dabei an den Einsatz der Farbe rot mit der sich u a N he und Aufmerksamkeit erzeugen l sst Zeichen und Hintergrundfarb
86. ateien an einem Beispiel Tag Bedeutung lt index gt F r das Hilfesystem wird kenntlich gemacht dass es sich um eine Indexdatei handelt lt indexitem text gt Der durch text spezifizierte Indexwert wird dargestellt Er dient als Oberbegriff zu dem einger ckt die weiteren Such begriffe dargestellt werden 29 29 lt indexitem text target gt wird der durch text spezifizierte Indexwert dargestellt Mit target wird die ID einer Datei zugeordnet die bei Auswahl dieses Men punktes angezeigt werden soll Tabelle A7 Tags in der Datei kdHelpIndex xml Hinweise zu den UML Diagrammen Verwendete UML Symbole In unserer Diplomarbeit haben wir zur Veranschaulichung der Zusammenh nge Use Case Akti vit ts Interaktions und Klassendiagramme genutzt Hier folgen nun die Erl uterungen zu den dabei jeweils verwendeten Symbolen Weitergehende Informationen sind u in 99 BURK97 und 98 u finden Use Case Diagramm Ein Anwendungsfall beschreibt eine Menge von Aktivit ten eines Systems aus der Sicht seiner Akteure die f r die Akteure zu einem wahrnehmbaren Ergebnis f hren Ein Anwendungsfall wird stets durch einen Akteur initiiert Ein Anwendungsfall ist ansonsten eine Komplette unteilbare Beschreibung OEST98 Seite 207 Symbol Erl uterung QO Mit diesem Symbol wird der Akteur gekennzeichne
87. aum aufgebaut werden In diesen lassen sich dann die Punkte nach den y Koordinaten sortiert einf gen Dieser Baum wird als statische Variante des Priorit tssuchbaums bezeichnet Ist das Universum bekannt aus dem die Punkte stammen k nnen wird zun chst ein Ger st baum f r dieses Universum erstellt Beim Auftreten der Punkte werden diese dynamisch in den Baum eingef gt Dieser Baum wird als semidynamische Variante bezeichnet Fehlt die Kenntnis ber das Universum muss der Baum v llig dynamisch aufgebaut werden Pro auftretendem Punkt muss der zugrunde liegende Ger stbaum zun chst um einen Knoten x Koordinate erweitert werden bevor dann der Punkt in diesen erweiterten Baum eingef gt werden kann Beim dynamischen Baumaufbau besteht die Gefahr der Entartung Es liegt schnell kein aus gewogener Skelettbaum mehr vor Die Laufzeiten beim Einf gen L schen und der Bereichs anfrage verschlechtern sich entsprechend 63 Elaboration Systemanalyse und Entwurf Deshalb wird als weitere Variante eine balancierte Version des Priorit tssuchbaums be trachtet die nach den Kriterien f r AVL B ume balanciert werden soll da den Studenten diese Balancierungsform aus dem Grundstudium bekannt ist Bei der Betrachtung einer allgemeinen Punktmenge sind auch Punkte mit identischen x Ko ordinaten zugelassen Diese werden dann als zweidimensionales Datenobjekt be trachtet und zus tzlich die lexikographische Ordnung f
88. aus KdTreeCanvas fragt beim Zeichnen eines Knotens nun zus tzlich den Zustand der Variablen _marked Animiertes Einf gen im ausgeglichenen und allgemeinen 2 d Baum F r den animierten Aufbau eines ausgeglichenen oder allgemeinen 2 d Baums wird auf die bereits implementierte schrittweise Darstellung zur ckgegriffen Nur wird jetzt der ebenenweise Aufbau des 2 d Baums automatisch weitergeschaltet Dies erfolgt durch einen Z hler Thread der nach einer festen Zeitspanne mit jedem neuen Schritt zus tzlich zu den bereits dargestellten Ebenen auch noch die n chste Ebene zeichnen l sst Der Thread kann stets definiert durch Bet tigen des Buttons Stopp beendet werden 8 3 8 Demos zum 2 d Baum Aufgrund der bis hierher durchgef hrten inkrementellen Softwareentwicklung stehen alle f r die Demos zum dynamischen und zum ausgeglichenen 2 d Baum ben tigten Methoden zur Verf gung Sie m ssen nur in separaten Threads in der gew nschten Abfolge zusammengestellt werden Dies erfolgt in den Thread Klassen KdDemoDynamic und KdDemoStatic 116 Construction Erzeugung 8 4 Construction des Priorit tssuchbaums Der Priorit tssuchbaum wird in seiner dynamischen und semidynamische Auspr gung betrachtet Deshalb enth lt die Klasse DrawablePrioTree Konstruktoren f r beide Formen des Baumes Im dynamischen Fall wird der Baum mit einem speziellen Wurzelknoten initialisiert der einen Wert enth lt Dieser ist gr er als alle m
89. balancierter Priorit tssuchbaum Gleichzeitig mit der Eingabe der Punkte wird der Priorit tssuchbaum aufgebaut Entsteht ein unausgewogener Priorit tssuchbaum wird er zun chst balanciert bevor weitere Punkte eingef gt werden Abschlie end wird ein Anfragehalbstreifen eingezeichnet Alle bei der Bereichsanfrage besuchten Knoten und die gefundenen Punkte werden markiert Tabelle 20 Prio Men punkte des Hilfe Men s 177 Schlu folgerungen und Ausblick 11 Schlussfolgerungen und Ausblick In der Elaboration Phase konnten wir keine Umfrage bei den zuk nftigen Benutzern von VisualGeom durchf hren um deren W nsche und Anregungen f r die Programmentwicklung zu ber cksichtigen Deshalb haben wir nur unsere eigenen Anforderungen an das Software produkt einbringen k nnen Die Validierung VisualGeom lie e sich in FU1840 im Sommersemester 2000 nachholen Umsetzbare W nsche der Benutzer k nnten in einer n chsten Release aufgenommen werden um das Programm noch besser auf die Bed rfnisse der Benutzer anzupassen Bei der Programmierung bereiteten uns die Umstellung auf die objektorientierte Programmier sprache Java und die h ufigen Erweiterungen der Firma SUN einige Schwierigkeiten Der Umgang mit einem derart m chtigen Software Development Kit f hrte dazu dass wir sicher nicht die Resourcen der Sprache aussch pfen konnten Hierzu fehlte uns die praktische Erfahrung Umfangreichere Vorkenntnisse h tte
90. beitet wird Zun chst beschreiben wir das Erstellen der gemeinsamen Benutzerschnittstelle unsere grunds tz liche Entscheidung wie die B ume gezeichnet werden sollen und die Verfeinerung der Baumklas senbildung Im Anschluss folgen Erkl rungen zu den gemeinsam genutzten Methoden bez glich Drucken Laden Speichern und Hilfesystem Abschlie end gehen wir auf die speziellen Entwick lungen zum 2 d Baum und zum Priorit tssuchbaum ein 8 2 Entwicklung der gemeinsamen Komponenten Nach unserer Entscheidung f r zwei getrennte Programmteile zum Arbeiten mit dem 2 d Baum und dem Priorit tssuchbaum geht es zun chst darum eine gemeinsame einheitliche Arbeitsumge bung zu schaffen 85 Construction Erzeugung Diese soll auch als Testumgebung bei der weiteren Programmentwicklung genutzt werden Somit sind die Komponenten f r ein Basisfenster zu realisieren die in beiden Spezialfenstern eingesetzt werden k nnen Dort m ssen dann nur die spezifischen Anteile erg nzt werden 8 2 1 Entwicklung der Benutzeroberfl che Mit Hilfe der in Java 2 enthaltenen Pakete javax swing und javax swing event gestalten wir die gemeinsame Basis f r die Benutzeroberfl che zu den Suchb umen Die Swing Pakete sind eine Erweiterung des AWT aus Java 1 1 Diese neuen Klassen sind im Gegensatz zu den AWT Komponenten nicht mehr auf betriebssystemabh ngige Benutzerschnitt stellenelemente angewiesen Sie zeichnen selbst alle Schnittstelleneleme
91. buch Addison Wesley Bonn 1999 BURK97 Burkhardt Rainer UML Unified Modeling Language Objektorientierte Modellierung f r die Praxis Addison Wesley Bonn 1997 CORN97 Cornell Gary und Horstmann Cay S Core Java 1 1 Vol 1 Fundamentals Vol 2 Advanced Features Sunsoft Press Prentice Hall 1997 DEIN96 Deininger ua Studien Arbeiten Teubner Stuttgart 3 Aufl 1996 DUDES88 Claus V und Schwill A Duden Informatik Dudenverlag Mannheim 1988 FU1663 Kurs 1663 der FernUniversit t Hagen Datenstrukturen FernUniversit t Gesamthochschule Hagen 1999 FU1840 Kurs 1840 der FernUniversit t Hagen Algorithmische Geometrie FernUniversit t Gesamthochschule Hagen 1996 Literaturverzeichnis FU4763 98 HAM92 94 80 159922 KOCH91 MEH94a MEH94b Kurs 4763 der FernUniversit t Hagen Software Ergonomie und Neue Techniken Gamma Erich u a Entwurfsmuster Elemente wiederverwendbarer objektorientierter Software Addison Wesley Bonn 1998 2 Nachdruck Hampe Neteler u a Software Ergonomie Verfahren der Evaluierung und Standards zur Entwicklung von Benutzeroberfl chen Forschungsbericht des Studiengangs Informatik der Uni Bremen Bericht 2 92 1992 Herczeg M Software Ergonomie Grundlagen der Mensch Computer Kommunikation Addison Wesley Bonn 1994 Hettinger Th u a Ergonomie am Arbeitsplatz Kiel Verlag 198
92. che zum Entgegennehmen der Benutzeraktionen und zur Baumdarstellung Controller berwachen die Aktivit ten des Benutzers und den Zustand des Modells Sie bilden eine enge Einheit mit der grafischen Oberfl che und den dort stattfindenden Ereignissen und schaffen die Verbindung zum Modell und den dort auszuf hrenden Methoden 7 3 Gestaltung der Benutzeroberfl che Beiden Programmteilen dem 2 d Baum und dem Priorit tssuchbaum soll eine einheitliche be nutzerfreundliche Bedieneroberfl che zugrunde liegen die f r die unterschiedlichsten Anwen dungen aus dem Bereich der algorithmischen Geometrie Ansatz finden kann und die neuen M g lichkeiten von JDK2 zur Gestaltung von Benutzeroberfl chen ausnutzt Der Programmstart liefert ein Startfenster das die Auswahl einer Komponente 2 d Baum oder Priorit tssuchbaum erm glicht Visualisierung geometrischer Datenstrukturen Priorit tssuchbaum 2 dimensionaler Suchbaum Abbildung 11 Startbildschirm Beim MVC Konzept dem Model View Controller Konzept handelt es sich um ein typisches Entwurfsmuster siehe auch GAMM9 8 Seite 4ff 35 Elaboration Systemanalyse und Entwurf Pro Komponente wird dann ein weiteres Fenster als Arbeitsumgebung ge ffnet Abbildung 12 zeigt dass die Bildschirmgestaltung der Fenster f r den 2 d Baum und den Priorit tssuchbaum einheitlich ist Nur ihre Men systeme differieren in den Unterpunkten der Pulldown Men s Titelleis
93. chen Baum nach Einf gen der Punkte 717 515 1018 und 212 Der letzte Punkt 212 hat die Punkte 515 und 717 verdr ngt Der Punkt 1018 hat seine Position nicht ver ndert Das Zusammenspiel aller am Einf gen eines Punktes beteiligten Objekte zeigen die Interaktions diagramme von Abbildung 66 und Abbildung 67 Der InputAreaToTreeAndPointsAdapter wertet den MouseEvent aus und erzeugt den neuen Punkt mit den transformierten Werten der Bildschirmkoordinaten Der Punkt wird dem Punktvektor hinzugef gt Dieser informiert den PointVectorToViewAdapter ber die Ver nderung Dieser wiederum veranlasst das Neuzeichnen der Punkte in der Eingabefl che _view 5 Input reaToTree view list odel changeListeners PointV ectorTo AndPointsAdapter Imput reaPrio Point2DV ector EventListenerList View Adapter T T 1 1 mouseClicked add oint point new d i Point2D R H Double I 1 i i i getListenerList i listeners stateChanged 7 A changed _points Le L 1 Abbildung 66 Interaktionsdiagramm Einf gen im semidynamischen Baum Teil 1 Der Punkt wird in den Baum eingef gt Der Baum verst ndigt den PrioTreeToViewAdap ter von der nderung Der Adapter legt eine neue Instanz der Klasse PrioTreeShow an die diverse Methoden zum Zeichnen des Baums enth
94. chen Modellen und Ausgabefl che Zwischen Punktmenge und Eingabebereich PointVectorToViewAdapter bzw PointlistToViewAdapter Zwischen Suchbaum und Baumzeichenfl che KdTreeToViewAdapter bzw PrioTreeToViewAdapter Der Controller der Eingabefl che InputAreaToTreeAndPointsAdapter analysiert die Mausaktionen des Benutzers Der im Eingabebereich ausgel ste MouseEvent wird berpr ft Aus dem Event l sst sich der angeklickte Punkt ermitteln und berpr fen Ist der Punkt unter den eingestellten Programmoptionen erlaubt werden die Einf gemethoden in der Baumklasse und in der Punktmengenklasse aufgerufen Die Datenmodelle Punktmenge und Priorit tssuchbaum wer den aktualisiert Die Ver nderungen in den Modellen sorgen ihrerseits daf r dass ber die bei den Modellen ange meldeten ChangeListener PointListToViewAdapter und KdTreeToViewAdapter das Neuzeichnen der Punktmenge und des Suchbaumes veranlasst wird 90 Construction Erzeugung madel La hargi EK abea 27 A d Ingut renTaTsen ndPioistm dapter amas e disali kadi tanali _listhiedel L Input resToStahuelins dapter 1 H 1 fire ange state changed Abbildung 48 Zusammenspiel der Klasse
95. chische Aus wirkungen minimiert werden Vielmehr sollen Kompetenzen beim Umgang mit dem Software produkt entwickelt werden der Benutzer seine Pers nlichkeit durch den Umgang mit den Soft wareprodukt weiterentwickeln k nnen Dies sollte unseres Erachtens nach die wesentliche Inten tion einer Lehr Lern Software darstellen 4 Siehe auch Kapitel 6 5 Da die Aufgabe unserer Diplomarbeit ist geometrische Datenstrukturen zu visualisieren haben wir das Pro gramm VisualGeom genannt Wir werden nachfolgend grunds tzlich diesen Namen in unseren Ausf hrungen zu verwenden 17 Softwareergonomische Aspekte 5 gestahung 7 tw ep E e e iniormationsdersiellung interaktionstormen Manis u Masken Direkte Maripulsilon Hiltesystene eg er Tutoriale Syaleme Modellkerung Sensorik Motorik Wahrnehmung akustische Wahrnehmung Wahrnehmung Ged chtnis Verstehen Lennan Hardal Abbildung 3 Der Software Ergonomie zuzuordnende Themengebiete 26 HERC94 Seite 7 18 Softwareergonomische Aspekte F r unsere Softwareentwicklung erscheint uns die Definition aus DUDE88 zu allgemein ge halten Um Antworten auf unsere Frage von Seite 17 zu erhalten wenden wir uns deshalb der Abbildung 3 zu Diese Klassifikation zeigt einen berblick ber alle Themen die der Software Ergonomie zugeordne
96. chlussfolgerung Die Software soll den bisherigen Erfahrungen der Benutzer in der Funktionalit t e den Eigenschaften und dem Verhalten so weit als m glich entsprechen Bei dem sp teren Einsatz des Programms gehen wir von zwei verschiedenen Benutzerklassen aus e Prim re Benutzerklasse Hierzu z hlen wir Studenten oder sonstige Personen aus dem Fachbereich Informatik die sich gezielt mit dem 2 d Baum oder dem Priorit tssuchbaum besch ftigen wollen Sekund re Benutzerklasse Dieser Klasse ordnen wir u a die Mitarbeiter des Lehrgebietes zu die das Programm zur Veranschaulichung bei Studientagen oder zum Erstellen von Einsendeaufgaben nutzen wollen Dieses wird von SUN auch als Java 2 SDK Version 1 2 x Standard Edition bezeichnet Wir verwenden im weiteren die Abk rzung 2 Siehe hierzu Kapitel 10 2 Eingangsvoraussetzungen der Adressaten Wir werden deshalb nachfolgend statt des Begriffes Student nur noch den Begriff Benutzer verwenden Aus den beiden Benutzerklassen ergeben sich Konsequenzen f r den Funktions umfang und die Anforderungen an das von uns zu erstellende Programm 5 d Auch den Begriff Benutzer verwenden wir im Sinne von pars pro toto Rahmenbedingung f r die Softwareentwicklung 3 Rahmenbedingungen f r die Softwareentwicklung Unser Programm soll sowohl als Applet als auch als Applikation lauff hig sein und dies m glichst auf
97. den zugegriffen Mit diesen Informationen werden die Splitgeraden im Eingabebereich eingezeichnet Voraussetzung daf r ist allerdings dass an die Eingabeklasse InputAreakd neben der aktuellen Punktliste auch der 2 d Baum bergeben wird In der Methode paint der Baumausgabeklasse KdTreeCanvas wurde mit _tree DrawingKD ein Preorderdurchlauf implementiert um den dynamischen 2 d Baum mit den abgespeicherten Punkten zu zeichnen Bei sofortiger Darstellung werden alle Knoten und die Punkte schwarz gezeichnet 104 Construction Erzeugung Hinweis zur Implementation des dynamisch interaktiven 2 d Baums Die insertPoint Methode wurde von uns berladen indem wir neben den Punktkoordi naten auch noch zus tzlich den Splitwert bergeben haben Damit konnten die vorhandenen privaten Methoden f r das Einf gen eines Blattes in den dynami schen 2 d Baum durch geringe Erg nzungen Fallunterscheidungen bei _pointInsert auch f r den interaktiven dynamischen 2 d Baum genutzt werden Zus tzlich wurde in diesem Fall nur noch die Methode insertTest erg nzt Sie st tzt sich auf den privaten Methoden f r das Einf gen eines Punktes in den dynamischen 2 d Baum ab und liefert die f r das Testen der Benutzereingabe ben tigte Splitinformation also Splitrichtung und Splitintervall zur ck JOptionPane treelModel KdTreeTo view AndPointsAdapter DrawableK dTree View dapter KdTreeCanvas m
98. der Ebene beschr nkt beziehen sich die weiteren Ausf hrungen nur noch auf den k d Baum mit 2 Beim 2 d Baum werden die Punkte aus der Ebene nach folgenden Kriterien abgelegt Alle Punkte werden in den Bl ttern eingetragen In den inneren Knoten befinden sich die Splitinformationen Die Splitrichtung wechselt mit jeder Ebene zwischen x und y Richtung Begonnen wird mit der x Richtung Die Splitinformation wird abh ngig von der Splitrichtung aus den x bzw y Werten ausge w hlter unmittelbar benachbarter Punkte berechnet Existieren Punkte mit einem Koordinatenwert der identisch mit dem Splitwert ist so werden diese Punkte in einem ausgeglichenen 1 d Baum also einem eindimensionalen Suchbaum gespeichert Unterhalb eines jeden inneren Knotens ist der eindimensionale Suchbaum f r die 50 Punkte auf der Splitgeraden hinzugekommen Es entsteht ein tern rer Baum Der 2 d Baum l sst sich in unterschiedlichen Varianten realisieren Dies h ngt davon ab wie viele Kenntnisse ber die Punktmenge vorliegen Die zu betrachtende Punktmenge ist bereits vorgegeben Sie besteht aus Punkten die sich in allen Koordinaten voneinander unterscheiden In diesem Fall ist der Aufbau eines ausgegli chenen 2 d Baums m glich Es handelt sich um eine statische Variante des 2 d Baums 50 Siehe FU1840 Seite 122 37 Elaboration Systemanalyse und Entwurf Die zu betrachtende Punktmenge ist bereits vorgegeben
99. der Punktmenge befindet sich nur ein Punkt Der 2 d Baum besteht aus einem Blatt In diesem trivialen Fall m ssen nur die Punktliste geleert und das Blatt aus dem Baum entfernt werden 57 Aus diesem Grunde haben wir uns auch dazu entschlossen auf das L schen im ausgeglichenen und allgemei nen 2 d Baum zu verzichten Beim L schen und auch beim Einf gen weiterer Punkte wird ein kompletter Neuaufbau des 2 d Baums durchgef hrt 49 Elaboration Systemanalyse und Entwurf 6 17 Abbildung 17 2 d Baum mit einem Blatt Abbildung 18 2 d Baum mit zwei Bl ttern 50 Elaboration Systemanalyse und Entwurf Im Fall von Abbildung 18 ergibt sich beim L schen eines der beiden Punkte z B 3115 kein Problem Der ausgew hlte Punkt muss aus der Punktliste entfernt werden Der neu aufzubauende 2 d Baum besteht nur noch aus einem Blatt Also sind der Splitknoten mit x 4 5 und das Blatt mit dem Punkt 3115 aus dem 2 d Baum und die zugeordnete Splitgerade aus dem Eingabebereich zu entfernen Auch dieser Fall scheint problemlos implementierbar zu sein 5 0 2 49 3 12 8 4 6 17 8 18 50 N 160 D 3 12 216 7 15 4 6 17 8 18 Abbildung 19 2 d Baum mit zwei Bl ttern an einem Splitknoten 51 Elaboration Systemanalyse und Entwurf In Abbildung 19 wird mit 4114 ein Blatt gel scht an dessen Splitknoten mit x 3 5 sich das wei tere Blatt mit 3112 befin
100. det Dies bedeutet dass mit dem zu l schenden Blatt auch der Knoten mit der Splitinformation und damit die Splitgerade zu l schen ist Das verbleibende Blatt mit 3112 muss eine Ebene h her r cken Nachfolger des Knotens mit dem Splitwert y 15 werden Der Splitwert y 15 stellt nicht das arithmetische Mittel von y 12 und y 16 dar Eine Kor rektur des Splitwertes ist allerdings nicht zwingend erforderlich da als Splitwert jedes y aus dem offenen y Intervall also ye 12 16 ausgew hlt werden darf Damit scheint auch dieser Fall problemlos implementierbar 6 11 4 13 4 13 6 11 Abbildung 20 2 d Baum mit einen Blatt am Wurzelknoten 52 Elaboration Systemanalyse und Entwurf In Abbildung 20 befindet sich am linken Ast der Wurzel ein Blatt und am rechten Ast ein kompletter Teilbaum Wird nun der Punkt 219 gel scht so ist der Wurzelknoten mit seinem Splitwert berfl ssig Da sich im 2 d Baum die Splitkoordinaten zyklisch abwechseln aber stets mit den x Koordinaten bei der Berechnung des ersten Splitwertes begonnen wird m ssen in diesem Fall beide Splitknoten gel scht und die verbleibenden beiden Punkte in einen neu aufzu bauenden Baum eingef gt werden Dies bedeutet verallgemeinert dass stets ein kompletter Neuaufbau mit der verbleibenden Punktliste erforderlich wird wenn im Baum ein Blatt gel scht wird das unmittelbar am Wurzelknoten angeheftet ist Dies zu implementieren stellt kein Problem dar Die
101. durch den implementierten Algorithmus angefasst werden Damit l sst sich sogar eine Vermutung ber die Laufzeit beim Einf gen eines Punktes treffen 47 Elaboration Systemanalyse und Entwurf 3 0 Ni O Q 2 11 D S O 4 12 817 1 Schritt Ausgangssituation mit den bereits eingef gten Punkten 2111 4112 und 8117 2 Schritt Einf gen des Punktes 619 Abbildung 16 Beispielskizzen zum Einf gen des Punktes 619 Wie aus Abbildung 16 ersichtlich liegt der neu einzuf gende Punkt 619 im Splitbereich des Punktes 4112 Dies bedeutet dass das Blatt 4112 am Knoten mit dem Splitwert y 14 5 ab zuh ngen ist Dort wird jetzt der Knoten mit dem neuen Splitwert x 5 der sich als arith metisches Mittel der x Koordinaten 4 und 6 ergibt angeh ngt An diesem neuen Knoten wird links das Blatt mit dem Punkt 4112 und rechts das mit dem Punkt 619 angeheftet Die Splitgerade mit dem Splitwert x 5 wird im Eingabebereich ab der bergeordneten Splitgeraden mit y 14 5 eingezeichnet Durch die farbliche Kennzeichnung sind somit alle beim Baumaufbau entstandenen nde rungen ohne Probleme erkennbar 48 Elaboration Systemanalyse und Entwurf 7 4 3 2 Punkt aus dem dynamischen 2 d Baum l schen Im Eingabebereich w hlt der Benutzer den zu l schenden Punkt mit der rechten Maustaste aus Befindet sich die Maus ber einem bereits vorhandenen Punkt muss dieser sowohl aus der Punktliste als auch dem
102. e blich l schen Q d 1 5 Zwischenschritt mit neuer Kante Endergebnis mit korrigierten Knotenpositionen Abbildung 39 Animiertes L schen im dynamischen Priorit tssuchbaum 77 Elaboration Systemanalyse und Entwurf 7 5 3 5 Bereichsanfrage durchf hren Der Benutzer zieht im Eingabebereich mit der Maus einen nach unten offenen Halbstreifen auf Dies soll in jede Richtung m glich sein W hrend der Ziehbewegung wird stets der aktuelle Halb streifen angezeigt damit er dynamisch korrigiert werden kann Beim Loslassen der Maustaste werden die aktuellen Werte f r das x Intervall und den y Grenz wert ermittelt Der aufgezogene Bereich muss berpr ft werden Ein zu kleiner Abstand in x Richtung deutet auf eine fehlerhafte Mausaktion hin und darf zu keiner Bereichsanfrage f hren Ist der Bereich erfolgreich berpr ft werden die Werte f r das x Intervall und der y Grenzwert in Werte f r den 1 Quadranten umgerechnet Bereich OK a a re Fa kr Me TE Bereichsanfrage ausf hren BAUM gefundene Vorg nge im i Punkte i Baum markieren darstellen PUNKTDARSTELLUNG BAUMDARSTELLUNG 964 Abbildung 40 Aktivit tsdiagramm Bereichsanfrage Zur Erl uterung der Symbole siehe Tabelle A9 78 Elaboration Systemanalyse und Entwurf Mit den transformierten Werten f hrt das Programm im aktuellen Priorit tssuchbaum eine Be reich
103. e Alle drei Punkte liegen rechts oder links von der Splitgeraden Abbildung 61 Zwei Punkte liegen auf der einen und ein Punkt auf der anderen Seite der Splitgeraden Abbildung 61 112 Construction Erzeugung Der allgemeine 2 d Baum _lolx Der allgemeine 2 d Baum ioj xi Datei Bearbeiten Strukturvariante Optionen Hilfe Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Anfrage l schen Baum zeichnen Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken BEI Sg Zum Anzeigen der mittleren B ume einen Baumknoten klicken Abbildung 61 Restpunktliste mit drei Punkten Nach dem Entfernen aller Punkte auf der Splitgeraden enth lt die Restpunktliste mehr als drei Punkte Hierbei sind weitere F lle zu unterscheiden e Alle Punkte liegen auf einer Seite der Splitgeraden Dieser Fall entspricht prinzipiell dem rechten Bild von Abbildung 61 e Auf der einen Seite der Splitgeraden liegt nur ein Punkt auf der anderen die brigen Punkte Abbildung 62 e Auf jeder Seite der Splitgeraden befinden sich mindestens zwei Punkte Abbildung 62 allgemeine 2 d Baum ioj xi SIE allgemeine 2 d Baum 15 Datei Bearbeiten Strukturvariante Optionen Hilfe Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Anfrage l schen Baum zeichnen gt
104. e sollen ergonomisch richtig Kombiniert werden Dabei ist auch auf die richtige Gestaltung von Zeichengr e Gestalt der Zeichen Zeilenabstand und Zei chenkontrast zu achten Um akzeptable Antwortzeiten beim Einsatz unseres Java Programms VisualGeom zu erhalten sehen wir uns gezwungen Minimalanforderungen an die Hardwarekonfiguration zu formulieren Hiermit sind nach 94 Seite 69 Zeigefehler gemeint die vor allem durch Muskelzittern verursacht wer den und ein punktgenaues Treffen verhindern Dies konnte auf einem Laptop mit einem 13 3 TFT Display und einer Aufl sung von 1024 768 Bildpunkten festgestellt werden Siehe auch 94 Seiten 73 bis 77 22 Softwareergonomische Aspekte Schlussfolgerungen f r VisualGeom zur Kognitionspsychologie Benutzer soll die Aufgabenstellung durchschauen k nnen Es soll f r ihn erkennbar sein welche Auswirkungen sein Eingreifen beim Einf gen oder L schen eines Punktes auf den 2 d Baum oder den Priorit tssuchbaum oder beim Erzeugen von Anfragen besitzt e vVisualGeom soll dem Benutzer stets aktuelle Informationen zum ausgew hlten Baumtyp anzeigen Bei Fehleingaben sind verst ndliche und konstruktive Meldungen in der Statuszeile auszugeben e Besonderes Augenmerk wollen wir auf die Fehlerrobustheit des Systems und die einheitliche Strukturierung der Fehlermeldungen legen Benutzer soll einen angemessenen Entscheidungsspielraum erhalten So wird
105. eeNode FileMenu StartWindowApplet LeafSearchTree IOArea SuffixFilterJPG SearchTreeNode Point2DVector TreeException PaintInfo Pointlist VisualGeomApplet Tabelle 2 Klassen aus dem Paket common Zur Erl uterung der Symbole siehe Tabelle 10 Zum Erstellen des Diagramms wurde die Demoversion des Programms Rational Rose 98 eingesetzt Construction Erzeugung 8 2 4 Drucken 72 72 1 1 Druckbarer Bereich eines DIN A4 Blattes 540 720 7 5710 Abbildung 52 Druckbereich eines DIN A4 Blattes Das Implementieren einer Druckroutine gestaltete sich entgegen eigenen Erwartungen schwierig Hierzu trug u a bei dass sich der Druckertreiber unter den verschiedenen Betriebssystemen nicht identisch verh lt Schlie lich mussten wir feststellen dass unter Windows95 und 98 bei einem Pixelformat von 1 72 die sich aus dem Blattformat ergebenden 648 Bildpunkte in der H he nicht genutzt werden k nnen Experimente lieferten einen maximal zul ssigen aber nicht nachvollzieh baren Wert von 514 Bildpunkten Das Durchforsten der FAQs und der News von SUN lieferte erst Ende Oktober 1999 den Hinweis dass es sich hierbei um ein Bug handelt Er verhindert das Einstellen des Seitenformates unter Windows Unter LINUX und Solaris trat dieses Problem nicht 76 auf In allen drei F llen musste allerdings nachvollziehbar in den Newsgruppen festgestellt werden dass der Zeitaufwand beim Drucken sehr hoch is
106. ei Men s 164 Bedienungsanleitung des Programms VisualGeom 10 6 3 Das Men Bearbeiten zum 2 d Baum Alle Punkte l schen Alle Punkte werden aus der Punktliste entfernt Die Punkte aus dem Ein gabebereich und der 2 d Baum aus dem Ausgabebereich gel scht Der Be nutzer hat damit die M glichkeit die Punkte erneut einzugeben Wurde be reits die Punktliste in einer Datei gespeichert bleibt dieser Dateiname erhal ten Gleiches gilt auch f r die Einstellung unter Optionen und Art des Zeichnens Rasterabstand Der Abstand zwischen den Rasterlinien zum Einfangen der Punkte ist ein stellbar Zur Auswahl stehen 10 5 und 2 Bildpunkte Abstand zwischen den ganzzahligen x bzw y Koordinaten Liegt der Abstand bei 2 so werden keine Rasterlinien angezeigt Neuzeichnen Die Inhalte des Eingabe und des Ausgabefensters werden gel scht Ab h ngig von der ausgew hlten Strukturvariante und der Einstellung unter Optionen Art des Zeichnens erfolgt anhand der Punktliste der Neuauf bau von Punkten Splitgeraden und 2 d Baum Dabei wird jeweils nur die aktuelle Punktliste genutzt Gel schte Punkte haben keinen Einfluss auf den Aufbau des jeweiligen 2 d Baums Tabelle 8 2 d Men punkte des Bearbeiten Men s 10 6 4 Das Men Strukturvariante zum 2 d Baum War bereits eine der Strukturvarianten aus Tabelle 9 oder Tabelle 10 ausgew hlt und wird diese erneut oder eine andere gew
107. eide seit Jahren im Bereich der Erwachsenenbildung t tig und f hren Aus und Fortbildungsveranstaltungen durch 19 Aus STAMS84 Seite 64 13 Lernpsychologische Aspekte k nnen u a an Einzelbeispielen erfahrene Wahrnehmungen zusammengefasst werden Dies be deutet die zu erarbeitenden neuen Begriffe in die vorhandene kognitive Struktur einordnen zu k nnen Durch den Einsatz des Variationsprinzips also die Darstellung der Beispiele in ver schiedenen Darstellungsformen ist eine weitere Verst rkung erzielbar Dieser lerntheoretische Ansatz wird auch durch das Modell von Bruner Abbildung 2 gest tzt Nach diesem Modell Abbildung 2 ist der Wissensbereich Suchb ume auf drei verschiedene Arten darstellbar Fnaktiv Das Lehrziel soll durch eine entsprechende Anzahl von Handlungen erreicht werden Ikonisch Durch eine Reihe zusammenfassender Bilder oder Grafiken wird eine bestimmte Konzeption versinnbildlicht Dabei erfolgt allerdings keine vollst ndige Definition der Begriffe e symbolisch Dies wird repr sentiert durch eine Folge von Lehrs tzen und Definitionen Basierend auf einer kognitiven Psychologie m chten wir mit Bruner feststellen Der Lernprozess l sst sich wesentlich verbessern wenn der Wechsel zwischen den drei Ebenen von den Benutzern bewusst vollzogen wird Eine weitere Position von Bruner ist besonders das entdeckende Lernen zu f rdern Mit dieser Aussage verdeutlicht
108. eilten wiederum nach der x Koordinate sortierten Punktlisten angeheftet 17 0 2 16 1 22 4 14 3 8 Abbildung 25 Aufbau eines ausgeglichenen 2 d Baums Teil 3 Entsprechend wird im n chsten Schritt verfahren Nun werden f r die Ermittlung der Splitwerte wieder die x Koordinaten verwendet Es ergibt sich die Abbildung 26 An jedem Splitknoten befindet sich nun eine Punktliste mit einem Punkt Im letzten Schritt kann also der Baumaufbau vervollst ndigt werden indem an den zugeordneten Splitknoten nur noch die Bl tter mit den Punkten angeheftet werden siehe Abbildung 27 56 Elaboration Systemanalyse und Entwurf 17 0 216 1414 1 22 318 615 8 13 6 19 7 21 Abbildung 26 Aufbau eines ausgeglichenen 2 d Baums Teil 4 170 54054545 Gg 414 023 3 18 615 1813 619 721 Abbildung 27 Aufbau eines ausgeglichenen 2 d Baums Teil 5 57 Elaboration Systemanalyse und Entwurf Visualisieren des Aufbaus eines ausgeglichenen 2 d Baums Sofortiger Aufbau Nach der Eingabe der Punkte und dem Bet tigen der Schaltfl che Baum zeichnen werden der 2 d Baum und alle Splitgeraden unmittelbar eingezeichnet Schrittweise Nach der Eingabe der Punkte und dem Bet tigen der Schaltfl che Baum zeichnen wird der Wurzelknoten mit den beiden nach y Koordinaten sortierten Punktlisten dargestellt Der Be nutzer kann den weiteren Baumaufbau sukz
109. en Ausgeglichener Baum f r 7 Punkte Beispiel 7 139 Programmtest Erwartetes Ergebnis Verhalten des Programms Ein ausgeglichener 2 d Baum hat in BS Der ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe der untersten Ebene genau dann eine Anfrage l schen Baum zeichnen zwischen Beispiel 6 und Beispiel 7 liegende Besetzung wenn f r die Anzahl k der Punkte f r gilt 2 1 lt k lt 2 lmitn gt 2 Beispiel 7 Ausgeglichener Baum f r 11 Punkte F r die Anfrage im ausgeglichenen 2 d Baum werden folgende Eingabe quivalenzklassen betrach tet e Es befindet sich kein Punkt im Anfragerechteck s Beispiel 8 Dieser Fall l sst sich in weitere Unterf lle aufteilen So kann das Anfragerechteck komplett in einem Splitbereich liegen oder mehrere Splitbereiche schneiden liegen alle Punkte im Anfragerechteck s Beispiel 9 liegen einzelne Punkte im Anfragerechteck e Anfragerechteck bedeckt ausschlie lich die Splitbereiche der enthaltenen Punkte s Beispiel 10 e Anfragerechteck schlie t auch andere Splitbereiche ohne deren Punkte ein s Beispiel 11 140 Programmtest Erwartetes Ergebnis Verhalten des Programms Im Beispiel m ssen die drei Bl tter als angefasst gr n gekennzeichnet werden deren zugeordnete Splitbe reiche v
110. en farblich hervorgehoben in den Priorit tssuchbaum eingezeichnet Use Case Demo aufrufen Der Benutzer w hlt im Men Hilfe eines der angebotenen Demos aus Das Demo zeigt in einem Film die Vorg nge beim Einf gen und L schen von Punkten und bei der Bereichsanfrage im Baum ber eine Schaltfl che kann das Demo jederzeit vom Benutzer wohl definiert abgebrochen werden d h das Demo wird den aktuellen Arbeits schritt abschlie en bevor es endet 7 5 3 Verfeinerte Analyse mit Aktivit tsdiagrammen Einen ersten bergang von der Analyse Was soll gemacht werden zum Entwurf Wie soll dies geschehen bieten Aktivit tsdiagramme Sie stellen verfeinerte Abl ufe der Anforderungen dar und bringen M glichkeiten ins Spiel wie diese Forderungen erf llt werden k nnen 2 Sinngem nach OEST98 68 Elaboration Systemanalyse und Entwurf Dies wird hier f r die zuvor genannten Anwendungsf lle durchgef hrt Dabei erfolgen auch ber legungen wie die Visualisierung der Baumalgorithmen durchgef hrt werden kann 7 5 3 1 Punkt in dynamischen Priorit tssuchbaum einf gen Der Benutzer klickt im Eingabebereich einen Punkt mit der Maus an Die ermittelten Bildschirm koordinaten m ssen in Punkte des ersten Quadranten umgerechnet werden Dabei ist das ein gestellte Raster zu ber cksichtigen Die Punkte werden eingefangen und zu Rasterpunkten um gerechnet 0 0 oben
111. en Input Area und TreeCanvas geh ren zu den View Klassen f r die grafische Benutzeroberfl che Die Mausaktionen die noch der Klasse InputArea zugeordnet sind werden f r das Zusam menspiel nach dem MVC Konzept in separate Controller Klassen ausgelagert Einzelheiten zur Implementierung der Benutzeroberfl che und damit auch zur noch fehlenden Klasse Men folgen im Kapitel 8 2 1 82 Elaboration Systemanalyse und Entwurf Zun chst ergeben unsere berlegungen die vorl ufigen Klassendiagramme von Abbildung 43 und Abbildung 44 Splitwert Punkt KnotenEinf gen LinkerSohn KnotenL schen Mittlerer 1 d Baum PunktEinf gen rechterSohn KdNode Point 2D Double x Wert y Wert PunktAnh ngen PunktL schen KdTreeCanvas InputAreaKd KoordinatenkreuzZeichnen RasterZeichnen BaumZeichnen PunkteZeichnen SplitgeradenZeichnen Abbildung 43 Vorl ufiges Klassendiagramm zum 2 d Baum 66 Zur Erl uterung der Symbole siehe Tabelle 10 83 Elaboration Systemanalyse und Entwurf PrioTree PrioNode Splitwert KnotenEinf gen Punkt KnotenL schen linkerSohn PunktEinf gen rechterSohn PunktL schen Bereichsanfrage Point 2DVector Point2D Double PunktAnh ngen x Wert PunktL schen y Wert InputAreaPrio KoordinatenkreuzZeichnen RasterZeichnen PrioTreeCanvas BaumZeichnen PunkteZeichnen Abbildung
112. en im unmittelbaren Zusammenhang mit der aktuellen Situ ation der Applikation realisieren e Bei der Verwendung von 2 lassen sich s mtliche Hilfedateien zu einer jar Datei zu sammenfassen und komprimieren Dies erleichtert das Verwalten der Hilfedateien e _Ver nderbar und Erg nzbarkeit Unabh ngig von der Applikation oder dem Applet kann das Hilfesystem jederzeit erweitert oder ver ndert werden Da das Hilfesystem noch nicht auf allen Plattformen implementiert ist wurde auf die Nutzung der SearchEngine verzichtet Wir haben deshalb nur die Verwaltung des Inhaltsverzeichnisses und des Indexverzeichnisses implementiert Nur so konnten wir uns auf die ausschlie liche Nutzung der in der Datei jhall enthaltenen Klassen von JavaHelp zur ckziehen und auch die Verwen dung unter Linux gew hrleisten Beim Einsatz von JavaHelp ergaben sich einige Ungereimtheiten im Zusammenhang mit Applets und dem Programm appletviewer Unter Linux wird die Metadatei mit den Strukturinformationen hs nicht gefunden e Unter Windows erfolgt die Ausgabe einer Fehlermeldung dass javax help nicht aufge funden werden kann Im Debug Modus der Entwicklungsumgebung KAWA ergaben sich keine Probleme Unter Windows konnte das Hilfesystem beim Starten des Applets aus dem Netscape Commu nicator oder Internet Explorer problemlos genutzt werden Vielleicht liegt es daran dass es laut mitgelieferter Dokumen
113. en verschiedene Tags verwendet Ihre Bedeutung ist der Tabelle A3 ent nehmbar 9 Anleitung zum Erstellen der Hilfedateien an einem Beispiel Tag Bedeutung lt helpset gt Mit diesem Tag wird JavaHelp mitgeteilt dass es sich bei dieser Datei um eine HelpSet Datei handelt lt title gt Der Name des HelpSets wird festgelegt lt maps gt Angabe des Namens der zu nutzenden den Map Datei lt homelD gt Diese Standard ID wird angezeigt bei Aufruf der HelpViewer ohne dass dabei eine ID genannt wird lt mapref gt Der Name der Map Datei wird bestimmt lt view gt Navigationsm glichkeiten wie die Angabe des Inhalts und das Indexverzeichnises werden beschrieben lt name gt Der Name des Navigators TOC Index Search wird angegeben lt label gt Es erfogt das Festlegen des Namens f r den Benutzer lt type gt Dieses Tag schlie t die Angabe des Pfades der zu verwendenden Navigatorklasse ein Hier z B javax help TOCView lt data gt Dieser Tag gibt den Pfad auf die f r das Inhaltsverzeichnis oder das Indexverzeichnis verwendeten Datendateien an F r die Suchma schine ergibt sich folgende spezielle Beschreibung lt data engine com sun java help search DefaultSearchEngine gt JavaHelpSearch lt data gt Tabelle A3 Tags in der HelpSet Datei Help hs A 10 Anleitung zum Erstellen der Hilfedateien an einem Beispiel A 2 2 Die Date
114. ene Modelle f r die Erkl rung des Zustandekommens von Lernprozessen im Lernenden an Eines dieser Modelle geht vom handelnden Menschen aus Dieser lernt durch sein Tun Dabei werden durch den Einsatz ge eigneter Verst rker Verhaltensweisen und Handlungen gef rdert Angemerkt sei dass auch das Verfahren Trial an Error bei positiver R ckmeldung eine Verst rkung herbeif hren kann Mit unserem Programm sollen folgende M glichkeiten er ffnet werden e Das bliche Lehr Lern Konzept der Hochschule bei dem die Stoffvermittlung im Rahmen einer systematisch geordneten Lehrbuchstruktur erfolgt kann zumindest in einem Teilbereich des Kurses Algorithmische Geometrie FU1840 Seiten 118 bis 125 und 130 bis 135 durchbrochen werden e Das Programm kann im Rahmen der virtuellen Universit t durch geeignete Querverweise im Kurstext von FU1840 gezielt eingesetzt werden Die Benutzer setzen das Programm zur L sung geeignet aufbereiteter Einsendeaufgaben zu FU1840 ein 13 Siehe Ausf hrungen zur Inception Phase Voruntersuchung im Kapitel 6 Gerade die naive Vorgehensweise bei diesem Verfahren bietet sich beim Umgang mit dem Programm und bei Auswahl der Animation an und kann so zu grundlegenden Einsichten ber den Aufbau der Suchb ume f hren 10 Lernpsychologische Aspekte Wir behalten 50 von dem was wir h ren und sehen 10 vom dem was wir lesen 20 von dem 70 von dem was was wir h ren man
115. er seine starke N he zum von Freudenthal vertretenen genetischen Prinzip 20 Dies sind hier der Kurstext und die Visualisierung durch unser Programm 14 Lernpsychologische Aspekte Damit ergibt sich eine interessante Alternative zu einer an der systematisch geordneten Lehrbuch struktur orientierten Lehr Lern Organisation wie sie bei den Buch und Online Versionen der Informatikkurse an der FernUniversit t existiert Mit dem Kurstext liegt eine symbolische Repr sentation vor Lernende sind aber h ufig enaktiv veranlagt Mit unserem Softwareprodukt kann durch gezielten Einsatz erreicht werden dass durch eine umfangreiche Anzahl von Handlungen die zu erlernenden Begriffe schrittweise auf den drei unterschiedlichen Repr sentationsebenen erschlie bar werden Diese Variation bedingt aber eine gezielte Einbindung des Programms in die Kurseinheit 3 von FU1840 und oder die Ein bindung von Aussagen der Kurseinheit 3 in das Hilfesystem des Softwareproduktes Welche M glichkeiten bieten sich nun f r den adressatengerechten und effizienten Einsatz unseres Softwareproduktes im Rahmen des Kurses Algorithmische Geometrie an der FernUniversit t Hagen Schlussfolgernd sehen wir folgende Einsatzm glichkeiten f r das von uns zu erstellende Pro gramm Benutzer erlebt experimentell oder per Trial and Error eine erste enaktive Einf hrung in den 2 d Baum und den Priorit tssuchbaum e Benu
116. erden alle Knoten Ebene f r Ebene kopiert Mit ihr wird der Aufbau nach Abbildung 57 erm glicht Nach der Eingabe aller Punkte l st der Benutzer mit der Schaltfl che Baum zeichnen den schrittweisen Aufbau aus Dies bewirkt das L schen von Baum und Splitgeraden und das Setzen eines Ebenenz hlers auf Null In den paint Methoden werden der Wurzelknoten mit den angeh ngten Teillisten und die Splitgerade dargestellt Die angeh ngten Teillisten werden dabei in rot dargestellt Mit dem Button Weiter ist der Ebenenz hler inkrementierbar und damit die n chste Ebene darstellbar Ist die Anzahl der in der Queue befindlichen Knoten kleiner oder gleich DT L So wird der gesamte ausgeglichene 2 d Baum dargestellt 8 3 6 Der allgemeine 2 d Baum Bei der Implementation des 2 d Baums f r allgemeine Punktmengen traten zwei Probleme auf Zum einen konnte der Algorithmus f r den ausgeglichenen 2 d Baum nicht genutzt werden andererseits mussten aufgrund der Entscheidungen unter 7 4 3 5 Methoden f r die Auswahl das ffnen und das Zeichnen der 1 d B ume implementiert werden F r das Sortieren der Punkte wurde es erforderlich die Methoden addSortedXPoint und addSortedYPoint aus der Klasse Pointlist so zu erweitern dass bei identischer x Koordinate bzw y Koordinate die Punkte aufsteigend nach der y Koordinate bzw nach der x Koordinate sortiert werden 110 Construction Erzeugung Aufteilen allgemeiner Punktmen
117. erfol gel schter gen Dabei wird zuerst der Suchpfad Punkt zum Vater des zu l schenden Blatt knotens markiert Befindet sich in diesem Knoten noch ein Punktwert so wird dieser den verbleibenden Nachfolgeknoten verschoben Erst Punkt 5 10 erreicht danach erfolgt das L schen der Kno Abbildung 91 L schen im dynamischen ten Die neue Kante wird zun chst Priorit tssuchbaum rot dargestellt 172 Bedienungsanleitung des Programms VisualGeom semidynamische Priorit tssuchbaum Nach dem Aufziehen eines Anfrage Datei Bearbeiten Strukturvariante Optionen Hilfe FETTEN halbstreifens werden im Baum besuchten Pfade gr n gekenn zeichnet Die bei der Anfrage gefun denen Punkte werden in der gleichen Farbe markiert gefundene Punkte ebenfalls besuchte Knoten Abfragehalbstreifen Abbildung 92 Anfrage durchf hren 10 7 2 Das Menu Datei zum Priorit tssuchbaum Neu Das Programm wird in den Startzustand zur ckgesetzt Ggf ge ffnete Dateien werden geschlossen Dateinamen gel scht und die ausgew hlte Strukturvariante zur ck gesetzt Die Men punkte unter Optionen werden ebenfalls auf die Startwerte zu r ckgesetzt In der Titelleiste erscheint die Meldung Der Priorit tssuchbaum Alle in diesem Modus nicht nutzbaren Men punkte und die Buttons werden deaktiviert ffnen Beim ersten Mal wird das Dateiverzeichni
118. ese wird auch als Splitkoordinate bezeichnet Im Wurzelknoten wird immer mit der ersten Koordinate begonnen Hierdurch entstehen in der Ebene Splitgeraden Sie teilen die Punktmenge auf Wenn sich die Punkte in allen Koordinaten voneinander unterscheiden differieren die beiden so entstandenen Punktteilmengen maximal um eins Ein ausgeglichener 2 d Baum f r n Punkte in der Ebene l sst sich in Zeit O nlogn kon struieren Er belegt O n viel Speicherplatz Eine Bereichsanfrage mit achsenparallelem Rechteck l sst sich in Zeit On a beantworten hierbei bezeichnet a die Gr e der Antwort FU1840 S 121 Einleitung Der Priorit tssuchbaum Der Priorit tssuchbaum dient ausschlie lich zur Speicherung von Punkten in der Ebene Er be steht aus einer Kombination eines eindimensionalen Bereichsbaums und eines Punkte Heaps Beim eindimensionalen Bereichsbaum handelt es sich um einen ausgeglichenen bin ren Suchbaum Es wird zwischen dynamisch und statisch aufgebauten Priorit tssuchb umen unterschieden Vor dem Aufbau eines statischen Priorit tssuchbaums muss die Punktemenge bekannt sein Es er folgt erst der Aufbau eines eindimensionalen Bereichsbaums In diesen werden anschlie end die gegebenen Punkte unter Ber cksichtigung folgender Kriterien eingetragen Jeder Punkt befindet sich auf dem Suchpfad zu seiner x Koordinate Die Werte der y Koordinaten steigen entlang des Pfades von der Wurzel zu einem Blatt monoto
119. eser endet in dem Vaterknoten des zu l schenden Blattknotens Ist noch ein Punkt im Vaterknoten abgelegt so muss dieser animiert tiefer im Baum neu eingef gt werden Dann wird die Kante rot eingezeichnet um das Zeigerumh ngen zu verdeutlichen Alle Knoten stehen noch an ihren alten Positionen aber die gel schten sind ausgeblendet Abschlie end wird der neue Baum mit den korrigierten Knotenpositionen angezeigt Die Informationslisten f r alle Zwischenschritte werden von den L schmethoden im DrawablePrioTree aufbereitet Die L schanimation arbeitet alle Zwischenschritte hnlich wie beim Punkteinf gen sequentiell ab sendet jedes neuaufbereitete Image zum Anzeigen an die Baumzeichenfl che Nur wandern die Punkte beim L schen vom Zielknoten zum Startknoten r ckw rts den Baum hinauf 130 Construction Erzeugung Abbildung 76 Animiertes L schen im dynamischen Priorit tssuchbaum Beim Erstellen der Animationen gab es vor allem Probleme mit der Ablaufgeschwindigkeit Anfangs war es auch schwierig zu einer ruhigen flackerfreien Darstellung zu gelangen Zuerst haben wir f r das Einf gen von Punkten in den dynamischen Priorit tssuchbaum mit drei aufeinanderfolgenden Threads gearbeitet die zun chst den alten Baum gezeichnet dann die Knoten erg nzt und zuletzt den Punkt eingef gt haben Sie wurden in der paint Methode der Klasse PrioTreeCanvas aufgerufen Da das Umsetzen der oben beschr
120. essen Splitwert dann auf 4 den Nachfolgerwert korrigiert wird Der Punkt 4111 muss beim L schvorgang nat rlich erhalten bleiben Er muss vor dem L schen der Knoten in den verbleibenden Nachfolgerknoten Blatt 4 verlagert werden Der dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Punkt 7 13 erreicht Der dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Punkt 7 13 erreicht Beispiel 16 L schen im dynamischen Baum 1 146 Programmtest Erwartetes Ergebnis Verhalten des Programms Im Beispiel wird der Punkt 4111 gel scht Der Blattknoten 4 und der innere Knoten 4 bilden ein zu sammenh ngendes Knotenpaar Beim L schen muss das Blatt 7 linker des Nachfolger inneren Knotens mit dem Splitwert 7 werden Da nach dem L schen des Punktes 411 der Punkt 7113 in den inneren Knoten 4 hochgezogen wird muss sicher gestellt sein dass der Punkt trotz des L schens erhalten bleibt Er muss vor dem Entfernen der Knoten wieder in den verblei benden Nachfolgerknoten Blatt 7 verschoben werden Der dynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Punkt 4 11 erreicht orit tssuchbaum Der dynamische Pn Datei Bearbeiten Strukturvariante Optionen Hilfe Punkt 4 11
121. essive Ebene f r Ebene vornehmen lassen siehe Abbildung 23 bis Abbildung 26 Daf r wird eine Schaltfl che weiter zur Verf gung gestellt e Animiert W hrend unter schrittweise der n chste Schritt durch den Benutzer erfolgt geschieht dies hier automatisiert Der Vorgang kann dabei zu jeder Zeit definiert abgebrochen werden 7 4 3 4 Rechteckanfrage durchf hren Der Benutzer zieht im Eingabebereich mit der linken Maustaste ein Anfragerechteck auf Dies soll in jede Richtung m glich sein W hrend der Ziehbewegung soll au erdem stets das aktuelle Rechteck angezeigt werden Nur so wird dem Benutzer ein dynamischer Aufbau des Anfrage rechtecks erm glicht Nachdem die linke Maustaste losgelassen wurde erfolgt eine berpr fung des aufgezogenen Be reichs Ein zu kleiner Abstand in x oder y Richtung deutet auf eine fehlerhafte Mausaktion hin Es f hrt zu keiner Bereichsanfrage Ist der Bereich hinreichend gro gew hlt worden so werden die Bildschirmkoordinaten von Anfangs und Endpunkt in Weltkoordinaten umgerechnet 58 Elaboration Systemanalyse und Entwurf BEREICHSEINGARE Anfragerechteck aufziehen I I I I falscher i Bereich I I I D D I 1 1 I Bereich pr fen Bereich OK Get e Ae m a a erer a fl Bereichsanfrage ausf hren BAUM pe wm em em em zm em
122. f den Methoden des dynamischen Falls auf Wird ein neuer Punkt mit dem zugeh rigen Knoten eingef gt entsteht zun chst ein eventuell unbalancierter Baum An schlie end wird der neu eingef gte Knoten erneut aufgesucht um den notwendigen Balan cierungsvorgang durchzuf hren 7 10 11 9 13 5 816 eingef gt Doppelrotation links rechts Abbildung 71 Beispiel zum Punkteinf gen in den dynamisch balancierten Baum 125 Construction Erzeugung Daf r haben wir als Basis den f r AVL B ume blichen Balancierungsalgorithmus mit einfacher oder Doppelrotation eingesetzt Der Algorithmus musste nat rlich an die Gegebenheiten im Prio rit tssuchbaum angepasst werden Das Rotieren darf den y Heap der im Baum gespeicherten Punkte nicht verletzen Dazu muss vor einer Rotation der zuk nftige Wurzelknoten des rotie renden Teilbaumes freigemacht werden Ein dort abgespeicherter Punkt muss auf seinem Pfad zum Blatt eine Position tiefer neu eingef gt werden Nach der Rotation wird die entstandene L cke im neuen Wurzelknoten durch Hochziehen des passenden Punktes geschlossen Im Bei spiel in Abbildung 71 wird die Punktfolge 7110 1119 1315 417 614 und 816 eingegeben Nach dem Einf gen des Punktes 1315 reicht eine einfache Rotation Nach 614 und 816 sind Doppelrotationen erforderlich um die Balance wiederherzustellen Zum Aufrechterhalten des y Heaps dienen die fertigen Punkteinf ge und L schme
123. gen Unabh ngig vom implementierten Algorithmus ist der allgemeine 2 d Baum in Sonderf llen nicht mehr ausgeglichen Der von uns implementierte Algorithmus f r das Aufteilen der Punktliste in zwei Teillisten ermittelt zun chst das arithmetische Mittel der x Koordinaten der in der Mitte liegenden benachbarten Punkte Da aber weitere Punkte mit dem berechneten Splitwert als x Koordinate existieren k nnen wird im n chsten Schritt die Punktliste nach derartigen Punkten durchsucht Diese Punkte m ssen aus der vorhandenen Punktliste entfernt und in eine separate Punktliste eingetragen werden aus der ein 1 d Baum aufgebaut wird Nur die verbleibende Restpunktliste darf unter Ber cksichtigung des Splitwertes in zwei Teilpunktlisten aufgeteilt werden Hierbei waren diverse Sonderf lle zu ber cksichtigen Nachfolgend werden diese Sonderf lle kurz dargestellt Alle werden in der privaten Methode _insertPointlistEqual von DrawableKdTree durch Fallunterscheidungen ber ck sichtigt Der allgemeine 2 d Baum lof x Datei Bearbeiten Strukturvariante Optionen Hilfe Alle Punkte liegen auf der Split geraden Anfrage l schen Baum zeichnen Nach dem Entfernen aller Punkte auf der Splitgeraden ergibt sich eine leere verbleibende Punktmenge 14 Om Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Abbildung 58 leere Restpunktliste 111 Construction Erzeugung
124. gerecht zu werden haben wir zur Validierung von VisualGeom folgende Testverfahren eingesetzt e _White Box Tests um Sequenzen Auswahlen und Wiederholungen im Rahmen bestimmter Methoden zu testen e Black Box Tests um in hinreichendem Umfang die Funktionalit t von VisualGeom zu ge w hrleisten Code Review zum Auffinden besonders hartn ckiger semantischer Fehler Beim Auftreten von Fehlern z B dem Abweichen des beobachteten Zustandes der Graphen vom theoretisch zu erwartenden Bild haben wir die jeweilige Fehlerursache durch die Ausgabe von Zwischenwerten oder das gezielte Debuggen mit Breakpoints und dem Verfolgen von Variab lenzust nde eingekreist Anschlie end wurde die jeweilige Fehlerursache beseitigt Hilfreich war dabei die von uns genutzte integrierte Entwicklungsumgebung Sie erm glicht im Gegensatz zum im JDK integrierten Debugger eine komfortable Fehlersuche Kontrolliert werden muss allerdings noch ob unser Softwareprodukt den aufgestellten ergono mischen Anforderungen gen gt Dies bedeutet u a eine Evaluation bei den Nutzern der Software Aus der Menge m glicher Evaluationsmethoden FU4763 Seite 91 sehen wir bei dem Adressatenkreis folgende M glichkeiten Anlehnung 4763 Seite 92 bis 94 sollte zun chst ein Fragebogen ausgearbeitet wer den und damit eine schriftliche Befragung der Studenten im Zusammenhang mit der Bear beitung des Kurstextes FU1840 erfolgen 7 Ka
125. gsfallsicht Die Anwendungsfallsicht beschreibt das funktionale Verhalten des Softwareproduktes aus der Sicht von Benutzern und Entwicklern Es werden z B mittels UML der Unified Modeling Language die Interaktionen zwischen den Benutzern und dem Anwendungssystem bei der Durchf hrung eines Arbeitsganges beschrieben Hierzu stellt BOOC9YI fest What do you want the system to do for each user A use case specifies a sequence of actions including variants that the system can perform and that yields an observable result of value to a particular actor 43 99 Seite 38 44 99 Seite 41 28 Objektorientierte Softwareentwicklung Design View Entwurfssicht Mit der Beschreibung der Objekte Schnittstellen und Beziehungen wird die statische Struk tur des Systems als Menge von Subsystemen Klassen und Interfaces festgelegt Die Anwen dungsf lle werden dabei mittels UML zus tzlich in Kollaborationsdiagrammen dargestellt ya Design View Classes interfaces collaborations End user Functionality Active classes System integrators Performance Scalability Throughput Conceptual Process View teg 3 Implementation View a d a Components Programmers Software management Deployment View Nodes System engineering System topology Delivery installation Communication Physical Abbildung 6 4 1 Sichten Process View Prozesssicht
126. gungen ergibt sich das Aktivit tsdiagramm von Abbildung 33 f r das Einf gen eines Punktes in den dynamischen Priorit tssuchbaum Es zeigt die ermittelten Aktivit ten und ihre Abfolge Werden darin die Aktivit ten nach Zust ndigkeiten gruppiert so kommen die gestrichelt eingezeichneten Komponenten zustande die sich als Kandidaten f r eine grobe Klasseneinteilung anbieten PUNKTEINGABE falscher i Punkt PUNKIMENGE Knoten Punkt in Punkt in Punktmenge Baum einf gen aktualisierten Punkt in Ebene Baum zeichnen einzeichnen PUNKTDARSTELLUNG Abbildung 33 _Aktivit tsdiagramm Punkt in Priorit tssuchbaum einf gen Zur Erl uterung der Symbole siehe Tabelle 9 70 Elaboration Systemanalyse und Entwurf berlegungen zum Visualisieren W nschenswert ist eine animierte schrittweise Darstellung aller Abl ufe in der Baumzeichen fl che Zun chst jedoch soll zum Testen der Baumalgorithmen die Visualisierung in einfacher Form vorgenommen werden Der Baum wird nach jeder Ver nderung sofort in seiner neuen Form angezeigt Knoten und Kanten werden schwarz gezeichnet die Splitwerte an den Knoten ebenfalls schwarz eingetragen Die Punkte im y Heap werden blau dargestellt Dieser sofortige Zeichenmodus soll auch sp ter als Option im Programm erhalten bleiben weil er ein schnelleres Arbeiten erlaubt wenn der Benutzer die Algorithmen erst einmal verstanden hat Im folgenden werden de
127. hase liegt der Schwerpunkt auf dem Testen des Programms unter Realwelt bedingungen der Beseitigung von Fehlern und dem Durchf hren noch erforderlicher Pro grammmodifikationen Ziel sollte dabei die Herstellung der Qualit tssicherung nach 1509001 sein Des weiteren erfolgt die Schulung der Benutzer und die Auslieferung des Software produktes Diese Phase kann f r VisualGeom erst nach dem Ende der Diplomarbeit erfolgen 27 Objektorientierte Softwareentwicklung Im Rahmen der Softwareentwicklung mit dem Rational Unified Process werden in jeder der vier Phasen pro Iteration die einzelnen Arbeitsschritte Process Workflows Requirement Analysis amp Design Implementation Test nacheinander durchlaufen Je nachdem in welcher aktuellen Phase sich das Produkt gerade befindet ergibt sich nach Abbildung 5 mit welcher Intention der betreffende Process Workflow bearbeitet wird In den fr hen Iterationen werden die Anforderungen die Probleme und Risiken konkretisiert In den sp teren Iterationen kommt jeweils ein weiterer Baustein zum Programm hinzu Es w chst inkrementell Deshalb bezeichnen Booch Jacobson und Rumbaugh den Prozess der Softwareentwicklung mit dem Rational Unified Process auch als iterativ und inkrementell Zur Veranschaulichung der in der Elaboration Phase entwickelten Architektursicht des Systems verwenden Booch Jacobson und Rumbaugh die 4 1 Sichtendarstellung von Abbildung 6 Use Case View Anwendun
128. hen Priorit tssuchbaum Nach gleicher Vorgehensweise wie beim Einf gen von Punkten wurde der L schalgorithmus im semidynamischen Fall mit der Methode pointFromSkeletonDelete implementiert und getestet L schen im dynamischen Priorit tssuchbaum Im dynamischen Fall m ssen zus tzlich zum Punkt auch die Knoten mit dem x Wert des Punktes gel scht werden Hierf r haben wir die Methode deletePoint erg nzt Sie nutzt die Me thode zum L schen des Punktes im semidynamischen Fall und entfernt anschlie end die zuge h rigen Knoten mit der Methode delete delete sucht zun chst nach dem inneren Knoten Ist dessen linker Sohn der gesuchte Blattknoten so ist das gesuchte Knotenpaar gefunden An sonsten muss der gesuchte Blattknoten den gr ten Splitwert im linken Teilbaum des inneren Knotens aufweisen Gel scht werden immer der Blattknoten und sein Vorg ngerknoten auch wenn dies nicht der zu geh rige innere Knoten ist Der Vorg ngerknoten kann jedoch noch einen Punkt gespeichert ha ben Dieser muss vor dem L schen durch einen Punkteinf gevorgang in den verbleibenden Nachfolgerknoten verlagert werden Eingesetzt wird dazu die bereits fertige Methode pointIn SkeletonInsert Erst danach k nnen die Knoten durch eine neue Verzeigerung gel scht werden Dabei wird der verbleibende Nachfolgerknoten zum Sohn des Vorg ngers seines Vaterknotens War der innere Knoten nicht der direkte Vorg nger des gel schten Blattknotens
129. hirm vorgenommen werden Hierzu geh ren vor allem Orts und Farbcodierung Dies wollen wir u a erreichen indem wir das Einf gen und L schen und das Erstellen von Anfragen in geeigneter Weise farblich hervorheben Schlussfolgerungen f r VisualGeom zu Unterst tzungssystemen e Online Hilfesystem ist in VisualGeom einzubinden Dabei wollen wir folgende Ziele verfolgen Erkl rung des Anwendungsbereiches des Programms und der Grenzen des Systems Erkl rung der konkreten Anwendungsziele Erkl rung der Objekte und Operatoren des Anwendungsbereiches Erkl rung der syntaktischen Eingaberegeln und Korrekturvorg nge Belegung der Tasten des Zeigeinstrumentes Demonstrationen der M glichkeiten unseres Programms e Im Hilfesystem sollen Querverweise zum Kurstext FU1840 enthalten sein e Uns erscheint sinnvoll im Text und der Onlineversion von FU1840 einen Querverweis auf VisualGeom vorzusehen e Als Erg nzung wird auch eine Bedienungsanleitung in schriftlicher Form angeboten Schlussfolgerungen f r VisualGeom zur Physiologie Die Eingabe der Punkte soll mit der Maus erfolgen Bei der Auswahl der Punkte im Eingabebe reich werden wir nur Punkte mit ganzzahligen Koordinaten verwenden Dies wird erreicht durch Fang und Raster f r das Eingabesignal von linker oder rechter Maustaste 35 Siehe auch HERC9A4 Seiten 73 bis 77 34 35 Siehe auch Kapitel 10 Diese Anleitung ist als eigenst ndige Postscript D
130. i Map jhm Der nachfolgende Auszug von Abbildung A3 verdeutlicht den grunds tzlichen Aufbau einer Map Datei lt xml version 1 0 encoding ISO 8859 1 gt lt DOCTYPE map gt lt map version 1 0 gt lt mapID target toplevelfolder url images toplevel gif gt lt mapID target top url kdstart html gt lt mapID target kd intro url kdstart html gt lt mapID target menus file url menus file html gt lt mapID target menus edit url menus edit html gt lt mapID target menus structure url menus structure html gt lt mapID target menus options url menus options html gt lt mapID target menus help url menus help html gt lt mapID target menus help url menus help html gt lt map gt Abbildung A3 Die Datei Map jhm An der tabellarischen Darstellung f llt bereits auf dass diese Datei in der linken Spalte die jeweili gen IDs und in der rechten Spalte die zugeordneten URLs enth lt Tag Bedeutung lt map gt Mit diesem Tag beginnt eine Tabelle von Zuordnungen zwischen den IDs und den URLs lt target url gt Die Zuordnung zwischen der URL und der in den nachfolgenden Dateien verwendeten ID wird beschrieben Die Angabe der URL ist relativ da der absolute Pfad auf das Hilfe system bereits in der Applikation festgelegt wurde Tabelle A4 Bedeutung der Tags in der Map Datei Anleitung zum Erstellen der Hi
131. ickt im 1 Quadranten der Ebene mit der rechten Maustaste einen bereits im 2 d Baum enthaltenen Punkt an Der Punkt wird aus der Ebene gel scht Das betroffene Blatt und der zugeordnete Splitknoten werden aus dem Baum entfernt Die Splitgerade wird gel scht Der 2 d Baum muss teilweise neu aufgebaut und dann erneut angezeigt werden 41 Elaboration Systemanalyse und Entwurf Use Case Punkte in den ausgeglichenen 2 d Baum einf gen Der Benutzer klickt mit der linken Maustaste alle f r den Baumaufbau auszuw hlenden Punkte im 1 Quadranten der Ebene an Dabei werden nur Punkte mit ganzzahligen Koordinatenwerten zugelassen die sich in allen Koordinaten voneinander unter scheiden Die Punkte werden in den Eingabebereich eingezeichnet Sind alle Punkte eingegeben worden veranlasst der Benutzer den Aufbau des ausgeglichenen 2 d Baums Von Baumebene zu Baumebene wechselt die Splitrichtung beginnend bei der x Koordinate Die jeweiligen Splitwerte werden berechnet und der Splitknoten in den Baum eingef gt Die Punkte werden in den Bl ttern eingetragen Im Ausgabebereich wird der 2 d Baum auf unterschiedliche Weise dargestellt Der 2 d Baum und die Splitgeraden werden sofort angezeigt Der 2 d Baum und die Splitgeraden werden durch Benutzeraufforderung schritt weise Ebene f r Ebene gezeichnet Die Abl ufe beim Baumaufbau werden schrittweise in einer Animation veranschau licht 42 Elaboratio
132. iebenen Vorgehensweise leider nur unter Windows zu vertret baren Ergebnissen gef hrt hat aber leider nicht unter Linux und Solaris musste dieser Weg aufgegeben werden Als neuen Ansatz w hlten wir das Zeichnen in ein BufferedImage ein Hintergrundbild wie es das Java Paket Graphics2D zur Verf gung stellt Es gestattet das Vorbereiten einer komplexen Darstellung im Hintergrund w hrend noch ein anderes Bild am Monitor zu sehen ist Das fertige Image wird dann nur noch in den Anzeigebereich kopiert Dies gestattet ein schnelles Anzeigen eines kompletten Bildes in der paint Methode der View Klasse PrioTreeCanvas Zun chst wurde pro Bild der gesamte alte Baum neu gezeichnet bevor der wandernde Punkt an seiner neuen Position eingezeichnet wurde Dies f hrte zu einer sauberen flimmerfreien Dar stellung der Abl ufe aber die Geschwindigkeit der Animation war vor allem unter Unix wieder zu langsam Erst das Einschr nken des Neuzeichnens auf berschaubar kleine Bereiche brachte eine Bes serung so dass jetzt die Geschwindigkeit unter allen drei Betriebssystemen vertretbar ist Leider hat dadurch aber manchmal die Sauberkeit gelitten Es werden immer noch Bereiche gel scht die nicht wieder sofort nachgezeichnet werden Dies f llt besonders auf wenn zwei unterschiedliche ste im Baum sehr dicht nebeneinander liegen 131 Construction Erzeugung 8 4 9 Demos zum Priorit tssuchbaum Die zur Verf gung gestellten Demos we
133. in Punkt gel scht und die hierdurch erforderliche nderung im Suchbaum und bei den Splitgeraden vorgenommen Abschlie end wird ein Anfragerechteck gezeichnet Alle bei der Bereichsanfrage angefassten Knoten und alle aus gew hlten Blattknoten werden markiert e ausgeglichener 2 d Baum Zun chst erfolgt nur die Eingabe aller Punkte Dann wird schrittweise der Suchbaum durch Teilung der sortierten Punktlisten ebenenweise aufgebaut Dabei werden die jeweils ermittelten Splitgeraden eingezeichnet Abschlie Bend wird ein Anfragerechteck gezeichnet Alle bei der Bereichsanfrage angefassten Knoten und alle ausgew hlten Blattknoten werden markiert Tabelle 12 2 d Men punkte des Hilfe Men s 168 Bedienungsanleitung des Programms VisualGeom 10 7 Der Priorit tssuchbaum 11 D D Der Priorit tssuchbaum Datei Strukturvariante Hilfe Titelleiste mit aktueller Baumbezeichnung Startmen zur Zeit deaktivier te Buttonleiste Eingabebereich f r die Punkte Ausgabebereich f r die verschie denen Suchb ume 341 Ir Bitte eine Strukturvariante ausw hlen Statuszeile Abbildung 86 Startfenster des Priorit tssuchbaums Erst nach der Auswahl einer Strukturvarianten k nnen mit der Maus Punkte im Eingabebereich eingegeben oder gel scht und Anfragehalbstreifen ge ffnet werden Dabei gelten folgende Zuord nungen e Linke Maustaste im Eingabebereich Das Klicken mit der linken Maustaste i
134. inen Nachteil dar der unseres Erachtens bei der Nutzung von JDK2 Applets im Rahmen des Internets nicht zu gering eingesch tzt werden darf Weitere Java Tools wie das Java Hilfesystem JavaHelp befanden sich bis Juli 1999 noch in ihrer Entwicklung JavaHelp ist kein Bestandteil des JDK Die aktuelle Version des appletviewer ist laut SUN nicht daf r angepasst Das JPEG Paket ist Bestandteil des JDK2 Nutzen konnten wir es unter den Versionen 1 2 und 1 2 1 jedoch erst nachdem es compiliert in eine jar Datei konvertiert und dann in den CLASSPATH eingebunden wurde Die Situation der permanenten Fortentwicklung von Java gestaltete die Implementation der Soft ware nicht leichter Hinzu kam dass die von SUN viel ger hmte v llige Plattformunabh ngigkeit doch nicht gegeben ist siehe hierzu auch Kapitel A 4 im Anhang Java tm Plug In HTML Converter Dee i Hierbei handelt es sich um komprimiertes Java Archiv das mit dem Java Archive Tool erzeugt wurde 11 i 4 3 Im dieses Umgebungsvariablen wird festgelegt von wo die Systemklassen zu importieren sind Rahmenbedingung f r die Softwareentwicklung Deshalb beschlossen wir folgende Rahmenbedingungen festzulegen um ein gewisses Ma an Sta bilit t in unsere Implementationsaktivit ten zu bekommen e Die Entwicklung erfolgt mit JDK2 unter Windows95 bzw Windows98 mit Kawa als inte griertem Entwicklungswerkzeug Erg nzend werden die Kl
135. iner Ebene liegen alle auf einer H he Ebenen befinden sich parallel untereinander e Der linke Sohn ist links vom Vater positioniert e Der rechte Sohn befindet sich rechts vom Vater Vater liegt eine Ebene oberhalb der S hne mittig zwischen ihnen e Der Baum spiegelt also die Durchlaufanordnung der bekannten Traversal Algorithmen Inorder Preorder oder Postorder wider Der Baum hat minimale Breite Nach dem Algorithmus von Wetherell amp Shannon werden Teilb ume abh ngig von ihrer Position im Baum jedoch manchmal unterschiedlich dargestellt weil die Symmetrie von B umen noch nicht ber cksichtigt wird Diese Schw che behebt der hier verwendete Algorithmus von Reingold und Tilford Teilb ume werden danach immer gleichf rmig gezeichnet unabh ngig von ihrer Position im Baum und ihrer Umgebung Der Preis f r diese nat rlichere Darstellung ist jedoch manchmal eine etwas gr ere Baumbreite Um die Anforderungen zu erf llen bestimmt der R amp T Algorithmus relative Positionen der Kno ten in den Teilb umen Erst zum Zeichnen werden diese relativen Angaben in konkrete x und y Koordinaten umgerechnet wenn die gew nschte Position des Wurzelknotens im Zeichenbereich bekannt ist Das Ermitteln der relativen Positionen geschieht w hrend eines Postorder Durchlaufs 93 Construction Erzeugung Die beiden Teilb ume eines Knotens werden zun chst unabh ngig voneinander untersucht die am weite
136. ispiel 23 Erwartetes Ergebnis Verhalten des Programms Der Anfragehalbstreifen beinhaltet keine Punkte Im Baum muss das aufgezogene x Intervall von 2 bis 11 durchsucht werden Die Suche ist abzubrechen wenn dabei Punkte angetroffen werden deren y Koor dinate gr er als 3 y Grenzwert ist oder ein Knoten keinen Punkt ent h lt Die Bereichsanfrage im Beispiel muss bereits im Wurzelknoten abbrechen elt semidynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Beispiel 19 Anfrage ohne Punkt Erwartetes Ergebnis Verhalten des Programms Alle Punkte liegen im Halbstreifen Besucht werden muss das markierte x Intervall von 2 bis 10 Die Suche kann nur noch durch nichtbesetzte Knoten fr her abgebrochen werden Alle Punkte m ssen nach Ende der Suche markiert sein re Bee Pie Tse leten large Oplia Fhia Beispiel 20 Anfrage mit allen Punkten 150 Programmtest Erwartetes Ergebnis Verhalten des Programms Durchsucht werden muss das x Intervall von 6 bis 9 Dabei sind die Punkte 718 und 815 als gefunden zu markieren Die Suche soll bei Punkten mit y gt 9 oder in leeren Knoten abbrechen Im Beispiel m s sen deshalb alle drei Pfade bis zu den Bl ttern durchlaufen werden cm ha Beispiel 21 Anfrage mit ausgew h
137. ist in der Bedienungsanleitung im Kapitel 10 zu finden Der 2 dimensionale Suchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Hilfethemen Demos dynamisch ausgeglichen dynamisch dynamisch interaktiv ausgeglichen allgemein Alle Punkte l schen Bereichsanfrage l schen Rasterabstand 10 5 2 Neuzeichnen Art des Zeichnens o schrittweise o animiert e sofortiger Aufbau Grafik in Datei Eingabebereich Ausgabebereich Abbildung 30 Men system zum 2 d Baum 62 Elaboration Systemanalyse und Entwurf 7 5 7 5 Der Elaboration des Priorit tssuchbaums 1 Datenstruktur Priorit tssuchbaum ist ein Blattsuchbaum f r ein x Intervall in dem Punkte aus der Ebene nach folgenden Kriterien abgelegt werden Der Jeder Punkt P x y steht auf dem Suchpfad zu seiner x Koordinate L ngs eines Pfades von der Wurzel zu einem Blatt nehmen die y Koordinaten der Punkte mo noton zu Die y Werte im Baum bilden einen Minimumheap Die Punkte stehen so dicht bei der Wurzel wie m glich Zu Lernzwecken besitzen die Punkte zun chst paarweise verschiedene x Koordinaten Sp ter wird auf eine Verarbeitung einer allgemeinen Punktmenge erweitert Priorit tssuchbaum l sst sich in unterschiedlichen Varianten realisieren je nachdem wie viele Kenntnisse ber die abzuspeichernden Punkte vorliegen Ist die zu betrachtende Punktmenge bereits gegeben so kann ein ausgewogener Ger stb
138. iviert weil in dieser Variante die Splitwerte nicht als arithmetisches Mittel ausgerechnet sondern vom Benutzer bestimmt werden ausgeglichener 2 d Baum Zun chst ist die Eingabe und das L schen von Punkten m glich Der Aufbau eines ausgeglichenen 2 d Baums erfolgt erst wenn der Button Baum zeichnen angeklickt worden ist Die Darstellung des Baumaufbaus ist abh ngig von der Einstellung unter Optionen Art des Zeichnens Bei Durchf hren einer Anfrage werden alle angefassten Knoten mar kiert Die ausgew hlten Blattknoten werden gesondert gekennzeichnet Tabelle 9 2 d Men punkte des Men s Strukturvariante Teil 1 166 Bedienungsanleitung des Programms VisualGeom allgemeiner 2 d Baum Zun chst ist die Eingabe und das L schen von beliebigen Punkten m g lich Der Aufbau eines allgemeinen 2 d Baums erfolgt erst wenn der Button Baum zeichnen angeklickt worden ist Die Darstellung des Baumaufbaus ist abh ngig von der Einstellung unter Optionen Art des Zeichnens Ist an einem inneren Knoten eine zus tzliche blaue Markierung ange bracht so deutet dies auf einen angeh ngten 1 d Baum hin Wird ein so markierter Knoten mit der linken Maustaste angeklickt ffnet sich ein kleines Fenster das den am Knoten angeh ngten 1 d Baum darstellt Bei Durchf hren einer Anfrage werden alle angefassten Knoten mar kiert Die ausgew hlten Blattknoten werden gesonder
139. ker setDisplayed true _lookHelp Abbildung 54 Nutzen des HelpSet aus einer Anwendung 102 Construction Erzeugung 8 3 Construction des 2 d Baums Die Klasse DrawableKdTree enth lt einen Konstruktor f r alle drei Formen des 2 d Baumes Initialisiert wird dabei mit null Das iterative Umsetzen der Anwendungsf lle beim 2 d Baum erfolgte in nachstehender Reihenfolge 1 Einf gen von Punkten in einen dynamischen 2 d Baum mit sofortiger Anzeige der nde rungen im Baum und der neuen Splitgeraden Bereichssuche im dynamischen 2 d Baum L schen von Punkten im dynamischen 2 d Baum Der sofortige Aufbau des ausgeglichenen 2 d Baums Der schrittweise Aufbau des ausgeglichenen 2 d Baums Der Aufbau des allgemeinen 2 d Baums Aufteilen allgemeiner Punktmengen Darstellen der Splitgeraden und Kennzeichnen der Knoten mit einem 1 d Baum Einbinden separater Fenster f r die 1 d B ume 7 Animationen e f r das Einf gen von Punkten e f r die Bereichssuche 8 Demos Jeder Iterationsschritt endete mit gezielten Tests Exemplarische Testbeispiele sind im Kapitel 9 1 beschrieben 8 3 1 Einf gen von Punkten im dynamischen 2 d Baum Beim Anklicken eines Punktes im Eingabebereich erfolgen zwei Aktionen Der Punkt wird an das Ende der Punktliste angef gt Hierf r haben wir in der Klasse Point list die Methode addPoint implementiert Mit dieser Methode wird der neue Punkt an
140. ktes hochgezogen wurden um die entstandenen L cken zu schlie en Durch den Farbeinsatz l sst sich im Nachhinein gut erkennen auf welchem Pfad dies erfolgt ist e Dynamische dynamisch balancierte Variante Die entfernten Knoten werden im aktualisierten Baum nicht mehr angezeigt F r die Punkte gilt gleiches wie im semidynamischen Fall Der L schvorgang kann im dynamischen Fall aber auch einen Einf gevorgang enthalten Punkt aus Knoten verdr ngen bevor dieser gel scht werden darf Weil alle Punkte mit einer neuen Position im Baum eingef rbt werden k nnen deshalb an verschiedenen Stellen rote Markierungen auftreten 75 Elaboration Systemanalyse und Entwurf Animation e _Semidynamisch statische Variante Es gibt keine L schdynamik Der Baum wird wie beim animierten Punkteinf gen auf Seite 72 beschrieben nach dem L schen von Punkten komplett neu aufgebaut e _Semidynamisch statische Variante Der Skelettbaum wird st ndig unver ndert angezeigt nur das L schen der Punkte muss ani miert werden Zun chst wird dem Betrachter das Auffinden des Punktes gezeigt indem der Suchpfad in roter Farbe eingezeichnet wird Der gefundene Punkt wird vom Bildschirm gel scht und der Punkt der die L cke f llen soll l uft von seinem Knoten hoch zum jetzt leeren Knoten Die letzte Aktion wiederholt sich bis alle dabei entstehenden L cken geschlossen sind Abbildung 38 zeigt das L schen des Punktes 214
141. laufen Abschlie end wird eine Bereichsanfrage demonstriert Nach jeder Aktion kann der Benutzer ber eine Schaltfl che das Demo beenden In beiden Demos wird die gleiche Punktmenge verwendet so dass der Benutzer die Unterschiede zwischen den Varianten gut beobachten kann Die Demos greifen auf die animierten Darstel lungen der verschiedenen Abl ufe zur ck fassen diese in einem Film zusammen W hrend ein Demo abl uft muss f r den Benutzer durch erkl renden Text deutlich werden wel cher Vorgang gerade abl uft und welcher Punkt eingef gt oder gel scht wird da er nur passiver Betrachter ist und nicht selbst agiert 7 5 3 7 Spezielles Men system zum Priorit tssuchbaum Dem Benutzer sollen die verschiedenen Baumvarianten die Einstelloptionen f r die Darstellungs art des Baumes sowie die Auswahl der Demos ber ein Men system angeboten werden Deshalb wird zun chst das Men system aus Abbildung 42 geplant Es ber cksichtigt auch bereits Men punkte die erst sp ter bei der Erweiterung des Programms aufgegriffen werden sollen Die Bedeutung der einzelnen Men punkte ist der Bedienungsanleitung im Kapitel 10 entnehmbar Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe semidynamisch statisch semidynamisch dynamisch Punktmenge dynamisch balanciert e disjunkte x Werte o allgemein Alle Punkte l schen Art des Zeichnens Halbstreifen l schen e animier
142. lementiert Ist die Knotenanzahl eine 2erPotenz dann wird durch 2 geteilt um den Wert der Variablen Mittelndex zu ermitteln Sonst 1 N chstgr ere 2erPotenz ermitteln 2 N chstkleinere 2erPotenz ermitteln 3 Differenz zwischen den 2erPotenzen bilden 4 Knotenanzahl lt kleine 2erPotenz Differenz 2 Dann Mittelndex kleine 2erPotenz 2 Knotenanzahl kleine 2erPotenz Sonst MitteIndex gro e 2erPotenz 2 Mittelndex von Mittelndex 1 Mit Mittelndex auf die Punktliste zugreifen um den x Wert des Punktes zu ermitteln Neuen Knoten mit x Wert in den Skelettbaum einf gen _staticTree2 Mitte tl bis _staticTree2 von Mitte 1 Der rekursive Aufruf von _staticTree2 muss nach rechts beginnen damit nach den Re geln f r den Blattsuchbaum der zuvor ermittelte Knoten seine Position beh lt Nach links muss die Knotenanzahl stets um 1 erh ht werden weil der Knoten mit dem kleineren Wert als linker Sohn ein zweites Mal eingef gt wird 4 4 O Knoten 5 einf gen Q Tho Das Einf gen der Punkte in den Skelettbaum erfolgt wie im semidynamischen Fall mit der Me thode pointsInSkeletonInsert Nur sind im statischen Fall schon alle Punkte bekannt deshalb werden sie vor dem Einf gen nach den y Koordinaten sortiert So Kommt es zu keinen Punktverdr ngungsvorg ngen 124 Construction Erzeugung 8 4 6 Der balancierte dynamische Baum Der balancierte Fall setzt au
143. lfedateien an einem Beispiel A 2 3 Die Datei kdHelpTOC xml Der nachfolgende Auszug verdeutlicht den grunds tzlichen Aufbau einer HelpTOC Datei lt xml version 1 0 encoding IS0O 8859 1 gt lt DOCTYPE toc gt lt toc xml lang de gt lt tocitem text 2 d Baum image toplevelfolder gt lt tocitem text Men s gt lt tocitem text Men amp quot Dateisquot lt tocitem text Men amp quot Bearbeitensquot lt tocitem text Men amp quot Strukturvariantesquot lt tocitem text Men amp quot Optionensquot lt tocitem text Men amp quot Hilfesquot lt tocitem gt lt tocitem text Mausaktionen lt tocitem gt lt toc gt target menus target menus target menus target menus target menus target mouse file gt edit gt structure gt options gt help gt mouse gt Abbildung A4 Auszug aus einer TOC Datei Diese Datei erm glicht den Aufbau eines Inhaltsverzeichnisses mit Untergliederungspunkten Tag Bedeutung lt toc gt Diese so spezifizierte Datei wird als eine Inhaltsverzeichnisdatei interpretiert lt tocitem text image Ein Verzeichniseintrag mit dem unter text festgelegten Namen wird definiert Dieser Name wird bei der Auswahl des Eintrags angezeigt Mit image wird das zusammen mit dem Eintrag auszugebende Bild angegeben Dies erfolgt mittels einer ID Diese verweist auf die URL
144. ls arithmetisches Mittel der zugeordneten Koordinaten der betroffenen Punkte berechnet Im zweiten Fall muss der Benutzer zuerst die Splitrichtung und dann den Splitwert selbst bestimmen Beim Aufbau des Baums kann dieser bis hin zur Liste entarten denn die AVL Kriterien f r das Balancieren bin rer B ume sind wegen der sich abwechselnden Splitkoordinaten nicht nutzbar Beim Entfernen eines Punktes kann die nderung dem dynamischen Baum im worst case trotzdem seinen kompletten Neuaufbau erforderlich machen 7 4 2 Use Cases zum 2 d Baum Nach den berlegungen zu der darzustellenden Datenstruktur erarbeiten wir jetzt verschiedene Anwendungsf lle Sie dienen der Anforderungsermittlung und der groben Abstimmung dessen was das zuk nftige Programm bei der Darstellung von 2 d B umen leisten soll gt Siehe hierzu Kapitel 7 4 3 2 39 Elaboration Systemanalyse und Entwurf Der Benutzer soll zu den vier verschiedenen Varianten des 2 d Baumes Punkte einf gen und entfernen und eine Bereichsanfrage durch Festlegen eines Anfragerechtecks initiieren k nnen Nach allen Aktionen erfolgt das Neuzeichnen des aktuellen 2 d Baumes Einf hrende animierte Demos f r die verschiedenen Baumvarianten sollen dem Benutzer das Arbeiten mit dem 2 d Baum erleichtern Unsere berlegungen f hren zu dem allgemeinen Use Case Diagramm von Abbildung 13 Punkt im 2 d Baum einf gen Punkt aus 2 d Baum l schen
145. lt Die Zeichenmethoden werden nicht mehr in 9 Zur Erl uterung der Symbole siehe Tabelle All 119 Construction Erzeugung der paint Methode von PrioTreeCanvas aufgerufen Es wird jetzt in ein BufferedImage gezeichnet Das Image wird an PrioTreeCanvas gesandt und dort nur noch von der paint Methode am Bildschirm eingeblendet Inp t reaToTree view treeModel PrioTreeTo AndPoints Adapter PrioTreeCanvas DrawablePuioTree View Adapter LI 4 1 Point2D changeListeners i Double EwentListenerList 1 insertPoint potini 1 Set mert lis teners 1 stateChanged H gt PrioTree 4 show Show getRoot 0 gt createlmage offscreenlmage gt treeDrawing Wrze screenlmage offscreenlmage contents New D raar wenlmage E offscreenlmage E sendImagel offscreenlmage 1 H H 1 H H H H 1 1 J i H H H H H H H 1 H H H H H 1 Abbildung 67 Interaktionsdiagramm Einf gen im semidynamischen Baum Teil 2 8 4 2 Einf gen von Punkten im dynamischen Baum F r das Einf gen im dynamischen Fall muss die Methode insertPoint in der Klasse DrawablePrioTree erg nzt werden Im diesem Fall muss mit der Methode insert zun chst der neue K
146. lten Punkten 151 Bedienungsanleitung des Programms VisualGeom 10 Bedienungsanleitung des Programms VisualGeom 10 1 Systemvoraussetzungen Das Programm VisualGeom wurde von uns auf folgenden Computern entwickelt und getestet e SUN UltraSparc 144MHz mit 64MB unter Solaris 2 6 e Pentium 266MMX mit 128MB unter Linux mit der SuSE Distribution in der Version 6 1 e Pentium 233MHz mit 128MB unter Windows95 e Pentium 266MMX mit 128MB unter Windows98 Auf allen Systemen konnte auch bei der Animation ein ansprechender Bewegungsablauf erzielt werden Die Geschwindigkeit beim Test mit einem Pentium 166 mit 64MB unter Windows95 war gerade noch vertretbar Aufgrund dieser Ergebnisse erscheint uns unter Windows und Linux als Minimalanforderung ein Pentium Rechner mit mindestens 200MHz angeraten Dabei werden an freiem Speicherplatz auf der Festplatte f r die Installation von JDK2 mindestens 90MByte f r JRE2 mindestens 25MByte und f r JavaHelp mindestens 12MByte ben tigt F r das Nutzen des Programms als Applikation gelten die Rahmenbedingungen von Tabelle 3 Betriebssystem Erforderliche Software Windows 95 JDK2 oder JRE2 Windows 98 e JavaHelp oder die Datei jhall jar aus dem JavaHelp System Windows NT e abh ngig von der jeweiligen JDK2 Version ggf das compilierte Paket com sun image codec jpeg Linux JDK2 oder JRE2 JavaHelp oder die Datei jhall jar aus dem JavaHelp System
147. m Bereich der algorithmischen Geometrie einsetzbar sein Dabei sind die M glichkeiten von JDK2 bei der Gestaltung von Benutzeroberfl chen zu ber cksichtigen Des weiteren wird der Einsatz der Software als Applikation und als Applet gew nscht Eingangsvoraussetzungen der Adressaten 2 Eingangsvoraussetzungen der Adressaten Wesentlich f r die Entwicklung eines Softwareproduktes ist das Ermitteln und Ber cksichtigen der Eingangsvoraussetzungen der Benutzer Zur Evaluation w re hierf r in unserer Diplomarbeit die Erhebung und Analyse einer statistisch gesicherten Stichprobe bei den Studierenden des Kur ses Algorithmische Geometrie durchzuf hren Dies war leider nicht m glich da sich keine zeit liche bereinstimmung von Diplomarbeit und Kurs ergab Bei den weiteren Ausf hrungen greifen wir deshalb auf unsere eigenen Erfahrungen zur ck Diese haben wir zum einen beim Studium des Kurses Algorithmische Geometrie FU1840 und der Vor bereitung auf die Diplompr fung erworben Hinzu kommen die Erkenntnisse aus der Betreuung von Studenten im Rahmen unserer T tigkeit als Mentoren f r Informatik am Studienzentrum in L beck Zu Beginn des Kurses Algorithmische Geometrie sollten die Studenten ber Kenntnisse aus dem Kurs Datenstrukturen FU1663 verf gen Da der zeitliche Abstand zwischen beiden Kursen vor allem bei Teilzeitstudenten recht lang ist muss ber cksichtigt werden dass diese Kenntnisse oft nicht mehr pr sent sind
148. m haben wir den Einf gealgorithmus insertPoint zun chst in der Klasse PrioritySearchTree aufgenommen und ge testet Nach erfolgreicher Implementation haben wir die Methode auch in die Klasse Draw ablePrioTree bernommen und dort mit Zeicheninformationen und den Aufruf des Change Listeners erg nzt F r die sofortige Ausgabe des ge nderten Baumes in der Zeichenfl che muss ein Attribut im Kno ten festhalten ob ein Punkt neu eingef gt wurde Wir haben daf r als zus tzliche Zeichen information das Attribut _contentsNew in die Klasse PaintInfo aufgenommen Es wird auf true gesetzt wenn ein neuer Punkt im Knoten abgespeichert wird In der Methode paint der Baumausgabe Klasse PrioTreeCanvas wird zun chst ein Pre order Baumdurchlauf implementiert um den Baum mit den abgespeicherten Punkten zu zeichnen Unver nderte Punkte werden blau eingezeichnet Punkte mit neuer Position rot Da die Adapterklasse InputAreaToTreeAndPointsAdapter bereits implementiert wurde siehe Benutzeroberfl che in Kapitel 8 2 1 konnten wir im weiteren Verlauf der Softwareent wicklung alle Tests in grafischer Form durchf hren E Der semidynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Punkt 2 2 erreicht Abbildung 65 Einf gen von Punkten im semidynamischen Priorit tssuchbaum 118 Construction Erzeugung Abbildung 65 zeigt den semidynamis
149. m Eingabebereich bewirkt dass ein Punkt eingegeben wird Ist dieser Punkt oder seine x Koordinate bereits vorhanden und eine disjunkte Punkt menge eingestellt erfolgt die Ausgabe einer Fehlermeldung in der Statuszeile e Rechte Maustaste im Eingabebereich Das Anklicken mit der rechten Maustaste bewirkt das Entfernen dieses Punktes aus dem Ein gabebereich e Ziehen der Maus mit gedr ckter linker Maustaste im Eingabebereich Dies f hrt zum Platzieren und ffnen eines Halbstreifens 169 Bedienungsanleitung des Programms VisualGeom Die Buttons in der Buttonleiste sind abh ngig vom jeweiligen Programmmodus aktiviert oder deaktiviert Ihre Bedeutung kann der Tabelle 13 entnommen werden Button Bedeutung Anfrage l schen Die Anfragemarkierung im Baum und der Anfragehalbstreifen in der Eingabefl che werden gel scht Baum zeichnen Erst nach dem Bet tigen dieses Buttons erfolgt beim semidynamisch stati schen Priorit tssuchbaums der Aufbau des Suchbaums Wird w hrend eines Baumaufbaus erneut dieser Button bet tigt so beginnt der Baumaufbau von neuem Stopp Demo Die Demos zum Priorit tssuchbaum werden nach Abschluss der aktuellen Aktion beendet Tabelle 13 Bedeutung der drei Buttons beim Priorit tssuchbaum 10 7 1 Interpretation der Ausgaben zum Priorit tssuchbaum E ufbau des semidynamischen Priorit tssuchbaumes aus einer sortierten P Datei Bearbeiten Strukturv
150. m aus dem Ausgabebereich gel scht Der Benutzer kann die Punkte erneut l schen eingeben Wurde bereits die Punktliste in einer Datei gespeichert bleibt der Dateiname er halten auch die Einstellungen unter Optionen und Art des Zeichnens Raster Der Abstand zwischen den Rasterlinien zum Einfangen der Punkte ist einstellbar abstand Ausw hlbar sind 10 5 und 2 Bildpunkte Abstand zwischen den ganzzahligen x bzw y Ko ordinaten Liegt der Abstand bei 2 so werden keine Rasterlinien mehr angezeigt Anzahl Be der Strukturvariante semidynamisch ist die Anzahl der Bl tter im Baumskelett ein Bl tter stellbar Ausgew hlt werden k nnen 8 16 32 Bl tter oder eine beliebige Blattzahl zwischen 2 und 32 Neu Die Inhalte des Eingabe und des Ausgabefensters werden gel scht Abh ngig von der zeich ausgew hlten Strukturvariante und der Einstellung unter Optionen Art des Zeichnens nen erfolgt anhand der Punktliste der Neuaufbau des Suchbaums Dabei wird jeweils nur die aktuelle Punktliste genutzt Gel schte Punkte haben keinen Einfluss Tabelle 16 Prio Men punkte des Bearbeiten Men s 174 Bedienungsanleitung des Programms VisualGeom 10 7 4 Das Men Strukturvariante zum Priorit tssuchbaum War bereits eine der Strukturvarianten ausgew hlt und wird diese erneut oder eine andere ge w hlt so werden Punktliste Punkte und Suchbaum gel scht Welche Strukturvariante gerade ausgew hlt ist kan
151. mm In einem Klassendiagramm werden Klassen und die zwischen ihnen bestehenden Beziehungen veranschaulicht Symbol Erl uterung Eine Klasse wird im Klassendiagramm durch ein Rechteck mit eingetragenem Klassennamen veranschaulicht Des weiteren Variablen k nnen die Variablen die Konstruktoren und die Methoden in Methoden dem Symbol eingetragen werden Der ge ffnete Pfeil macht eine Benutzungsbeziehung kenntlich Mit dem geschlossenen Pfeil ist die Information verbunden dass es sich um eine Vererbungsbeziehung handelt Dabei weist der Pfeil auf die Oberklasse von der die Unterklassen erben Tabelle A10 Verwendete Klassendiagrammsymbole A 16 Hinweise zu den UML Diagrammen Interaktionsdiagramm H ufig wird in der Fachliteratur der Begriff Interaktionsdiagramm als Sammelbegriff f r Sequenz Kollaborations und Aktivit tsdiagramm verwendet Wir verwenden hier den Begriff synonym zum Begriff Sequenzdiagramm Eine Sequenz zeigt eine Reihe von Nachrichten die eine ausgew hlte Menge von Objekten in einer zeitlich begrenzten Situation austauscht wobei der zeitliche Ablauf betont wird OEST99 Seite 306 Symbol Erl uterung Die gestrichelte senkrechte Linie macht ein Objekt kenntlich Sie wird auch als Lebenslinie des betreffenden Objektes be zeichnet In das ber der Lebenslinie platzierte Rechteck wird der Name des Objektes eingetragen
152. mm soll zus tzlich die aktuellen Punkte in Eingabereihenfolge festhalten damit der Benutzer jederzeit die M glichkeit hat das Gelernte durch Wiederholungen zu festigen Gegen ber dem Istzustand erm glicht das Programm nicht nur die Eingabe von Punkten um einen Priorit tssuchbaum aufzubauen und zu zeichnen Der Benutzer erh lt den sukzessiv wachsenden Baum vom Programm und somit eine Kontroll m glichkeit ob er den Algorithmus richtig verstanden hat sich vorher die korrekten neuen Posi tionen von Knoten und Punkten berlegt hat der Baum mit dem y Heap so wie erwartet erweitert wurde Zus tzlich wird ein einf hrendes Demo bereitgestellt Dieses kann als Lernprogramm eingesetzt werden um sich den Ablauf der Algorithmen zu verdeutlichen 7 2 Architektur des Programms Dem Benutzer wird eine grafische Benutzeroberfl che zum Arbeiten mit dem Programm ange boten Die Datenstrukturen mit denen er arbeitet m ssen einerseits im Speicher verwaltet und anderer seits am Bildschirm dargestellt werden Benutzeraktionen sollen den Baumzustand ver ndern Diese nderungen erfordern jedes Mal ein Aktualisieren der Baumdarstellung 34 Elaboration Systemanalyse und Entwurf Deshalb entscheiden wir uns f r den Einsatz des bekannten MVC Konzeptes das eine saubere Trennung von Daten und deren Ansicht in der grafischen Benutzeroberfl che unterst tzt Das Modell sind die Baumvarianten View ist die grafische Oberfl
153. more in der Klasse PrioTreeGUI auf false gesetzt Dann wartet der Demothread bis der aufgerufene Einf gethread beendet und dadurch die Variable more in PrioTreeGUI auf true gesetzt ist Dies Zusammenspiel der Threads zeigt auch das Interaktionsdiagramm von Abbildung 77 Erst nach dem Ende des Demos stehen dem Benutzer wieder alle Men punkte zur Verf gung W hrend ein Demo abl uft darf kein weiteres gestartet werden Beide w rden nebenl ufig arbeiten ihre Ausgaben gleichzeitig in der Baumzeichenfl che darstellen und so f r ein heilloses Durcheinander sorgen 132 Construction Erzeugung D Die Demoklassen werden auch genutzt wenn der Benutzer in der Option animierte Darstellung ein Neuzeichnen des Baumes verlangt Nur wird hier das Demo statt mit den vorbereiteten Demowerten mit der aktuellen Punktliste abgearbeitet Das Demo ist in diesem Fall aber nur ein kontinuierliches Einf gen der aktuellen Punkte es kann jederzeit durch eine andere Benutzeraktion abgebrochen werden die Men punkte bleiben weiter pr sent 1 listlvodel Input reaPrio treeVlocel Point2DV ector Drawable PrioTree 1 PnrioTreeTo View dapter View dapter 1 stateChanged Ehamgeit addPointfpoint iD r 1 amp senilmask Image addPomt E stateC 0 bag elt
154. n e Die Punkte sind so im Priorit tssuchbaum zu platzieren dass sie m glichst dicht an der Wurzel stehen Ein Priorit tssuchbaum f r n Punkte in der Ebene kann in Zeit O nlogn aufgebaut werden Er ben tigt O n viel Speicherplatz und gestattet es eine Halbstreifenanfrage in Zeit O logn a zu beantworten FU1840 S 132 Das Hauptziel des zu entwickelnden Programms stellt die Nutzbarkeit f r die Studenten dar Ihnen soll erm glicht werden Schwierigkeiten bei der Auseinandersetzung mit den beiden geometrischen Datenstrukturen zu reduzieren und zu beseitigen Hierzu soll das Programm begleitend zur Einheit 3 des Kurses 1840 Algorithmische Geometrie die M glichkeit er ffnen mit den Datenstrukturen 2 d Baum und Priorit tssuchbaum zu experimentieren Zur besseren Lesbarkeit verwenden wir in unserer Diplomarbeit den Begriff Student im Sinne von pars pro toto Einleitung e dynamischen Fall erfolgt nach der Eingabe eines Punktes die nderung im jeweiligen Suchbaum e Im statischen Fall wird nach der Eingabe aller Punkte ein visualisierter Baumaufbau durchgef hrt e Bei Bereichsanfragen wird dargestellt welche Punkte gefunden wurden und welche Knoten hierf r im Baum angefasst werden mussten Um die Datenstrukturen sinnvoll nutzen zu k nnen soll eine einheitliche benutzerfreundliche Be dieneroberfl che erstellt werden Sie soll auch f r die unterschiedlichsten Anwendungen aus de
155. n Systemanalyse und Entwurf Use Case Punkte in den allgemeinen 2 d Baum einf gen Der Benutzer klickt mit der linken Maustaste alle Punkte im 1 Quadranten der Ebene an Dabei werden nur Punkte mit ganzzahligen Koordinatenwerten zugelassen Das mehrfache Eingeben eines Punktes ist nicht m glich Die Punkte werden in den Eingabebereich eingezeichnet Sind alle Punkte eingegeben worden veranlasst der Benutzer den Aufbau des allge meinen 2 d Baums Von Baumebene zu Baumebene wechselt beim Aufbau die Splitrichtung Es werden die jeweiligen Splitwerte berechnet Dabei wird ber cksichtigt ob Punkte vorhanden sind deren Koordinatenwerte mit dem Splitwert bereinstimmen F r Punkte die auf der Splitgeraden liegen wird ein separater 1 d Baum aufgebaut der dem entsprechenden Splitknoten zugeordnet ist Die Punkte werden in den Bl ttern eingetragen Im Ausgabebereich wird der 2 d Baum auf unterschiedliche Weise gezeichnet Der 2 d Baum und die Splitgeraden werden sofort angezeigt Der 2 d Baum und die Splitgeraden werden nach Benutzeraufforderung schritt weise Ebene f r Ebene gezeichnet Die Abl ufe beim Baumaufbau werden schrittweise in einer Animation veranschau licht Use Case Rechteckanfrage durchf hren Im Eingabebereich zieht der Benutzer mit der linken Maustaste das Rechteck f r die Anfrage auf Der 2 d Baum wird abh ngig von dem ausgew hlten x und dem ausgew hlten y Intervall durchsucht Dabei m
156. n dem wir anwendungsfallorientiert vorgehen und zur Dokumentation Diagramme in UML Nota verwenden Die Anwendungsf lle dienen zur Ermittlung der Anforderungen und zur groben Abstimmung des zuk nftigen Systemverhaltens bzgl der grafischen Benutzeroberfl che Die detaillierteren Ausf hrungen zu den Anwendungsf llen setzen wir in Aktivit tsdiagramme um und entwickeln daraus zusammen mit den Detailbeschreibungen zu den Anwendungsf llen erste grobe Klasseneinteilungen 7 1 Ist und Sollzustand Ausgangspunkt f r die Analyse ist der Auftrag dem Benutzer die Arbeit mit Papier Bleistift und Radiergummi beim Zeichnen der Baumstrukturen durch ein Programm zu erleichtern Istzustand Wie ist der Benutzer bisher vorgegangen Der Benutzer arbeitet mit Papier Bleistift und Radiergummi Im 1 Quadranten eines Koordina tensystems zeichnet er einen Punkt ein 7 den Punkt 412 Zuvor hat er im Beispiel bereits den Punkt 213 in den Priorit tssuchbaum eingef gt wie in der Abbildung 7 ersichtlich ist Abbildung 7 Beispiel f r die Baumdarstellung Teil 1 46 47 Die verwendeten UML Symbole werden im Kapitel des Anhangs erl utert Dies stellen wir stellvertretend am Beispiel des Priorit tssuchbaumes vor 31 Elaboration Systemanalyse und Entwurf Der Benutzer erg nzt im Priorit tssuchbaum die Knoten f r den neuen x Wert 4 nach den Regeln f r den normalen Blattsuchbaum Das Ergebni
157. n Splitwert der gr er als alle m glichen x Koordinaten ist damit der L schalgorithmus ohne Sonderf lle auskommt Die Eingabe eines Punktes bewirkt unmittelbar eine Erweiterung des Priorit tssuchbaums um einen Blattknoten mit dem Wert der x Koordinate des neuen Punktes Anschlie end wird der Punkt in den erweiterten Suchbaum eingef gt Wird ein Punkt aus dem Eingabebereich gel scht so erfolgt dies unmittelbar auch im Suchbaum Zus tzlich wird auch das zugeordnete Knotenpaar im Baum gel scht dynamisch balanciert Diese Variante arbeitet wie die dynamische Sollten Einf ge oder L schvorg nge zu einem unausgewogenen Priorit tssuchbaum f hren erfolgt abschlie end eine Balan cierung nach den AVL Kriterien Tabelle 18 Prio Men punkte des Men s Strukturvariante Teil 2 10 7 5 Men Optionen zum Priorit tssuchbaum Punktmenge Abh ngig von der ausgew hlten Strukturvariante besteht die M glichkeit zwischen disjunkter Punktmenge und allgemeiner Punktmenge zu wechseln Grafik in Datei Ein Abbild vom Eingabebereich oder Ausgabebereich kann als Datei im JPEG Format auf der Festplatte abgespeichert werden um es sp ter mit einem Textverarbeitungsprogramm oder mit einem Grafikprogramm weiter zu bearbeiten Dateiname und Verzeichnis sind frei w hlbar Das Suffix jpg wird automatisch gesetzt Art des Zeichnens Hier kann zwischen animiert und sofortiger Aufba
158. n Teilbaum einen gr eren x Wert Zeichenkoordinate aufweist als der Wurzelknoten reicht es nicht aus sich am x Wert zu orientieren um den richtigen Knoten zu finden Zus tzlich muss die Tiefe des Baumes y Wert ber cksichtigt werden 114 Construction Erzeugung Wird z B der Knoten mit dem Splitwert 13 in Abbildung 63 gesucht so ist dessen x Wert gr er als der x Wert des Wurzelknotens Eine normale Suche nach diesem Knoten w rde im Wurzelknoten nach rechts verzweigen Der rechte Teilbaum der Wurzel weist aber nicht die erforderliche Tiefe auf deshalb w hlt der Algorithmus zun chst den linken Nachfolger y 11 5 und erst dann dessen rechten Sohn x 5 0 weil jetzt auch der rechter Teilbaum die erforderliche Tiefe aufweist Dieser Suchalgorithmus wurde als Methode searchTree in der Klasse DrawableKdTree erg nzt Er liefert die Instanz eines 1 d Baums zur ck Ist im gefundenen Knoten ein nicht leerer I d Baum vorhanden so wird ein zus tzliches Fenster ge ffnet und der Baum darin angezeigt Dazu wurden eine zus tzliche Fensterklasse Middle TreeFrame und eine weitere Klasse MiddleCanvas f r die neue Zeichenfl che implementiert Abbildung 64 KdTreeToviewAdapter El stateChangedd _drawKdTree 7 treeModel N N d 4 9 N _kdTree 2 H d Input4reaKd Input4reaToTreeAndPointsAdapter E MiddleCanvas mouseQlicked
159. n der Titelleiste entnommen werden semidynamisch statisch Zun chst m ssen alle gew nschten Punkte im Eingabebereich angeklickt werden Dann kann mit Bet tigen des Buttons Baum zeichnen der Auf bau des Priorit tssuchbaums im Ausgabebereich veranlasst werden Nach nderungen an der Punktmenge muss erneut der Button Baum zeichnen bet tigt werden um den Aufbau des neuen Priorit tssuchbaums zu erhalten semidynamisch Nach der Auswahl dieses Men punktes wird ein Skelettbaum mit 16 Bl ttern gezeichnet Die Anzahl der Bl tter kann ber Bearbeiten Anzahl Bl tter ge ndert werden Das Anklicken eines Punktes im Eingabebereich bewirkt das Eintragen dieses Punktes im Skelett des Priorit tssuchbaums Wird versucht einen Punkt mit einer x Koordinate au erhalb des zugelassenen Intervalls auszu w hlen erfolgt in der Statuszeile die Ausgabe einer Fehlermeldung Das L schen eines Punktes f hrt ebenfalls sofort zum Entfernen des Punktes aus dem Skelettbaum Wird zu einem Baum mit einer kleineren Knotenanzahl gewechselt und existieren Punkte im Baum mit gr eren x Koordinaten so werden diese Punkte beim Wechsel gel scht Tabelle 17 Prio Men punkte des Men s Strukturvariante Teil 1 175 Bedienungsanleitung des Programms VisualGeom dynamisch Bei Auswahl dieser Strukturvariante wird zun chst der initiale im Ausgabebereich dargestellt Er enth lt eine
160. n insbesondere im Animationsbereich noch ansprechendere L sungen m glich gemacht Im einf hrenden Kapitel 6 zum Rational Unified Process werden die Entwicklungsschritte f r umfangreiche Softwareprojekte beschrieben Da es sich bei der Entstehung von VisualGeom um ein recht kleines Softwareprodukt handelt haben wir uns nur an dem Prinzip der Anwendungsfallzentrierung und der iterativen Entwicklung orientiert In ausgew hlten Beispielen haben wir die UML Dokumentationsformen des Konzeptes genutzt um Zusammenh nge zu verdeutlichen F r eine der n chsten Releases von VisualGeom erscheinen uns folgende Punkte sinnvolle Er g nzungen darzustellen e Applikation und Applet werden um die Datenstruktur Bereichssuchbaum erweitert e Die Suchb ume lassen sich kollabieren um so auch sehr umfangreiche B ume zu visualisieren e Zus tzlich zur Men leiste wird eine Symbolleiste f r h ufig benutzte Men punkte eingef gt 178 Schlu folgerungen und Ausblick e F r die Punktmengen wird ein Datenformat festgelegt das es erm glicht diese Datei unmit telbar als Textdatei in einem Textverarbeitungsprogramm in der Form 11 2 einzulesen Damit auch das externe Erstellen von Punktlisten mit einem Texteditor m glich ist wird die Methode zum Lesen der Punktliste um einen Syntaxchecker erweitert Die Druckmethode wird abh ngig von der Geometrie des jeweiligen Suchbaums optimiert Dabei erscheint es aktuell si
161. n nach dem MVC Prinzip Alle Methoden in den Modellklassen von Abbildung 48 die zu einer Ver nderung des aktuellen Modells f hren rufen die Methode fireChange auf Sie benachrichtigen die angemeldeten ChangeListener Klassen PointlistToViewAdapter und KdJTreeToViewAdapter ber den Aufruf der Methode stateChanged von der nderung Diese Methode bergibt den aktuellen Zustand des Modells zum Neuanzeigen an die View Klassen InputAreaKd und KdTreeCanvas Dort erfolgt in der Methode changed die Neuanzeige durch repaint Ein Beispiel wie ein ChangeListener bei einer Modell Klasse angemeldet wird zeigt das Interaktionsdiagramm in Abbildung 49 Der Adapter zwischen Punktvektor und Eingabebereich wird zun chst instantiiert Er wird als ChangeListener bei der Punktmenge angemeldet dort in die Liste der ChangeListener eingetragen 70 Zur Erl uterung der Symbole siehe Tabelle A10 Zum Frstellen des Diagramms wurde die Demoversion des Programms Rational Rose 98 eingesetzt 91 Construction Erzeugung Die Punktmenge als Modell sorgt danach sofort daf r dass der neue Controller die zugeh rige View Klasse ber die nderung informiert Diese zeichnet die aktuelle Punktmenge erneut in den Eingabebereich ein PrioTreeGUl input rea 4 tren points new Point2DV ector new CH changeListeners changeListeners EventListenerList 4 1 1 new _points
162. ne 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Baum zeichnen Datei ist leer Beispiel 4 Laden einer leeren Punktliste 137 Programmtest Beispiele f r das Testen funktionaler quivalenzklassen F r den Test des ausgeglichenen 2 dimensionalen Suchbaums wird eine grobe Einteilung in Eingabe und Ausgabe quivalenzklassen vorgenommen Mit Stichproben aus den jeweiligen quivalenzklassen werden die folgenden Testbeispiele ausgef hrt Wir testen das Verhalten beim Baumaufbau mit folgenden Ausgabe quivalenzklassen e leerer Baum s Beispiel 1 e Baum mit nur einem Blatt s Beispiel 2 e Baum mit einem Splitknoten und zwei Bl ttern s Beispiel 3 e Baum der in der untersten Ebene die maximal m gliche Anzahl von Bl ttern besitzt s Beispiel 5 und mehr als 2 Ebenen hat e Baum der in der untersten Ebene nicht die maximal m gliche Anzahl von Bl ttern besitzt Baum der in der untersten Ebene nur zwei Bl tter besitzt Beispiel 6 b Baum der in der untersten Ebene zwei Bl tter weniger als die maximal m gliche Anzahl besitzt Beispiel 7 c Baum dessen Besetzung in der untersten Ebene zwischen Fall a und Fall b liegt Erwartetes Ergebnis Verhalten des Programms Ein Baum ist in der untersten Ebene EN eng Datei Bearbeiten Strukturvariante Optionen Hilfe vollst ndig gef llt wenn die
163. nnvoll auf die von SUN implementierte Methode zu verzichten und eine eigene oder aus dem Internet erh ltliche Druckroutine zu verwenden e in der hier vorliegende Release das Speichern von Eingabe und Ausgabebereich nur im JPEG Format m glich ist bietet sich der Einsatz des inzwischen von SUN erh ltlichen Java Advanced Imaging Paketes JAI an Hiermit kann dann der Benutzer beim Speichern zwischen den verschiedenen Grafikformaten selbst ausw hlen e Die Animation sollte auch auf die Balancierung der B ume erweitert werden um die damit verbundenen komplexen Vorg nge besser zu visualisieren Abschlie end wollen wir die mit dieser Arbeit f r uns gewonnene Erkenntnis darlegen Die Bedeutung der Aussage von Franklin Tell me and I forget Teach me and I remember Involve me and I learn konnten wir im Rahmen unserer Arbeit selbst erleben als wir die vom anderen erstellte Datenstruktur testeten Durch das enaktive Auseinandersetzen mit der visualsierten Datenstruktur erfuhren wir ein tieferes Verst ndnis als es beim Bearbeiten von FU1840 Seiten 118 bis 125 und 130 bis 135 mit Papier und Bleistift m glich war 179 Aufteilung der Gruppenarbeit Aufteilung der Gruppenarbeit In Absprache mit dem Lehrgebiet VI und dem Pr fungsamt Mathematik und Informatik wurde die Diplomarbeit Visualisierung Geometrischer Datenstrukturen unter Ber cksichtigung soft wareergonomischer und lernpsychologischer Gesichtspunkte
164. noten im Skelettbaum eingef gt werden bevor die Methode zum Punkteinf gen pointsInSkeletonInsert aufgerufen werden kann F r die Fallunter scheidung wird in der Klasse DrawablePrioTree das Attribut treeType f r den Baumtyp erg nzt TT Zur Erl uterung der Symbole siehe Tabelle All 120 Construction Erzeugung 8 4 3 Bereichssuche im semidynamischen Baum Die Methode arraySearch setzt bei ihrem Baumdurchlauf in allen besuchten Knoten das Flag _marked auf true Die bei der Suche gefundenen Punkte werden mit _contentsNew true festgehalten Der am Ende der Methode aufgerufene ChangeListener veranlasst das Neuzeichnen des Baumes Alle markierten Pfade Knoten und Kanten und die gefundenen Punkte werden gr n eingezeichnet Abbildung 68 zeigt das Anfrageergebnis f r einen Halbstreifen mit x Intervall von 1 bis 7 und einem y Grenzwert von 4 Zu untersuchen w ren alle Knoten zwischen und auf den Pfaden zu Blatt 1 und Blatt 7 Da die Suche aber abgebrochen wird sobald ein y Wert auftritt der gr er ist als der Grenzwert 4 oder ein Knoten keinen Punkt enth lt Kommen wir zu dem Suchverlauf von Abbildung 68 Der semidynamische Priorit tssuchbaum Datei Bearbeiten Strukturvariante Optionen Hilfe Abbildung 68 Bereichsanfrage im semidynamischen Priorit tssuchbaum 121 Construction Erzeugung 8 4 4 L schen im semidynamischen und dynamischen Baum L schen im semidynamisc
165. nte in Java und verwalten diese Die Swing Pakete bieten daher eine Vielzahl von komfortablen Schnittstellenelementen zum Er zeugen von Benutzeroberfl chen die nun frei gestaltet werden k nnen Einschr nkungen durch das jeweilige Betriebssystem brauchen dabei nicht bedacht zu werden F r Men systeme stellt Swing die Klassen JMenu und JMenultem zur Verf gung Mit ihnen lassen sich Men systeme in Applikationen entwickeln die auch v llig unproblematisch in Applets benutzt werden K nnen Das Paket javax swing event stellt die f r die Realisierung des MVC Konzeptes ben tigten Listener Klassen f r die Eventsteuerung zur Verf gung Unsere Basis f r die Abbildung 45 ist ein Swing Fenster der Klasse JFrame das unter der Titel leiste das bliche Zeilenmen mit den in der Analyse beschriebenen Men punkten aufweist Dar unter schlie t sich eine Buttonleiste mit Schaltfl chen f r schnell ausf hrbare Aktionen an z B zum Anhalten animierter Darstellungen Unter der Buttonleiste bleibt der Hauptteil des Fensters f r den Eingabebereich und den Ausgabe bereich reserviert Am unteren Fensterrand wird eine Statuszeile eingef gt In dieser k nnen Benutzerhinweise und Fehlermeldungen ausgegeben werden 86 Construction Erzeugung Der Eingabe und Ausgabebereich sollen individuell ver nderbar sein und dies nicht nur abh ngig von der Gesamtfenstergr e So soll der Ausgabebereich das Betrachten von B umen unter
166. olaris 2 und Windows NT nur 7 besitzt Daran wird schon deutlich dass die Abbildung der Threads unter den verschiedenen Betriebssysteme verschiedenes Verhalten bewirkt Des weiteren lassen sich die Java Klassen unter Solaris und Linux mit insgesamt vier Kombinationen compilieren Green Thread x Native Thread x Die Bedeutung der vier Begriffe ist der nachfolgenden tabellelarischen Darstellung zu entnehmen W hrend die 2 Pre Release 1 der JDK2 Version 1 2 f r Linux unter der SuSE Distribution in der Version 6 1 das System beim Compilieren mit Green Threads aufh ngte konnten die Klassen mit der Pre Release 2 nur bei der Kombination Green JIT nicht compiliert werden Bei den drei brigen Varianten zeigte sich ebenso wenig ein unterschiedliches Laufzeitverhalten wie bei der direkten Verwendung der unter Windows compilierten Klassen A 18 Anmerkungen zur Plattformunabh ngigkeit Begriff Bedeutung Green Thread Threading wird durch die VM virtual maschine realisiert Green Threads versus Native Threads When Java 1 0 first came out on Solaris it did not use the native Solaris library libthread so to support threads Instead it used runtime thread sup port that had been written in Java for an earlier project code named Green 1 185 That thread library came to be known as green threads Es handelt sich also um ein System kooperativer Threads Native
167. om Anfragerechteck ge schnitten werden Die in den Bl ttern gespeicherten Punkte m ssen schwarz bleiben weil sie au erhalb des Anfragerechtecks liegen Alle Pfade zu den besuchten Bl ttern sollen ebenfalls gekennzeichnet sein ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Beispiel 8 Anfrage mit leerem Anfragerechteck Erwartetes Ergebnis Verhalten des Programms Befinden sich alle Punkte im An fragerechteck so m ssen alle Kno ten besucht werden Dies soll durch gr ne Einf rbung der Knoten er kennbar sein Da alle Punkte im An fragerechteck liegen m ssen auch sie gr n dargestellt werden ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen Baum zeichnen Beispiel 9 Anfrage mit allen Punkten im Anfrage rechteck 141 Programmtest Erwartetes Ergebnis Verhalten des Programms Die zu den Punkten im Anfrage rechteck geh renden Bl tter sind in gr n als angefasst zu kennzeichnen Des weiteren sollen die Punkte die ser Bl tter in gr n dargestellt wer den Alle Knoten auf den Wegen zu diesen Bl ttern m ssen ebenfalls als angefasst gekennzeichnet sein ausgeglichene 2 d Baum mit disjunkten Koordinaten Datei Bearbeiten
168. or eingestellt Sie kennzeichnen Punktmengen mit disjunkten Werten und allgemeine Punktmen gen 8 2 6 Auswahl des Grafikformates Standardm ig unterst tzt JDK nicht das Speichern von Images in einem Grafikformat F r das Speichern von Eingabebereich und den Ausgabebereichen boten sich deshalb zwei L sungen an e JAI Java advanced imaging Diese Paket ist erst im Juli 1999 von der Firma SUN f r den allgemeinen Gebrauch frei gegeben worden Es erm glicht das Laden und Speichern von Bildern in verschiedenen Gra fikformaten hat jedoch den Nachteil der Evaluation wie SUN es selbst beschreibt Damit verbietet sich die Nutzung dieses Paketes da ja unser Programm von den Endbenutzern ver wendet werden soll 77 Es befindet sich trotz Freigabe noch in der Entwicklung Die Klassen und Methodenbezeichnungen k nnen sich bei Freigabe der n chsten Release ndern 98 Construction Erzeugung das Paket com sun image codec jpeg Diese Klassen sind zwar Bestandteil des JDK 1 2 Es fehlt allerdings eine Dokumentation Desweiteren liegen sie in der Datei sre jar nicht in compilierter Form vor Mit diesen Klassen wird u a das Speichern eines Image in eine Bilddatei im JPEG Format erm glicht Wir haben uns entschieden diese Klassen aus dem Paket com sun image codec jpeg zu verwenden Dies bedeutete dass wir sie compilieren mussten und dann als jar Datei codec jar f r die Nutzung auf allen drei Betriebssys
169. orf im November 1999 Ingrid Schumacher Klaus Dieter Schumacher 181 ANHANG INHALTSVERZEICHNIS 7 0000000000000000000000000000000000090000000900009009006 1 All B CHER UND 7 5 1 A 1 2 4 AN3 414 eeh e E ee Bene 5 E SE E e e e EE 5 2 ANLEITUNG ZUM ERSTELLEN DER HILFEDATEIEN AN EINEM 7 251 M ALEGEMEINEHINWEISE uch sn een eu 7 A 2 2 IDIE D TELKDHELP EE 8 A22 EEN ENNEN SEAN EE ENEE ENEE EE 1 23 12 24 DIE DATEI KDHELPINDEX XML eh essen 13 A 3 VERWENDETE UML SYMBOLE 22200000000000ssssssnsnnnnnnnnsnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnsnnsnsnsnsssnsssssnnnnnne 15 A 4 ANMERKUNGEN ZUR PLATTFORMUNABH NGIGKEIT ENEE 18 A 5 EE 21 ABBILDUNG Al ABBILDUNG 2 ABBILDUNG ABBILDUNG 4 ABBILDUNG 5 TABELLE Al TABELLE A2 TABELLE A3 TABELLE A4 TABELLE 5 TABELLE TABELLE TABELLE 8 TABELLE A9 TABELL
170. orithmen die vorgenommenen Aktionen gut nachvollziehbar aufzeigen soll m ssen diverse Zwischenergebnisse beim Abarbeiten der Algorithmen dargestellt werden Wir haben uns entschieden diese Informationen in zus tzlichen Animations Datenstrukturen festzuhalten w hrend der normale Algorithmus abl uft 127 Construction Erzeugung Wir konnten dazu die vorhandenen Algorithmen erg nzen In unterschiedlichen Listen werden Informationen ber den alten Baum ber Suchpfade Einf gevorg nge f r Knoten oder L schpfade in der Klasse DrawablePrioTree festgehalten Die Listen werden den Animationsobjekten ber Methoden vom Baumobjekt zur Verf gung gestellt Die Zeicheninformation wird begleitend zu den rekursiven Aufrufen in den Baumalgorithmen zusammengestellt Sie enth lt jeweils Start und Zielknoteninformation und macht so f r die Animation die eingeschlagenen Wege verf gbar Jede einzelne Information umfasst Knotenkoordinaten Split und Punktwerte Die Zeichenthreads der Animation nutzen diese Informationen zum schrittweisen Aufbereiten der Abl ufe beim Einf gen L schen und der Bereichsanfrage obwohl der Baum bereits komplett in der fertigen neuen Struktur vorliegt F r das animierte Zeichnen ist der alte Baum in modifizierter Weise festzuhalten Er muss f r den Betrachter die alten Inhalte aufweisen f r die kommenden Darstellungen aber bereits mit den ak tualisierten Zeichenkoordinaten dargestellt
171. raus fallen anschlie end der rechte Sohn Der Punkt wird abschlie end in den erweiterten Baum eingef gt Abbildung 35 zeigt das Einf gen der Punkte 512 und 214 in den zun chst leeren Baum fe P eh Ausgangs Entwicklung Entwicklung neuen Punkt wie Punkt 5 2 eingef gt Situation linker Sohn rechter Sohn blich einf gen f r Pfad zum n chsten Linken Sohn entwickeln Rechten Sohn entwickeln Ansatzknoten f r x 2 f r x 5 Pfad zum Blatt mit x Wert 2 Punkt 2 4 eingef gt Abbildung 35 Beispielskizzen zum animierten Einf gen in den dynamischen Baum 73 Elaboration Systemanalyse und Entwurf Wenn der Baum beim dynamischen Aufbau das AVL Kriterium verletzt muss er balanciert 24 werden Entarteter Baum Neuen Wurzelknoten freimachen Abbildung 36 Balancieren im Priorit tssuchbaum Teil 1 Wird der Baum aus Abbildung 35 um den Punkt 115 erweitert ergibt sich zun chst der entartete Baum aus Abbildung 36 Im Wurzelknoten ist das AVL Kriterium verletzt Der Baum muss durch eine einfache Rotation nach rechts balanciert werden Vorher ist der Punkt 214 in den richtigen Teilbaum hier den linken nach dem blichen Algorithmus einzuf gen um den neuen Wurzel knoten frei zu machen Abbildung 37 verdeutlicht dass der Punkt aus dem alten Wurzelknoten 5 in den neuen Wur zelknoten 2 bernommen wird Dann kann die eigentliche Rotation durchgef hrt werden
172. rden Beim Internet Explorer 4 0 unter Windows arbeitet die Sandbox leider nicht korrekt Alle Ein und Ausgabeoperationen konnten von uns durchgef hrt werden Deshalb entschlossen wir uns im Men system von VisualGeom alle eigentlich im Appletmodus nicht verf gbaren Men punkte zu deaktivieren 9 Dies ist die Bezeichnung f r die gesch tzte Umgebung in der das Applet ohne Signieren lauff hig ist A 20 CD 5 CD Die CD enth lt neben der Diplomarbeit im Postscript und Winword97 Format noch weitere Dateien Hierzu geh ren Die Installationsanleitungen f r Java f r die Betriebssysteme Windows Linux und Solaris einschlie lich spezieller Hinweise f r die einzelnen Installationen und zus tzlichen Fonts f r Linux um so die Fehlermeldungen beim Programmstart beseitigen zu k nnen Die Installationsanleitungen f r VisualGeom f r die Betriebssysteme Windows Linux und Solaris Die Java Quellcode Dateien von VisualGeom Die class Dateien von VisualGeom einschlie lich der Hilfesysteme f r den 2 d Baum und den Priorit tssuchbaum in komprimierter Form getrennt f r die Betriebssysteme Windows Linux und Solaris Die JDK2 und JRE2 Versionen f r Windows Linux und SUN OS Die jar Datei der f r das Programm ben tigten Klassen von JavaHelp Das JavaHelp Tool Die jar Datei der Klassen zum Konvertieren in das JPEG Format und Speichern im JPEG Format Die Bedienungsanleitung aus Kapitel 10 als eigenst ndige Postscrip
173. rden als separate Thread Klassen realisiert Sie werden ber Unterpunkte des Hilfemen s aufgerufen und laufen automatisch ab bis die Threads beendet sind oder der Benutzer den Ablauf unterbricht Jedes Demo ist eine Sequenz von Punkteinf ge und Punktl schvorg ngen und einer abschlie Benden Bereichsanfrage Nachdem ein Feld mit Punkten initialisiert ist werden in einer Demoklasse die gew nschten Akti vit ten sequentiell aufgerufen Alle daf r ben tigten Methoden stehen bereits zur Verf gung Ein Demo kann vom Benutzer nur wohldefiniert d h mit dem Ende einer Transaktion abge brochen werden Stoppt der Benutzer das Demo ber die Stopp Schaltfl che wird die aktuelle Aktion noch zu Ende gef hrt Erst dann erfolgt der Abbruch des Demos Das Beenden der Demo Threads geschieht ber eine boolesche Variable _continue die beim Start des Demos auf true und durch die vom Benutzer aufgerufene stop Methode des De mos auf false gesetzt wird Diese Vorgehensweise ersetzt die deprecated Threadmethode Thread stop Diese Methode soll nicht mehr verwendet werden weil Transaktionen da durch willk rlich unterbrochen wurden Auch die Methoden suspend und resume gelten als deprecated und werden deshalb in unserem Programm nicht mehr eingesetzt Das Zusammenspiel von Threads regeln wir ebenfalls ber boolesche Variablen Ruft das Demo einen weiteren Thread z B zum Punkteinf gen auf so wird zuvor vom Demo die boolesche Variable
174. rvalls 0 1400 liegt Ist der zul ssige Bereich berschritten erfolgt eine Fehlerausgabe in der Statuszeile 106 Construction Erzeugung 8 3 2 Bereichssuche im dynamischen 2 d Baum Um das Ergebnis der Bereichssuche darstellen zu k nnen wurde es erforderlich weitere Attribute und den Zugriff darauf in der Klasse PaintInfo zu erg nzen Das Attribut _marked dient als boolesche Variable zur Information ob ein innerer Knoten oder ein Blatt im Rahmen der Anfrage angefasst wurde Mit dem Attribut _query wird kenntlich gemacht ob das betreffende Blatt einen Punkt aus dem Anfragerechteck enth lt In DrawableKdTree haben wir zwei weitere Methoden erg nzt Die Methode find Points bernimmt das x und das y Intervall des Anfragerechtecks setzt in allen besuchten Knoten _marked auf true und in allen Bl ttern deren Punkte im Anfragerechteck liegen zu s tzlich die Variable _query auf true Die sich im Anfragerechteck befindlichen Punkte wer den in einer Punktliste eingetragen und diese an die aufrufende Klasse als Anfrageergebnis zur ckgegeben Mit dem so modifizierten Baum k nnen in der Klasse KATreeCanvas die Markierungen f r die Anfrage im Baum eingezeichnet werden Die Ergebnisliste erm glicht das Markieren der gefundenen Punkte im Eingabebereich InputAreakd Mit der Methode resetMarked Query k nnen die Attribute _marked und _query auf false zur ckgesetzt werden 8 3 3 L schen von Punkten im dynamischen 2 d Ba
175. s folgende M glichkeiten e Der Algorithmus f r das sch ner Zeichnen muss auf das Zeichnen tern rer B ume angepasst werden 60 Elaboration Systemanalyse und Entwurf e Falls an einem Knoten 1 d Baum mit Punkten auf der Splitgeraden vorkommt wird dies am Knoten blau farblich kenntlich gemacht Der 1 d Baum wird auf Anforderung in einem separaten Fenster dargestellt Die Anforderung erfolgt durch Klicken auf den betreffenden Knoten Auch in diesem Fall muss von unserer Seite eine Design Entscheidung getroffen werden Zur Entscheidungsfindung wollen wir betrachten wie viele Knoten jeweils maximal pro Ebene bei einem tern ren 2 d Baum gezeichnet werden m ssten Dies kann der Tabelle 1 entnommen werden Danach wird die maximale Knotenanzahl gegen ber dem bin ren Baum schnell sehr gro Dies w rde dazu f hren dass bereits ab der Ebene 4 der Baum nicht mehr komplett im Ausgabefenster darstellbar ist Auch sehen wir die Gefahr des Verlustes der bersichtlichkeit gegeben Deshalb entscheiden wir uns daf r die jeweiligen 1 d B ume in separaten Fenstern anzeigen zu lassen Dies bedeutet allerdings dass eine Mausaktion im Ausgabebereich implementiert werden muss Diese hat zun chst auszuwerten welcher Knoten angeklickt wurde um dann den zugeordneten 1 d Baum in einem neu zu ffnenden Fenster anzuzeigen Baumh he Maximal m gliche Anzahl Maximal m gliche Anzahl
176. s Problem dar Der Benutzer kann die neuen Knoten in tieferen Ebenen immer schlechter anordnen Des fteren muss er zum Radier gummi greifen und den ganzen Baum ausradieren um ihn komplett neu mit gr eren Abst nden zu zeichnen Sollzustand Ein Programm soll dem Benutzer zuk nftig das Einf gen von Punkten in einen Priorit tssuch baum das L schen von Punkten aus dem Baum und das Durchf hren von Bereichsanfragen er m glichen Dazu werden dem Benutzer verschiedene Varianten des Priorit tssuchbaumes angeboten Ein Programm muss dem Benutzer also am Bildschirm einen Eingabebereich reduziert auf den 1 Quadranten zur Verf gung stellen in dem er mit der Maus Punkte eingeben und l schen und einen Anfragebereich einzeichnen kann In einem Ausgabebereich soll das Programm den Baum jedes Mal nach einer Aktion in der aktu ellen Form anzeigen 48 Siehe Kapitel 7 5 1 Datenstruktur 33 Elaboration Systemanalyse und Entwurf Das Programm soll dabei den beschriebenen Schwierigkeiten begegnen d h es soll die B ume stets sch n zeichnen Die Vorg nge beim Einf gen und L schen von Punkten und der Bereichs anfrage sollen f r den Benutzer nachvollziehbar dargestellt werden Eine einheitliche Benutzeroberfl che mit einem Men system und einer Statuszeile soll dem Benut zer ein leichtes Arbeiten mit dem Programm erm glichen Ein Online Hilfesystem gibt Auskunft zu den Programmm sglichkeiten Das Progra
177. s Verzeichnis VisualGeom zu wechseln In diesem befinden sich die Startdatei VisualGeom class f r den Aufruf als Applikation VisualGeom html f r den Start als Applet mit dem Programm appletviewer und VisualGeomPlugIn html f r den Start als Applet mit dem Netscape Communicator oder dem Internet Explorer wenn JRE2 einschlie lich Plug In installiert ist Dabei ist VisualGeomPlugIn html eine mit dem HTMLConverter von SUN modifizierte HTML Datei Diese wird f r die Nutzung mit den Browsern von Netscape und Microsoft ben tigt 156 Bedienungsanleitung des Programms VisualGeom e Start als Applikation aus einem Textfenster java VisualGeom e Start als Applet Browser Aufruf Netscape Communicator Den Netscape Communicator starten und dann die Datei VisualGeomPlugIn html laden Internet Explorer Den Internet Explorer starten und dann die Datei VisualGeomPlugIn html laden appletviewer Das Programm wird aus einem MSDOS oder xterm Fenster aufgerufen mittels appletviewer VisualGeom html Tabelle 5 Aufruf von VisualGeonm als Applet Zus tzlich lassen sich auch die Programme f r den 2 d Baum oder den Priorit tssuchbaum einzeln als Applikation oder Applet im Verzeichnis VisualGeom aufrufen e Start als Applikation aus einem Textfenster java kd KdApplication f r den 2 d Baum java prio PrioApplication f r den Priorit tssuchbaum e Start als Applet appletviewer KdApplet html f r den 2 d
178. s VisualGeom ge ffnet sonst das aktuell eingestellte Die ausgew hlte Strukturvariante bestimmt den Filter f r die Datei anzeige e pr Dateien mit Punkten die sich in der x Koordinate voneinander unterscheiden e pra Dateien mit allgemeiner Punktmenge Tabelle 14 Prio Men punkte des Datei Men s Teil 1 173 Bedienungsanleitung des Programms VisualGeom Speichern Die abgespeicherte Punktliste wird aktualisiert Speichern unter Der Benutzer hat die M glichkeit die Punktliste als Textdatei auf der Festplatte in einem ausw hlbaren Verzeichnis zu sichern Bei erstmaligem Speichern wird das Verzeichnis Visualgeom ge ffnet sonst das aktuell eingestellte Ver zeichnis und nach einem Dateinamen gefragt Die Dateiendung pr bzw pra wird automatisch als Suffix angeh ngt Drucken Der Inhalt von Ein und Ausgabefenster werden auf einem Drucker ausgegeben Schlie en Die Bearbeitung des Suchbaums wird beendet und die Fenster geschlossen Wurde der Priorit tssuchbaum aus dem Startmen aufgerufen so wird dieses angezeigt Andernfalls wird die Applikation oder das Applet beendet Beenden Das Arbeiten mit dem Programm VisualGeom wird beendet Tabelle 15 Prio Men punkte des Datei Men s Teil 2 10 7 3 Men Bearbeiten zum Priorit tssuchbaum Alle Alle Punkte werden aus der Punktliste entfernt die Punkte aus dem Eingabereich und der Punkte Priorit tssuchbau
179. s zeigt Abbildung 8 Abbildung 8 Beispiel f r die Baumdarstellung Teil 2 Jetzt muss der Benutzer den neuen Punkt in den y Heap einf gen Dabei kann es zum Verdr ngen von zuvor eingef gten Punkten kommen Auf dem Weg zum Blatt mit seinem x Wert 4 wird der neue Punkt in den y Heap eingef gt Der Punkt im Wurzelknoten 213 weist einen gr eren y Wert auf als der neu einzuf gende Punkt 412 Deshalb wird der neue Punkt 412 in der Wurzel abgelegt und der verdr ngte Punkt 213 auf seinem Pfad zum Blatt weiter unten eingef gt wie Abbildung 9 zeigt Abbildung 9 Beispiel f r die Baumdarstellung Teil 3 Der Benutzer radiert verdr ngte Punkte aus Das Streichen der Punkte Abbildung 9 w rde den Priorit tssuchbaum schnell un bersichtlich machen da die Punkte in einem Knoten h ufiger ver dr ngt werden k nnen 32 Elaboration Systemanalyse und Entwurf Eine Schwierigkeit ergibt sich beim Zeichnen der Baumerweiterungen Will der Benutzer im n chsten Schritt den Punkt 115 einf gen muss er den Baum zun chst um die entsprechenden Knoten erweitern Auf sch ne Weise geht dies nicht weil dann ein Knoten direkt ber einem bereits vorhandenen Knoten liegen w rde siehe Abbildung 10 Also w hlt der Benutzer geringere Knotenabst nde der Baum wird nicht mehr gleichm ig dargestellt Abbildung 10 Beispiel f r die Baumdarstellung Teil 4 W chst der Baum weiter stellt dies ein immer gr ere
180. sanfrage durch Die dabei durchlaufenen Pfade werden in der Zeichenfl che illustriert Die w hrend der Anfrage gefundenen Punkte werden im Baum und im 1 Quadranten markiert Diese berlegungen f hren zu dem Aktivit tsdiagramm von Abbildung 40 Auch in diesem Dia gramm sind Zust ndigkeiten eingezeichnet um die sp tere Klassenbildung zu unterst tzen Visualisieren der Bereichsanfrage Wie beim Einf gen von Punkten siehe Seite 71 ist zwischen Sofortmodus und Animation zu unterscheiden Sofortmodus F r die Bereichsanfrage werden in allen Varianten die im Baum besuchten Pfade und die gefun denen Punkte Ergebnis der Anfrage gr n markiert eingezeichnet Animation Die Bereichsanfrage wird f r alle Varianten identisch durchgef hrt siehe Abbildung 41 Das Besuchen der Pfade im Baum wird in Besuchsreihenfolge kontinuierlich in gr ner Farbe nachgezeichnet der Benutzer sieht den besuchten Bereich langsam wachsen Liegt im aktuellen Knoten ein Punkt aus dem Anfragebereich wird auch dieser gr n eingef rbt In der Eingabefl che wird der gefundene Punkt ebenfalls farbig hervorgehoben Abbildung 41 Beispielskizze zur Bereichsanfrage 79 Elaboration Systemanalyse und Entwurf 7 5 3 5 Demo einsetzen Es werden Demos zur semidynamischen und dynamischen Variante angeboten Startet der Benut zer eines der Demos wird ihm in einer Sequenz gezeigt wie die Algorithmen zum Einf gen und L schen von Punkten ab
181. schiedlichster Gr e erm glichen Dies wird ber einen scrollbaren Ausgabebereich erm glicht der es dem Benutzer berl sst welchen Baumausschnitt er gerade betrachten m chte Priorit tssuchbaum ojx Datei Strukturvariante Hilfe Bitte zuerst eine Strukturvariante ausw hlen Abbildung 45 Basisfenster f r die Suchb ume Der mittlere Fensterabschnitt mit dem Eingabe und dem Ausgabe Bereich wird als eigene Klasse entworfen Sie stellt einen zweigeteilten Bereich zur Verf gung in den individuell JPanel Klas sen zum Zeichnen und f r Benutzeraktionen eingebunden werden k nnen Die beiden Bereiche sind durch einen Mittelsteg voneinander getrennt Dieser Kann mit der Maus nach links und rechts verschoben werden So lassen sich individuelle Ver nderungen an der Aufteilung zwischen dem Eingabe und dem Ausgabebereich vornehmen Die Men s werden f r den 2 d Baum und den Priorit tssuchbaum als getrennte Klassen ent wickelt da sie unterschiedliche Untermen punkte enthalten Das beiden Men s gemeinsame Da teimen wird zuvor als eigene Klasse erstellt und dann in die speziellen Men s eingebunden F r die Buttonleiste wird eine gemeinsame Klasse eingesetzt Sie stellt die ben tigten Schaltfl chen zur Verf gung In der Eingabefl che weisen die Fenster f r den 2 d Baum und den Priorit tssuchbaum stets das in Abbildung 45 sichtbare Erscheinungsbild f r den 1 Quadran
182. schwarze Rechtecke und die Splitgeraden in rot eingezeichnet 56 Zur Erl uterung der Symbole siehe Tabelle A9 46 Elaboration Systemanalyse und Entwurf Visualisierung beim Einf gen eines Punktes Sofortiger Aufbau Der dynamische 2 d Baum wird unmittelbar nach der Eingabe des neuen Punktes aktualisiert Auch wird sofort die neue Splitgerade im Eingabebereich dargestellt Animiert Im Gegensatz zum Einf gen und L schen im Priorit tssuchbaum erscheint uns beim Einf gen eines Punktes in den dynamischen 2 d Baum eine Dynamisierung zur Veranschaulichung nicht erforderlich Der Benutzer wei aufgrund der Cursorposition im Eingabebereich welcher Punkt neu ist und dass der Splitbereich in dem sich bereits ein weiterer Punkt befindet nun zwischen die sem und dem neuen Punkt aufgeteilt wird Aus der Baumdarstellung ist au erdem entnehm bar wo sich das zugeordnete Blatt dieses Punktes im Baum befindet und damit wo die Ver nderung im Baum durchgef hrt wird Wir haben uns deshalb entschlossen in diesem Fall nur kenntlich zu machen welche Knoten beim Einf gen angefasst werden m ssen Diese Knoten werden durch zus tzliche rote Kreise gekennzeichnet Die beiden Punkte die von der Ver nderung im 2 d Baum betroffen sind werden au erdem rot dargestellt Mit dieser Visualisierung erh lt der Benutzer die M glichkeit die Baum nderungen aufgrund seiner Punkteingabe zu analysieren Auch erkennt er dabei welche Knoten
183. sen nun folgende Datendateien mit einem Texteditor erstellt werden Sie sind alle im Hilfeverzeichnis hier kdHelp zu speichern Die HelpSet Datei kdHelp hs Die Metadatei zur Beschreibung der Struktur des Hilfesystems kdHelpTOC xml Die Indexdatei f r den gezielten Zugriff auf einzelne Suchbegriffe kdHelpIndex xml Die Datei f r das Mapping von IDs und URLs Map jhm Die HTML Datei deren Inhalt beim Aufruf des Hilfesystem angezeigt wird kdStart htlm A 2 2 Die DateikdHelp hs Der nachfolgende Auszug aus Abbildung A2 verdeutlicht den grunds tzlichen Aufbau einer HelpSet Datei Anleitung zum Erstellen der Hilfedateien an einem Beispiel lt xml version 1 0 encoding ISO 8859 1 gt lt DOCTYPE helpset gt lt helpset version 1 0 gt lt title gt lt title gt Hilfe zum Kd Suchbaum lt title gt lt maps gt lt maps gt lt homeID gt top lt homelID gt lt mapref location Map jhm gt lt maps gt lt views gt lt view gt lt name gt TOC lt name gt lt label gt Inhaltsverzeichnis lt label gt lt type gt javax help TOCView lt type gt lt data gt kdHelpTOC xml lt data gt lt view gt lt view gt lt name gt Index lt name gt lt label gt Indexverzeichnis lt label gt lt type gt javax help IndexView lt type gt lt data gt kdHelpIndex xml lt data gt lt view gt lt helpset gt Abbildung A2 kdHelp hs In dieser Datei werd
184. shalb stets berlegungen zum Sofortmodus und zur animierten Darstellung vorgenommen 7 5 3 2 Visualisieren des Einf gevorgangs Sofortmodus e _Semidynamisch statische Variante Erst nach der Eingabe aller Punkte wird daraus der komplette Baum aufgebaut Er wird dabei ohne Farbmarkierungen gearbeitet weil keinerlei dynamische Ver nderungen aufzuzeigen sind _Semidynamische Variante Der Einf gepfad zum Blatt mit der x Koordinate des neuen Punktes wird gr n markiert Neu eingef gte Punkte werden durch rote Farbe deutlich gemacht Dies gilt auch f r verdr ngte Punkte So ist sofort f r den Benutzer ersichtlich wo der neue Punkt eingef gt wurde Sind mehrere Punkte rot l sst sich daran der Pfad verfolgen auf dem fr her eingef gte Punkte durch den neuen verdr ngt wurden e Dynamische dynamisch balancierte Variante Auch der neu eingef gte Blattknoten wird durch rote Farbe hervorgehoben F r die Punkte gilt gleiches wie im semidynamischen Fall 71 Elaboration Systemanalyse und Entwurf Animation e _Semidynamisch statische Variante Der Skelettbaum wird aufgebaut und ohne besondere Hervorhebungen angezeigt Der Ein f gepfad wird wie im Sofortmodus gr n markiert Anschlie end wandert Punkt f r Punkt in roter Farbe neuer Punkt auf dem Einf gepfad langsam an seine Position im Baum und wird dort in blauer Farbe abgelegt e _Semidynamisch Der Skelettbaum ist st ndig eingezeichnet Abbildung 34
185. sten au en liegenden Knoten dabei in einer separaten Datenstruktur festgehalten Extrempo sitionen Anschlie end werden beide Teilb ume unter Ber cksichtigung eines Minimalabstandes zwischen den Knoten so dicht wie m glich nebeneinander angeordnet Dabei werden die neuen Knotenpositionen Offsets festgehalten und zwar relativ zu ihrem Vater der ber den Wurzeln der Teilb ume mittig positioniert wird V ter stehen mittig oberhalb der S hne deshalb reicht ein Distanzwert in jedem Knoten der den horizontalen Offset zwischen dem Vaterknoten und jedem seiner S hne speichert Die Abbildung 50 zeigt die roten Offsetwerte der Knoten vor und nach dem Hinzuf gen eines neuen x Wertes in einen Blattsuchbaum Der Mindestabstand zwischen zwei Knoten einer Ebene betr gt hierbei 60 Beim Berechnen der tats chlichen x Koordinatenwerte zum Zeichnen f hrt dies zu den blauen Werten wenn f r die Wurzel der Wert 700 bergeben wird Blattknoten der tiefsten Ebene haben den Offsetwert 0 Abbildung 50 Sch nes Zeichnen mit relativem Offset und berechnetem x Wert Offset und x Koordinate k nnten mit einer Speicheradresse auskommen der Klarheit zuliebe verwendet der Algorithmus aber separate Variablen f r Offset und x Koordinate Jede Knotendatenstruktur muss also f r das Zeichnen der B ume um x und y Wert und Offset erweitert werden F r die Attribute zum Zeichnen erstellen wir die separate Klasse PaintInfo die zur jeweiligen Knotenklasse hin
186. suchbaum m s sen dann nur noch die beschriebenen Komponenten in der gew nschten Form zusammengestellt werden Abbildung 47 zeigt dies stellvertretend f r den Priorit tssuchbaum Fentertitel weitergeben an Superklasse JFrame super windowTitle auf Fensterkontext zugreifen Container getContentPane Layout Manager BorderLayout verwenden c setLayout new BorderLayout Menue einbinden _menu new PrioMenu this Buttonleiste einbinden _buttonLine new ButtonBorder this c add _buttonLine BorderLayout NORTH _buttonLine setVisible true _buttonLine disableAll Trennfeld mit Ein Ausgabebereich mittig einfuegen _middle new IOArea _inputArea _outputArea c add _middle BorderLayout CENTER Statuszeile am unteren Rand hinzuf gen _statusLine setForeground Color black _statusLine setText Bitte zuerst eine Strukturvariante ausw u00E4hlen c add _statusLine BorderLayout SOUTH Abbildung 47 Zusammenstellen der Fensterkomponenten Dabei sind _inputArea und _outputArea Instanzen der spezifischen Klassen Input AreaPrio und PrioTreeCanvas Beide Klassen sind Subklassen der Swingklasse JCompo nent und k nnen deshalb problemlos den Konstruktor der Klasse IOArea bergeben wer den public JComponent left JComponent right Die gemeinsam nutzbaren Klassen haben wir in das Paket common aufgenommen Es wird in die speziellen Pakete
187. t Dabei wurden Daten im Umfang mehrerer Megabyte erzeugt Dies konnte beim Drucken mehrerer Seiten in einer Postscriptdatei die etwa 100MB gro war festgestellt werden Damit wird auch deutlich warum die Druckmethode zwin gend den Aufruf der Garbage Collection erforderlich macht Siehe hierzu A 1 3 gt Dieser als Bug 4067405 spezifizierte Fehler soll mit dem Erscheinen der Version 1 3 beseitigt sein 76 Wir haben deshalb im Quellcode in den Dateien KATreeGUI und PrioTreeGUI in der Druckmethode f r den Ausgabebereich die korrekte Methode f r die Ermittlung der Seitenl nge implementiert und danach mit einer weiteren Anweisung die Seitenl nge auf 514 Bildpunkte reduziert Diese Anweisung braucht also nur auskommentiert zu werden 7 97 Construction Erzeugung Ein weiteres Problem beim Drucken ist dass der Ausgabebereich abh ngig von der Baumh he ber mehrere Seiten ausgedruckt werden muss Dies wird dadurch erm glicht dass das Image in mehrere Rechtecke die jeweils auf eine DIN A4 Seite passen unterteilt wird 8 25 Speichern und Laden der Punktmenge Da die zu speichernde Punktmenge nur f r den Einsatz in diesem Programm von Nutzen ist ha ben wir keinen besonderen Wert auf das Datenformat der Dateien gelegt Die Koordinatenwerte werden zeilenweise abgespeichert und eingelesen Die Endungen kd bzw kda f r die Punktlisten des 2 d Baums und pr bzw pra f r die Punktlisten des Priorit tssuchbaums sind fest v
188. t Hierbei handelt es sich um die am Anwendungsfall beteiligten Perso nen Unter dem Symbol ist die Symbolbezeichnung zu platzieren Hierbei handelt es sich um das Symbol f r den Anwendungs fall Der Name des Anwendungsfalls wird in das Symbol ein getragen Mit der Verbindungslinie wird kenntlich gemacht welche An wendungsf lle dem jeweiligen Akteur zu zuordnen sind Tabelle 8 Verwendete Use Case Diagrammsymbole Aktivit tsdiagramm Ein Aktivit tsdiagramm dient der Veranschaulichung des Flusses von einer Aktivit t zu anderen innerhalb eines Systems Damit ergibt sich A 15 Hinweise zu den UML Diagrammen Eine Aktivit t ist ein Zustand mit einer internen Aktion und einer oder mehreren ausgehenden Transaktionen die automatisch dem Abschluss der internen Aktion folgen Eine Aktivit t ist ein einzelner Schritt in einem Ablauf Eine Aktivit t kann mehrere ausgehende Transaktionen haben wenn diese durch Bedingungen unterschieden werden k nnen OEST99 Seite 295 Symbol Erl uterung Mit diesem Symbol wird eine Aktivit t visualisiert Eingetra gen wird in dieses Symbol eine Aktionsbeschreibung z B in frei formulierter Form Dieses Symbol macht kenntlich dass die Transaktion aufge teilt wird in zwei parallel laufende Teiltransaktionen Angabe der Flussrichtung Tabelle A9 Verwendete Aktivit tsdiagrammsymbole Klassendiagra
189. t Rasterabstand 10 5 2 o sofortiger Aufbau Anzahl Bl tter Grafik in Datei 8 16 32 beliebig Eingabebereich Neuzeichnen Ausgabebereich Abbildung 42 Spezielles Men system zum Priorit tssuchbaum Hilfethemen Demos semidynamisch dynamisch dynamisch balanciert 80 Elaboration Systemanalyse und Entwurf 7 6 Vorl ufige Klassenbildung Zur ersten groben Klassenbildung betrachten wir den Text der Use Cases aus den Kapiteln 7 4 2 und 7 5 2 Der Begriff Baum steht dabei stellvertretend f r den 2 d Baum oder den Priorit tssuchbaum Die Substantive Baum Eingabebereich Demo Knoten Ausgabebereich Animation Punkt Men deuten auf m gliche Klassenkandidaten hin Baum fassen wir als Menge Beh lter von Baumknoten auf deshalb entscheiden wir uns f r eine Klasse Node P mit den Attributen des Knotens und eine Klasse Tree die die Methoden bez glich der Knotenmenge enth lt z B die typischen Beh lteroperationen Einf gen L schen und Suchen eines Knotens Die Aktivit ten aus den verfeinerten Use Cases zum Aktualisieren des Priorit tssuchbaumes Punkt in Baum einf gen Punkt aus Baum l schen Bereichsanfrage im Baum m ssen offensichtlich der Klasse Tree als Methoden zugeordnet werden e F r die Klasse Punkt nutzen wir die fertige Java eigene Klasse Point2D Double e Die Klasse Eingabebereich InputArea muss Methoden enthalten f r das Zeichnen des 1 Quadranten Zeichnen der P
190. t Datei WinZip zum Entpacken von VisualGeom zip A 21 CD A 22
191. t des Lehrgebiets Praktische Informatik VI der FernUniversit t Literaturverzeichnis 5 84 VEST78 WAND93 WETH79 A 1 2 SUJT99 PART99 HOLU98 Stampe E Repetitorium Fachdidaktik Mathematik Klinkhardt Bad Heilbrunn 1994 Vester F Denken Lernen Vergessen dtv Stuttgart 1978 Wandmacher J Software Ergonomie DeGruyter Berlin 1993 Wetherell C und Shannon A Tidy Drawings of Trees In IEEE Transactions on Software Engineering Vol SE 5 No 5 September 1979 Page 514ff Online Dokumentationen B cher Tutorial http www javasoft com docs books tutorial index html Online version of The Java Tutorial http www boku ac at javaeinf Java Einf hrung von Hubert Partl BOKU Wien http www javaworld com javawolrd jw 09 1998 jw 09 threads html Allen Holub Programming Java threads in the real world Part 1 Literaturverzeichnis A 1 3 W hrend der Programmerstellung wurden von uns die Nachrichten in folgenden Gruppen als hilf reiche Hinweise f r die Programmerstellung das Vorhandensein von Bugs oder den Verweis auf spezielle Methoden genutzt e comp lang java gui e comp lang java help e comp lang java programmer e de comp lang java A 1 4 Downloads Produkt Internetquelle JDK2 f r e Windows 95 e Windows 98 Windows NT http java sun com products jdk 1 2 download windows html JR
192. t gekennzeichnet Tabelle 10 2 d Men punkte des Men s Strukturvariante Teil 2 10 6 5 Das Men Optionen zum 2 d Baum Grafik in Datei Ein Abbild vom Eingabebereich oder Ausgabebereich kann als Datei im JPEG Format auf der Festplatte abgespeichert werden um es sp ter mit einem Textverarbeitungsprogramm oder mit einem Grafikprogramm weiter zu bearbeiten Dateiname und Verzeichnis sind frei w hlbar Das Suffix jpg wird automatisch gesetzt Art des Zeichnens Zur Auswahl stehen schrittweise animiert und sofortiger Aufbau Welche dieser Optionen verf gbar ist h ngt von der jeweils ausgew hlten Strukturvariante ab Tabelle 11 2 d Men punkte des Men s Optionen 167 Bedienungsanleitung des Programms VisualGeom 10 6 6 Das Men Hilfe zum 2 d Baum Hilfethemen Angeboten wird eine Online Anleitung zur Benutzung von VisualGeom ber deren Inhalts und Indexverzeichnis kann gezielt auf eine bestimmte Hilfedatei zugegriffen werden Die Modifikation der einzelnen Hilfedateien ist problemlos m glich da es sich um HTML Dateien handelt Demos Es kann zwischen zwei Demos zum dynamischen und ausgeglichenen 2 d Baum gew hlt werden e dynamischer 2 d Baum Es werden zun chst mehrere Punkte eingef gt Dabei erfolgt parallel der Aufbau des dynamischen 2 dimensionalen Suchbaums die Ermittlung des Splitwertes und die Darstellung der Splitgeraden Dann wird e
193. t in der Ebene 1 Quadrant mit der Maus an Der Punkt wird in den Eingabebereich eingezeichnet Ein neuer Blattknoten mit der x Koordinate des Punktes wird im Baum erg nzt Der Punkt wird in den Priorit tssuchbaum eingef gt Im Ausgabebereich wird der Baum auf unterschiedliche Weise gezeichnet Der erweiterte Baum mit dem neu eingef gten Punkt wird sofort angezeigt Die Abl ufe beim Einf gen des neuen Punktes werden schrittweise in einer Animation verdeutlicht Use Case Punkt aus dem dynamischem Priorit tssuchbaum l schen Der Benutzer w hlt mit der Maus einen vorhandenen Punkt zum L schen aus Der Punkt wird in der Ebene 1 Quadrant gel scht Der Punkt wird aus dem Priorit tssuchbaum entfernt Die im y Heap entstandene L cke wird geschlossen Zus tzlich werden die Knoten Blatt und innerer Knoten mit der x Koordinate des gel schten Punktes aus dem Baum entfernt ohne dabei den y Heap zu verletzen Der aktualisierte Baum wird neu angezeigt 67 Elaboration Systemanalyse und Entwurf Use Case Halbstreifenbereichsanfrage durchf hren Im Eingabebereich zieht der Benutzer mit der Maus den Bereich f r die Anfrage Halbstreifen auf Im Baum wird das markierte x Intervall durchsucht jedoch nur solange die y Werte der gespeicherten Punkte nicht gr er als der obere y Grenzwert des Halbstreifens sind Die bei der Suche aufgefundenen Punkte und die besuchten Knoten werd
194. t werden k nnen Eine ausf hrliche Auseinandersetzung mit der Software Ergonomie w rde den Rahmen unserer Diplomarbeit sprengen Wir verweisen deshalb auf die im Literaturverzeichnis genannten B cher Wir greifen hier nur die unseres Erachtens f r unsere Softwareentwicklung besonders zu ber cksichtigenden Aspekte auf Als Konsequenz f r die Inception Phase im Rahmen der Diplomarbeit sahen wir es als erfor derlich an grunds tzlich die Aspekte e Dialogtechniken und Dialogparadigmen e _Unterst tzungssysteme e Physiologie _Wahrnehmungspsychologie und e _Kognitionspsychologie zu ber cksichtigen Hieraus haben wir die nachfolgend dargestellten Schlussfolgerungen f r die Entwicklung von VisualGeom gezogen Schlussfolgerungen f r VisualGeom zu Dialogtechniken und Dialogparadigmen e Die Informationsmenge pro Bildschirmseite werden wir auf die Punkte und die Graphen be schr nken Hierdurch wird der Umfang der Informationsmenge bersichtlich gehalten Fehler meldungen werden in der Statuszeile ausgegeben Geeignet gestaltete Hervorhebungen bei Animationen und Anfragen sollen f r den Benutzer verst ndnisf rdernd wirken 27 siehe hierzu auch HETT80 KOCH91 HAM92 WAND93 HERC94 OPPE94 28 siehe auch Kapitel 6 19 Softwareergonomische Aspekte Die Darstellung von 2 d Baum und Priorit tssuchbaum soll beim Einf gen L schen und bei der Anfrage durch farbliche Hervorhebung oder d
195. tation durchaus zu Schwierigkeiten im Zusammenhang mit dem JDK2 kommen kann F r die Entwicklung der Hilfedateien stand uns au er einem HTML Editor kein weiteres Werk zeug zur Verf gung Wir sind deshalb den Weg gegangen die mitgelieferten Beispiele zu analy sieren und hieraus f r unsere Anwendung angepasste Dateien zu erzeugen 100 Construction Erzeugung Applikation oder Applet mit JavaHelp Help hs Metadatei mit Strukturinformationen zum Inahlt und der Art der Darstellung des Hilfesystems Verweise auf alle weiteren Dateien HelpTOC xml Metadatei f r die Beschreibung des Inhaltes des Hilfesystems HelpIndex xml Indexdateif r das Indexverzeichnis Map jhm Verbindung der Topic Ids mit den URLs der HTML Dateien html Repr sentationen der Hilfedaten Abbildung 53 Grunds tzlicher Aufbau des Hilfesystems Das Hilfesystem setzt sich also aus folgenden Dateien zusammen Meta Dateien mit denen die Struktur des Online Hilfesystems festgelegt wird Hilfedateien die die Hilfeinformationen enthalten und e das JavaHelp API 101 Construction Erzeugung Der genaue Aufbau des Hilfesystems kann der Abbildung 53 entnommen werden Eine Kurzanleitung f r die Implementation der Hilfedateien findet sich im Kapitel A 2 des Anhangs Die Nutzung des Hilfesystems ist ber den Men punkt Hilfe Hilfethemen implementiert Dabei wird nach der Anwahl des Men punktes in KdTreeGUI bzw
196. te Datei Bearbeiten Strukturvariante Optionen Hilfe Punkteingabefl che Baumzeichenfl che 1 Quadrant des Koordinatensystems f r Eingabe der Punkte L schen einzelner Punkte Aufziehen eines Anfragebereiches Horizontal und vertikal scrollbar Statuszeile Hinweise Fehlermeldungen Positionsangaben zu den Mausbewegungen im 1 Quadranten als Orientierungshilfe Abbildung 12 Aufteilung des Arbeitsfensters in Bereiche Der Eingabebereich soll den 1 Quadranten des Koordinatensystems mit einem Punktraster ent halten in dem der Benutzer Rasterpunkte mit der Maus anklicken kann Der Eingabebereich muss deshalb Mausaktionen des Benutzers unterst tzen Der scrollbare Ausgabebereich soll stets den aktuellen Baumzustand anzeigen In speziellen F llen muss es m glich sein Knoten des Baumes anzuklicken um weitere Informationen zu erhalten Auch hier m ssen dann Mausaktionen unterst tzt werden Im weiteren erfolgt die Aufteilung der Arbeit in die parallele Entwicklung der spezifischen Teile zum 2 d Baum siehe Kapitel 7 4 und zum Priorit tssuchbaum siehe Kapitel 7 5 36 Elaboration Systemanalyse und Entwurf 7 4 Elaboration des 2 d Baums 7 4 1 Datenstruktur Bei dem k d Baum handelt es sich um einen k dimensionalen Blattsuchbaum der eine nat rliche Verallgemeinerung FU1840 Seite 118 des eindimensionalen Suchbaums darstellt Da sich unser Programm VisualGeom auf Punkte in
197. te so werden diese zus tzlich aufsteigend nach ihrer y Koordinate sortiert Diese Punktliste wird in der Mitte in zwei Punkt listen aufgeteilt Sie unterscheiden sich in der Anzahl der Elemente um maximal 1 Aus den x Koordinaten der beiden Punkte in der Mitte wird der Splitwert als arithmetisches Mittel berech net 38 Elaboration Systemanalyse und Entwurf Existieren Punkte die den Splitwert als x Koordinatenwert besitzen so werden diese in einem eigenen dem betreffenden inneren Knoten zugeordneten ausgeglichenen 1 d Baum eingef gt diesem Baum sind die Punkte sortiert nach ihrer y Koordinate eingef gt Aus den beiden Punktlisten werden alle Punkte die den Splitwert als x Koordinatenwert besitzen entfernt Der Vorgang erfolgt rekursiv abwechselnd f r x und y als Splitkoordinate 7 4 1 3 Der dynamische 2 d Baum Erfolgt beim Einf gen eines neuen Punktes in den 2 d Baum nicht sein kompletter Neuaufbau nach dem unter 7 4 1 1 beschriebenen Verfahren so handelt es sich um eine dynamische Variante des 2 d Baums F r die dynamische Variante m ssen Algorithmen f r das Einf gen und L schen von Punkten neu entwickelt werden da diese Variante in der Praxis nicht eingesetzt wird Sie wird hier aus didaktischen Gr nden implementiert um dem Benutzer das Experimentieren mit dem 2 d Baum zu erm glichen Dabei hat der Benutzer die Auswahl zwischen zwei F llen Im ersten Fall wird der jeweilige Splitwert vom Programm a
198. temen gepackt haben Der Ablauf beim Speichern des Eingabebereichs oder der Ausgabebereiche l sst sich in fol gende Schritte untergliedern 1 Es wird aus dem Grafikbereich ein Buffered Image erzeugt 2 Zum Buffered Image wird ein Grafikkontext eingerichtet 3 In das Buffered Image wird die Grafik gezeichnet 4 Ein BufferedOutputStream mit einem FileOutputStream lt Dateiname gt wird einge richtet 5 Es wird eine Instanz des JPEGlImage Encoders erzeugt Diese ist zum Encodieren der Image Daten als JPEG Datenflu erforderlich 6 Der Vorgang des Encodierens wird gestartet 7 Der Puffer wird in die Datei geschrieben und dann geschlossen 8 2 7 Das Java Hilfesystem Mit JavaHelp bietet die Firma Sun ein gelungen strukturiertes Hilfesystem mit dem sogar kon textbezogene Hilfen implementiert werden k nnen Dabei werden XML Dateien f r die Be schreibung des Hilfesystems und HTML Dateien f r die eigentliche Hilfeinformation verwendet Da dies mit einem selbst entworfenen Hilfesystem nicht m glich gewesen w re haben wir uns f r den Einsatz des Hilfe Toolkits der Firma Sun entschieden Es bietet es folgende Vorteile Volltextsuche Im Java Hilfesystem ist eine eigene Suchdatenbank implementiert Sie kann aus den Hilfe daten generiert werden Bestandteil ist dabei auch ein Tool f r die Indizierung der Such Da tenbank 99 Construction Erzeugung e _Kontextsensitive Hilfe Es lassen sich Hilfeinformation
199. ten mit Koordinatenkreuz und Rasterung auf 87 Construction Erzeugung W hrend der Arbeit in diesen Fenstern m ssen im Eingabebereich aber unterschiedliche zus tz liche Darstellungen vorgenommen werden Dies betrifft die Ausgabe der Splitgeraden beim 2 d Baum und die Darstellung von Anfragerechteck und Anfragehalbstreifen Es empfielt sich die Entwicklung einer gemeinsamen Oberklasse InputArea mit den Speziali sierungen InputAreakd und InputAreaPrio Der scrollbare Ausgabebereich weist weiter keine Gemeinsamkeiten auf Die Klassen KATreeCanvas und PrioTreeCanvas werden spezifisch entwickelt Einen berblick aller an der Oberfl che beteiligten Klassen zeigt Abbildung 46 FileMenu ButtonBorder FileMenu Dh ee ee E ees N fa N fa _datei P Noa atei _buttonLine d N N _buttonLine 2 _middlelO _ middle X N PrioMenu nn re 0 en rn _output rea InputAreakd Bi I _inputArea d N NA f KdTreeGuUl PrioTreeGUl Femme Abbildung 46 Klassendiagramm zur Benutzeroberfl che 68 69 Siehe hierzu auch Kapitel 8 3 und Kapitel 8 4 Zur Erl uterung der Symbole siehe Tabelle 10 Zum Erstellen des Diagramms wurde die Demoversion des Programms Rational Rose 98 eingesetzt 88 Construction Erzeugung Beim Gestalten der konkreten GUI Fenster f r den 2 d Baum und den Priorit ts
200. thoden die wir in die Balancierungs methoden integriert haben L schen dynamisch balanciert Das L schen von Punkt und Knoten erfolgt mit denselben Methoden wie im dynamischen Fall Ist der Baum nach dem L schen au er Balance so wird nicht sofort beim Aufl sen der Rekursion balanciert sondern wie schon beim Einf gen eines Punktes im dynamisch balancierten Fall wird der Balancierungsvorgang vom L schvorgang getrennt Dies ist f r das sp tere animierte Zeich nen noch wichtiger als beim Einf gen da das Balancieren nach dem L schen eines Knotens mehr fach notwendig werden kann 8 4 7 Erweiterung f r die allgemeine Punktmenge Entf llt die Einschr nkung dass nur Punkte mit disjunkten x Werten erlaubt sind k nnen beliebig viele Punkte mit gleicher x Koordinate auftreten Damit ist nicht mehr garantiert dass die Punkte auf ihrem Einf gepfad einen freien Speicherplatz vorfinden Deshalb haben wir wie in MEH94b vorgeschlagen den Blattknoten um eine Priority Queue erweitert die diese berz hligen Punkte aufnimmt Als Implementierung haben wir eine einfache sortierte Punktliste eingesetzt da in unserem Programm nicht mit gro en Punktmengen gearbeitet wird Ansonsten w re eine balancierte Baumstruktur f r die Implementierung vorzuziehen 126 Construction Erzeugung Da die Punkte bereits im disjunkten Fall als mit lexikografischer Ordnung der ersten Komponente bei gleichen y Werten eingef
201. tischer x Koordinate und drei weitere mit identischer y Koordinate vorkommen Bei Aufteilung der nach der x Koordinate sortierten Punktmenge ergibt sich x 3 als Splitwert Abbildung 85 Alle Punkte mit dieser x Koordinate werden in einem 1 d Baum gespeichert der am Knoten mit dem Splitwert x 3 iv angeh ngt ist Klicken mit der linken Zum Anzeigen der mittleren B ume auf einen Baumknoten klicken Maustaste auf dies en Knoten b ewirkt Abbildung 84 Allgemeiner 2 d Baum Teil1 das ffnen eines Fensters mit dem zugeordneten 1 d Baum Abbildung 85 162 Bedienungsanleitung des Programms VisualGeom Der allgemeine 2 d Baum iof x Datei Bearbeiten Strukturvariante Optionen Hilfe Hierdurch wird ge kennzeichnet dass am Knoten ein 1 d Baum existiert Splitgerade f r x 3 mit 4 Punkten gleicher x Koordinate zugeord netem Splitknoten mit 3 Hinweis auf einen 1 d Zum Anzeigen der mittleren B ume auf einen Baum und separatem Fenster f r die Darstel lung dieses 1 d Baums Punkte mit x 3 0 iol x SAAG mit y 10 0 JD x 10 0 5 0 9 11 0 4 6 10 3 9 3 10X3 11X3 12 4 10X5 10 Abbildung 85 Allgemeiner 2 d Baum 163 Bedienungsanleitung des Programms VisualGeom 10 6 2 Menu Datei zum 2 d Baum Neu Das Programm wird in den Startzustand zur ckgesetzt Ggf ge ffnete Dateien werden geschlossen Dateinamen gel scht und die ausgew hlte
202. tung Anfrage l schen Mit dem Bet tigen dieses Buttons werden die Anfragemarkierungen im 2 d Baum und das Anfragerechteck in der Eingabefl che gel scht Baum zeichnen Erst nach dem Bet tigen dieses Buttons erfolgt bei den statischen Varianten ausgewogener und allgemeiner 2 d Baum der Aufbau des Suchbaums Stopp Hiermit kann der animierte Aufbau eines 2 d Baums oder die Demonstration zum dynamischen bzw ausgewogenen 2 d Baum beendet werden Weiter Beim schrittweisen Aufbau des ausgewogenen oder allgemeinen 2 d Baums wird die n chste Ebene dargestellt Tabelle 6 Bedeutung der vier Buttons beim 2 d Baum 160 Bedienungsanleitung des Programms VisualGeom 10 6 1 Interpretation der Ausgaben zum 2 d Baum dynamische 2 d Baum ioj x Datei Bearbeiten Strukturvariante Optionen Hilfe 4 0 4 10 5 i 3 9 2 7 5 S 840 5 11X10 18 141 FS D Punkt 10 18 erreicht Abbildung 81 Animierter dynamischer 2 d Baum el dynamische 2 d Baum iof x Datei Bearbeiten Strukturvariante Optionen Hilfe Anfrage l schen L 4 gt 3 9 5 11 10 18 Abbildung 82 Anfrage durchf hren Beim dynamischen 2 d Baum wer den im animierten Modus alle Knoten rot gekennzeichnet die angefasst werden m ssen um den Punkt 10 18 einzuf gen Das Blatt das diesen Punkt enth lt ist ebenfalls rot gekennzeichnet
203. tzer festigt oder vertieft durch den Einsatz des Programms seine Kenntnisse ber den 2 d Baum und den Priorit tssuchbaum e Das Lehrgebiet Praktische Informatik VI nutzt das Programm bei der Erstellung von Ein sendeaufgaben e Benutzer erlebt mit den Demonstrationen eine Visualisierung der Zusammenh nge beim 2 d Baum und Priorit tssuchbaum TT Nach Abbildung 1 bernehmen wir 90 von dem was wir selbst tun in unser Langzeitged chtnis 15 Lernpsychologische Aspekte Diese verschiedenen Einsatzm glichkeiten m ssen nun von uns bei der Planung der Software be r cksichtigt werden Hieraus ergeben sich unabh ngig von der noch durchzuf hrenden Elaboration Phase folgende bei der Softwareentwicklung zu ber cksichtigende Aspekte e Die Bilder des Eingabe und des Ausgabebereiches sollen f r die weitere Bearbeitung mit einer Textverarbeitung oder einem Bildbearbeitungsprogramm in einem Standardgrafikformat wie TIFF JPEG oder GIF speicherbar sein Eingabe und Ausgabebereiche lassen sich auf einem Drucker ausgeben Dem Benutzer werden animierte Demonstrationen zur Veranschaulichung des Aufbaus von 2 d Baum und Priorit tssuchbaum zur Verf gung gestellt e Der Benutzer kann durch animiertes oder schrittweises Eintragen der Punkte in den 2 d Baum oder den Priorit tssuchbaum erfahren wie die in FU1840 Seiten 118 bis 125 und 130 bis 135 beschriebenen Algorithmen arbeiten e Durch die M
204. u gew hlt werden Welche dieser Optionen aktiviert ist h ngt von der jeweils ausgew hlten Strukturvariante ab Tabelle 19 Prio Men punkte des Men s Optionen 176 Bedienungsanleitung des Programms VisualGeom 10 7 6 Das Men Hilfe zum Priorit tssuchbaum Hilfethemen Hier kann die Online Anleitung zur Benutzung von VisualGeom aufgerufen werden ber das Inhalts und das Indexverzeichnis l sst sich dabei gezielt auf eine bestimmte Hilfedatei zugreifen Die Modifikation der einzelnen Hilfedateien ist problemlos m glich da es sich um HTML Dateien handelt Demos Es kann zwischen Demos zum semidynamischen und dynamischen Priorit ts suchbaum gew hlt werden e Semidynamischer Priorit tssuchbaum Zuerst erfolgt der Aufbau eines Baumger stes mit 16 Bl ttern In dieses werden dann nacheinander Punkte eingef gt und anschlie end einige wieder gel scht Abschlie end wird ein Anfragehalbstreifen eingezeichnet Alle bei der Bereichsanfrage besuchten Knoten und die gefundenen Punkte werden markiert Priorit tssuchbaum Gleichzeitig mit der Eingabe der Punkte wird der Priorit tssuchbaum auf gebaut Beim L schen eines Punktes wird auch das zugeordnete Knoten paar aus dem Priorit tssuchbaum entfernt Abschlie end wird ein Anfrage halbstreifen eingezeichnet Alle bei der Bereichsanfrage besuchten Knoten und die gefundenen Punkte werden markiert Dynamisch
205. u des ausgeglichenen 2 d Baums F r den schrittweisen Aufbau des 2 d Baums in der Ausgabefl che war es erforderlich die ange h ngten Punktlisten im jeweiligen Knoten zwischenzuspeichern Nur so konnten mit jedem Schritt diese Teillisten und die zugeordneten Splitgeraden ausgegeben werden Abbildung 57 Zum Speichern der Listeninformation haben wir in der Klasse DrawableKdNode zus tzlich die Attribute _leftList und_rightList aus der Klasse Pointlist implementiert Anfrage l schen Baum zeichnen Weiter Anfrage l schen Weiter 2 7X 1 14 4 8 15 2 7X 1 14 4 9 3 11 5 13 Anfrage l schen Baum zeichnen 2 7X 1 14 4 9 3 11 5 13 gt Abbildung 57 schrittweiser Aufbau des ausgeglichenen 2 d Baums 109 Construction Erzeugung Zwar ist damit die gesamte ben tigte Information in den Splitknoten abgelegt die Schwierigkeit stellte aber der Zugriff auf diese Daten dar da der Baum ebenenweise aufgebaut werden muss Hierzu wurde ein Breitendurchlauf und das Anlegen einer Hilfsdatenstruktur erforderlich In der Klasse DrawableKdTree wurde dazu eine _queue erg nzt Hierbei handelt es sich um ein Objekt aus der JDK Klasse LinkedList Am Ende der Methode insertPointlist wird die private Methode f r das Anlegen einer Queue mittels Breitendurchlauf erg nzt In diese Queue w
206. um Die grunds tzlichen berlegungen zum Algorithmus finden sich bereits im Kapitel 7 4 3 2 Deshalb soll nachfolgend nur noch kurz auf die konkrete Implementierung eingegangen werden F r das L schen haben wir in der Klasse DrawableKdTree die Methode deletePoint implementiert Da sie sowohl f r den dynamischen als auch den dynamisch interaktiven 2 d Baum genutzt werden soll haben wir eine Abfrage nach dem Baumtyp eingebaut Damit kann diese Methode f r beide Baumtypen genutzt werden Diese Methode ermittelt zun chst ob sich berhaupt ein Blatt mit der betreffenden Punkt information im Baum befindet Ist dies der Fall wird der 2 d Baum von diesem Blatt ausgehend 107 Construction Erzeugung nach oben durchsucht Dabei werden alle Bl tter und inneren Knoten gel scht und die den Bl ttern zugeordneten Punkte in einer Punktliste gespeichert bis der Splitknoten erreicht ist an dem mit dieser Punktliste der neu aufzubauende Teilbaum anzuh ngen ist Hierf r war es erforderlich zus tzlich zu den Verweisen auf die Nachfolger auch einen Verweis auf den Vorg nger des Knotens zu implementieren Dazu haben wir in der Klasse Search TreeNode das Attribut _pre erg nzt und Methoden f r den Zugriff auf dieses Attribut vorge sehen Des weiteren wurde in der Klasse DrawableKdTree die private Methode _insert Point so erweitert dass die Verweise auf die Vorg nger beim Einf gen eines neuen Blattes korrekt implementiert werden
207. unktmenge Reagieren auf MouseEvents Reagieren auf MouseMotionEvents S Zur besseren Lesbarkeit schreiben wir Klassennamen fett Variablen kursiv und Methoden in Courier 81 Elaboration Systemanalyse und Entwurf Die Klasse Ausgabebereich muss eine Methode zum Zeichnen des Baumes enthalten Wir bezeichnen sie deshalb als TreeCanvas Ein Blick auf die Verfeinerungen und Aktivit tsdiagramme in den Kapiteln 7 4 3 und 7 5 3 mit den Komponenten BAUMDARSTELLUNG PUNKTDARSTELLUNG BAUM PUNKTMENGE BEREICHSEINGABE PUNKTEINGABE DARSTELLUNG DER EINGABEFL CHE best tigt unsere bisherigen Entscheidungen f r die vorl ufige Klassenbildung Die Baumdarstellung erfolgt durch die Zeichenmethode der Klasse TreeCanvas die Punkt darstellung und die Punkt und Bereichseingabe werden durch Methoden der Klasse Input Area ausgef hrt F r die PUNKTMENGE m ssen wir weitere Klassen aufnehmen e Wir w hlen einen Point2DVector zum Speichern der Punkte in der Eingabereihenfolge als Spezialisierung der Java eigenen Klasse Vector die bereits Methoden zum Hinzuf gen und L schen von Objekten enth lt e F r den 2 d Baum ben tigen wir zus tzlich sortierbare Punktlisten Daf r sehen wir die Klasse Pointlist vor Sie st tzt sich auf der Java eigenen Klasse LinkedList ab Bei einer Orientierung an der gew hlten Programmarchitektur dem MVC Konzept sind die Klassen Tree Point2DVector und Pointlist als Modell Klassen einzuordn
208. unktmenge 1 Erwartetes Ergebnis Verhalten des Programms Das Einf gen des Punktes 6110 kann keine vorhandenen Punkte verdr ngen Da der gesamte Ein f gepfad zum Blatt 6 bereits belegt ist muss der Punkt 6110 im Blatt 6 in die Punktliste eingetragen werden Da die Punktliste noch leer ist muss der Punkt 610 als erster Eintrag der Liste erscheinen Em tamaha Stin large per s EH But aga Mech 2 1100 erreiche Beispiel 20 Einf gen im semidynamischen Baum bei allgemeiner Punktmenge 2 145 Programmtest Beim L schen im dynamischen Priorit tssuchbaum lassen sich folgende Ausgabe quivalenz klassen betrachten Die zu l schenden Knoten bilden ein getrenntes Knotenpaar Beispiel 16 Die zu l schenden Knoten bilden ein zusammenh ngendes Knotenpaar Dabei k nnen wir weiter unterteilen in den Spezialfall Wurzel und linker Sohn Beispiel 18 und sonstige F lle Beispiel 19 Erwartetes Ergebnis Verhalten des Programms Im Beispiel wird der Punkt 7113 gel scht Der Blattknoten 7 und der innere Knoten 7 bilden ein getrenntes Knotenpaar Deshalb wird der innere Knoten 7 nicht gel scht Nur sein Splitwert ist zu korrigieren nachdem der Blattknoten 7 und dessen Vorg ngerknoten 4 gel scht wurden Dabei wird das Blatt 4 linker Nachfolger des inneren Knotens 7 d
209. wa von der Firma Tek Tools allerdings nur unter Windows lauff hig 135 Programmtest Auch eine Online Befragung bei der Nutzung von VisualGeom als Applet in der virtuellen Universit t w re denkbar e Die Evaluation findet entlang von Standardaufgaben statt die als Einsendeaufgaben kon zipiert werden und unter Anwendung von VisualGeom zu l sen sind Diese Evaluation k nnen wir jedoch nicht im zeitlichen Rahmen unserer Diplomarbeit durch f hren Exemplarisch werden nachfolgend an ausgew hlten Beispielen zum 2 d Baum und zum Priorit ts suchbaum einige der von uns durchgef hrten Tests beschrieben 9 1 Tests zum 2 d Baum Beispiele f r den Test spezieller Werte Typische Beispiele hierf r sind das Verhalten der Software bei dem Versuch den leeren den aus einem Punkt bestehenden oder den aus zwei Punkten bestehenden 2 d Baum aufzubauen oder das Speichern und Laden einer leeren Punktliste durchzuf hren Diese Tests werden nachfolgend f r den ausgeglichenen 2 dimensionalen Suchbaum dargestellt Erwartetes Ergebnis Verhalten des Programms Beim Bet tigen des Buttons Baum Je 7 A Datei Bearbeiten Strukturvariante Optionen Hilfe zeichnen muss in der Statuszeile der Anfrage l schen Baum zeichnen Hinweis ausgegeben werden dass noch keine Punktliste existiert und somit kein 2 d Baum gezeichnet werden kann Noch keine Punkte ausgew hlt
210. werden wie Abbildung 72 verdeutlicht alter Baum neuer Baum Abbildung 72 Animierte Erweiterung des alten Baums Die Offsets und Zeichenkoordinaten f r den Baum m ssen also korrigiert sein bevor das Ein f gen als Film ablaufen kann Ohne die Korrektur ist kein Platz f r die neuen Blattknoten vor handen sie w rden alte Knoten berzeichnen Das bedeutet dass wir die Information f r den alten Baum aus dem neuen Baum gewinnen in die Infoliste alle Knoten bis auf die neu einge f gten bernehmen und zus tzlich f r den alten Blattknoten dessen alten Splitwert zur Verf gung stellen m ssen 128 Construction Erzeugung Die verschiedenen Informationslisten bilden die Grundlage f r die Animation Diese wird hier f r das animierte Knoteneinf gen in f nf Teilschritten dargestellt 1 Alten Baum mit aktualisierten Zeichenkoordinaten aufbauen 2 Suchpfad zum Ansatzknoten einzeichnen 3 Linken Knoten entwickeln 4 Splitwerte aktualisieren 5 Rechten Knoten entwickeln Ausgangssituation Suchpfad einzeichnen linken Sohn entwickeln rechten Sohn entwickeln Abbildung 73 Animiertes Einf gen eines neuen Knotens Das Einf gen der neuen Punkte in den Baum erfolgt beim semidynamischen und beim dynamischen Fall durch denselben Zeichenthread nachdem im dynamischen Fall zuvor das Baum ger st um den neuen Knoten erweitert wurde wie in Abbildung 73 verdeutlicht wird Wie in Kapitel
211. werkzeuge von der Firma Rational haben wir beschlossen unsere Softwareentwicklung am RUP anzu lehnen 9 Siehe auch IS9922 S 167 40 Rational Software Corporation 2800 San Tomas Expy Santa Clara ca 95051 9813 24 Objektorientierte Softwareentwicklung Was sind die wesentlichen Eigenschaften des Rational Unified Process Schwerpunkte des Rational Unified Process sind Die Orientierung an Anwendungsf llen Use Cases Die Architekturzentrierung Die iterative und inkrementelle Vorgehensweise Mit dem Rational Unified Process von Abbildung 5 erheben die drei Autoren den Anspruch den gesamten Lebenszyklus eines Softwareproduktes begleiten zu k nnen Phases Process Workflows Requirements Analysis amp Design Implementation Test Gs in Deployment de Supporting Workflows Configuration amp Change Management Project amp Process Management Iter Iter ter Iter j H g Iterations Abbildung 5 Der Rational Unified Process 41 RUP wurde von den drei Amigos Booch Jacobson und Rumbaugh entwickelt Sie sind ebenfalls an der Ent wicklung von UML BOOC99a beteiligt und inzwischen alle bei der Firma Rational besch ftigt 2 Diese Abbildung wurde von uns nach BOOC99 S 11 erstellt 25 Objektorientierte Softwareentwicklung Aus der Abbildung 5 wird ersichtlich dass beim RU
212. xistiert SERIEN des semidynamischen Priorit tssuchbaumes aus einer sorti Datei Bearbeiten Strukturvariante Optionen Hilfe Beispiel 14 semichmamisch statisch semichmamisch dynamisch dynamisch balanciert Wechsel vom semidynamisch statischen Baum zu anderen Strukturvarianten Beispiele f r das Testen funktionaler quivalenzklassen Exemplarisch folgen Beispiele zum Testen von Einf gevorg ngen L schsituationen und Bereichsanfragen bei verschiedenen Strukturvarianten Wenn m glich erfolgt dabei eine Eintei lung der Eingabe oder Ausgabedaten in quivalenzklassen mit einer Auswahl konkreter Test werte f r die Beispiele Beim Einf gen in den semidynamischen Priorit tssuchbaum mit allgemeiner Punktmenge ergeben sich zwei F lle f r das Ausgabeverhalten Der einzuf gende Punkt findet im Baum Platz Beispiel 20 Der einzuf gende Punkt muss in die Liste des zugeh rigen Blattes eingef gt werden weil der Einf gepfad im Baum bereits voll besetzt ist Beispiel 21 144 Programmtest Erwartetes Ergebnis Verhalten des Programms Beim Einf gen des Punktes 516 muss der Punkt 618 aus dem inneren Knoten 5 in den Blattknoten 6 verdr ngt werden Der Punkt 516 soll im inneren Knoten 5 des Baums seinen Platz finden Fiber Fre Beispiel 19 Einf gen semidynamischen Baum bei allgemeiner P
213. ynamischen Aufbau visualisiert werden Dabei wird der geeignete Einsatz der Farben unter Ber cksichtigung der aus der Literatur be kannten Farbcodierungen erfolgen F r 2 d Baum und Priorit tssuchbaum wollen wir die Oberfl che die Fenster und das Layout einheitlich gestaltet Dabei werden wir Men s als selektionsorientierte Interaktionsformen ausw hlen Auf den Einsatz einer Symbolleiste f r die unmittelbare Auswahl bestimmter Men punkte wird aus Zeitgr nden verzichtet Dies gilt ebenfalls f r Hotkeys oder kontextbezogene Pop up Men s Dies w ren sinnvolle Erweiterungen einer sp teren Release von VisualGeom Bei der Anordnung der Men elemente und der Reihenfolge der Men punkte erscheint es uns besonders wichtig bei den Benutzern Erwartungskonformit t zu erreichen Dies bedeutet die Sortierung der Men punkte grunds tzlich nach bei anderen Softwareprodukten bekannten Kriterien vorzunehmen Dabei werden die Auswahlmen s zustandsabh ngig sein also Men punkte abh ngig von der jeweils ausgew hlten Strukturvariante aktiviert oder deaktiviert werden Hierdurch erlebt der Benutzer welche M glichkeiten der jeweilige Modus ihm anbietet Wir wollen bei der Softwareentwicklung die Anforderungen an die Dialoggestaltung nach 1S09241 ber cksichtigen Hierzu geh ren u a e _Aufgabenangemessenheit wollen wir mit einem an die jeweilige Aufgabe angepassten Dialog erzielen Die Selbstbeschreibungsf higkeit
214. zeichenbar wird muss er um die Zeicheninformation x Koordinate y Ko ordinate und Offset erg nzt werden Dazu wird die Klasse Paint Info eingebunden und wir er halten die drawable Knotenklassen Die Baumklassen werden zu zeichenbaren Klassen indem die Methoden setup zum Ermitteln des Offsets und petrify zum Berechnen der Zei chenkoordinaten erg nzt werden Zus tzlich m ssen alle Methoden berschrieben werden die mit zus tzlicher Zeicheninformation versehen werden Z B wird die Methode f r die Bereichsanfrage ge ndert Um die durchlaufenen Wege festzuhalten wird dabei in jedem besuchten Knoten _marked das Attribut der Zeicheninformation auf t rue gesetzt So entstehen die drawable Baumklassen Auch den LeafSearchTree brauchen wir als zeichenbare Klasse um ihn im KdTree bei der allgemeinen Strukturvariante als mittleren Baum einsetzen zu k nnen Abbildung 51 zeigt die implementierte Klassenstruktur f r die zeichenbaren B ume Alle ge meinsam nutzbaren Klassen haben wir dem Paket common hinzugef gt Es enth lt jetzt insgesamt die Klassen von Tabelle 2 72 Siehe Kapitel 8 2 2 Sch ner Zeichnen 95 Construction Erzeugung ee SearchTreeNode R SS K DrawableSearchTreeNode N Steg Ja Abbildung 51 Klassendiagramm der implementierten Baumklassen DrawableLeafSearchTree ButtonBorder StartWindow DrawableSearchTr
215. zugef gt wird wenn zeichenbare Knoten ben tigt werden Das Ermitteln der relativen Offset Werte erfolgt nach jeder Ver nderung am zeichenbaren Baum durch die Methode setup die von der ver ndernden Methode aufgerufen wird Das Um rechnen der Offsets in konkrete x und y Koordinaten zum Zeichnen erfolgt durch die Methode petrify an die die x Koordinate des Wurzelknotens als Parameter bergeben wird siehe Abbildung 50 94 Construction Erzeugung 8 2 3 Baumklassen Die offensichtlichen Gemeinsamkeiten zwischen dem 2 d Baum und dem Priorit tssuchbaum ha ben uns dazu bewogen die nachfolgend beschriebene Struktur aufzustellen Da beide B ume Blattsuchb ume sind schaffen wird die Superklasse LeafSearchTree die als gemeinsame Methoden z B den Selektor f r den Wurzelknoten die An und Abmeldemethoden f r den ChangeListener und enth lt Genauso verfahren wir f r die Baumknotenklassen SearchTreeNode wird Superklasse f r KdNode und PrioNode Abbildung 51 und enth lt die blichen Knotenattribute f r den Split wert und den linken und rechten Sohn Weiter m ssen wir zwischen diesen normalen Modellklassen und den zeichenbaren Klassen unterscheiden Nur die zeichenbaren Klassen haben f r den Einsatz in unserem Programm Bedeutung Die ihnen zugrunde liegenden normalen Baumklassen sind zus tzlich f r die Nutzung der Datenstrukturen in sonstigen Anwendungen gedacht Damit ein Knoten

Visualisierung geometrischer Datenstrukturen

Contents

Download Pdf Manuals

Related Search

Related Contents