Approximation d'une enveloppe concave par coordonnées

Cette approximation d'enveloppe concave part de ce contour extérieur fiable, puis affine les longues arêtes à l'aide de points intérieurs inutilisés jusqu'au seuil demandé ou jusqu'à ce qu'aucune insertion valide ne subsiste. Le résultat déterministe fournit le contour ordonné, les longueurs d'arête, le périmètre, l'aire et le nombre d'arêtes impossibles à raccourcir. Vous pouvez ainsi contrôler l'approximation au lieu de la prendre pour une solution géométrique exacte.

Choisissez des coordonnées et un seuil pertinents

Fournissez au moins trois points plans sous forme de coordonnées numériques x et y, ainsi qu'un seuil de longueur d'arête strictement positif. Les coordonnées peuvent représenter des positions cartographiques projetées, des unités de dessin, des mesures ou tout autre repère cartésien bidimensionnel. Elles doivent partager la même échelle : ne mélangez pas des degrés de longitude et des distances en mètres si vous souhaitez que le seuil conserve un sens physique. Un seuil plus faible demande à l'algorithme de suivre plus fidèlement les points disponibles, tandis qu'un seuil plus élevé préserve davantage le contour convexe. Ce seuil est un objectif et non une garantie, car un jeu clairsemé peut ne contenir aucun point intérieur sûr capable de fractionner une arête donnée. Les coordonnées en double sont ignorées. Il doit rester au moins trois points uniques non colinéaires, puisqu'une droite ne forme pas un polygone. Pour des données de latitude et de longitude, projetez correctement les coordonnées avant d'employer un seuil exprimé comme une distance. L'outil effectue une géométrie plane et n'applique aucun modèle terrestre sphérique ou ellipsoïdal. Commencez par un seuil proche de l'espacement que vous jugez significatif, puis comparez le contour obtenu aux points d'origine.

Comprenez le mécanisme d'affinage du contour

L'algorithme calcule d'abord une enveloppe convexe déterministe avec la méthode de la chaîne monotone. Il examine ensuite les arêtes du contour qui dépassent le seuil indiqué, en commençant par la plus longue. Pour chacune, il recherche des points inutilisés situés à l'intérieur du polygone courant et capables de remplacer l'arête par deux segments plus courts sans croiser une autre partie du contour. Le candidat qui minimise le plus long segment de remplacement est retenu; les égalités sont départagées de manière stable selon la longueur totale puis l'ordre d'entrée initial. Après chaque insertion, la sélection recommence puisque le polygone a changé. L'affinage s'arrête lorsque toutes les arêtes respectent l'objectif ou lorsqu'aucun point restant ne peut améliorer sans risque une longue arête. Cette construction privilégie un résultat prévisible et explicable sans prétendre résoudre les différentes définitions d'une enveloppe concave exacte. Elle n'invente jamais de sommet, ne déplace aucune coordonnée, n'utilise aucun échantillonnage aléatoire et ne contacte aucun service distant. L'enveloppe renvoyée est une liste ouverte de sommets ordonnés, dont le dernier se raccorde au premier. Les longueurs suivent le même ordre cyclique.

Examinez les limites avant d'exploiter le polygone

Consultez unresolved_long_edges chaque fois que le seuil revêt une importance opérationnelle. Une valeur nulle signifie que toutes les arêtes renvoyées satisfont l'objectif; une valeur positive indique que la géométrie disponible ne permettait pas de l'atteindre sans croisement, déplacement vers l'extérieur ou remplacement incapable de raccourcir l'arête. Il s'agit d'une information utile, et non d'un échec dissimulé. L'approximation peut également différer des formes alpha, des enveloppes par plus proches voisins, des filtres de triangulation ou des méthodes propres au tracé des côtes. Comparez plusieurs méthodes lorsque la topologie entraîne des conséquences juridiques, scientifiques ou de sécurité. L'aire et le périmètre décrivent le polygone plan renvoyé dans le système de coordonnées fourni; ce ne sont pas des mesures géodésiques. Superposez le contour ordonné aux points sources afin de vérifier que le seuil restitue les groupes et les rentrants souhaités. Si le contour demeure trop large, ajoutez des points représentatifs ou réduisez le seuil; s'il devient trop détaillé, augmentez-le. La capacité accepte au maximum 500 éléments afin de borner les contrôles répétés d'intersection et de rester adaptée au navigateur comme à l'automatisation déterministe par API.