Das PIP-Problem (Punkt-in-Polygon) ist das Problem, zu bestimmen, ob ein Punkt ein beliebiges Polygon ist. Dies mag für ein einfaches Polygon wie ein Quadrat oder ein Dreieck trivial klingen, wird jedoch mit komplexeren Polygonen wie dem im folgenden Beispiel komplexer. In diesem Beitrag wird der gerade-ungerade Algorithmus, auch Kreuzungsnummernalgorithmus oder Jordan-Algorithmus genannt (da er mit dem Jordan-Kurvensatz bewiesen werden kann) eingeführt.

Beschreibung des Algorithmus

Das Grundprinzip hinter dem Even-Odd aka. Jordan aka. Der Kreuzzahlalgorithmus besteht darin, zu zählen, wie oft eine Linie vom betreffenden Punkt (in einer beliebigen Richtung) eine Kante des Polygons kreuzt. Diese Linie befindet sich immer außerhalb des Polygons an ihrem “Ende” im Unendlichen. Wenn sie sich also am Anfang (dem fraglichen Punkt) innerhalb des Polygons befindet, muss sie das Polygon irgendwann verlassen und eine Kante überqueren. Es kann das Polygon erneut eingeben (siehe Beispiel unten), muss jedoch immer wieder verlassen werden, wodurch die Gesamtzahl der Kreuzungen ungerade wird, wenn sich der Punkt im Polygon befindet. Das Gegenteil ist auch wahr; Wenn die Anzahl der Kreuzungen gerade ist, liegt der Punkt immer außerhalb des Polygons. Dies ist der oben erwähnte Jordan-Kurvensatz.

Der Algorithmus überprüft jede Kante des Polygons in einer Schleife, um festzustellen, ob die Linie vom Punkt bis zur Unendlichkeit diese kreuzt. Im folgenden Beispiel wird diese Linie vom Punkt bis unendlich nach rechts gezeichnet, kann jedoch eine beliebige Richtung haben.

Die Schritte sind:

1. Für jede Kante im Polygon:
2. Wenn die Kante die imaginäre Linie vom Punkt bis unendlich kreuzt, erhöhen Sie einen Zähler.
3. Wenn der Zähler am Ende ungleichmäßig ist, geben Sie true zurück. Andernfalls geben Sie false zurück.

Eine einfache boolesche Variable, die jedes Mal invertiert wird, wenn eine Kreuzung gefunden wird, ist ebenfalls möglich.

Beispiel des Algorithmus

Betrachten Sie das folgende Polygon mit 8 Kanten und zwei Punkten, für die wir bestimmen möchten, ob sie sich im Polygon befinden:

Die Schritte, die der Algorithmus für dieses Polygon ausführt, um zu bestimmen, ob sich der erste (grüne) Punkt im Polygon befindet, beginnen an der ersten Kante:

1. Grüner Punkt kreuzt Kante 8
2. Der grüne Punkt kreuzt nicht die Kante 1
3. Grüner Punkt kreuzt Kante 2
4. Der grüne Punkt kreuzt nicht die Kante 3
5. Grüner Punkt kreuzt Kante 4
6. Grüner Punkt kreuzt Kante 5
7. Grüner Punkt kreuzt nicht die Kante 6
8. Der grüne Punkt kreuzt nicht die Kante 7
9. Gesamtzahl der Überfahrten: 4
10. Gerade Anzahl von Kantenübergängen, daher befindet sich der Punkt nicht im Polygon

Die Schritte, die der Algorithmus für dieses Polygon ausführt, um zu bestimmen, ob sich der zweite (rote) Punkt im Polygon befindet, beginnen an der ersten Kante:

