Comment générer un polygone convexe aléatoire?

Question

J'essaie de concevoir une méthode pour générer des polygones convexes 2D aléatoires. Il doit avoir les propriétés suivantes:

• les coordonnées doivent être des entiers;
• le polygone doit être à l'intérieur d'un carré avec des coins (0, 0) et (C, C), où C est donné;
• le polygone doit avoir un nombre de sommets situés près d'un nombre donné N.

Par exemple, générer des polygones aléatoires qui ont 10 sommets et se situent à l'intérieur de crochets [0..100] x [0..100] .

Ce qui rend cette tâche difficile, c'est le fait que les coordonnées doivent être des entiers.

L'approche que j'ai essayée était de générer un ensemble aléatoire de points dans le carré donné et de calculer la coque convexe de ces points. Mais la coque convexe résultante est de très petits sommets par rapport à N.

Des idées?

Answer 1

Ce n'est pas tout à fait complet, mais il peut vous donner quelques idées.

Reculez si N < 3. Générez un cercle d'unité avec N sommets et faites-le tourner au hasard [0..90] degrés.

Extruder aléatoirement chaque sommet vers l'extérieur à partir de l'origine, et utiliser le signe du produit croisé entre chaque paire de sommets adjacents et l'origine pour déterminer la convexité. C'est l'étape où il y a des compromis entre la vitesse et la qualité. Après avoir configuré vos sommets, trouvez le sommet ayant la plus grande magnitude depuis l'origine. Divisez chaque sommet de cette magnitude pour normaliser le polygone, puis redimensionnez-le par (C/2). Traduire en (C/2, C/2) et renvoyer en entier.

Answer 2

Un algorithme simple serait:

1. Commencez par ligne au hasard (deux sommets et deux côtés d'un polygone)
2. Prenez bord aléatoire E du polygone
3. Faire nouveau P point au hasard sur ce bord
4. Prendre une ligne L perpendiculaire à E passant par le point P. En calculant l'intersection entre la ligne T et les lignes définies par les deux bords adjacents à E, calculer le décalage maximum de P lorsque la convexité n'est pas rompue.
5. Décaler le point P de manière aléatoire dans cette plage.
6. Si pas suffisamment de points, répéter de 2.

Answer 3

Votre approche initiale est correcte - le calcul de la coque convexe est la seule façon de vous satisfaire hasard, convexité et integerness. La seule façon dont je peux penser à optimiser votre algorithme pour obtenir plus de points est de les organiser autour d'un cercle plutôt que de manière complètement aléatoire. Vos points devraient être plus près des «bords» de votre carré que près du centre. Au centre, la probabilité devrait être ~ 0, puisque le polygone doit être convexe.

Une option simple serait de définir un rayon minimum pour vos points à apparaître - peut-être C/2 ou C * 0,75.Calculez le centre du carré C, et si un point est trop proche, éloignez-le du centre jusqu'à ce qu'une distance minimale soit atteinte.

Answer 4

Voici l'algorithme le plus rapide que je connaisse qui génère chaque polygone convexe avec une probabilité égale. La sortie a exactement N sommets, et le temps d'exécution est O (N log N), ce qui permet de générer très rapidement de gros polygones.

• Generate deux listes, X et Y, de N entiers aléatoires entre 0 et C. Assurez-vous qu'il n'y a pas de doublons.
• Trier X et Y et stocker leurs éléments maximum et minimum.
• Divisez aléatoirement les autres éléments (pas max ou min) en deux groupes: X1 et X2 et Y1 et Y2.
• Re-insérer les éléments minimum et maximum au début et à la fin de ces listes (minX au début de X1 et X2, maxX à la fin, etc.).
• Recherchez les différences consécutives (X1[i + 1] - X1[i]), en inversant l'ordre du second groupe (X2[i] - X2[i + 1]). Stockez-les dans les listes XVec et YVec.
• Randomiser (mélanger) YVec et traiter chaque paire XVec[i] et YVec[i] en tant que vecteur 2D.
• Triez ces vecteurs par angle, puis placez-les de bout en bout pour former un polygone.
• Déplacez le polygone vers les coordonnées min et max d'origine.

Une animation et une implémentation Java sont disponibles ici: Generating Random Convex Polygons.

Cet algorithme est basé sur un article de Pavel Valtr: "Probability that n random points are in convex position." Discrete & Computational Geometry 13.1 (1995): 637-643.