Points aléatoires à l'intérieur d'un parallélogramme
J'ai un 4 côté convexe Polygone défini par 4 points en 2D, et je veux être en mesure de générer des points aléatoires à l'intérieur.
Si vraiment il simplifie le problème, je peux limiter le polygone à un parallélogramme, mais d'une manière générale, la réponse est préféré.
La génération aléatoire des points jusqu'à ce que l'on est à l'intérieur du polygone ne fonctionne pas car il est vraiment imprévisible, le temps qu'il faut.
- qu'entendez-vous par hasard? vous pouvez choisir des points aléatoires qui se trouvent sur les diagonales. Ou voulez-vous remplir de remplir l'ensemble de polygones, de si vous produisez assez de points aléatoires?
- Si je produis assez je veux remplir l'ensemble du polygone
- Ce ne pouvait pas être plus simple: dessiner un simple rectangle qui est juste assez grand pour entourer votre poly. (Ou, d'ailleurs, aucune "forme ou d'une chose" que ce soit.) Maintenant créer des points qui sont distribués au hasard dans cette enfermant carré brut. Pour chacun, le test, il est à l'intérieur de votre forme. Jetez ceux qui sont à l'extérieur de la forme. C'est aussi simple que cela. Espérons que cela aide!
Vous devez vous connecter pour publier un commentaire.
A. Si vous pouvez restreindre votre entrée à parallélogramme, c'est vraiment simple:
u
etv
.Si votre parallélogramme est définie par les points ABCD tel que AB, BC, CD et DA sont les côtés, puis prenez votre point comme étant:
Où
AB
est le vecteur de A à B etAD
le vecteur de A à D.B. Maintenant, si vous ne pouvez pas, vous pouvez toujours utiliser les coordonnées barycentriques. Les coordonnées barycentriques correspondent, pour un quad, à 4 coordonnées
(a,b,c,d)
tels quea+b+c+d=1
. Puis, tout pointP
dans le quad peut être décrit par un 4-uple tels que:Dans votre cas, vous pouvez dessiner des 4 nombres aléatoires et de normaliser, de sorte qu'ils ajoutent jusqu'à 1. Que vous donnera un point. Remarque que la distribution des points ne sera PAS uniforme dans ce cas.
C. Vous pouvez aussi, comme le propose d'ailleurs, décomposer le quad en deux triangles et de l'utilisation de la demi-méthode du parallélogramme (c'est à dire, comme le parallélogramme, mais vous ajoutez la condition
u+v=1
) ou les coordonnées barycentriques pour les triangles. Toutefois, si vous souhaitez une distribution uniforme, la probabilité d'avoir un point dans une du triangle doit être égale à l'aire du triangle divisé par la surface de l'quad.La question par l'OP est un peu ambigu donc, la question que je vais répondre est: Comment générer un point à partir d'une distribution uniforme dans l'arbitraire d'un quadrilatère, qui est en fait une généralisation de Comment générer un point à partir d'une distribution uniforme à l'intérieur d'un arbitraire (convexe) polygone. La réponse est basée sur le cas de la génération d'un échantillon à partir d'une distribution uniforme dans un triangle (voir http://mathworld.wolfram.com/TrianglePointPicking.html, qui a une très belle explication).
Pour ce faire, nous:
Trianguler le polygone (c'est à dire générer une collection de non-cumul des triangulaires régions qui couvrent le polygone). Pour le cas d'un quadrilatère, créer un bord à travers
deux sommets adjacents. Pour les autres polygones, voir http://en.wikipedia.org/wiki/Polygon_triangulation pour un point de départ, ou http://www.cgal.org/ si vous avez juste besoin d'une bibliothèque.
De choisir l'un des triangles au hasard, laissez-nous attribuer un index pour chaque triangle (c'est à dire 0,1,2,...). Pour le quadrilatère, ils seront 0,1. Pour chaque triangle de nous attribuer un poids égal comme suit:
Puis la génération aléatoire d'indice i à partir de la limite de distribution de l'index donné leur poids. Pour le quadrilatère, c'est une loi de Bernoulli de distribution:
Laisser v0, v1, v2 sera sommets du triangle (représentés par leurs emplacements des points, de sorte que v0 = (x0,y0), etc. Ensuite, nous générer deux nombres aléatoires a0 et a1, tous deux établis de manière uniforme dans l'intervalle [0,1]. Nous calculons ensuite le point aléatoire x par x = a0 (v1-v0) + a1 (v2-v0).
Noter que, avec une probabilité de 0,5, x se trouve à l'extérieur à l'extérieur du triangle, mais s'il le fait, il se trouve à l'intérieur du parallélogramme composé de l'union de la triangle, c'est l'image après rotation de pi à travers le milieu de (v1,v2) (lignes en pointillés dans l'image). Dans ce cas, nous pouvons générer un nouveau point x' = v0 + R(pi)(x - v3), où R(pi) est une rotation de pi (180°). Le point x' sera à l'intérieur du triangle.
Note en outre que, si le quadrilatère est déjà un parallélogramme, alors nous n'avons pas à choisir un triangle au hasard, on peut choisir soit d'une façon déterministe, puis choisissez le point x sans les tests qu'il est à l'intérieur de la source triangle.
x' = v0 + (v3 - x)
Suis-je totalement à côté de la plaque? En regardant un peu plus, je ne suis pas sûr que je suis de droite, mais mon cas de test de v0 = [0,0] pose x' à l'extérieur du triangle.En supposant que vous voulez une distribution uniforme: la Forme de deux triangles à partir de votre polygone. Choisir le triangle pour générer le point en fonction de leur ratio de la superficie.
Appeler les coins du triangle A, B, C, du côté des vecteurs AB, BC, AC et de générer deux nombres au hasard dans [0,1], le " u et c. soit p = u * AB + v * AC.
Si Un+p est à l'intérieur du triangle, retour A+p
Si Un+p est à l'extérieur du triangle, retour A + AB + AC - p
(Ce qui est essentiellement PierreBdR de la formule, sauf pour le prétraitement et la dernière étape qui se plie le point de retour dans un triangle, de sorte qu'il peut gérer d'autres formes que des parallélogrammes).
Votre polygone est deux triangles, alors pourquoi ne pas choisir au hasard un de ces, puis de trouver un point au hasard dans le triangle.
Probablement pas la meilleure solution, mais il avait un travail.
Un peu moins "naïf" approche serait d'utiliser un polygone algorithme de remplissage, puis sélectionnez les points de fond de lignes au hasard.
C Exemple De Code
Par "général" voulez-vous dire tous les non-parallélogramme 4-côté polygones en général ou tout est possible polygones?
Comment à propos du dessin aléatoire d'une ligne reliant les 4 côtés par exemple, Si vous avez ceci:
De générer un point au hasard sur une unité carrée, marque ensuite le point sur la ligne B et D sur le pourcentage de la distance sur l'axe des abscisses. Faire de même sur la ligne A et C à l'aide de la valeur de l'axe Y.
Puis relier le point sur la ligne A à la ligne C et la ligne B à la ligne D, le point d'intersection est alors utilisée comme point aléatoire.
Il n'est pas uniforme à cause des erreurs d'arrondi aidera certains points, mais il devrait être proche si vous travaillez avec des points de valeurs.
Mise en œuvre devrait être plutôt facile, trop, car vous travaillez déjà avec des polygones. Vous devriez déjà avoir du code qui n'ces tâches simples.
Voici un rapide pseudo:
Cela fonctionne pour les généraux, les quadrilatères convexes:
Vous pouvez emprunter certains concepts de la Méthode des éléments Finis, en particulier pour quadrilatère (4 faces) des éléments (consulter la section 16.5 ici). Fondamentalement, il ya une bilinéaire paramétrage que les cartes d'un carré en u-v de l'espace (u, v \in [-1, 1] dans ce cas) à votre quadrilatère qui se compose de points de p_i (pour i = 1,2,3,4). Notez que Dans la condition de référence, les paramètres sont appelés \eta \xi.
Recette de base:
Le seul problème est que de points répartis uniformément dans le u-v de l'espace ne produira pas distribués de manière uniforme les points de votre quad (dans le Euclidienne sens). Si c'est important, vous pouvez travailler directement en 2D à l'intérieur de la boîte englobante de la quad et écrivez un point en quad (peut-être diviser le problème en deux point dans tris) test de la réforme de points aléatoires qui sont à l'extérieur.
Ne les points doivent être distribués de manière uniforme, ou toute distribution ok?
Pouvez le polygone être concave, ou est-elle garantie convexe?
Si la réponse à la question précédente, puis choisissez l'une ou l'autre des deux sommets et de choisir un point au hasard sur le segment de ligne entre eux. Ce service est limité à la ligne de segements reliant les sommets (c'est à dire, TRÈS non-uniforme); vous pouvez faire un peu mieux en choisissant un troisième sommet, puis sélection d'un point entre ça et le premier point, encore non-uniforme, mais au moins n'importe quel point dans le polygone est possible
De choisir un point au hasard sur une ligne entre deux points est facile, juste Un + p(B-A), où A et B sont les points et p est un nombre aléatoire compris entre 0.0 et 1.0
Quel type de distribution voulez-vous les points à avoir? Si vous n'avez pas de soins, les méthodes ci-dessus fonctionne correctement. Si vous voulez une distribution uniforme, la procédure suivante devrait fonctionner: Diviser le polygone en deux triangles, a et b. Laissez Un(a) et(b) être de leurs domaines. Exemple d'un point p de la distribution uniforme sur l'intervalle entre 0 et A(a)+(b). Si p < A(a), choisissez un triangle. Sinon, choisissez le triangle b. Choisir un sommet v de la choisi du triangle, et à laisser de c et d être les vecteurs correspondant aux côtés du triangle. Exemple de deux nombres x et y à partir de la distribution exponentielle avec l'unité de la moyenne. Alors le point (xc+yd)/(x+y), est un exemple de la répartition uniforme sur le polygone.
La fonction MATLAB cprnd génère des points de la distribution uniforme sur un polytope convexe. Pour votre question, un de plus spécialisé algorithme basé sur la décomposition de l'quadrilatère en triangles est plus efficace.
Pour PostGIS, c'est ce que j'utilise (vous voudrez peut-être un service pour possible une boucle infinie). Vous pouvez les exporter l'algorithme à votre langage de programmation: