|
Bewegung einer Leiter in 2 Dimensionen
- Visualisierung einer unteren Schranke
Applet wird gestartet...
Das Applet visualisiert ein Szenario, das aus Polygonen mit einer
Gesamtanzahl von n Knoten konstruiert wurde und für eine Leiter
fester Länge die Bewegung von einem bekanntem Startpunkt zu einem
bekannten Zielpunkt zulässt. Dabei darf die Leiter die Polygone, die in
diesem Falle Hindernisse darstellen nicht überspringen.
Beim gegebenen Szenario wird eine Mindestzahl von Ω(n2)
Bewegungen benötigt, um die Leiter von ihrer Startposition zwischen den
ersten beiden Hindernissknoten der A- und B-Reihe zu ihrer Zielposition
zwischen den letzten beiden Hindernissknoten der A- und B-Reihe zu
bewegen. Gezählt werden dabei Rotationen und Translationen als jeweils
ein Schritt.
Mögliche Mausaktionen sind:
- durch einen Linksklick auf einen der
Eckpunkte der Leiter lässt sich die Leiter um den anderen Eckpunkt
rotieren
-
durch einen Rechtsklick auf einen der
Eckpunkte der Leiter wird diese um das verschiebbare
Rotationszentrum rotiert
-
durch einen Linksklick auf das Liniensegment
zwischen den beiden Endpunkten der Leiter kann diese entlang ihrer
aktuellen Ausrichtung nach oben bzw. unten bewegt werden
-
durch einen Rechtsklick auf das Liniensegment
zwischen den beiden Endpunkten der Leiter kann diese zweidimensional
bei Beibehaltung der Orientierung verschoben werden.
- durch Drehen des Mausrades kann die Leiter
gemäß ihrer aktuellen Orientierung maximal nach oben bzw. unten
verschoben werden, gemäß der Drehrichtung des Mausrades
- durch einfaches Ziehen lässt sich das
Rotationszentrum verschieben (dies kostet natürlich keine Schritte)
|
Beispiel:
Quellen:
[1] Y. Ke, J. O'Rourke.
Moving a ladder in three dimensions:
upper and lower bounds. 1987.
siehe: ACM Portal
(Hinweis: Sie benötigen einen kostenpflichtigen Account)
|
