Punkt-in-Polygon in Javascript

Gepostet: , Zuletzt aktualisiert:

/**
 * Performs the even-odd-rule Algorithm (a raycasting algorithm) to find out whether a point is in a given polygon.
 * This runs in O(n) where n is the number of edges of the polygon.
 *
 * @param {Array} polygon an array representation of the polygon where polygon[i][0] is the x Value of the i-th point and polygon[i][1] is the y Value.
 * @param {Array} point   an array representation of the point where point[0] is its x Value and point[1] is its y Value
 * @return {boolean} whether the point is in the polygon (not on the edge, just turn < into <= and > into >= for that)
 */
const pointInPolygon = function (polygon, point) {
    //A point is in a polygon if a line from the point to infinity crosses the polygon an odd number of times
    let odd = false;
    //For each edge (In this case for each point of the polygon and the previous one)
    for (let i = 0, j = polygon.length - 1; i < polygon.length; i++) {
        //If a line from the point into infinity crosses this edge
        if (((polygon[i][1] > point[1]) !== (polygon[j][1] > point[1])) // One point needs to be above, one below our y coordinate
            // ...and the edge doesn't cross our Y corrdinate before our x coordinate (but between our x coordinate and infinity)
            && (point[0] < ((polygon[j][0] - polygon[i][0]) * (point[1] - polygon[i][1]) / (polygon[j][1] - polygon[i][1]) + polygon[i][0]))) {
            // Invert odd
            odd = !odd;
        }
        j = i;

    }
    //If the number of crossings was odd, the point is in the polygon
    return odd;
};

module.exports = {pointInPolygon}

Über den Algorithmus und die Programmiersprache in diesem Snippet:

Punkt-in-Polygon Algorithmus

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:

Punkt im Polygon Jordan (gerade-ungerade) Algorithmus Beispiel Polygon und Punkte

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).

JavaScript

JavaScript ist eine interpretierte Skriptsprache, die zuvor hauptsächlich in Webseiten verwendet wurde (die in Browsern ausgeführt werden) und seitdem über node.js auch für Back-End- und andere Aufgaben beliebt ist

Während es einen Großteil seiner Syntax von Java entlehnt, ist es eine ganz andere Sprache und sollte nicht verwechselt werden.

Getting to “Hello World” in JavaScript

Das Wichtigste zuerst - hier erfahren Sie, wie Sie Ihre erste Codezeile in JavaScript ausführen können. Wenn Sie JavaScript für das Backend verwenden möchten, lesen Sie das Kapitel zum Drucken von Hello World mit Node.js. Wenn Sie JavaScript im Frontend (d. H. Auf Webseiten) verwenden möchten, lesen Sie das Kapitel zum Drucken von Hello World im Browser.

Getting to “Hello World” in JavaScript using the browser

  1. Erstellen Sie eine Datei mit dem Namen hello_world.html
  2. Öffnen Sie es mit einem Texteditor (z. B. Sublime Text oder nur mit dem Standard-Windows-Editor).
  3. Fügen Sie den folgenden Codeausschnitt ein:
<html>
<head>
    <script type="application/javascript">
        // This prints to the browsers console
        console.log("Hello World")
        // This opens a popup
        alert("Hello world")
    </script>
</head>
<body>
    (Website content)
</body>
</html>
  1. Öffnen Sie diese Datei mit Ihrem Browser (indem Sie den Speicherort in die Adressleiste eingeben).
  2. Sie sollten ein Popup mit der Aufschrift “Hallo Welt” sehen.
  3. Wenn Sie die Browserkonsole verwenden (z. B. in Chrome: Rechtsklick -> Überprüfen), wird diese auch dort gedruckt.

Der Grund, warum wir das Skript in HTML verpacken, ist, dass der Browser das JavaScript ansonsten nicht ausführt, sondern nur dessen Inhalt anzeigt.

Getting to “Hello World” in JavaScript using Node.js

  1. Laden Sie die neueste Version von Node.js von nodejs.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert.
  2. Öffnen Sie ein Terminal und stellen Sie sicher, dass der Befehl node funktioniert. Wenn der Fehler “Befehl nicht gefunden” (oder ähnlich) 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 jede Plattform:

  3. Sobald dies funktioniert, kopieren Sie das folgende Snippet in eine Datei mit dem Namen hello_world.js:

    console.log("Hello World");
  4. Wechseln Sie das Verzeichnis, indem Sie “cd path / to / helloworld” eingeben und dann “node helloworld.js” ausführen. Dies sollte “Hello World” auf Ihrem Terminal drucken.

Das ist es! Beachten Sie, dass die Eintrittsbarriere ähnlich niedrig ist wie bei Python und vielen anderen Skriptsprachen.

Fundamentals in JavaScript

Um in JavaScript implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen. Jedes der folgenden Snippets kann mit Node.js einzeln ausgeführt werden, da kein Boilerplate erforderlich ist. Im Browser muss der Code wie im Hello World-Beispiel für den oben gezeigten Browser von HTML umgeben sein.

