Polygon-Konvexität prüfen
Das Rechteck (0, 0), (4, 0), (4, 3), (0, 3) ist konvex: Jede Ecke dreht in dieselbe Richtung, gegen den Uhrzeigersinn. Die Pfeilspitze (0, 0), (3, 1), (0, 2), (1, 1) mischt Links- und Rechtsdrehungen und ist daher konkav. Kostenlos in Ihrem Browser.
- Kostenlos
- Läuft in Ihrem Browser
- Ohne Anmeldung
- Ihre Daten bleiben auf Ihrem Gerät
Im Browser ausführen – kostenlos
Ein Polygon-Konvexitätstest beantwortet eine grundlegende Frage der algorithmischen Geometrie: Bleibt bei einem geordneten Ring kartesischer Eckpunkte jeder Innenwinkel höchstens einhundertachtzig Grad, sodass die Form nirgendwo nach innen einbeult? Vermesser, die Katasterparzellen prüfen, Spieleentwickler, die Kollisionshüllen entwerfen, GIS-Teams, die Geofence-Polygone bereinigen, CAD-Exporter, die Konvexitätsvorgaben erzwingen, und Unterrichtswerkzeuge, die Aufgaben zu einfachen Polygonen bewerten, brauchen eine deterministische Ja-oder-Nein-Antwort, ohne eine vollständige Geometriebibliothek aufzubauen. Diese Fähigkeit nimmt eine geordnete Liste von Eckpunkten entgegen, durchläuft den geschlossenen Ring einmal und vergleicht das zweidimensionale Kreuzprodukt jedes Paares aufeinanderfolgender Kanten. Teilen alle nichtverschwindenden Kreuzprodukte dasselbe Vorzeichen, gehen alle Wendungen in dieselbe Richtung und das Polygon ist konvex; gemischte Vorzeichen bedeuten mindestens einen Reflexwinkel und das Polygon ist konkav. Null-Kreuzprodukte markieren kollineare Eckpunkte und sind erlaubt, ohne die Konvexität zu brechen.
Wie Kreuzprodukte aufeinanderfolgender Kanten die Konvexität entscheiden
Beschriften Sie die geordneten Eckpunkte V null bis V n minus eins und schließen Sie den Ring, indem Sie die Kante vom letzten zum ersten Eckpunkt als vorhanden behandeln, auch wenn der Aufrufer den Startpunkt nicht wiederholt. An jedem Eckpunkt B mit Vorgänger A und Nachfolger C bilden Sie die ausgehenden Vektoren von A nach B und von B nach C. Ihr zweidimensionales Kreuzprodukt ist der Skalar z gleich (B.x minus A.x) mal (C.y minus B.y) minus (B.y minus A.y) mal (C.x minus B.x).
Das Vorzeichen von z ist die Wendungsrichtung an B: positiv für eine Linkswendung, wenn die Ebene mit y nach oben und x nach rechts orientiert ist (gegen den Uhrzeigersinn entlang des Rands), negativ für eine Rechtswendung (im Uhrzeigersinn) und null, wenn A, B und C kollinear sind. Ein einfaches Polygon ist genau dann konvex, wenn jede nichtverschwindende Wendung dasselbe Vorzeichen teilt, was bedeutet, dass jeder Innenwinkel höchstens einhundertachtzig Grad beträgt und der Rand seinen Drehsinn nie umkehrt.
Gemischte positive und negative Wendungen beweisen einen Reflexinnenwinkel irgendwo am Ring, also ist das Polygon konkav. Der Algorithmus ist streng O(n) in der Anzahl der Eckpunkte nach einem einzigen Normalisierungsschritt, der ein abschließendes Duplikat des ersten Punkts entfernt, wenn der Aufrufer den Ring bereits geschlossen hat.
Wann sich eine Konvexitätsprüfung lohnt
Karten- und GIS-Pipelines nutzen einen Polygon-Konvexitätstest vor Algorithmen, die konvexe Eingaben voraussetzen — Clipping gegen ein konvexes Fenster, Zerlegung komplexer Regionen oder Solver, die Reflexecken ablehnen. Spiel- und Simulationsengines prüfen designerseitige Kollisionsnetze, damit eine einzige Einbeulung später keine Separating-Axis- oder GJK-Annahmen bricht. CAD- und Fertigungsexporter erzwingen Konvexitätsvorgaben für Rohlinge und Stützpolygone, bevor Geometrie an ein Schneidwerkzeug geht.
Bildungsplattformen bewerten Aufgaben «Ist dieses Polygon konvex?» mit einem deterministischen Orakel, das kollineare Mid-Edge-Eckpunkte konsistent behandelt, statt sich auf Augenschein zu verlassen. Fehlgeschlagene Validierung wird nicht berechnet.
Anwendungsfälle
GIS-Geofence- und Parzellenprüfung
Lehnen Sie konkave Kataster- und Geofence-Ringe ab oder markieren Sie sie, bevor Pipelines, die konvexe Polygone für Clipping, Puffer oder Flächenroutinen annehmen, laufen.
Prüfungen von Spiel-Kollisionshüllen
Prüfen Sie designerdefinierte 2D-Kollisionspolygone, damit konvexitätsabhängige Kollisionsalgorithmen zur Laufzeit nie eine verbeulte Hülle erhalten.
Automatische Bewertung in Unterricht und Prüfung
Bewerten Sie Aufgaben «Ist dieses Polygon konvex?» mit einem deterministischen Kreuzprodukt-Orakel, das den Wendungsdefinitionen der Lehrbücher entspricht.
Häufige Fragen
Wie prüfen Sie, ob ein Polygon konvex ist?
Senden Sie geordnete Eckpunkte als {x, y}- oder [x, y]-Paare (mindestens drei).
Was gilt, wenn einige aufeinanderfolgende Eckpunkte kollinear sind?
Null-Kreuzprodukte sind erlaubt. Kollineare Punkte in der Kantenmitte brechen die Konvexität allein nicht; nur gemischte Links- und Rechtswendungen markieren ein konkaves Polygon.
Spielt die Eckpunktreihenfolge (Uhrzeigersinn oder dagegen) eine Rolle?
Jede konsistente Orientierung ist in Ordnung. Die Antwort meldet orientation als clockwise oder counterclockwise bei Konvexität und mixed, wenn die Wendungen nicht übereinstimmen.
Was geschieht bei weniger als drei Eckpunkten?
Ein Polygon-Konvexitätstest braucht mindestens drei Eckpunkte; ungültige Eingabe wird nicht berechnet.
Was sagt mir das Ergebnis außer Ja oder Nein?
Es nennt Ihnen die Drehrichtung des Rings: gegen den Uhrzeigersinn, im Uhrzeigersinn, gemischt bei einer konkaven Form oder kollinear, wenn alle Punkte auf einer Linie liegen. Außerdem zählt es echte Drehungen und gerade durchlaufene Eckpunkte.
Verwandte Tools
Für Entwickler — API-Zugang
Alles auf dieser Seite ist auch per API verfügbar. Dieser Abschnitt richtet sich an Teams, die es in ihre eigenen Systeme einbinden möchten; alle anderen nutzen einfach das Tool oben.
Endpunkt
Authentifizierung per Bearer-Token. Ein einziger POST stellt die Aufgabe in die Warteschlange; das Ergebnis erhalten Sie per Webhook oder über einen signierten Link.
Aufruf aus Ihrem Stack
curl -X POST https://api.kit.forhosting.com/geo/polygon-is-convex \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"vertices":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3}]}'const res = await fetch("https://api.kit.forhosting.com/geo/polygon-is-convex", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"vertices": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
}
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/geo/polygon-is-convex",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"vertices": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
}
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/geo/polygon-is-convex", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"vertices":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3}]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"vertices":[{"x":0,"y":0},{"x":4,"y":0},{"x":4,"y":3},{"x":0,"y":3}]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/geo/polygon-is-convex", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Beispiel-Anfrage
{
"vertices": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
}
]
}Beispiel-Antwort
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "geo.polygon_is_convex",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}Die API arbeitet asynchron: Sie erhalten sofort eine task_id. Polling ist mit 1 Anfrage pro Sekunde erlaubt.
Preis
Der Preis steht auf der Seite – keine Tokens, keine Credits. Fehlgeschlagene Aufgaben werden nicht berechnet.
Fehler
| HTTP | Code | Bedeutung |
|---|---|---|
401 | unauthorized | Der API-Schlüssel fehlt oder ist ungültig – prüfen Sie den Authorization-Header (Bearer). |
402 | insufficient_balance | Ihr Guthaben reicht für diese Aufgabe nicht aus – Aufladungen verfallen nicht. |
404 | unknown_type | Unbekannter Aufgabentyp – prüfen Sie das Feld „type“ gegen den Katalog. |
429 | rate_limited | Zu viele Anfragen – warten Sie kurz; Polling ist mit 1 Anfrage pro Sekunde erlaubt. |
Technische Hinweise
Wie Kreuzprodukte aufeinanderfolgender Kanten die Konvexität entscheiden
Sind alle Kreuzprodukte null, liegen die Eckpunkte auf einer Geraden; die Form hat keine Fläche und dieser Endpunkt meldet is_convex false mit orientation collinear, statt eine konvexe Hülle zu erfinden.
Eingabevertrag, Antwortform und Fehlerverhalten
Jeder Punkt kann ein Objekt mit endlichen x und y (oder lon- und lat-Aliasen) oder ein Zwei-Element-Array [x, y] sein. Ein abschließender Eckpunkt, der mit dem ersten identisch ist, wird automatisch verworfen, sodass sowohl GeoJSON-artige geschlossene Ringe als auch offene Unterrichtslisten funktionieren. Beispiel: das Quadrat (0,0), (4,0), (4,3), (0,3) ist konvex mit gegenläufiger Orientierung. Kombinieren Sie den Booleschen Wert mit Ihrem eigenen Zeichen-Code, falls Sie eine Skizze brauchen; dieser Endpunkt klassifiziert nur Konvexität und liefert weder Plots noch Hüllen noch Triangulation. Senden Sie per POST einen JSON-Körper mit einem Pflichtfeld: vertices, ein geordnetes Array mit mindestens drei Punkten. Die Aliase points, polygon und coords werden mit derselben Bedeutung akzeptiert, sodass vorhandene GIS-Payloads ohne Umbenennung passen. Weniger als drei Eckpunkte nach dieser Normalisierung, Nicht-Array-Payloads, fehlende Koordinaten und nicht-endliche Zahlen scheitern mit invalid_input und werden nicht berechnet. Bei Erfolg enthält der Körper is_convex als Booleschen Wert; n als normalisierte Eckpunktanzahl; orientation als counterclockwise, clockwise, mixed oder collinear; turn_count als Anzahl nichtverschwindender Wendungen; zero_turns als kollineare Zählung; eine formula-Zeichenkette, die die Kreuzprodukt-Identität neu formuliert; und vertices als {x, y}-Objekte in Ringreihenfolge. Der konkave Pfeil (0,0), (3,1), (0,2), (1,1) mischt Wendungsvorzeichen und liefert is_convex false.
Wo eine API zur Polygon-Konvexität echten Nutzen stiftet
Weil die Implementierung reines Parse-Tier-A ist, kostet jeder erfolgreiche Aufruf den veröffentlichten Basispreis $0.002 ohne Modell-Tokens und ohne ausgehendes Netz. Halten Sie Ringe bescheiden, pinnen Sie is_convex und orientation in Tests, und Sie erhalten reproduzierbare Konvexitätskennzeichnungen für Geofences, Unterrichtskontrollen und Edge-Worker, ohne eine vollständige Stack der algorithmischen Geometrie selbst auszuliefern.
Technische Fragen
Was kostet der Polygon-Konvexitätstest?
Das Browser-Werkzeug ist kostenlos. API-Anfragen nutzen vorausbezahltes KIT-Guthaben zu $0.002 pro erfolgreichem Aufruf; ungültige Eingabe wird nicht berechnet.