1. Der rote Punkt kreuzt nicht die Kante 8
2. Der rote Punkt kreuzt nicht die Kante 1
3. Der rote Punkt kreuzt nicht die Kante 2
4. Der rote Punkt kreuzt nicht die Kante 3
5. Roter Punkt kreuzt nicht die Kante 4
6. Roter Punkt kreuzt Kante 5
7. Der rote Punkt kreuzt nicht die Kante 6
8. Der rote Punkt kreuzt nicht die Kante 7
9. Gesamtzahl der Überfahrten: 1
10. Ungleichmäßige Anzahl von Kantenübergängen, daher befindet sich der Punkt im Polygon

Laufzeitkomplexität des Algorithmus

Die Laufzeitkomplexität des Jordan-Algorithmus aka. Crossing Number Algorithmus aka. Der geradzahlige Algorithmus zur Lösung des Punkt-in-Polygon-Problems für einen einzelnen Punkt ist in Bezug auf die Anzahl der Kanten linear. Dies wird deutlich, wenn man sich den Code ansieht, der eine einzelne Schleife über den Kanten enthält, ohne Rekursion oder weitere Funktionsaufrufe oder Schleifen.

Formal ist die Laufzeit *O(| V |), | V |: = Anzahl der Kanten im Polygon *.

Speicherkomplexität des Algorithmus

Die Speicherkomplexität ist auch linear w.r.t. die Anzahl der Kanten, da zusätzlich zum Polygon nur Variablen mit fester Größe gespeichert werden müssen. Darüber hinaus kann der Algorithmus online implementiert werden, sodass keine vergangenen Kanten während der Schleife betrachtet werden müssen, sodass sie aus dem Speicher entfernt werden können (oder vergleichbare Maßnahmen zur Leistungsverbesserung).

Python

Python™ ist eine interpretierte Sprache, die für viele Zwecke verwendet wird, von der eingebetteten Programmierung bis zur Webentwicklung, wobei einer der größten Anwendungsfälle die Datenwissenschaft ist.

In Python zu “Hello World”

Das Wichtigste zuerst - so können Sie Ihre erste Codezeile in Python ausführen:

1. Laden Sie die neueste Version von Python von python.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert. Viele Technologien erfordern dies aufgrund der mit Python 3 eingeführten Änderungen weiterhin.
2. Öffnen Sie ein Terminal, stellen Sie sicher, dass der Befehl “python” oder “python3” funktioniert und dass der Befehl, den Sie verwenden, sich auf die Version bezieht, die Sie gerade installiert haben, indem Sie “python3 —version” oder “python —version” ausführen. Wenn der Fehler “Befehl nicht gefunden” (oder ähnliches) angezeigt wird, starten Sie die Befehlszeile, und, falls dies nicht hilft, Ihren Computer neu. Wenn das Problem weiterhin besteht, finden Sie hier einige hilfreiche Fragen zu StackOverflow für Windows, Mac und Linux.
3. Sobald dies funktioniert, können Sie das folgende Snippet ausführen: print("Hello World"). Sie haben zwei Möglichkeiten, dies auszuführen: 3.1 Führen Sie “python” in der Befehlszeile aus, fügen Sie einfach das Code-Snippet ein und drücken Sie die Eingabetaste (Drücken Sie “STRG + D” oder schreiben Sie “exit ()” und drücken Sie die Eingabetaste, um das Programm zu beenden). 3.2 Speichern Sie das Snippet in einer Datei und nennen Sie es etwas, das mit “.py” endet, z.B. hello_world.py und führepython path / to / hello_world.py aus. Tipp: Verwenden Sie den Befehl ls (dir in Windows), um herauszufinden, welche Dateien sich in dem Ordner befinden, in dem sich Ihre Befehlszeile gerade befindet.

Das wars schon! Beachten Sie, dass das Drucken von etwas auf die Konsole in Python nur eine einzige Zeile ist - diese niedrige Eintrittsbarriere und das Fehlen von erforderlichem Boilerplate-Code machen einen großen Teil der Attraktivität von Python aus.

Grundlagen in Python

Um in Python implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen.

Variablen und Arithmetik

Variablen in Python sind wirklich einfach. Sie müssen weder einen Datentyp deklarieren noch deklarieren, dass Sie eine Variable definieren. Python weiß das implizit.