Variables and Arithmetic

Variablen in JavaScript werden dynamisch typisiert, dh der Inhalt einer Variablen wird zur Laufzeit festgelegt und muss beim Schreiben des Codes nicht angegeben werden.

var number = 5;
var decimalNumber = 3.25;
var result = number * decimalNumber;
var callout = "The number is ";
// In this instance, the values are concatenated rather than added because one of them is a String.
console.log(callout + result);

Dies wird “The number is 16.25” drucken.

Arrays

Arrays in JavaScript werden als Objekte implementiert, wobei der Index nur der Name der Eigenschaft ist. Dies macht sie dynamisch dimensioniert. Die gesamten Konzepte von Objekten und Arrays werden in JavaScript zusammengeführt, wie das folgende Snippet zeigt.

var integers = {}; // initialized as object
integers[3] = 42; // assigned using array index
console.log(integers["3"]); // Accessed using property name, prints "42"

var strings = ["Hello"]; // strings[0] is now Hi
strings[2] = "World"; // index 1 skipped
strings.beautiful = "Beautiful" // Assigned using property name

console.log(strings[0] + " " + strings["beautiful"] + " " + strings[2]); // Prints "Hello World"

Conditions

Wie die meisten Programmiersprachen kann JavaScript “if-else” -Anweisungen ausführen. Darüber hinaus kann JavaScript auch “switch-case” -Anweisungen ausführen.

var value = 5;
if(value === 5){
    console.log("Value is 5");
} else if(value < 5){
    console.log("Value is less than 5");
} else {
    console.log("Value is something else");
}

switch (value){
    case 1:
        console.log("Value is 1");
        break; // Don't go further down the cases
    case 2:
        console.log("Value is 2");
        break; // Don't go further down the cases
    case 3:
        console.log("Value is 3");
        break; // Don't go further down the cases
    case 4:
        console.log("Value is 4");
        break; // Don't go further down the cases
    case 5:
        console.log("Value is 5");
        break; // Don't go further down the cases
    default:
        console.log("Value is something else");
}

Der obige JavaScript-Code gibt zweimal “Wert ist 5” aus.

Schleifen

JavaScript unterstützt sowohl for-, while- als auch do while-Schleifen. Die Anweisungen break undcontinue werden ebenfalls unterstützt. Das folgende Beispiel zeigt die Unterschiede:

var value = 2;
for (var i = 0; i < value; i++) {
    console.log(i);
}
while (value > 0) {
    console.log(value);
    value--;
}
do {
    console.log(value);
    value--;
} while (value > 0);

Dadurch wird Folgendes auf das Terminal gedruckt:

0
1
2
1
0

Beachten Sie die letzte “0”: Sie wird gedruckt, weil in der “do-while” -Schleife im Vergleich zur “while” -Schleife. Der Codeblock wird mindestens einmal ausgeführt, bevor die Bedingung überprüft wird.

Funktionen

Funktionen in JavaScript können mit vielen verschiedenen Syntaxen deklariert werden, z. B. als Objekteigenschaften, als Variablen oder in neueren JavaScript-Versionen als Teil einer Klasse.

Hier ist ein Beispiel für eine JavaScript-Funktion als Variable:

var my_function = function(){
    console.log("Hello World")
}

my_function()

Hier ist ein Beispiel für eine JavaScript-Funktion als Objekteigenschaft:

var function_object = {}
function_object.my_function = function(){
    console.log("Hello World")
}

function_object.my_function()

Und hier ist ein Beispiel für den Aufruf einer Funktion eines Objekts einer Klasse:

class FunctionClass {
    my_function(){
        console.log("Hello World")
    }
}

new FunctionClass().my_function();

(Alle diese Beispiele drucken “Hello World”.)

Syntax

Wie bereits erwähnt, teilt JavaScript einen Großteil seiner Syntax mit Java. JavaScript erfordert die Verwendung von geschweiften Klammern ({}), um Codeblöcke in Bedingungen, Schleifen, Funktionen usw.; Es sind nicht immer Semikolons am Ende von Anweisungen erforderlich, aber ihre Verwendung wird empfohlen, da ihre Verwendung bedeutet, dass die Verwendung von Leerzeichen für die bevorzugte Formatierung (z. B. Einrücken von Codeteilen) den Code nicht beeinflusst.

Fortgeschrittenes Wissen in JavaScript

JavaScript wurde erstmals 1993 veröffentlicht und ist ein Multi-Paradigma.

Es ist in erster Linie ereignisgesteuert und funktional, folgt aber auch objektorientierten und imperativen Paradigmen. Es ist dynamisch typisiert, bietet jedoch in neueren Versionen und Dialekten wie TypeScript eine gewisse statische Typisierung. Für weitere Informationen hat JavaScript einen großartigen Artikel Wikipedia.