WEBVTT 00:00.000 --> 00:05.740 Ein Thema, das durchaus interessant ist. 00:05.920 --> 00:07.960 Es geht um die Lösung geometrischer Probleme. 00:08.120 --> 00:09.900 In vielen Anwendungen hat man damit zu tun. 00:10.240 --> 00:12.580 Erstaunlich viele Anwendungen sind es. 00:14.280 --> 00:19.800 Letztes Mal hatte ich hier diese Objekte aufgezeichnet und dabei ein 00:19.800 --> 00:24.840 paar Probleme, die aufgelistet sind, einfach kurz illustriert, 00:24.900 --> 00:25.560 visualisiert. 00:25.700 --> 00:29.960 Überwachung von Galerien oder Geschäften oder die 00:29.960 --> 00:33.720 Überschneidungsprobleme bei geometrischen Figuren, die man für 00:33.720 --> 00:39.500 Darstellungen auf jeden Fall im Griff haben muss. 00:40.880 --> 00:44.540 Ein Anwendungsbereich, den ich letztes Mal gar nicht erwähnt habe, ist 00:44.540 --> 00:50.220 der des Entwurfs von Schaltkreisen. 00:51.020 --> 00:54.460 Wenn Sie Leiterbahnen zeichnen im Full-Custom-Entwurf, dann zeichnen 00:54.460 --> 00:56.400 Sie geometrische Objekte, im Prinzip Rechtecke. 00:56.400 --> 01:01.420 Und da gibt es genaue Vorschriften, welche Überschneidungen dort 01:01.420 --> 01:04.540 vorkommen müssen, genaue Regeln, wie weit sie sich überlappen müssen, 01:04.620 --> 01:08.040 einzelne Rechtecke, die Leiterbahnenabschnitte charakterisieren. 01:08.860 --> 01:12.680 Und da braucht man also auch effiziente geometrische Algorithmen. 01:14.000 --> 01:18.000 So, was für Objekte geht es? 01:18.060 --> 01:20.400 Lassen Sie mich das kurz auf Präsentationsmodus umschalten. 01:21.360 --> 01:26.640 Es geht um verschiedenste Objekte, die dabei auftauchen können, in 01:26.640 --> 01:28.460 unterschiedlichen Dimensionen. 01:28.860 --> 01:33.220 Es geht los mit Punkten, die müssen irgendwo auf dem Bildschirm 01:33.220 --> 01:34.200 dargestellt werden. 01:35.720 --> 01:36.920 Was für Punkte? 01:37.540 --> 01:40.200 Es können Punkte auf einer Linie geraden sein, es können also 01:40.200 --> 01:42.440 unterschiedlich dimensionale Räume sein, in denen wir Punkte 01:42.440 --> 01:47.240 betrachten, allgemein halt irgendein euklidischer Raum. 01:47.240 --> 01:52.660 Und warum müssen wir hier sagen euklidischer Raum? 01:52.800 --> 01:55.300 Es geht halt darum, dass wir eine bestimmte Metrik haben, um die 01:55.300 --> 01:57.080 Abstände zwischen Punkten zu berechnen. 01:57.920 --> 02:03.520 Wir haben halt hier den Rd angenommen mit euklidischer Metrik, wobei 02:03.520 --> 02:06.360 das hier durchaus ein Problem sein kann. 02:07.060 --> 02:16.140 Reelle Zahlen als Koordinaten für Punkte zuzulassen, hat gewisse 02:16.140 --> 02:20.800 Probleme, weil nämlich reelle Zahlen relativ klein sein können, oder 02:20.800 --> 02:24.160 relativ nah oder sehr dicht nebeneinander liegen. 02:24.680 --> 02:27.720 Wir wissen, dass wir im Rechner nur eine gewisse Genauigkeit haben, 02:27.900 --> 02:30.900 aber auch unsere Berechnungen haben nur gewisse Genauigkeiten. 02:31.560 --> 02:34.840 Und wenn Sie also hier so eine Reihe Punkte haben, und ich male hier 02:34.840 --> 02:40.320 so ein paar Punkte mal auf, im Prinzip liegen die ja auf einer Linie. 02:40.320 --> 02:43.500 Ja, liegen die wirklich auf einer Linie, oder liegt einer rechts oder 02:43.500 --> 02:44.080 links davon? 02:45.440 --> 02:49.460 Es ist keineswegs klar, ob man das mit der nötigen Genauigkeit 02:49.460 --> 02:50.340 feststellen kann. 02:50.740 --> 02:51.900 Ich gehe darauf später nochmal ein. 02:52.640 --> 02:56.880 Wir machen normalerweise Annahmen, dass so etwas nicht auftaucht. 02:57.360 --> 03:01.280 Dass die Punkte gutartig sind, dass sie weit genug auseinanderliegen, 03:01.320 --> 03:05.900 sodass man eindeutig etwas darüber sagen kann, zum Beispiel, dass 03:05.900 --> 03:09.860 dieser Punkt hier, wenn wir da eine Gerade durch die anderen beiden 03:09.860 --> 03:13.980 legen, dass der rechts von dieser Geraden liegt. 03:14.820 --> 03:18.880 Oder wenn wir so eine Gerade durchziehen, ist es halt klar, dass der 03:18.880 --> 03:20.700 dritte Punkt links davon liegt. 03:21.460 --> 03:23.020 Solche Aussagen muss man manchmal machen. 03:23.560 --> 03:27.300 Und dafür ist natürlich wichtig, dass man solche Aussagen auch 03:27.300 --> 03:29.640 eindeutig, auch korrekt macht. 03:29.640 --> 03:33.780 Die Grundannahmen werden sein, dass die Punkte so geartet sind, dass 03:33.780 --> 03:35.300 keine großen Probleme auftauchen. 03:35.980 --> 03:38.200 Man muss sich aber auch um die anderen Probleme kümmern, und darauf 03:38.200 --> 03:40.440 gehe ich auch noch etwas ein. 03:43.200 --> 03:45.760 Nächstes Objekt, das man sich anschaut, sind Geraden. 03:45.840 --> 03:47.560 Ich hätte gerade hier Geraden reingezeichnet. 03:48.300 --> 03:52.220 Eine Gerade ist allgemein eine eindimensionale Teilmenge des 03:52.220 --> 03:56.680 eukalyptischen Raumes, gegeben durch einen Punkt und eine Richtung. 03:57.640 --> 03:59.560 Das war ich, ein Punkt und eine Richtung. 03:59.780 --> 04:04.000 Oder ich brauche zwei Punkte, dadurch habe ich auch eine Gerade 04:04.000 --> 04:05.120 gegeben. 04:05.800 --> 04:07.340 Dadurch kann ich eine Geradengleichung aufstellen. 04:07.700 --> 04:10.640 Das wissen wir alle aus der Schulmathematik oder auch aus sonstigen 04:10.640 --> 04:11.980 mathematischen Veranstaltungen. 04:13.000 --> 04:17.860 Dann gibt es Linien oder Streckenkanten, irgendwelche Abschnitte auf 04:17.860 --> 04:18.600 einer Geraden. 04:19.120 --> 04:22.420 Da habe ich auf jeden Fall zwei Punkte, nämlich einen Anfangspunkt und 04:22.420 --> 04:22.980 einen Endpunkt. 04:22.980 --> 04:26.760 Dann kann ich über die Länge seiner Strecke reden und kann auch 04:26.760 --> 04:33.520 darüber reden, wenn ich jetzt zwei Strecken habe, die würden sich 04:33.520 --> 04:35.980 nicht überschneiden, die würden sich überschneiden. 04:36.840 --> 04:37.980 Solche Punkte kann man anschauen. 04:41.560 --> 04:46.260 Wenn ich zwei Geraden betrachte, da habe ich Punkt und Richtung, da 04:46.260 --> 04:48.360 kann ich immer irgendeinen Schnittpunkt feststellen, es sei denn, sie 04:48.360 --> 04:48.920 sind parallel. 04:50.400 --> 04:54.480 Bei Linien muss ich, um zu entscheiden, ob sie einen Schnittpunkt 04:54.480 --> 04:59.540 haben, auch die genauen Abschnitte angucken, auf denen tatsächlich die 04:59.540 --> 05:05.260 Punkte liegen, damit in so einer Situation dieses Linienstück hier, 05:05.500 --> 05:08.460 wenn wir die Gerade betrachten, die dadurch definiert ist, würde es 05:08.460 --> 05:12.060 natürlich einen Schnittpunkt geben zu der anderen Linie, aber so 05:12.060 --> 05:12.700 natürlich nicht. 05:13.260 --> 05:15.460 Dafür braucht man Dinge wie, dass z.B. 05:15.600 --> 05:17.600 dieser Punkt rechts von der anderen Linie liegt. 05:17.600 --> 05:19.560 Also hier ein Beendpunkt. 05:21.580 --> 05:22.680 So, Hyper-Ebenen. 05:23.500 --> 05:24.760 Das ist eigentlich das Gegenteil. 05:25.080 --> 05:28.840 Keine eindimensionale Teilmenge, sondern eine d-1-dimensionale 05:28.840 --> 05:32.660 Teilmenge eines d-dimensionalen onklidischen Raumes. 05:34.840 --> 05:38.660 Im dreidimensionalen wäre das halt eine ganz normale Ebene, im 05:38.660 --> 05:40.840 zweidimensionalen ist eine Hyper-Ebene eine Gerade. 05:43.060 --> 05:45.980 Und, ganz wichtig, Polygone. 05:48.380 --> 05:53.300 Streckenzüge, also geschlossene Kantenzüge im E2. 05:53.980 --> 05:55.780 Normalerweise betrachten wir nur den E2. 05:57.400 --> 06:02.440 Wir haben also eine Folge von Eckpunkten und verbinden diese Punkte 06:02.440 --> 06:03.980 durch Liniensegmente. 06:06.440 --> 06:13.440 Und das sind dann im E2 auch Polyeder oder Polytopen. 06:13.840 --> 06:19.680 Oder man kann natürlich anders, wenn man nicht den E2 betrachtet, im 06:19.680 --> 06:20.660 E2 sind das Polygone. 06:21.000 --> 06:24.520 Wenn man höhere Dimensionen betrachtet, dann haben wir Polyeder oder 06:24.520 --> 06:24.980 Polytope. 06:27.400 --> 06:32.680 Auch dort kann man eine ganze Reihe, eine Vielfalt von geometrischen 06:32.680 --> 06:33.780 Problemen untersuchen. 06:33.780 --> 06:36.300 Das machen wir aber nicht, wir beschränken uns hier auf den 06:36.300 --> 06:38.380 zweidimensionalen Fall, der ist schon schwierig genug. 06:40.460 --> 06:43.640 Und man sieht, dass es durchaus sehr unterschiedliche Arten von 06:43.640 --> 06:44.740 Polygonen geben kann. 06:45.240 --> 06:52.740 Wenn Sie sich dieses Polygone hier anschauen, ein Quadrat, oder dieses 06:52.740 --> 06:57.200 hier oben, die unterscheiden sich dadurch, dass das eine konvex ist, 06:57.300 --> 06:58.940 das andere konkav. 06:59.840 --> 07:04.520 Bei dem oberen sehen wir halt, dass wir Punkte haben, die wir 07:04.520 --> 07:09.540 miteinander verbinden, die die Verbindungslinie nicht vollständig im 07:09.540 --> 07:09.900 Inneren. 07:12.140 --> 07:16.300 Dann gibt es auch so etwas wie hier unten, das ist noch anders, da 07:16.300 --> 07:20.120 kann ich nicht so ohne weiteres sagen, was ist eigentlich das Innere 07:20.120 --> 07:21.680 des Polygons, was ist das Äußere. 07:22.520 --> 07:25.440 Bei den anderen drei Beispielen habe ich eindeutig einen inneren 07:25.440 --> 07:26.780 Bereich und einen äußeren Bereich. 07:26.780 --> 07:33.640 Bei dem verdrehten Viereck, dort rechts unten, kann ich nicht sagen, 07:33.760 --> 07:35.760 was ist jetzt Innen und was ist Außen. 07:38.260 --> 07:40.760 Also solche Fragen sind aber häufig wichtig. 07:41.260 --> 07:45.660 Ich weiß, ob ein Punkt innerhalb eines Bereiches liegt oder außerhalb 07:45.660 --> 07:46.760 eines Bereiches. 07:47.620 --> 07:50.760 Und da müsste ich im Prinzip einen künstlichen weiteren Punkt hier 07:50.760 --> 07:51.780 dazunehmen. 07:51.780 --> 07:56.180 Und dann hätte ich natürlich zwei innere Bereiche und einen äußeren 07:56.180 --> 07:56.660 Bereich. 07:57.020 --> 07:58.940 Aber das wäre dann ein anderes Polygon. 08:02.300 --> 08:07.220 Ansonsten haben wir im Polygon immer nur eine Kante, die reinläuft, 08:07.320 --> 08:08.280 eine die rausläuft. 08:08.380 --> 08:11.060 Was ich gerade reingemalt habe, diesen roten Punkt, das wäre ein 08:11.060 --> 08:16.480 Punkt, bei dem zwei Kanten reinlaufen, also vier Kanten im Prinzip mit 08:16.480 --> 08:17.280 dem verbunden sind. 08:18.020 --> 08:20.600 Etwas, was wir normalerweise in Polygonen gar nicht betrachten. 08:21.520 --> 08:26.740 Sowas würden wir eigentlich als zwei getrennte Polygone auffassen. 08:30.110 --> 08:32.570 So, wenn wir jetzt solche Objekte haben, wie modellieren wir die? 08:34.470 --> 08:37.470 Das ist, zunächst schaut man sich an, was sind eigentlich hier die 08:37.470 --> 08:39.790 Problemgrößen, das ist relativ eindeutig. 08:40.230 --> 08:43.050 Wenn wir Mengen von Punkten haben, die Anzahl der Punkte, bei Geraden 08:43.050 --> 08:45.630 haben wir die Anzahl der Geraden zu betrachten, bei Polygonen die 08:45.630 --> 08:46.790 Anzahl der Eckpunkte. 08:49.730 --> 08:54.710 Das ist eigentlich offensichtlich, dass das die Problemgröße ist. 08:56.090 --> 09:02.430 Datenstrukturen, auch relativ einfach, obwohl so einfach ist es gar 09:02.430 --> 09:02.670 nicht. 09:03.070 --> 09:06.410 Es hängt davon ab, was für Fragen man beantworten will, dafür muss man 09:06.410 --> 09:07.870 entsprechende Datenstrukturen machen. 09:08.510 --> 09:11.410 Also, man macht häufig Suchanfragen, dafür brauchen wir Suchbäume. 09:11.610 --> 09:13.590 Wir wissen, wie wir Suchbäume aufbauen. 09:14.390 --> 09:18.450 Für einige Dinge ist es sinnvoll, ein Array zu verwenden. 09:18.670 --> 09:22.030 Wenn ich also eine feste Menge von Punkten habe und keine Dynamik in 09:22.030 --> 09:28.990 der Probleminstanz, dann kann ich auch eine andere Struktur nehmen. 09:30.290 --> 09:34.310 Sobald ich Dynamik habe mit Einfügen und Löschen, sind immer Suchbäume 09:34.310 --> 09:36.430 wichtig, wie wir festgestellt haben. 09:36.430 --> 09:42.790 Ich kann Folgen von Punkten betrachten, bei den Polygonen muss ich ja 09:42.790 --> 09:43.610 Folgen betrachten. 09:44.130 --> 09:47.830 Das heißt, da werde ich entweder ein Array verwenden oder eine lineare 09:47.830 --> 09:50.290 Liste oder ein Vektor oder irgendetwas. 09:51.470 --> 09:55.650 Und dann gibt es einige Probleme, bei denen man 09:55.650 --> 09:57.230 Prioritätswarteschlangen braucht. 09:59.110 --> 10:01.770 Und dann wird man sowas wie ein Heap verwenden. 10:03.330 --> 10:06.110 Also unterschiedliche Strukturen sind hier sinnvoll. 10:07.010 --> 10:10.310 Bei den Suchbäumen gibt es übrigens bei geometrischen Problemen 10:10.310 --> 10:15.230 einige, die man speziell für geometrische Probleme entworfen hat, die 10:15.230 --> 10:17.390 noch besondere Eigenschaften haben. 10:20.150 --> 10:22.190 Aufwand ist das Übliche. 10:22.510 --> 10:25.890 Wir schauen uns an den Zeitaufwand, arithmetisch-logische Operationen. 10:27.370 --> 10:32.050 Hier kommen auch Vergleiche vor, also auch die logischen Operationen 10:32.050 --> 10:32.490 sind ja drin. 10:32.610 --> 10:34.570 Wir können uns also nicht auf die arithmetischen Operationen 10:34.570 --> 10:36.650 beschränken oder auf Vergleiche. 10:36.710 --> 10:39.890 Wie bei den talgebraschen Problemen hatten wir nur die arithmetischen 10:39.890 --> 10:40.630 Operationen. 10:40.650 --> 10:44.170 Bei den sortierenden Suchverfahren hatten wir die 10:44.170 --> 10:45.710 Vergleichsoperationen genommen. 10:45.830 --> 10:47.990 Hier müssen wir beides berücksichtigen. 10:49.010 --> 10:51.270 Platzaufwand ist auch klar, dass das eine Rolle spielt. 10:51.270 --> 10:54.710 Was ich jetzt nicht betrachte, sind parallele Varianten von solchen 10:54.710 --> 10:55.350 Verfahren. 10:55.990 --> 11:00.630 Kann man aber alles auch parallelisieren, parallel betrachten, werde 11:00.630 --> 11:02.310 ich aber in diesem Abschnitt nicht weiter vertiefen. 11:02.430 --> 11:06.290 Hier geht es mir eigentlich mehr um ein paar Prinzipien des 11:06.290 --> 11:09.430 Algorithmenentwurfs, die wir jetzt noch, oder algorithmische 11:09.430 --> 11:13.750 Werkzeuge, die hierfür entwickelt wurden, ganz interessant sind. 11:15.010 --> 11:17.750 Wenn ich den Aufwand abschätze, also normalerweise haben wir immer den 11:17.750 --> 11:20.450 Aufwand abgeschätzt, um ein Problem zu bearbeiten. 11:20.450 --> 11:23.670 Bei der Auswertung eines Polynoms oder Matrixmultiplikationen oder 11:23.670 --> 11:24.310 Ähnliches. 11:24.670 --> 11:31.990 Bei der Polynomauswertung hatten wir uns auch einmal überlegt, dass 11:31.990 --> 11:35.850 man, sofern man mehrfach ein Polynom auswerten muss, auch einen 11:35.850 --> 11:38.370 gewissen Aufwand reinstecken kann in die Vorbereitung. 11:39.450 --> 11:42.150 Und das ist das, was man hier auch macht, das werden wir gleich sehen, 11:42.730 --> 11:46.890 dass es manchmal sehr sinnvoll ist, wenn ich weiß, ich werde bezüglich 11:46.890 --> 11:50.850 einer gewissen geometrischen Problemstellung viele gleichartige 11:50.850 --> 11:56.050 Anfragen haben, dann macht es Sinn, sich entsprechende Datenstrukturen 11:56.050 --> 12:00.950 zu konstruieren, durch die dann diese vielfachen Anfragen sehr 12:00.950 --> 12:02.070 effizient ausführbar sind. 12:02.410 --> 12:05.850 Der Zeitaufwand für die Vorbereitung kann dann vernachlässigt werden. 12:07.690 --> 12:13.390 Und jetzt zeige ich also einfach ein paar typische Probleme, die man 12:13.390 --> 12:17.050 in der algorithmischen Geometrie betrachtet. 12:18.070 --> 12:22.610 Und das erste Problem, das ich hier anspreche, ist, ich habe eine 12:22.610 --> 12:23.770 Menge von Punkten gegeben. 12:25.510 --> 12:30.010 Und jetzt, so irgendwelche Punkte, was immer das ist, ist völlig egal. 12:30.710 --> 12:34.690 Und ein achsenparalleles Rechteck, das irgendwie dort rüber geschoben 12:34.690 --> 12:34.990 wird. 12:35.910 --> 12:39.690 Sie gehen praktisch mit einem Fenster über Ihren Bildschirm. 12:40.790 --> 12:44.110 Jetzt wollen Sie wissen, wie viele Punkte der Menge innerhalb des 12:44.110 --> 12:44.790 Rechtecks liegt. 12:44.790 --> 12:50.090 Also, Sie wollen wissen, wie viele Punkte der gegebenen Menge habe ich 12:50.090 --> 12:51.190 mit meinem... 12:51.190 --> 12:54.270 oder auch welche Punkte, das sind zwei unterschiedliche Dinge, welche 12:54.270 --> 12:58.670 Punkte oder nur wie viele, liegen innerhalb des Rechtecks. 13:00.170 --> 13:01.730 Das kann man natürlich ganz einfach feststellen. 13:02.750 --> 13:06.110 Ein bisschen Überlegung, geometrische Überlegung. 13:06.670 --> 13:11.110 Ich muss ja nur feststellen, ob er im Rechteck liegt oder nicht. 13:11.710 --> 13:12.890 Das ist ganz einfach zu machen. 13:12.890 --> 13:16.410 Also, für jeden Punkt stelle ich fest, wenn ich also hier den Punkt 13:16.410 --> 13:18.450 betrachte, wie sind dessen Koordinaten. 13:19.550 --> 13:23.870 Ich kann über den Vergleich der Koordinaten mit, ja, mit den Ecken... 13:23.870 --> 13:27.290 Ich gucke mir an, ist der... 13:27.290 --> 13:31.870 Ich muss halt vergleichen mit den Viereckpunkten, mit den Koordinaten, 13:32.310 --> 13:33.290 ob der da drin liegt. 13:33.850 --> 13:36.630 Punkte hier liegen offensichtlich eben drin, weil die Koordinaten 13:36.630 --> 13:41.110 größer sind als die Koordinaten von den beiden unteren Punkten. 13:41.770 --> 13:48.030 Und kleiner als die x-Koordinate von den rechten Punkten hier und 13:48.030 --> 13:52.670 größer bei den x-Koordinaten als die beiden linken Punkte. 13:52.790 --> 13:56.550 Also x-Koordinaten zwischen den beiden Werten x und x'. 13:56.550 --> 13:59.390 y-Koordinaten zwischen y und y'. 13:59.390 --> 14:01.210 Wenn das der Fall ist, liegt der Punkt drin. 14:01.790 --> 14:06.310 Wenn er draußen ist, liegt er halt... oder wenn die Koordinaten 14:06.310 --> 14:07.710 außerhalb sind, liegt er halt draußen. 14:12.690 --> 14:14.590 Und damit kann man das einfach überprüfen. 14:14.930 --> 14:18.890 Für n Punkte muss man das halt überprüfen. 14:19.790 --> 14:22.150 Also man muss für jeden Punkt das überprüfen, ob er drin liegt oder 14:22.150 --> 14:22.550 nicht. 14:23.530 --> 14:26.850 Da habe ich offensichtlich eine Zeit von O von n. 14:27.470 --> 14:29.510 Also wenn ich... ich weiß ja... 14:29.510 --> 14:32.990 Ich muss also für ein beliebiges Rechteck... 14:32.990 --> 14:35.270 will ich also wissen, wie viele Punkte sind dort drin. 14:35.270 --> 14:40.490 Und der Aufwand dafür ist offensichtlich linear in der Anzahl der 14:40.490 --> 14:40.750 Punkte. 14:42.070 --> 14:44.110 Wie will man das auch kürzer machen? 14:44.250 --> 14:45.770 Es könnte sein, dass alle Punkte drin sind. 14:46.550 --> 14:49.630 Wenn ich also wissen will, wie viele das sind, muss ich alle mal 14:49.630 --> 14:50.090 durchgehen. 14:52.310 --> 14:56.530 Und also dieser Zeitaufwand hier, Platzaufwand, ist offensichtlich... 14:56.530 --> 14:57.970 Wir haben nichts in die Vorbereitung gesteckt. 14:58.470 --> 15:01.770 Und jetzt ist die Überlegung, kann ich sinnvoll eine Vorbereitung 15:01.770 --> 15:06.770 machen, wenn ich weiß, ich habe eine bestimmte Punktmenge gegeben und 15:06.770 --> 15:10.350 die Problemstellung, die jetzt kommt, ist, dass ich ein beliebiges 15:10.350 --> 15:14.070 Rechteck da reinlege und ich will das für viele solcher Rechtecke 15:14.070 --> 15:16.390 überprüfen können, wie viele Punkte da drin liegen. 15:19.010 --> 15:26.850 Und diese Überlegung oder die Idee, wie man das machen kann, geht über 15:26.850 --> 15:27.830 folgenden Ansatz. 15:28.690 --> 15:33.270 Wenn ich wissen will, wie viele Punkte in dem Rechteck liegen, dann 15:33.270 --> 15:35.910 schaue ich mir im Prinzip die vier Eckpunkte an. 15:39.780 --> 15:43.040 Und ich kann im Prinzip die Frage, wie viele Punkte liegen im 15:43.040 --> 15:50.920 Rechteck, transformieren in eine Frage, wie viele Punkte zum Beispiel 15:50.920 --> 15:54.400 sind kleiner gleich x'y'. 15:54.400 --> 15:58.800 Ich gucke mir diesen Punkt hier an und schaue mir an, wie viele Punkte 15:58.800 --> 16:02.840 kleiner gleich x'y' sind. 16:05.450 --> 16:06.390 Wieso ist das? 16:06.970 --> 16:10.330 Also das ist sicherlich eine Anzahl von Punkten, die größer sein wird, 16:10.850 --> 16:13.630 als die Anzahl der Punkte, die im Rechteck sind. 16:14.410 --> 16:16.030 Da habe ich sicherlich zu viele gezählt. 16:18.170 --> 16:22.310 Jetzt schaue ich mir an, alle Punkte, die kleiner gleich sind, x' und 16:22.310 --> 16:23.650 y'. 16:24.270 --> 16:26.850 Das heißt, ich schaue mir jetzt an diese hier. 16:27.390 --> 16:28.610 Ja, die habe ich ja zu viel da drin. 16:29.550 --> 16:30.530 Die muss ich abziehen. 16:31.370 --> 16:33.430 Also ziehe ich diese Anzahl von Punkten ab. 16:34.510 --> 16:38.250 Dann schaue ich mir an, alle, wobei ich sage ja einfach Punkt kleiner 16:38.250 --> 16:52.250 gleich, wann ist er, also xy ist kleiner gleich x'y', genau dann, wenn 16:52.250 --> 16:58.790 x kleiner gleich x' und y kleiner gleich y'. 16:58.790 --> 16:59.890 Ja, das ist klar. 17:02.150 --> 17:09.550 So, dann muss ich die abziehen, die kleiner gleich x' und y' sind. 17:09.990 --> 17:11.530 Alle in diesem Bereich hier. 17:15.390 --> 17:19.350 Jetzt habe ich aber die Punkte, oder den einen Punkt dort zweimal 17:19.350 --> 17:19.910 abgezogen. 17:20.910 --> 17:22.430 Da habe ich ein zu viel abgezogen. 17:22.710 --> 17:28.730 Ich muss also alle die nochmal dazunehmen, die kleiner sind als xy. 17:29.070 --> 17:30.690 Weil ich die zweimal abgezogen hatte. 17:30.690 --> 17:31.610 Das müssen wir noch einmal dazu. 17:31.970 --> 17:33.590 Muss ich aber explizit nochmal feststellen. 17:36.490 --> 17:39.410 Wie kommt man auf die Idee, so etwas zu machen, wenn man doch nur 17:39.410 --> 17:42.630 wissen will, welche Punkte oben in diesem Rechteck drin liegen. 17:44.630 --> 17:50.030 Das, was wir gerade eben gemacht haben, sind vier Fragestellungen, bei 17:50.030 --> 17:52.950 denen ich jeweils feststellen muss, wie viele Punkte kleiner gleich 17:52.950 --> 17:54.590 als ein bestimmter Punkt sind. 17:55.410 --> 17:56.630 Das ist doch viel schwieriger. 17:57.310 --> 17:58.010 Viel mehr Aufwand. 17:58.010 --> 18:03.850 Aber auf jeden Fall stellt man hier fest, ich kann das Problem 18:03.850 --> 18:08.510 festzustellen, wie viele Punkte in einem Rechteck liegen, durch vier 18:08.510 --> 18:14.170 Punktanfragen lösen, bezüglich der Eckpunkte des Rechtecks. 18:15.230 --> 18:22.650 Und jetzt überlegt man sich, gibt es eine Möglichkeit, wie ich solche 18:22.650 --> 18:29.550 Punktanfragen lösen kann, für einen beliebigen Punkt in diesem 18:29.550 --> 18:31.250 zweidimensionalen Bereich. 18:32.910 --> 18:37.250 Kann ich das einfach mir vorher schon überlegen. 18:38.370 --> 18:41.290 Das ist ja nur, ich kann ja einfach alle möglichen Punkte, die infrage 18:41.290 --> 18:42.510 kommen, einfach mal durchgehen. 18:43.810 --> 18:49.690 Und das vielleicht schneller machen. 18:50.270 --> 18:55.590 Und es ist tatsächlich so, dass man mit ein bisschen Vorbereitung in 18:55.590 --> 19:00.330 der Lage ist, diese Punktanfragen jeweils mit konstantem Aufwand zu 19:00.330 --> 19:01.510 beantworten. 19:02.250 --> 19:03.810 Nach entsprechender Vorbereitung. 19:04.850 --> 19:07.950 Und wenn man das kann, dann wird... 19:08.770 --> 19:10.410 Stimmt nicht, konstanter Aufwand nicht. 19:11.690 --> 19:15.030 Ich brauche logarithmischen Aufwand, weil ich noch eine gewisse Suche 19:15.030 --> 19:15.530 machen muss. 19:16.170 --> 19:21.210 Also logarithmischer Aufwand für logarithmisch in N, Anzahl der 19:21.210 --> 19:25.830 Punkte, habe ich, um jeweils die Punktanfragen zu beantworten. 19:25.830 --> 19:31.450 Und dann komme ich von linearem Aufwand auf logarithmischen Aufwand 19:31.450 --> 19:34.830 runter, für die Beantwortung der Frage, wie viele Punkte liegen im 19:34.830 --> 19:35.250 Rechteck. 19:38.560 --> 19:38.640 So. 19:39.080 --> 19:41.880 Und jetzt geht es darum, wie kann man das Ganze jetzt vorbereiten. 19:43.880 --> 19:45.620 Dazu mache ich folgendes. 19:46.460 --> 19:51.140 Ich habe meine Punktmenge, und das lege ich einfach durch jeden Punkt 19:51.140 --> 19:52.700 zwei Geraden. 19:53.220 --> 19:55.020 Eine vertikale, eine horizontale. 19:57.840 --> 20:03.040 Dadurch unterteile ich meine Ebene in eine Reihe von Rechtecken. 20:03.700 --> 20:05.360 Entsprechend diesen Koordinatenlinien. 20:06.760 --> 20:08.080 Und ich habe auch noch Randflächen. 20:08.180 --> 20:09.940 Also hier sehen wir, da sind solche Randflächen. 20:10.900 --> 20:12.920 Einmal rum habe ich diese vier N-Randflächen. 20:13.900 --> 20:18.760 Und außerdem habe ich eben eine ganze Reihe von Rechtecken. 20:21.880 --> 20:26.140 Ich muss mir also im Prinzip jetzt alle diese Rechtecke merken. 20:26.140 --> 20:33.180 Ich bestimme jetzt im Prinzip für jedes Rechteck so einen rechten 20:33.180 --> 20:34.600 oberen Punkt. 20:38.340 --> 20:41.560 Damit charakterisiere ich im Prinzip hier meine ganzen... also 20:41.560 --> 20:43.520 eigentlich brauche ich natürlich zwei Punkte jeweils. 20:44.460 --> 20:47.370 Und damit kann ich jetzt so viele Rechtecke verwalten. 20:48.200 --> 20:49.300 Das mache ich jetzt dann noch schwieriger. 20:50.240 --> 20:53.320 Jetzt habe ich N² Objekte, die ich verwalten muss. 20:58.040 --> 21:00.240 Jetzt mache ich folgendes. 21:00.400 --> 21:03.020 Ich berechne für jedes Rechteck. 21:03.220 --> 21:05.220 Ich schaue mir also irgendein Rechteck an. 21:07.720 --> 21:13.420 Für jedes Rechteck berechne ich die Anzahl der dominierten Punkte. 21:16.830 --> 21:22.610 Also, das heißt, ich schaue mir irgendeinen Punkt an in solch einem 21:22.610 --> 21:23.190 Rechteck. 21:24.050 --> 21:27.570 Wenn ich also für dieses Rechteck hier rechts mache, irgendeinen Punkt 21:27.570 --> 21:33.670 in einem Rechteck und schaue mir an, wie viele Punkte der Menge werden 21:33.670 --> 21:34.870 dadurch dominiert. 21:37.500 --> 21:39.520 Ich habe meine N-Punkte in der Menge. 21:41.800 --> 21:46.300 Also, werden dominiert heißt, wie viele Punkte sind kleiner oder 21:46.300 --> 21:47.320 gleich diesem x. 21:49.000 --> 21:53.400 Und in dem Fall wären, das ist klar, da habe ich hier, also alles, was 21:53.400 --> 21:57.920 in dem Bereich liegt, das sind die Punkte, die kleiner gleich sind. 21:59.540 --> 22:06.500 Und es ist klar, diese N-Punkte sind ja gerade rechte obere Ecken von 22:06.500 --> 22:07.340 solchen Rechtecken. 22:09.740 --> 22:14.060 Damit ist es klar, wenn ich irgendeinen Punkt in einen solchen 22:14.060 --> 22:20.340 Rechteck nehme, wie dieses x hier, ich brauche das nur im Prinzip für 22:20.340 --> 22:24.180 einen Eckpunkt zu berechnen, welche anderen Punkte kleiner sind. 22:25.640 --> 22:31.180 Ich brauche nicht hier für jeden Punkt im Rechteck das genau zu 22:31.180 --> 22:31.440 machen. 22:32.480 --> 22:35.420 Weil ja in dem Rechteck selbst kein Punkt der Menge liegt. 22:37.040 --> 22:40.120 So, jetzt überlegt man sich, wie man das hinkriegen kann. 22:40.120 --> 22:47.220 Es ist klar, dass die Aussage für das Rechteck, in dem dieses x hier 22:47.220 --> 22:53.840 liegt, natürlich bestimmt wird durch die Aussagen von den anderen 22:53.840 --> 22:54.380 Punkten. 22:54.940 --> 22:59.360 Man kann das mit dem Aufwand insgesamt N² hinbekommen. 22:59.440 --> 23:01.960 Das würde bedeuten, konstanter Aufwand pro Rechteck. 23:02.480 --> 23:06.720 Das macht man durch ein einigermaßen systematisches Verfahren. 23:07.420 --> 23:08.560 Das will ich nicht im Einzelnen machen. 23:09.320 --> 23:12.580 Ja, man macht das für die einzelnen Punkte, kann man feststellen. 23:12.680 --> 23:15.200 Für die Rechtecke, bei denen jetzt die einzelnen Punkte rechts oben 23:15.200 --> 23:19.280 sind, da kann man das sehr einfach feststellen, wie viele dominiert 23:19.280 --> 23:19.580 werden. 23:19.680 --> 23:22.480 Da brauche ich nur punktweise Vergleiche zu machen und ich kriege das 23:22.480 --> 23:22.720 raus. 23:22.800 --> 23:25.200 Wenn ich das für alle Rechtecke machen würde, hätte ich einen Aufwand 23:25.200 --> 23:25.960 von N⁴. 23:27.480 --> 23:29.740 N² mit N Punkten vergleichen. 23:30.320 --> 23:32.640 Oder nein, N² mit N Punkten vergleichen, nicht mit N². 23:32.800 --> 23:34.520 Einen Aufwand von N³ hätte ich. 23:34.520 --> 23:35.920 Das wäre natürlich zu viel. 23:36.240 --> 23:37.760 Es geht mit O von N². 23:38.200 --> 23:40.560 Das will ich hier nicht im Einzelnen ausführen. 23:42.540 --> 23:55.200 Kann man aber machen, weil die Eigenschaften so eines Rechtecks sind 23:55.200 --> 23:59.820 bestimmt durch die Eigenschaften der begrenzenden Linien. 23:59.960 --> 24:01.640 Und für die kann man das im Prinzip festlegen. 24:02.560 --> 24:07.660 Man macht das im Prinzip über diese 2N Linien, über die kann man das 24:07.660 --> 24:09.220 hinbekommen. 24:10.860 --> 24:19.240 Wenn ich das habe, für jedes Rechteck weiß ich, wie viele Punkte 24:19.240 --> 24:20.540 dominiert sind. 24:21.880 --> 24:23.580 Für jedes dieser festen Rechtecke. 24:24.880 --> 24:28.720 Dann mache ich folgendes, ich sortiere die X-Koordinaten der Punkte. 24:28.720 --> 24:33.360 Wir sehen das hier sortiert, aber im Rechner habe ich bisher nur eine 24:33.360 --> 24:34.220 Menge von Punkten. 24:35.040 --> 24:36.440 Die ist nicht notwendigerweise sortiert. 24:37.720 --> 24:40.620 Ich habe ja diese Linien gemalt, die sind auch nicht notwendigerweise 24:40.620 --> 24:41.180 sortiert. 24:42.460 --> 24:44.780 Also muss ich einmal diesen Sortieraufwand reinstecken. 24:45.820 --> 24:49.640 Dann habe ich also einmal den Aufwand N log N fürs Sortieren der 24:49.640 --> 24:50.940 Koordinatenlinien. 24:52.380 --> 24:53.240 Wozu brauche ich das? 24:53.420 --> 24:56.480 Weil ich anschließend die Punktfragen beantworten muss. 24:56.480 --> 24:58.460 Ich nehme ja irgendeinen Punkt hier. 24:59.240 --> 25:00.300 Irgendeinen Punkt XY. 25:02.900 --> 25:04.960 Und zum Beispiel diesen Punkt hier oben. 25:05.600 --> 25:06.720 Der hat die Koordinaten XY. 25:08.060 --> 25:14.640 Dann muss ich wissen, welches Rechteck ist damit gemeint. 25:15.200 --> 25:17.340 Ich muss ja in der Datenstruktur das auffinden können. 25:18.620 --> 25:22.780 Und ich bestimme also einfach durch binäre Suche auf den X- und Y 25:22.780 --> 25:27.880 -Koordinatenlinien das Rechteck, in dem das XY liegt. 25:29.200 --> 25:31.700 Ich habe das ja verwaltet irgendwo. 25:32.160 --> 25:33.380 Kann ich darauf zugreifen. 25:34.680 --> 25:45.960 Ich muss also den... die sind ja irgendwie von X1 bis XN und Y1 bis YN 25:45.960 --> 25:46.720 durchnummeriert. 25:47.520 --> 25:52.220 Und da muss ich halt das richtige Koordinatenpaar finden, zwischen dem 25:52.220 --> 25:53.620 jetzt das X bzw. 25:53.620 --> 25:54.480 das Y liegt. 25:55.120 --> 25:56.960 Und damit habe ich das Rechteck identifiziert. 25:58.100 --> 26:02.100 Und für jedes Rechteck habe ich abgespeichert, wie viele Punkte 26:02.100 --> 26:05.740 kleinergleich irgendeinem beliebigen Punkt in dem Rechteck sind. 26:06.600 --> 26:09.180 Und damit habe ich die Anfrage beantwortet. 26:09.480 --> 26:11.200 Die binäre Suche macht Aufwand log N. 26:12.100 --> 26:16.320 Und damit habe ich das Zeit für eine Punktanfrage Aufwand log N. 26:17.000 --> 26:20.020 Für vier Punktanfragen, wenn ich also das bestimmen will bezüglich 26:20.020 --> 26:26.300 eines Rechtecks, muss ich halt dann den entsprechenden vierfachen 26:26.300 --> 26:28.320 Aufwand berücksichtigen, aber das ist immer noch log N. 26:32.070 --> 26:32.590 Gut. 26:34.330 --> 26:38.090 Ich habe jetzt das Verfahren hier oben nicht genauer erläutert, aber 26:38.090 --> 26:45.250 ich denke, das Wesentliche hier ist jetzt zu sehen, dass ich aufgrund 26:45.250 --> 26:50.390 einer gewissen Vorbereitung in der Lage bin, die einzelnen Anfragen 26:50.390 --> 26:52.950 dann tatsächlich effizient zu bearbeiten. 26:53.730 --> 26:57.830 Sehen Sie das hier einfach als ein Orakel an, das Ihnen diese Punkte 26:57.830 --> 26:59.230 gibt oder diese Antworten gibt. 27:03.790 --> 27:07.870 Solche Punktanfragen kann man in unterschiedlichster Art und Weise 27:07.870 --> 27:09.230 machen. 27:10.270 --> 27:11.950 Gerade eben hatten wir Rechtecke betrachtet. 27:11.950 --> 27:16.150 Ein Rechteck ist ein relativ einfaches Gebilde. 27:17.310 --> 27:21.130 Jetzt betrachte ich ein einfaches Polygon. 27:22.690 --> 27:26.190 Also das, was hier unten ist, ist das typische Beispiel eines nicht 27:26.190 --> 27:27.390 einfachen Polygons. 27:27.910 --> 27:29.390 Da überschneiden sich zwei Kanten. 27:31.130 --> 27:34.170 Ich hatte auf einer der ersten Folien auch schon ein nicht einfaches 27:34.170 --> 27:35.070 Polygon angegeben. 27:35.070 --> 27:44.230 Also ein Polygon ist einfach, wenn die Ebene durch das Polygon in 27:44.230 --> 27:46.490 genau zwei Bereiche aufgeteilt wird. 27:46.610 --> 27:48.270 Einen inneren Bereich und einen äußeren Bereich. 27:48.950 --> 27:52.130 Das ist bei dem Beispiel dort nicht der Fall. 27:52.770 --> 27:57.650 Jetzt ist die Frage, ich habe irgendeinen Punkt in einem einfachen 27:57.650 --> 27:58.010 Polygon. 27:58.050 --> 28:00.050 Die sieht gar nicht so einfach aus, aber sie ist einfach. 28:00.650 --> 28:02.630 In dem Sinne, wie ich es gerade definiert habe. 28:03.710 --> 28:11.310 Das ist ein einfaches Polygon, weil der Bereich in einen inneren und 28:11.310 --> 28:13.930 äußeren eingeteilt wird. 28:14.390 --> 28:17.110 Und die Frage ist, wenn ich irgendeinen Punkt habe... 28:17.110 --> 28:19.410 Also das hier ist jetzt mein Punkt Q. 28:20.810 --> 28:22.450 Liegt der innerhalb oder außerhalb? 28:22.510 --> 28:24.630 Wenn Sie da so rauf gucken, das sehen Sie nicht sofort. 28:26.090 --> 28:28.110 Stellen Sie sich das als praktisches Problem vor. 28:28.110 --> 28:35.750 Sie haben hier einen Landwirt mit seinem Haus. 28:36.690 --> 28:41.530 Und dahinten steht nicht der Buchstabe Q, sondern eine Kuh. 28:43.430 --> 28:48.400 Und der Landwirt steht hier und möchte gerne wissen... 28:50.690 --> 28:54.090 Diese Kuh dahinten, ist die eigentlich noch auf der Weide oder ist die 28:54.090 --> 28:54.420 ausgebrochen? 28:55.600 --> 28:59.560 Und er schaut einfach auf diese komplizierte Weide rauf. 29:00.380 --> 29:01.680 Mit seinem Fernglas. 29:02.900 --> 29:07.700 Und die Frage ist, wie kann er feststellen, wenn er darüber guckt, ob 29:07.700 --> 29:10.580 die Kuh in der Weide ist oder außerhalb von der Weide. 29:13.680 --> 29:15.240 Und das ist ganz einfach. 29:16.340 --> 29:17.320 Er steht ja außerhalb. 29:17.860 --> 29:19.180 Das weiß er, wo er steht. 29:19.180 --> 29:28.880 Wenn er außerhalb ist, dann zählt er einfach die Anzahl der Zäune, die 29:28.880 --> 29:32.980 zwischen ihm und der Kuh liegen. 29:35.260 --> 29:40.220 Und wenn diese Anzahl der Zäune gerade ist, dann heißt das, er ist 29:40.220 --> 29:42.940 einmal rein und wieder raus. 29:42.940 --> 29:44.680 Rein und wieder raus. 29:44.880 --> 29:45.380 Und wieder rein. 29:46.120 --> 29:48.640 Bei einer geraden Fall wäre er wieder raus. 29:49.280 --> 29:50.580 Dann würde er immer rein-raus gehen. 29:51.420 --> 29:56.680 Wenn er aber ungerade ist, dann weiß er, die Kuh ist drin. 29:59.240 --> 30:04.620 Also muss man nur zählen die Anzahl der Linien des Polygons, die durch 30:04.620 --> 30:13.420 die Verbindungslinie zwischen dem äußeren Beobachter und diesem Punkt 30:13.420 --> 30:15.100 geschnitten werden. 30:16.560 --> 30:19.960 Wenn es gerade ist, ist der Punkt draußen. 30:20.660 --> 30:22.660 Wenn es ungerade ist, ist der Punkt drinnen. 30:24.060 --> 30:25.120 Sehr praktisches Problem. 30:26.020 --> 30:29.640 Können Sie sich auch so überlegen, wenn Sie durch Australien fahren 30:29.640 --> 30:35.460 und Sie wissen, Sie starten mit Ihrem Fahrzeug irgendwo außerhalb 30:35.460 --> 30:36.060 einer Weide. 30:36.740 --> 30:39.700 Jetzt fahren Sie durch die Landschaft und ab und zu mal sind dort 30:39.700 --> 30:44.440 diese Gitter oder die Zäune über die Straße rüber, die dort einfach 30:44.440 --> 30:48.120 als Metallgitter vorkommen. 30:49.140 --> 30:51.540 Sie wollen abends ihr Zelt aufschlagen, wollen aber nicht gerne 30:51.540 --> 30:54.880 innerhalb der Weide übernachten, sondern wollen außerhalb der Weide 30:54.880 --> 30:55.360 übernachten. 30:55.840 --> 30:59.260 Sie müssen nur zählen, ob Sie eine gerade oder ungerade Anzahl von 30:59.260 --> 31:00.620 Zäunen überfahren haben. 31:01.580 --> 31:04.800 Sie wissen, ob Sie in der Weide sind oder außerhalb der Weide sind. 31:05.760 --> 31:07.020 Ganz einfach festzustellen. 31:08.540 --> 31:12.260 Also, das nennt man formal die Strahlmethode. 31:12.880 --> 31:16.460 Wir betrachten eine beliebige Gerade durch diesen Punkt Q, hier 31:16.460 --> 31:18.540 nochmal gestrichelt angedeutet. 31:18.540 --> 31:24.440 Und jetzt bestimmt man einfach die Anzahl der Schnittpunkte der 31:24.440 --> 31:28.840 geraden Mittkanten des Polygons auf dem Weg von Q nach draußen. 31:30.020 --> 31:31.260 Genau das haben wir gerade eben gemacht. 31:33.280 --> 31:37.580 Und damit haben wir also dieses Problem gelöst. 31:38.460 --> 31:44.000 Aufwand ist natürlich linear, weil Sie überprüfen müssen für jede 31:44.000 --> 31:48.380 Kante des Polygons, ob sie geschnitten wird durch diesen Strahl oder 31:48.380 --> 31:48.780 nicht. 31:51.920 --> 31:54.400 Also, hier haben wir keine Vorbereitung. 31:55.280 --> 31:57.560 Es ist die Frage, geht das besser? 31:58.360 --> 32:03.020 Also nach dem ersten Problem wird man vorsichtig mit der Frage, kann 32:03.020 --> 32:05.360 man das eventuell schneller hinkriegen oder nicht. 32:07.820 --> 32:12.040 In diesem Fall kann man für beliebige Polygone das nicht verbessern. 32:14.080 --> 32:16.300 Das ist zu unstrukturiert. 32:16.340 --> 32:17.700 Das andere war ein strukturiertes Problem. 32:17.900 --> 32:20.980 Dieses hier wird durch die beliebige Lage der Polygonkanten 32:20.980 --> 32:21.760 unstrukturiert. 32:24.180 --> 32:29.620 Aber jetzt schauen wir uns als nächstes ein etwas anderes Polygon an. 32:30.820 --> 32:34.860 Immer noch einfach, aber sogar sehr einfach, weil es auch noch konvex 32:34.860 --> 32:35.220 ist. 32:36.880 --> 32:39.460 Also hier haben wir ein typisches konvexes Polygon. 32:40.660 --> 32:43.160 Das daneben ist nicht konvex. 32:45.240 --> 32:51.560 Und die schöne Eigenschaft ist, wenn Sie einen beliebigen Punkt nehmen 32:51.560 --> 32:58.600 innerhalb dieses konvexen Polygons, dann wird jeder Strahl nach 32:58.600 --> 33:01.020 draußen nur eine einzige Kante schneiden. 33:01.900 --> 33:09.000 Wenn Sie ein nicht konvexes Polygon haben, dann gibt es Strahlen von 33:09.000 --> 33:12.660 dem Punkt aus nach draußen, die mehrere Kanten schneiden. 33:15.250 --> 33:17.870 Beim konvexen Polygon nur eine Kante. 33:18.570 --> 33:19.870 Und das kann man ausnutzen. 33:19.950 --> 33:23.430 Wenn ich weiß, ich habe irgendeinen Punkt R hier oder irgendeinen 33:23.430 --> 33:28.290 Punkt im Innern eines konvexen Polygons, dann schneidet also jeder von 33:28.290 --> 33:30.990 R ausgehende Strahl das Polygon genau einmal. 33:32.970 --> 33:35.410 Ich kann sogar Folgendes machen. 33:37.470 --> 33:44.130 Ich nutze das aus, um systematisch festzustellen, ob der Punkt innen 33:44.130 --> 33:45.130 oder außen ist. 33:46.790 --> 33:48.070 Und zwar... 33:49.650 --> 33:52.050 Ich nehme die nächste Folie, da steht es drauf. 33:53.690 --> 33:54.710 Hier ist die Idee. 33:55.930 --> 34:00.350 Ich habe diesen Punkt R und jetzt teile ich mein Polygon auf in 34:00.350 --> 34:01.210 Sektoren. 34:02.790 --> 34:06.050 Ich habe also hier meinen Punkt R. 34:06.750 --> 34:11.170 Dieser Punkt R, beliebiger Punkt im Innern des Polygons, teilt mein 34:11.170 --> 34:12.750 Polygon auf in Sektoren. 34:12.750 --> 34:16.290 Also, das ist zum Beispiel ein Sektor. 34:17.330 --> 34:18.970 Ich habe einen beliebigen Punkt Q. 34:19.890 --> 34:22.990 Und für diesen Punkt Q möchte ich feststellen, liegt er im Inneren 34:22.990 --> 34:25.050 oder im Äußeren. 34:27.450 --> 34:33.650 Dazu kann ich jetzt einfach sagen, ich muss zunächst mal wissen, in 34:33.650 --> 34:38.770 welchem Sektor liegt dieser Punkt Q bezogen auf den Punkt R im Inneren 34:38.770 --> 34:39.510 des Polygons. 34:41.070 --> 34:46.110 Diesen Sektor kann ich suchen durch binäre Suche. 34:46.170 --> 34:48.870 Für binäre Suche brauche ich eine lineare Anordnung. 34:49.470 --> 34:52.570 Die lineare Anordnung bekomme ich, indem ich einfach einmal hier 34:52.570 --> 34:53.610 radial rumlaufe. 34:54.910 --> 35:03.370 Das heißt, ich betrachte von dem R aus eine Folge der Polygonpunkte 35:06.470 --> 35:09.330 und laufe dann einfach einmal hier rum. 35:09.450 --> 35:15.230 Ich kann ja Polarkoordinaten zu den einzelnen Polygonpunkten bestimmen 35:15.230 --> 35:26.250 und kann feststellen, in welchem Sektor liegt jetzt dieser Punkt Q. 35:26.430 --> 35:29.170 Dessen Radialkoeffizienten kann ich auch bestimmen. 35:30.510 --> 35:36.050 Damit weiß ich, in welchem Sektor dieser Punkt Q liegt. 35:36.830 --> 35:39.690 Wenn ich jetzt feststellen will, ob er innen oder außen liegt, muss 35:39.690 --> 35:43.670 ich nur feststellen, ob er in diesem Sektor innen oder außen liegt. 35:43.770 --> 35:47.010 Das heißt, ich muss das nur vergleichen mit dieser Kante, 35:49.110 --> 35:51.650 Verbindungslinie zwischen Pi und Pi plus 1. 35:55.950 --> 36:00.750 Und da muss ich also nur feststellen, liegt der Punkt rechts oder 36:00.750 --> 36:01.650 links von der Kante. 36:03.210 --> 36:05.450 Wenn er rechts liegt, ist er draußen, wenn er links liegt, ist er 36:05.450 --> 36:05.770 drinnen. 36:08.510 --> 36:11.850 Und diese Aufgabe ist also jetzt eine Aufgabe, die man lösen muss. 36:13.270 --> 36:16.990 Man sieht, auch hier haben wir das Problem reduziert auf ein 36:16.990 --> 36:17.570 Teilproblem. 36:19.150 --> 36:22.850 Wir müssen feststellen, ob ein Punkt links oder rechts von einer 36:22.850 --> 36:23.590 Geraden liegt. 36:25.530 --> 36:27.050 Und das ist ja einfach zu lösen. 36:27.130 --> 36:27.870 Wie macht man das denn? 36:29.770 --> 36:32.650 Fällt man da irgendwie das Lot da drauf, oder wie macht man das? 36:34.190 --> 36:38.470 Die Idee ist auch hier relativ einfach, ein bisschen Geometrie. 36:40.050 --> 36:43.290 Es gibt zunächst mal diese beiden Möglichkeiten. 36:43.510 --> 36:47.610 Wir haben hier eine beliebige Anordnung, drei Punkte. 36:49.030 --> 36:56.350 Und wir haben einen Winkel QRPI. 36:59.230 --> 37:06.910 Wenn wir so durchlaufen, habe ich mich von QR nach PI einmal links 37:06.910 --> 37:07.590 herum gedreht. 37:10.250 --> 37:11.630 Das war eine Linksdrehung. 37:12.710 --> 37:15.350 QRPI in diesem Fall ist eine Rechtsdrehung. 37:20.890 --> 37:24.110 Also geht es jetzt darum, habe ich wieder ein anderes Problem. 37:24.270 --> 37:26.450 Nicht, liegt ein Punkt links oder rechts von einer Geraden, sondern 37:26.450 --> 37:30.250 ist ein Winkel eine Rechtsdrehung oder eine Linksdrehung? 37:33.650 --> 37:36.190 Und das ist durchaus wichtig. 37:37.490 --> 37:39.210 Interessante andere Fragestellung. 37:40.130 --> 37:43.110 Und das gucken wir uns jetzt nochmal ein bisschen anders an. 37:44.230 --> 37:49.110 Das linke Bild, hier einfach etwas anders dargestellt. 37:49.230 --> 37:50.670 Wir gucken uns bestimmte Flächen an. 37:52.210 --> 37:58.110 Und das, was wir bestimmen wollen, ist also der Inhalt des Dreiecks, 37:58.250 --> 38:01.130 das von QR und PI aufgespannt wird. 38:02.630 --> 38:05.010 Und wie kann man dieses Dreieck bestimmen? 38:05.950 --> 38:08.610 Ich habe hier einige Flächen unterschiedlich schraffiert. 38:09.690 --> 38:16.190 Die Fläche dieses Dreiecks, also ich möchte dieses Dreieck hier genau 38:16.190 --> 38:19.470 bestimmen, ist durch diese Formel gegeben. 38:19.510 --> 38:20.730 Wie kommt diese Formel zustande? 38:21.010 --> 38:21.830 Ist ganz einfach. 38:23.650 --> 38:26.530 yi plus yi halbe mal xi minus x. 38:27.790 --> 38:31.590 xi ist dieser Punkt hier, x ist der Punkt. 38:35.350 --> 38:41.730 Und yi ist also diese Distanz, dieser Teil. 38:42.490 --> 38:44.530 Und y ist der Teil. 38:45.830 --> 38:51.810 Ich schaue mir einfach die Fläche des Trapezes an, das hier 38:51.810 --> 38:53.050 aufgespannt wird. 38:54.230 --> 38:55.210 Diese Trapez. 38:56.750 --> 39:05.390 Die Fläche dieses Trapezes ist offensichtlich yi plus yi halbe mal xi 39:05.390 --> 39:06.050 minus x. 39:07.650 --> 39:09.010 Das ist die Fläche dieses Trapezes. 39:10.230 --> 39:15.650 Und jetzt nimmt man das Gleiche im Vergleich zwischen den Punkten Q 39:15.650 --> 39:16.190 und R. 39:17.350 --> 39:23.810 Dann hat man dieses Trapez hier betrachtet, die Fläche. 39:24.990 --> 39:26.030 Addiert man dazu. 39:27.250 --> 39:32.450 Wenn ich die beiden addiert habe, habe ich aber genau diesen Bereich 39:32.450 --> 39:37.040 hier zu viel da drin. 39:37.500 --> 39:40.500 Ich will ja nur die Fläche des Dreiecks haben. 39:41.220 --> 39:42.500 Also ziehe ich das wieder ab. 39:43.500 --> 39:46.660 Und das Trapez hat gerade die Fläche, die hier abgezogen wird. 39:49.590 --> 39:52.030 Das heißt, ich habe hier ganz einfache Berechnungen. 39:52.030 --> 39:56.350 Ich muss nur so ein paar Additionen, Subtraktionen machen und ein paar 39:56.350 --> 39:57.710 Multiplikationen. 39:59.150 --> 40:01.730 Und dann natürlich auch noch hier durch zwei dividieren. 40:01.890 --> 40:03.450 Aber das ist ja auch eine einfache Operation. 40:03.610 --> 40:05.070 Durch zwei dividieren ist einmal shiften. 40:06.410 --> 40:08.070 Also das ist eine sehr einfache Operation. 40:08.410 --> 40:12.230 Ich brauche keine komplizierten Winkelberechnungen zu machen. 40:13.990 --> 40:16.530 Also wenn Sie fest... Sie würden normalerweise denken, das mache ich 40:16.530 --> 40:19.630 irgendwie mit Sinus und Kosinus und irgendwelchen Dingen. 40:19.630 --> 40:20.750 Braucht man hier nicht. 40:21.330 --> 40:23.750 Keine trigonometrischen Funktionen. 40:23.930 --> 40:26.090 Ich berechne einfach die Fläche dieses Dreiecks. 40:27.270 --> 40:29.110 Wieso berechne ich die Fläche des Dreiecks? 40:29.270 --> 40:30.030 Was hilft mir das? 40:30.890 --> 40:33.110 Stellen Sie sich vor, wir hätten diese Situation. 40:35.210 --> 40:39.910 Dann würde ja das so aussehen, dass wir hier den Punkt haben. 40:40.670 --> 40:47.550 Jetzt hätten wir einmal dieses Trapez berechnet, dann dieses Trapez 40:47.550 --> 40:52.130 und ziehen davon ab die Fläche dieses Trapezes. 40:53.230 --> 40:56.590 Und wenn wir das abziehen, dann wird daraus ein negativer Wert. 40:57.810 --> 41:02.730 Das heißt, das was uns interessiert, ist eigentlich nur, ob der Wert, 41:02.910 --> 41:06.130 der hier berechnet wird, positiv oder negativ ist. 41:06.130 --> 41:13.610 Ist der größer 0, weiß ich, dass der Punkt links liegt von meiner 41:13.610 --> 41:16.250 Geraden. 41:16.630 --> 41:17.710 Dann ist das diese Situation. 41:18.890 --> 41:22.110 Ist der Wert negativ, dann habe ich diese Situation. 41:25.370 --> 41:30.050 Und das was hier oben steht als Formel, die ich berechnen muss, kann 41:30.050 --> 41:33.130 ich ein bisschen allgemeiner aufschreiben als gerade diese 41:33.130 --> 41:33.790 Determinante. 41:35.850 --> 41:37.910 Da werden genau diese Operationen gemacht. 41:38.030 --> 41:39.450 Ich muss den Wert nur noch durch 2 teilen. 41:40.570 --> 41:44.850 Also ein Halbmal der Wert dieser Determinante, in dem die drei Punkte 41:44.850 --> 41:48.750 genau in der Art vorkommen, also q, r, p, i in der Reihenfolge, 41:49.430 --> 41:50.850 Koordinaten so aufgeschrieben. 41:51.510 --> 41:53.870 Davon die Determinante berechnet und dann muss noch die Einzelrechte 41:53.870 --> 41:55.970 daneben berücksichtigt werden, damit das richtig hinkommt. 41:56.910 --> 41:58.630 Das ist genau der Wert, den ich berechnen muss. 41:58.630 --> 42:02.810 Keinerlei trigonometrischen Funktionen berechnet, sondern ich brauche 42:02.810 --> 42:09.010 hier nur ganz einfache Multiplikationen, Additionen zu machen. 42:09.690 --> 42:10.890 Eine Division durch zwei. 42:12.650 --> 42:16.010 Das Problem ist nur, was mache ich? 42:16.190 --> 42:17.330 Das hatte ich vorhin schon angesprochen. 42:18.370 --> 42:24.270 Ich weiß, das sind alles Reelle Werte der einzelnen Koordinaten. 42:24.270 --> 42:30.750 Und wenn dieser Punkt q sehr nah an der Verbindungslinie liegt, also 42:30.750 --> 42:35.530 wenn ich hier so eine Gerade habe und der Punkt liegt irgendwo da ganz 42:35.530 --> 42:38.090 nah dran, dann kann das zu Problemen führen. 42:39.550 --> 42:42.650 Aber wir gehen in der Regel davon aus, dass wir die sauber voneinander 42:42.650 --> 42:43.250 trennen können. 42:44.810 --> 42:50.090 Wenn man das nicht kann, muss man durchaus einige andere Überlegungen 42:50.090 --> 42:50.510 noch machen. 42:51.530 --> 42:57.430 Aber man könnte einfach sagen, man lässt nur Punkte zu, die einen 42:57.430 --> 42:59.190 gewissen Mindestabstand voneinander haben. 42:59.630 --> 43:02.570 Das wäre einmal eine Vorbereitung und dann kann man das Verfahren so 43:02.570 --> 43:03.530 laufen lassen. 43:05.830 --> 43:07.810 Also, Interpretation ist jetzt klar. 43:08.810 --> 43:13.610 Wenn der Wert größer 0 ist, das ist der Fall, der hier oben angedeutet 43:13.610 --> 43:17.570 ist, dann ist der Wert des Flächeninhalts positiv berechnet. 43:17.570 --> 43:21.390 Das heißt, q liegt auf der linken Seite. 43:22.710 --> 43:29.190 Und wenn es kleiner ist, dann habe ich eine Rechtsdrehung, dann liegt 43:29.190 --> 43:32.710 der Punkt rechts davon. 43:33.930 --> 43:38.670 Und damit habe ich also genau die Antwort, die ich brauchte. 43:39.730 --> 43:43.250 Und der Aufwand insgesamt für den Algorithmus besteht also jetzt 43:43.250 --> 43:49.550 darum, dass ich einmal, also zur Vorbereitung, erst mal den Sektor 43:49.550 --> 43:50.330 bestimmen muss. 43:54.170 --> 44:00.010 Den Sektor zu bestimmen ist, naja, ich sage hier in linearer Zeit 44:00.010 --> 44:02.430 möglich, also ich kann das in linearer Zeit vorbereiten. 44:02.430 --> 44:08.190 Das geht nur, wenn ich das beim konvexen Polygon, die Punkte bereits 44:08.190 --> 44:09.930 radial sortiert vorliegen habe. 44:12.010 --> 44:13.850 Das muss schon der Fall sein. 44:13.930 --> 44:17.390 Wenn das nicht der Fall ist, dann müsste ich die erst noch radial 44:17.390 --> 44:19.230 sortieren, das wäre dann Aufwand nlog n. 44:20.550 --> 44:23.450 Wenn die schon radial sortiert sind und wir nehmen in der Regel an, 44:23.970 --> 44:27.710 dass die, so wie es hier steht, der Reihe nach nummeriert sind, geht 44:27.710 --> 44:32.570 irgendwo mit dem untersten Punkt los, P1, P2, P3 usw. 44:33.670 --> 44:38.630 Dann weiß ich genau, wie die Punkte verbunden sind und genau in der 44:38.630 --> 44:39.270 Reihenfolge. 44:40.050 --> 44:44.790 Und dann brauche ich die nicht nochmal zu sortieren, um diese Sektoren 44:44.790 --> 44:47.450 dann bestimmen zu können mit dieser Punkteanfrage. 44:48.410 --> 44:52.970 Und der Aufwand danach ist ja konstant, um festzustellen, rechts oder 44:52.970 --> 44:54.490 links, haben wir gerade eben gesehen, wie das geht. 44:54.490 --> 44:59.370 Also ist dann der Aufwand für die einzelne Anfrage logarithmisch, im 44:59.370 --> 45:03.750 Wesentlichen der Aufwand, um den richtigen Sektor zu bestimmen. 45:05.870 --> 45:12.490 Jetzt haben wir das Ganze gerade eben vereinfacht betrachten können, 45:12.570 --> 45:16.850 weil das Polygon konvex war, natürlich auch einfach. 45:18.230 --> 45:20.830 Und die Frage ist, was sind das eigentlich für Eigenschaften? 45:21.590 --> 45:22.770 Wie kann man die eigentlich bestimmen? 45:24.350 --> 45:28.690 Also, woher weiß ich, ob ein Polygon einfach ist oder nicht? 45:31.510 --> 45:39.790 Wir haben gesagt, einfach ist es dann, wenn das Polygon die Ebene in 45:39.790 --> 45:41.930 genau zwei unterschiedliche Bereiche teilt. 45:42.490 --> 45:47.510 Hier habe ich ein Beispiel, wo die Ebene in drei verschiedene Bereiche 45:47.510 --> 45:48.190 geteilt wird. 45:48.450 --> 45:50.530 Nicht einfach, zwei Kanten überschneiden sich. 45:51.710 --> 45:56.730 Und das heißt, was man machen kann, ist, ich kann einfach je zwei 45:56.730 --> 46:00.650 Kantenpaare mir hernehmen und überprüfen, ob die sich überschneiden. 46:02.590 --> 46:05.050 Das wäre aber ein Aufwand von n². 46:05.270 --> 46:06.730 Ich habe n solche Liniensegmente. 46:07.630 --> 46:10.510 Wenn ich das überprüfen will, der jeweilige Überprüfungsaufwand ist 46:10.510 --> 46:11.770 konstanter Zeit machbar. 46:13.370 --> 46:17.510 Das heißt, ich habe hier für einen naiven Ansatz Zeit n². 46:18.470 --> 46:23.450 Und der kluge Ansatz würde halt versuchen, das zu reduzieren. 46:24.910 --> 46:27.010 Und jetzt kommt eine weitere Technik. 46:27.870 --> 46:36.510 Ich nehme ein Planesweep-Verfahren, also ein Ebenenfegen-Verfahren auf 46:36.510 --> 46:36.870 Deutsch. 46:37.610 --> 46:38.330 Planesweep. 46:38.610 --> 46:40.110 Ich fege die Ebene einmal ab. 46:40.110 --> 46:42.850 Und die Idee ist ganz einfach. 46:43.090 --> 46:50.410 Ich nehme eine Linie und bewege diese Linie durch meinen Bereich, der 46:50.410 --> 46:53.150 die interessanten Punkte enthält und die interessanten Objekte 46:53.150 --> 46:54.470 enthält, einfach durch. 46:55.670 --> 46:59.710 Komme irgendwann auf der rechten Seite wieder raus und irgendwann 46:59.710 --> 47:02.890 erreiche ich irgendeinen Punkt da drin, den ersten Punkt. 47:03.780 --> 47:10.690 Den zweiten Punkt, den dritten Punkt, den vierten Punkt, den fünften 47:10.690 --> 47:10.950 Punkt. 47:11.670 --> 47:13.110 Auch das ist eine Annahme. 47:13.170 --> 47:15.970 Ich bin ein bisschen ausgewichen. 47:16.890 --> 47:20.610 Man nimmt immer an, dass nie zwei Punkte die gleichen x-Koordinaten 47:20.610 --> 47:20.990 haben. 47:21.690 --> 47:22.710 Noch so eine Annahme. 47:23.550 --> 47:26.330 Wenn das der Fall ist, muss man Sondermaßnahmen ergreifen. 47:27.890 --> 47:31.050 Aber um die Algorithmen vorzustellen, kann man diese Anfangsannahmen 47:31.050 --> 47:31.410 machen. 47:31.850 --> 47:34.430 Wenn man so ein Ding tatsächlich implementiert, muss man Sonderfälle 47:34.430 --> 47:34.970 betrachten. 47:36.310 --> 47:37.850 Was passiert an diesem Punkt? 47:40.190 --> 47:45.610 Wenn ich ganz rechts angelangt bin, an dieser Stelle hier, dann heißt 47:45.610 --> 47:48.430 das, ich habe einen Punkt, von dem gehen zwei Kanten aus. 47:50.350 --> 47:54.110 Und ich kann sofort feststellen, ob... 47:54.110 --> 47:56.810 Gut, diese zwei Kanten schneiden sich natürlich in diesem Punkt, weil 47:56.810 --> 47:57.870 die beiden davon ausgehen. 47:58.170 --> 47:59.310 Die können sich nicht nochmal schneiden. 48:00.190 --> 48:01.690 Ich kann also weitergehen nach rechts. 48:02.350 --> 48:03.650 Kommen wir zum nächsten Punkt. 48:04.190 --> 48:06.930 Von dem geht natürlich auch eine Kante aus, diese Kante hier. 48:07.690 --> 48:12.210 Ich weiß aber, das habe ich mir hier drauf gemerkt, hier war eine 48:12.210 --> 48:17.010 Kante, oder hier hatte eine Kante begonnen mit Koordinaten. 48:19.230 --> 48:21.650 Bestimmten Koordinaten von Anfangs- und Endpunkt. 48:22.410 --> 48:26.010 Und ich füge jetzt eine neue Kante ein in meine Datenstruktur, die im 48:26.010 --> 48:30.350 Prinzip sich bezieht auf das, was ich an Ereignissen auf dieser Linie 48:30.350 --> 48:32.670 habe, auf der vertikalen Linie. 48:33.970 --> 48:38.510 Und ich weiß, da gibt es bereits eine Kante, und es kommt eine neue 48:38.510 --> 48:41.750 Kante dazu, und ich kann feststellen, überschneiden sich die beiden 48:41.750 --> 48:42.170 Kanten. 48:43.030 --> 48:43.670 Machen sie nicht. 48:43.930 --> 48:45.050 Kein besonderes Ereignis. 48:45.130 --> 48:47.350 Ich merke mir aber, dass ich jetzt zu der Kante gekommen bin. 48:47.890 --> 48:49.610 Ich gehe weiter, komme zu diesem Punkt. 48:51.010 --> 48:52.810 Da hört die eine Kante auf. 48:52.970 --> 48:57.890 Ich kann also den Eintrag von meiner Linienstruktur löschen. 48:58.650 --> 49:00.060 Ich muss eine neue Kante hinzufügen. 49:01.530 --> 49:05.850 Ich muss jetzt diese Kante, den Eintrag über diese Kante, vergleichen 49:05.850 --> 49:08.590 mit dem Eintrag über die Kante, die ich hier oben gespeichert hatte. 49:09.930 --> 49:12.630 Ich stelle fest, die beiden überschneiden sich nicht, weil sie nicht 49:12.630 --> 49:13.330 weit genug laufen. 49:13.410 --> 49:15.910 Wenn sie länger laufen würden, würden sie sich überschneiden. 49:22.630 --> 49:27.390 Dann gehe ich wieder weiter, komme zu dem Punkt hier oben. 49:28.110 --> 49:30.650 Auch von dem geht eine Kante nach rechts raus. 49:31.790 --> 49:33.050 Ich stelle fest, keine Überschneidung. 49:36.260 --> 49:38.700 Ich gehe weiter, komme zu diesem Punkt. 49:40.640 --> 49:42.640 Hier laufen zwei Kanten los. 49:44.880 --> 49:51.880 Und jetzt werden hier Kanten eingetragen, diese Kante und die Kante. 49:52.840 --> 49:56.440 Und da kann ich jetzt eine Überschneidung feststellen. 50:01.380 --> 50:06.040 Ich habe hier nebeneinander liegende Ereignisse. 50:06.140 --> 50:08.520 Das Ereignis ist hier gespeichert, das ist gespeichert, die beiden 50:08.520 --> 50:09.240 liegen übereinander. 50:09.900 --> 50:13.260 Und ich kann feststellen, die beiden Kanten schneiden sich 50:13.260 --> 50:13.700 tatsächlich. 50:15.120 --> 50:19.880 Man sieht, dass man auf dieser Linie im Prinzip stets nur 50:19.880 --> 50:24.880 Eigenschaften abspeichert, die sich auf die gerade aktiven Kanten 50:24.880 --> 50:25.360 beziehen. 50:25.360 --> 50:29.060 Die gerade durch diese Vertikale betroffen sind. 50:31.120 --> 50:36.060 Und wenn sich zwei Kanten schneiden, dann nur dadurch, dass ich 50:36.060 --> 50:38.240 übereinander liegende Ereignisse im Prinzip habe. 50:38.340 --> 50:39.940 Diese hier liegen genau nebeneinander. 50:40.860 --> 50:43.620 Nur die Kanten, die von den Punkten ausgehen, können sich überhaupt 50:43.620 --> 50:44.060 schneiden. 50:48.280 --> 50:50.600 Mit anderen kann es keine Schnittpunkte geben. 50:51.000 --> 50:56.200 Und insofern habe ich hier immer nur ganz lokal Entscheidungen zu 50:56.200 --> 50:56.500 treffen. 50:56.500 --> 51:02.140 Und ich muss also nur über diese Haltepunkte hinweg meine Kante oder 51:02.140 --> 51:06.000 meine Linie, die vertikale Linie über diese Ebene hinweg bewegen. 51:06.440 --> 51:11.280 Ich habe eine Reihe Ereignisse, die dabei auf dieser Ebene oder auf 51:11.280 --> 51:13.820 dieser Linie auftauchen, oder auf dieser Geraden. 51:15.340 --> 51:19.480 Die Ereignisse verwalte ich in einer effizienten Art und Weise, in 51:19.480 --> 51:21.540 einer gewissen Baumstruktur. 51:23.520 --> 51:32.160 Und damit kann ich an jedem Haltepunkt diese Frage, überschneiden sich 51:32.160 --> 51:35.120 zwei Kanten, mit konstantem Aufwand lösen. 51:35.920 --> 51:39.300 Beziehungsweise es ist kein konstanter Aufwand, ich habe eventuell 51:39.300 --> 51:42.960 hier logarithmischen Aufwand, um den richtigen Punkt zu finden, an dem 51:42.960 --> 51:44.860 ich das einsortieren muss in diese Suchstruktur. 51:45.480 --> 51:47.880 Also habe ich an Endpunkten logarithmischen Aufwand. 51:48.980 --> 51:53.920 Dieser logarithmische Aufwand kommt immer dadurch, dass ich in einer 51:53.920 --> 51:56.020 Suchstruktur einen neuen Punkt einfügen muss. 51:57.260 --> 52:00.300 Und ich muss den richtigen Ort fürs Einfügen finden, das ist immer der 52:00.300 --> 52:00.960 Aufwand Log N. 52:01.940 --> 52:04.620 Und damit habe ich insgesamt einen Aufwand von N Log N. 52:08.610 --> 52:11.170 Und das ist die Idee von dem Plane Sweep. 52:11.230 --> 52:13.370 Und das, was man hier macht, ist das, was hier steht. 52:14.790 --> 52:20.650 Ich reduziere das Problem, das ich habe, durch Plane Sweep, auf eine 52:20.650 --> 52:28.190 Folge von Problemen in einem D-1 dimensionalen Raum. 52:28.290 --> 52:35.470 Wenn ich einen D-dimensionalen Raum habe, schaue ich mir das an auf 52:35.470 --> 52:39.710 einem eindimensionalen Objekt, nämlich auf dieser Linie Ereignisse, 52:39.810 --> 52:41.910 eine Folge von Ereignissen auf einem eindimensionalen Objekt. 52:41.910 --> 52:45.330 Und das ist die interessante algorithmische Technik, die man hier 52:45.330 --> 52:51.050 einsetzt, dass ich durch diese Reduktion des Problems auf ein etwas 52:51.050 --> 52:59.130 anderes, auf dieser eindimensionalen Geraden, kann ich das Problem 52:59.130 --> 53:01.110 insgesamt effizienter lösen. 53:01.890 --> 53:02.650 Plane Sweep. 53:03.670 --> 53:04.850 Ein ganz wichtiges Prinzip. 53:05.070 --> 53:08.790 Damit kann man eine ganze Reihe von Problemen in der algorithmischen 53:08.790 --> 53:12.410 Geometrie auf effiziente Art und Weise lösen. 53:15.370 --> 53:17.490 Und das, was man hier, eben hier ist es nochmal angedeutet, wie man 53:17.490 --> 53:20.950 das macht, im Prinzip löst man hier so eine Art 53:20.950 --> 53:22.110 Intervallüberschneidungsproblem. 53:23.730 --> 53:31.230 Denn die Projektion dieser Linien auf die Geraden, das sind im Prinzip 53:31.230 --> 53:31.810 Intervalle. 53:34.250 --> 53:38.230 Jede, wenn ich mir irgendeine Kante anschaue, auf meiner Linie ist 53:38.230 --> 53:45.590 diese Kante hier, ist ja hier drin ein Intervall auf der Linie. 53:46.630 --> 53:49.330 Und wenn ich hier rüber laufe, habe ich also eine Reihe von 53:49.330 --> 53:49.870 Intervallen. 53:51.030 --> 53:53.570 Und solange sich die Intervalle nicht überschneiden, habe ich auch 53:53.570 --> 53:54.730 keinen Schnittpunkt der Linien. 53:56.090 --> 53:59.590 Nur wenn sich Intervalle überschneiden, habe ich Schnittpunkte. 54:01.550 --> 54:07.530 Insofern reduziere ich das Problem der Überschneidung von Linien auf 54:07.530 --> 54:10.030 ein Problem Überschneidung von Intervallen. 54:11.810 --> 54:16.030 Und ich habe immer Operationen, irgendwo lokal auf meiner Linie. 54:17.170 --> 54:21.110 Und wenn also hier Punkte eingefügt werden, kann ich feststellen, ob 54:21.110 --> 54:26.350 sich auf der Linie jetzt hier irgendwelche Überschneidungen ergeben. 54:26.470 --> 54:30.530 Und man sieht in dem Fall ergeben sich Überschneidungen der 54:30.530 --> 54:32.010 Intervalle, die gerade aktiv sind. 54:33.010 --> 54:37.350 Also das ist in dem Fall das Linienüberschneidungs- oder 54:37.350 --> 54:41.890 Schnittproblem auf ein Intervallüberschneidungsproblem reduziert. 54:43.710 --> 54:50.150 Und ich brauche also nur diese Linie über diese Haltepunkte hinweg zu 54:50.150 --> 54:50.570 bewegen. 54:51.130 --> 54:56.290 Und die Haltepunkte sind die Anfangs- und Endpunkte der Kanten des 54:56.290 --> 54:56.830 Polygons. 54:58.750 --> 55:04.870 Also diese Punkte, die gerade die Linien definieren. 55:07.790 --> 55:11.310 Und diese Intervallüberschneidungsprobleme kann ich eben jeweils 55:11.310 --> 55:12.510 schnell lösen. 55:12.590 --> 55:15.450 Ich muss nur wissen, an welcher Stelle bei der auf der Linie 55:15.450 --> 55:17.070 gespeicherten Intervalle bin ich gerade. 55:17.210 --> 55:18.710 Das geht in logarithmischer Zeit. 55:18.710 --> 55:21.610 Und ob sich jetzt benachbarte Intervalle bzw. 55:21.770 --> 55:24.570 durch den Eintrag eines neuen Intervalls oder die Veränderung eines 55:24.570 --> 55:27.650 dort bisher abgespeicherten Intervalls eine Überschneidung ergibt, das 55:27.650 --> 55:29.410 kann ich dann in konstanter Zeit feststellen. 55:33.170 --> 55:38.570 Hier sind die Operationen an den Haltepunkten nochmal genau angegeben. 55:40.150 --> 55:45.510 Ich glaube, ich kann darauf verzichten, das alles nochmal hier 55:45.510 --> 55:49.190 aufzuführen, wie das exakt abläuft. 55:49.190 --> 55:52.630 Ich habe das gerade eben aufgeführt oder versucht anzudeuten, wie man 55:52.630 --> 55:53.070 das macht. 55:54.190 --> 55:57.710 Und hier sind die Operationen nochmal explizit angegeben. 55:57.850 --> 55:58.670 Schauen Sie sich das an. 55:59.290 --> 56:04.930 Ich erwarte nicht, dass Sie in der Prüfung wissen, wie genau die 56:04.930 --> 56:07.250 einzelnen Operationen an den Haltepunkten hier laufen. 56:07.390 --> 56:10.910 Also Sie müssen mir nicht diese drei Punkte hier alle vorbeten können. 56:10.910 --> 56:16.670 Aber was ich von Ihnen wissen will, ist, ob Sie eben die Idee dieses 56:16.670 --> 56:20.790 Planesweep verstanden haben, was man dort eigentlich macht. 56:21.470 --> 56:24.810 Und wie man eben dann auf den logarithmischen Zeitaufwand kommt. 56:26.950 --> 56:30.930 Und es ist eben so, dass man jede Kante genau einmal einfügt und 56:30.930 --> 56:31.610 wieder löscht. 56:31.610 --> 56:41.370 Dann haben wir also insgesamt an diesen Haltepunkten N-mal 56:41.370 --> 56:45.370 logarithmischen Aufwand, den richtigen Ort zu finden. 56:45.930 --> 56:54.330 Der Platz, den man braucht auf dieser vertikalen Linie, ist linear. 56:55.930 --> 56:59.450 Wenn ich Pech habe, könnte es sein, dass alle Kanten gleichzeitig 56:59.450 --> 57:00.570 abgespeichert sind. 57:00.570 --> 57:03.570 Aber das wäre ein sehr extremer Fall und taucht normalerweise gar 57:03.570 --> 57:03.970 nicht auf. 57:05.370 --> 57:09.430 Größenordnung N als Platz muss natürlich irgendwo das ganze Problem 57:09.430 --> 57:10.050 abspeichern. 57:10.490 --> 57:12.770 Weniger habe ich hier, also geht hier auf keinen Fall. 57:14.370 --> 57:15.970 Und das ist schon das Problem gewesen. 57:17.190 --> 57:19.710 War das ausreichend jetzt zunächst mal? 57:20.010 --> 57:20.170 Ja?