Points aléatoires à l'intérieur d'un parallélogramme

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.

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.

La génération de points aléatoires jusqu'à ce qu'il y en ait un à l'intérieur du polygone ne fonctionnerait pas, car le temps que cela prend est vraiment imprévisible.

Answer 1

A. Si vous pouvez limiter votre entrée au parallélogramme, c'est très simple:

1. Prenez deux nombres aléatoires compris entre 0 et 1. Nous appellerons ensuite u et v.

2. Si votre parallélogramme est défini par les points ABCD tels que AB, BC, CD et DA sont les côtés, prenez alors votre point comme étant:

    p = A + (u * AB) + (v * 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. Les coordonnées barycentriques correspondent, pour un quad, à 4 coordonnées (a,b,c,d) telles que a+b+c+d=1. Ensuite, tout point P dans le quad peut être décrit par un quadruple tel que:

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

Dans votre cas, vous pouvez dessiner 4 nombres aléatoires et les normaliser pour qu’ils totalisent un. Cela vous donnera un point. Notez que la distribution des points ne sera PAS uniforme dans ce cas.

C. Vous pouvez également, comme proposé ailleurs, décomposer le quad en deux triangles et utiliser la méthode du demi-parallélogramme (c’est-à-dire le parallélogramme mais vous ajoutez la condition u+v=1) ou les coordonnées barycentriques des triangles. Toutefois, si vous souhaitez une distribution uniforme, la probabilité d'avoir un point dans l'un des triangles doit être égale à l'aire du triangle divisée par l'aire du quad.

Answer 2

La question du PO étant un peu ambiguë, la question à laquelle je vais répondre est la suivante: Comment générer un point à partir d'une distribution uniforme dans un quadrilatère arbitraire , qui est en réalité une généralisation de Comment générer un point à partir d'une distribution uniforme dans un polygone arbitraire (convexe) . La réponse est basée sur le cas de la génération d’un échantillon 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:

1. Triangulez le polygone (c’est-à-dire générez une collection de régions triangulaires ne se chevauchant pas qui recouvrent le polygone). Pour le cas d'un quadrilatère, créez un bord sur deux sommets non adjacents quelconques. Pour les autres polygones, consultez http://fr.wikipedia.org/wiki/Polygon_triangulation pour un démarrage point, ou http://www.cgal.org/ si vous avez simplement besoin d'une bibliothèque.

   

2. Pour choisir un des triangles de manière aléatoire, affectons un index à chaque triangle (0,1,2, ...). Pour le quadrilatère, ils seront 0,1. Pour chaque triangle, nous attribuons un poids égal comme suit:

   

3. Générez ensuite un indice aléatoire i à partir de la distribution finie sur les indices, en fonction de leur poids. Pour le quadrilatère, il s’agit d’une distribution de Bernoulli:

   

4. Soit v0, v1, v2 les sommets du triangle (représentés par leurs emplacements de points, de sorte que v0 = (x0, y0), etc. Nous générons ensuite deux nombres aléatoires a0 et a1, tous deux tirés uniformément l'intervalle [0,1], puis nous calculons le point aléatoire x par x = a0 (v1-v0) + a1 (v2-v0).

   

5. Notez que, avec une probabilité de 0,5, x est en dehors du triangle, il se trouve dans le parallélogramme composé de l'union du triangle avec son image après une rotation de pi autour du milieu de (v1 , v2) (lignes pointillées 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 degrés). Le point x 'sera à l'intérieur du triangle.

6. Notez en outre que, si le quadrilatère était déjà un parallélogramme, nous n'avons pas à choisir un triangle au hasard, nous pouvons en choisir un de manière déterministe, puis choisir le point x sans vérifier qu'il est à l'intérieur triangle source.

Answer 3

En supposant que vous souhaitiez une distribution uniforme: Formez deux triangles à partir de votre polygone. Choisissez le triangle dans lequel générer le point en fonction de leur rapport de surfaces.

Appelez les angles du triangle A, B, C, les vecteurs latéraux AB, BC, AC et générez deux nombres aléatoires dans [0,1] appelés u et v. Soit p = u * AB + v * AC.

Si A + p est à l'intérieur du triangle, retourne A + p

Si A + p est en dehors du triangle, retourne A + AB + AC - p

(Il s'agit essentiellement de la formule de PierreBdR, à l'exception du prétraitement et de la dernière étape qui replie le point dans un triangle afin qu'il puisse gérer d'autres formes que les 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 cela fonctionnerait.

Answer 5

Un peu moins " na & # 239; ve " L’approche consisterait à utiliser un algorithme de remplissage de polygone , puis à sélectionner des points à partir des lignes de remplissage de manière aléatoire.

Exemple de code C

//  public-domain code by Darel Rex Finley, 2007

int  nodes, nodeX[MAX_POLY_CORNERS], pixelX, pixelY, i, j, swap ;

//  Loop through the rows of the image.
for (pixelY=IMAGE_TOP; pixelY<IMAGE_BOT; pixelY++) {

  //  Build a list of nodes.
  nodes=0; j=polyCorners-1;
  for (i=0; i<polyCorners; i++) {
    if (polyY[i]<(double) pixelY && polyY[j]>=(double) pixelY
    ||  polyY[j]<(double) pixelY && polyY[i]>=(double) pixelY) {
      nodeX[nodes++]=(int) (polyX[i]+(pixelY-polyY[i])/(polyY[j]-polyY[i])
      *(polyX[j]-polyX[i])); }
    j=i; }

  //  Sort the nodes, via a simple “Bubble” sort.
  i=0;
  while (i<nodes-1) {
    if (nodeX[i]>nodeX[i+1]) {
      swap=nodeX[i]; nodeX[i]=nodeX[i+1]; nodeX[i+1]=swap; if (i) i--; }
    else {
      i++; }}

  //  Fill the pixels between node pairs.
  //  Code modified by SoloBold 27 Oct 2008
  //  The flagPixel method below will flag a pixel as a possible choice.
  for (i=0; i<nodes; i+=2) {
    if   (nodeX[i  ]>=IMAGE_RIGHT) break;
    if   (nodeX[i+1]> IMAGE_LEFT ) {
      if (nodeX[i  ]< IMAGE_LEFT ) nodeX[i  ]=IMAGE_LEFT ;
      if (nodeX[i+1]> IMAGE_RIGHT) nodeX[i+1]=IMAGE_RIGHT;
      for (j=nodeX[i]; j<nodeX[i+1]; j++) flagPixel(j,pixelY); }}}

   // TODO pick a flagged pixel randomly and fill it, then remove it from the list.
   // Repeat until no flagged pixels remain.

Answer 6

Par " général " voulez-vous dire tous les polygones à 4 côtés sans parallélogramme en général ou tous les polygones possibles?

Pourquoi ne pas tracer une ligne aléatoire reliant les 4 côtés, par exemple. Si vous avez ceci:

.BBBB.
A    C
A    C
.DDDD.

Générez ensuite un point aléatoire sur une unité de carré, puis marquez le point sur les lignes B et D en fonction du pourcentage de distance sur l’axe X. Faites la même chose sur les lignes A et C en utilisant la valeur de l’axe des Y.

Ensuite, connectez le point de la ligne A à la ligne C et la ligne B à la ligne D, le point d'intersection est alors utilisé comme point aléatoire.

Ce n'est pas uniforme parce que les erreurs d'arrondi aideront certains points, mais il devrait être proche si vous travaillez avec des valeurs à virgule flottante.

La mise en œuvre devrait également être assez facile, car vous travaillez déjà avec des polygones. Vous devriez déjà avoir du code qui effectue ces tâches simples.

Voici un pseudocode rapide:

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);

}

Answer 7

Ceci fonctionne pour les quadrilatères convexes généraux:

Vous pouvez emprunter certains concepts à la méthode des éléments finis, en particulier pour les éléments quadrilatéraux (à 4 côtés) ( reportez-vous à la section 16.5 ici ). Fondamentalement, il existe une paramétrisation bilinéaire qui mappe un carré dans l’espace uv (pour u, v \ in [-1, 1] dans ce cas) à votre quadrilatère constitué des points p_i (pour i = 1,2,3,4 ). Notez que dans la référence fournie, les paramètres sont appelés \ eta et \ xi.

Recette de base:

1. Choisissez un générateur de nombre aléatoire approprié pour générer des points bien répartis dans un domaine 2D carré
2. Génère des paires u-v aléatoires dans l'intervalle [-1, 1]
3. Pour chaque paire uv, le point aléatoire correspondant dans votre quad = 1/4 * ((1-u) (1-v) * p_1 + (1 + u) (1-v) * p_2 + (1+ u) (1 + v) * p_3 + (1-u) (1 + v) * p_4)

Le seul problème est que les points uniformément répartis dans l'espace u-v ne produiront pas de points uniformément répartis dans votre quad (au sens euclidien). Si cela est important, vous pouvez travailler directement en 2D dans la boîte englobante du quad et écrire un test point-en-quad (peut-être en scindant le problème en deux points en tris) pour éliminer les points aléatoires qui se trouvent à l'extérieur.

Answer 8

Les points doivent-ils être répartis uniformément ou une distribution est-elle correcte?

Le polygone peut-il être concave ou est-il garanti d'être convexe?

Si la réponse à la question ci-dessus est non, choisissez deux des sommets et choisissez un point aléatoire sur le segment de ligne qui les sépare. Ceci est limité aux segments de lignes reliant les sommets (c'est-à-dire, TRÈS non uniforme); vous pouvez faire un peu mieux en choisissant un troisième sommet puis en choisissant un point entre celui-ci et le premier point - toujours non uniforme, mais au moins n'importe quel point du polygone est possible

Choisir un point au hasard sur une ligne entre deux points est facile, il suffit de A + p (B-A), où A et B sont les points et p est un nombre aléatoire compris entre 0,0 et 1,0

Answer 9

Quel type de distribution voulez-vous que les points aient? Si vous ne vous en souciez pas, les méthodes ci-dessus fonctionneront bien. Si vous voulez une distribution uniforme, la procédure suivante fonctionnera: Divisez le polygone en deux triangles, a et b. Soit A (a) et A (b) leurs zones. Échantillonnez un point p de la distribution uniforme sur l'intervalle compris entre 0 et A (a) + A (b). Si p & Lt; A (a), choisissez le triangle a. Sinon, choisissez triangle b. Choisissez un sommet v du triangle choisi et laissez c et d les vecteurs correspondant aux côtés du triangle. Échantillonnez deux nombres x et y de la distribution exponentielle avec la moyenne unitaire. Alors le point (xc + yd) / (x + y) est un échantillon de la distribution uniforme sur le polygone.

Answer 10

La fonction MATLAB cprnd génère des points à partir de la distribution uniforme sur un polytope convexe général. Pour votre question, un algorithme plus spécialisé basé sur la décomposition du quadrilatère en triangles est plus efficace.

Answer 11

Pour PostGIS, c’est ce que j’utilise (vous voudrez peut-être un pupitre pour d’éventuelles boucles infinies). Vous pouvez exporter l'algorithme vers votre langage de programmation:

CREATE or replace FUNCTION random_point(geometry)
RETURNS geometry
AS $$
DECLARE 
    env geometry;
    corner1 geometry;
    corner2 geometry;
    minx real;
    miny real;
    maxx real;
    maxy real;
    x real;
    y real;
    ret geometry;
begin

select ST_Envelope($1) into env;
select ST_PointN(ST_ExteriorRing(env),1) into corner1;
select ST_PointN(ST_ExteriorRing(env),3) into corner2;
select st_x(corner1) into minx;
select st_x(corner2) into maxx;
select st_y(corner1) into miny;
select st_y(corner2) into maxy;
loop
    select minx+random()*(maxx-minx) into x;
    select miny+random()*(maxy-miny) into y;
    select ST_SetSRID(st_point(x,y), st_srid($1)) into ret;
    if ST_Contains($1,ret) then
        return ret ;
    end if;
end loop;
end;
$$
LANGUAGE plpgsql
volatile
RETURNS NULL ON NULL INPUT;