Test de convexité d'un polygone
Le rectangle (0, 0), (4, 0), (4, 3), (0, 3) est convexe : chaque coin tourne dans le même sens, antihoraire. La pointe de flèche (0, 0), (3, 1), (0, 2), (1, 1) mêle virages à gauche et à droite : elle est concave. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Un test de convexité de polygone répond à une question fondamentale de géométrie algorithmique : étant donné un anneau ordonné de sommets cartésiens, chaque angle intérieur reste-t-il au plus égal à cent quatre-vingts degrés de sorte que la forme ne se creuse jamais vers l'intérieur ? Les géomètres qui valident des parcelles cadastrales, les développeurs de jeux qui définissent des enveloppes de collision, les équipes SIG qui nettoient des polygones de géorepérage, les exportateurs CAO qui imposent des contraintes de convexité et les outils de classe qui notent des exercices sur les polygones simples ont tous besoin d'une réponse déterministe oui ou non sans déployer une bibliothèque géométrique complète. Cette capacité accepte une liste ordonnée de sommets, parcourt l'anneau fermé une seule fois et compare le produit croisé bidimensionnel de chaque paire d'arêtes consécutives. Lorsque chaque produit croisé non nul partage le même signe, chaque virage va dans le même sens et le polygone est convexe ; des signes mixtes indiquent au moins un angle rentrant et le polygone est concave. Les produits croisés nuls marquent des sommets colinéaires et sont autorisés sans rompre la convexité.
Comment les produits croisés d'arêtes consécutives décident de la convexité
Étiquetez les sommets ordonnés V zéro jusqu'à V n moins un et fermez l'anneau en traitant l'arête du dernier sommet vers le premier comme présente même lorsque l'appelant ne répète pas le point de départ. À chaque sommet B avec le sommet précédent A et le suivant C, formez les vecteurs sortants de A vers B et de B vers C. Leur produit croisé bidimensionnel est le scalaire z égal à (B.x moins A.x) multiplié par (C.y moins B.y) moins (B.y moins A.y) multiplié par (C.x moins B.x).
Le signe de z est le sens du virage en B : positif pour un virage à gauche lorsque le plan est orienté avec y vers le haut et x vers la droite (parcours antihoraire du contour), négatif pour un virage à droite (parcours horaire), et zéro lorsque A, B et C sont colinéaires.
Un polygone simple est convexe si et seulement si chaque virage non nul partage le même signe, ce qui signifie que chaque angle intérieur est au plus de cent quatre-vingts degrés et que le contour n'inverse jamais son sens de rotation. Des virages positifs et négatifs mélangés prouvent un angle intérieur rentrant quelque part sur l'anneau, donc le polygone est concave. L'algorithme est strictement O(n) en le nombre de sommets après une seule passe de normalisation qui supprime un doublon final du premier point lorsque l'appelant a déjà fermé l'anneau.
Quand vérifier la convexité d'un polygone
Les pipelines de cartographie et de SIG utilisent un test de convexité de polygone avant des algorithmes qui supposent une entrée convexe — découpage contre une fenêtre convexe, décomposition de régions complexes, ou alimentateurs de solveurs qui rejettent les sommets rentrants. Les moteurs de jeux et de simulation valident des maillages de collision définis par les concepteurs afin qu'un seul creux ne casse pas ensuite les hypothèses d'axes de séparation ou de GJK.
Les exportateurs CAO et de fabrication imposent des contraintes de convexité sur les flans et les polygones de support avant d'envoyer la géométrie à un outil de coupe. Les plateformes éducatives notent les items « ce polygone est-il convexe ? » avec un oracle déterministe qui traite de façon cohérente les sommets colinéaires en milieu d'arête au lieu de s'en remettre à l'œil.
La validation échouée ne consomme pas le solde.
Cas d’usage
Validation de géorepérages et de parcelles SIG
Rejetez ou signalez les anneaux cadastraux et de géorepérage concaves avant les pipelines qui supposent des polygones convexes pour le découpage, le tampon ou les routines d'aire.
Contrôles d'enveloppes de collision de jeu
Validez les polygones de collision 2D définis par les concepteurs afin que les algorithmes dépendant de la convexité ne reçoivent jamais une enveloppe bosselée à l'exécution.
Notation automatique en classe et aux examens
Notez les items « ce polygone est-il convexe ? » avec un oracle déterministe de produits croisés aligné sur les définitions de sens de virage des manuels.
Questions fréquentes
Comment tester si un polygone est convexe ?
Envoyez des sommets ordonnés sous forme de paires {x, y} ou [x, y] (au moins trois).
Que se passe-t-il si certains sommets consécutifs sont colinéaires ?
Les produits croisés nuls sont autorisés. Les points colinéaires en milieu d'arête ne rompent pas à eux seuls la convexité ; seuls des virages mixtes à gauche et à droite marquent un polygone concave.
L'ordre des sommets (horaire ou antihoraire) importe-t-il ?
Toute orientation cohérente convient. La réponse signale orientation comme clockwise ou counterclockwise lorsque le polygone est convexe, et mixed lorsque les virages divergent.
Que se passe-t-il avec moins de trois sommets ?
Un test de convexité de polygone nécessite au moins trois sommets ; l'entrée invalide n'est pas facturée.
Que m'indique le résultat en plus du oui ou du non ?
Il donne le sens de rotation de l'anneau : antihoraire, horaire, mixte pour une figure concave, ou aligné quand tous les points sont sur une droite. Il compte aussi les vrais virages et les sommets où le contour continue tout droit.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre 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)Exemple de requête
{
"vertices": [
{
"x": 0,
"y": 0
},
{
"x": 4,
"y": 0
},
{
"x": 4,
"y": 3
},
{
"x": 0,
"y": 3
}
]
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "geo.polygon_is_convex",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Comment les produits croisés d'arêtes consécutives décident de la convexité
Lorsque chaque produit croisé est nul, les sommets sont sur une seule droite ; la forme n'a pas d'aire et ce point de terminaison signale is_convex false avec orientation collinear au lieu d'inventer une enveloppe convexe.
Contrat d'entrée, forme de la réponse et comportement d'erreur
Un sommet final identique au premier est supprimé automatiquement, de sorte que les anneaux fermés style GeoJSON et les listes ouvertes de classe fonctionnent tous deux. Exemple : le carré (0,0), (4,0), (4,3), (0,3) est convexe avec orientation antihoraire. Associez le booléen à votre propre code de dessin si vous avez besoin d'un croquis ; ce point de terminaison ne classe que la convexité et n'émet ni tracés, ni enveloppes, ni triangulation. Envoyez en POST un corps JSON avec un champ obligatoire : vertices, un tableau ordonné d'au moins trois points. Chaque point peut être un objet avec x et y finis (ou les alias lon et lat) ou un tableau de deux éléments [x, y]. Les alias points, polygon et coords sont acceptés avec le même sens afin que les charges utiles SIG existantes s'intègrent sans renommage. Moins de trois sommets après cette normalisation, des charges qui ne sont pas des tableaux, des coordonnées manquantes et des nombres non finis échouent avec invalid_input et ne sont pas facturés. En cas de succès le corps inclut is_convex en booléen ; n comme le nombre de sommets normalisé ; orientation comme counterclockwise, clockwise, mixed ou collinear ; turn_count comme le nombre de virages non nuls ; zero_turns comme le décompte colinéaire ; une chaîne formula qui reformule l'identité du produit croisé ; et vertices renvoyés comme objets {x, y} dans l'ordre de l'anneau. La fléchette concave (0,0), (3,1), (0,2), (1,1) mélange les signes de virage et renvoie is_convex false.
Où une API de convexité de polygone apporte une valeur concrète
Comme l'implémentation est pure parse de niveau A, chaque appel réussi coûte le prix de base publié $0.002 sans jetons de modèle ni réseau sortant. Gardez des anneaux modestes, figez is_convex et orientation dans les tests, et vous obtenez des étiquettes de convexité reproductibles pour les géorepérages, les contrôles de classe et les workers en périphérie sans déployer une pile complète de géométrie algorithmique.
Questions techniques
Combien coûte le test de convexité de polygone ?
L'outil dans le navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; l'entrée invalide n'est pas facturée.