Points aléatoires à l'intérieur d'un polygone

Question

J'ai un polygone convexe à 4 côtés défini par 4 points en 2D et je veux pouvoir générer des points aléatoires à l'intérieur de celui-ci.

Si cela simplifie vraiment le problème, je peux limiter le polygone à un parallélogramme, mais une réponse plus générale est préférable.

Générer des points aléatoires jusqu'à ce que l'on se trouve à l'intérieur du polygone ne fonctionnerait pas, car le temps que cela prend est vraiment imprévisible.

Answer 1

La question de 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 à l'intérieur d'un arbitraire quadralateral, qui est en fait une généralisation de la méthode pour 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.htmlqui a une très belle explication).

Pour ce faire, nous:

1. 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.

   

2. Pour 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:

   

3. Ensuite, 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 distribution de Bernoulli:

   

4. Laissez-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).

   

5. Notez qu'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.

6. Notons 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.

Answer 2

A. Si vous pouvez restreindre votre entrée à parallélogramme, c'est vraiment simple:

1. Prendre deux nombres aléatoires entre 0 et 1. Nous appellerons alors u et v.

2. 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:

   p = A + u*AB + b*AD

où AB est le vecteur de A à B et AD le vecteur de A à D.

B. Maintenant, si vous ne pouvez pas, vous pouvez toujours utiliser les coordonnées barycentriques. Fondamentalement, les coordonnées barycentriques correspondent, pour un quad, à 4 coordonne (a,b,c,d) tels que a+b+c+d=1. Puis, tout point P dans le quad peut être décrit par un 4-uple tels que:

P = a A + b B + c C + d D

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 que 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 du quad.

Answer 3

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.

Appelez 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] est appelé a et b. Soit p = a*AB + b*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).

Answer 4

Votre polygone est constitué de deux triangles, alors pourquoi ne pas en choisir un au hasard, puis rechercher un point au hasard dans le triangle.

Probablement pas la meilleure solution, mais ça marcherait.

Answer 5

En "général", vous voulez 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:

.BBBB.
A    C
A    C
.DDDD.

Ensuite 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.

Connectez ensuite 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.

La 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 pseudo-code:

void GetRandomPoint(Polygon p, ref float x, ref float y) {

    float xrand = random();
    float yrand = random();

    float h0 = p.Vertices[0] + xrand * p.Vertices[1];
    float h1 = p.Vertices[2] + yrand * p.Vertices[3];

    float v0 = p.Vertices[0] + xrand * p.Vertices[2];
    float v1 = p.Vertices[1] + yrand * p.Vertices[3];

    GetLineIntersection(h0, h1, v0, v1, x, y);

}