a = 1
b = {'c':2}

print(a + b['c']) # prints 3

Arrays

Das Arbeiten mit Arrays ist in Python ähnlich einfach:

arr = ["Hello", "World"]

print(arr[0]) # Hello
print(arr[1]) # World
# print(arr[2]) # IndexError

arr.append("!")

print(arr[2]) # !

Wie diejenigen von Ihnen, die mit anderen Programmiersprachen wie Java vertraut sind, möglicherweise bereits bemerkt haben, handelt es sich nicht um native Arrays, sondern um Listen, die wie Arrays gekleidet sind. Dies wird durch die Tatsache deutlich, dass keine Größe angegeben werden muss und Elemente nach Belieben angehängt werden können. Tatsächlich druckt print (type (arr)) <class ‘list’> `. Dies bedeutet, dass Arrays in Python erheblich langsamer sind als in Programmiersprachen niedrigerer Ebene. Es gibt jedoch Pakete wie numpy, die echte Arrays implementieren, die erheblich schneller sind.

Bedingungen

Wie die meisten Programmiersprachen kann Python “if-else”-Anweisungen ausführen:

value = 1
if value==1:
    print("Value is 1")
elif value==2:
    print("Value is 2")
else:
    print("Value is something else")

Python hat jedoch keine “case”-Anweisungen, die andere Sprachen wie Java haben. Meiner Meinung nach kann dies durch die Einfachheit der “if”-Anweisungen entschuldigt werden, die den “syntaktischen Zucker” von “case” -Anweisungen überflüssig machen.

Schleifen

Python unterstützt sowohl “for” - als auch “while” -Schleifen sowie “break” - und “continue” -Anweisungen. Es gibt zwar keine “do-while” -Schleifen, aber eine Reihe von integrierten Funktionen, die das Schleifen sehr bequem machen, wie “enumerate” oder “range”. Hier sind einige Beispiele:

value = 10
while value > 0:
    print(value)
    value -= 1

for index, character in enumerate("banana"):
    print("The %d-th letter is a %s" % (index + 1, character))

Beachten Sie, dass Python nicht die gemeinsame Iteratorvariablensyntax anderer Sprachen verwendet (z. B. for (int i = 0; i <arr.length; i ++) in Java) - hierfür kann die Funktion enumerate verwendet werden.

Funktionen

Funktionen in Python sind einfach zu definieren und erfordern zum Guten oder Schlechten keine Angabe von Rückgabe- oder Argumenttypen. Optional kann ein Standardwert für Argumente angegeben werden:

def print_something(something="Hello World"):
    print(something)
    return "Success"

print_something()
print(print_something("banana"))

 (Dies druckt “Hallo Welt”, “Banane” und dann “Erfolg”)

Syntax

Sie haben vielleicht bemerkt, dass Python keine geschweiften Klammern ({}) verwendet, um Codeblöcke in Bedingungen, Schleifen, Funktionen usw. zu umgeben. Dies liegt daran, dass Python als Teil seiner Syntax von Einrückungen (Leerzeichen) abhängt. Während Sie in Java beliebig viele Leerzeichen (Leerzeichen, Tabulatoren, Zeilenumbrüche) hinzufügen und löschen können, ohne das Programm zu ändern, wird die Syntax in Python dadurch unterbrochen. Dies bedeutet auch, dass keine Semikolons erforderlich sind, was in anderen Sprachen ein häufiger Syntaxfehler ist.

Fortgeschrittene Kenntnisse in Python

Python wurde erstmals 1990 veröffentlicht und ist ein Multi-Paradigma. Das bedeutet, dass es in erster Linie zwingend und funktional ist, aber auch objektorientierte und reflektierende Elemente enthält. Es ist dynamisch typisiert, bietet jedoch seit Version 3.5 Syntax für die schrittweise Eingabe. Für weitere Informationen hat Python einen großartigen Artikel Wikipedia.