Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


24. Elementare geometrische Methoden



Übungen

  1. Geben Sie den Wert von ccw für die drei Fälle an, daß zwei der Punkte identisch sind (und der dritte von ihnen verschieden ist), und für den Fall, daß alle drei Punkte identisch sind.
  2. Geben Sie einen schnellen Algorithmus an, mit dem ohne Verwendung von Divisionen bestimmt werden kann, ob zwei Strecken parallel sind.
  3. Geben Sie einen schnellen Algorithmus an, mit dem ohne Verwendung von Divisionen bestimmt werden kann, ob vier Strecken ein Quadrat bilden.
  4. Gegeben sei ein Feld von Linien; wie würden Sie testen, ob sie ein einfaches geschlossenes Polygon bilden?
  5. Zeichnen Sie die einfachen geschlossenen Polygone, die sich ergeben, wenn A, C und D in Abbildung 24.1 in dem in diesem Kapitel beschriebenen Verfahren als »Anker« benutzt werden.
  6. Angenommen, wir benutzen in dem in diesem Kapitel beschriebenen Verfahren einen beliebigen Punkt als »Anker« zur Berechnung eines einfachen geschlossenen Polygons. Geben Sie Bedingungen an, denen ein solcher Punkt genügen muß, damit das Verfahren funktioniert.
  7. Was gibt die Funktion intersect zurück, wenn sie mit zwei Kopien der gleichen Strecke aufgerufen wird?
  8. Betrachtet inside eine Ecke des Polygons als innerhalb oder außerhalb des Polygons befindlich?
  9. Welches ist der maximale Wert, den count erreichen kann, wenn inside für ein Polygon mit N Ecken ausgeführt wird? Geben Sie ein Beispiel an, das Ihre Antwort bestätigt.
  10. Schreiben Sie ein effizientes Programm, mit dem bestimmt werden kann, ob sich ein gegebener Punkt innerhalb eines gegebenen Vierecks befindet.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]