pontos aleatórios dentro de um paralelogramo

Question

Eu tenho um lado 4 convexo polígono definido por 4 pontos em 2D, e eu quero ser capaz de gerar pontos aleatórios dentro dela.

Se ele realmente simplifica o problema, posso limitar o polígono para um paralelogramo, mas uma resposta mais geral é o preferido.

Gerar pontos aleatórios até que um está dentro do polígono não iria funcionar porque é realmente imprevisível o tempo que leva.

Answer 1

A. Se você pode restringir sua entrada para paralelogramo, isso é muito simples:

1. Tomar dois números aleatórios entre 0 e 1. Vamos chamar então u e v.

2. Se o seu paralelogramo é definido pelos pontos ABCD tal que AB, BC, CD e DA são os lados, em seguida, tomar o seu ponto como sendo:

    p = A + (u * AB) + (v * AD)
   

Onde AB é o vector de A para B e AD o vector de A a D.

B. Agora, se você não pode, você ainda pode usar as coordenadas baricêntricas. As coordenadas baricêntricas correspondem, por um quadrilátero, a 4 coordenadas (a,b,c,d) tal que a+b+c+d=1. Então, qualquer P ponto dentro do quadrilátero pode ser descrito por uma 4 pela tripla tal que:

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

No seu caso, você pode desenhar 4 números aleatórios e normalizar-los para que eles somam 1. Isso lhe dará um ponto. Note-se que a distribuição de pontos não será uniforme nesse caso.

C. Você também pode, como proposto em outros lugares, decompor o quad em dois triângulos e usar o método de meia-paralelogramo (ou seja, como o paralelogramo mas você adicionar o u+v=1 condição) ou as coordenadas baricêntricas para triângulos. No entanto, se você quer uma distribuição uniforme, a probabilidade de ter um ponto em um dos o triângulo deve ser igual à área do triângulo dividida pela área do quad.

Answer 2

A pergunta do OP é um pouco ambígua então a questão eu vou responder é: Como gerar um ponto de uma distribuição uniforme dentro de uma arbitrária quadrilátero , que na verdade é uma generalização do como gerar um ponto de uma distribuição uniforme dentro de uma arbitrária (convexa) polígono . A resposta baseia-se no caso de gerar uma amostra de uma distribuição uniforme de um triângulo (ver http: // MathWorld .wolfram.com / TrianglePointPicking.html , que tem uma ótima explicação).

A fim de conseguir isso,:

1. triangular o polígono (isto é, gerar um conjunto de regiões que não se sobrepõem triangulares que cobrem o polígono). Para o caso de um quadrilátero, criar uma borda em toda quaisquer dois vértices não adjacentes. Para outros polígonos, consulte http://en.wikipedia.org/wiki/Polygon_triangulation para uma partida ponto, ou http://www.cgal.org/ se você só precisa de uma biblioteca.

   

2. Para escolher um dos triângulos de forma aleatória, vamos atribuir um índice para cada triângulo (ou seja, 0,1,2, ...). Para o quadrilátero, que será 0,1. Para cada triângulo que atribuir um peso igual a seguinte:

   

3. Em seguida, gerar um índice aleatório i a partir da distribuição finita sobre índices indicados os seus pesos. Para o quadrilátero, esta é uma distribuição de Bernoulli:

   

4. Let v0, v1, v2 ser vértices do triângulo (representada pelas suas localizações de pontos, de modo que v0 = (x0, y0), etc. Em seguida, gerar dois números aleatórios A0 e A1, ambos desenhados de forma uniforme a partir de o intervalo [0,1]. Em seguida, calcula-se a ponto x aleatória por x = a0 (v1-v0) + a1 (v2-V0).

   

5. Note que, com probabilidade de 0,5, x está fora fora do triângulo, no entanto, se isso acontecer, ele está dentro do paralelogramo formado da união do triângulo com a imagem que é depois de uma rotação de pi em torno do ponto médio (v1 , v2) (linhas tracejadas na imagem). Nesse caso, pode-se gerar um novo ponto x'= V0 + R (PI) (x - v3), em que R (pi) é uma rotação por pi (180 graus). O ponto x' será dentro do triângulo.

6. Além disso, note que, se o quadrilátero já era um paralelogramo, então não temos que escolher um triângulo de forma aleatória, que pode escolher qualquer um dos dois de forma determinística, em seguida, escolher o ponto x sem testar que é dentro é triângulo fonte.

Answer 3

Assumindo que você quer uma distribuição uniforme: Formulário de dois triângulos de seu polígono. Escolher qual triângulo para gerar o ponto de acordo com a sua relação de área.

Chamada os cantos do triângulo A, B, C, os vectores secundários AB, AC, AC e gerar dois números aleatórios em [0,1] chamado u e v. Seja p = u * AB + v * AC.

Se A + p está dentro do triângulo, retornar A + p

Se A + p está fora do triângulo, retornar A + AB + AC - p

(Esta é basicamente a fórmula de PierreBdR exceto para o pré-processamento e o último passo que dobra a volta ponto em um triângulo, de modo que ele pode lidar com outras formas de paralelogramos).

Answer 4

O seu polígono é dois triângulos, então porque não escolher aleatoriamente um desses, em seguida, encontrar um ponto aleatório no triângulo.

Provavelmente não é a melhor solução, mas ele iria trabalhar.

Answer 5

Uma abordagem um pouco menos " ingênua " seria a utilização de um < a href = "http://alienryderflex.com/polygon_fill/" rel = "nofollow noreferrer"> polígono algoritmo de preenchimento e selecione pontos a partir das linhas de preenchimento aleatoriamente.

Código C Amostra

//  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

Por "geral" você quer dizer todos os não-paralelogramo polígonos 4-secundários em geral ou todos os polígonos possíveis?

Que tal desenho de uma linha de ligação aleatória os 4 lados, por exemplo, Se você tem este:

.BBBB.
A    C
A    C
.DDDD.

Em seguida, gerar um ponto aleatório numa unidade quadrada, em seguida, marcar o ponto na linha B e D para a percentagem de distância sobre o eixo X. Fazer o mesmo na linha A e C, utilizando o valor do eixo Y.

Em seguida, ligar o ponto na linha A para a linha C e a linha B para a linha D, o ponto de intersecção é então utilizado como o ponto aleatório.

Não é uniforme porque erros de arredondamento ajudará certos pontos, mas deve estar perto se você estiver trabalhando com valores pontos flutuante.

A implementação deve ser bastante fácil, também, desde que você já está trabalhando com polígonos. Você já deve ter código que faz essas tarefas simples.

Aqui está um pseudocódigo rápida:

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

Isso funciona para gerais, quadriláteros convexos:

Você pode pedir alguns conceitos do Método dos Elementos Finitos, especificamente para elementos quadriláteros (4 lados) ( consulte a seção 16,5 aqui ). Basicamente, há uma parametrização bilinear que mapeia um quadrado no espaço uv (para u, v \ in [-1, 1], neste caso) para o seu quadrilátero que consiste em pontos p_i (para i = 1,2,3,4 ). Note que na referência fornecido, os parâmetros são chamados \ eta e \ xi.

Receita básica:

1. Escolha um gerador de números aleatórios adequado para gerar pontos bem distribuídos em um domínio 2D quadrado
2. Gerar u-v pares aleatórios no intervalo [-1, 1]
3. Para cada par UV, o ponto aleatório correspondente no seu quad = 1/4 * ((1-u) (1-v) * p_1 + (1 + L) (1-v) * p_2 + (1+ u) (1 + v) * p_3 + (1-u) (1 + v) * P_4)

O único problema é que os pontos distribuídos uniformemente no espaço u-v não irá produzir uniformemente distribuída pontos em sua quad (no sentido euclidiano). Se isso é importante, você pode trabalhar diretamente em 2D dentro da caixa delimitadora do quad e escrever um point-in-quad (talvez dividindo o problema em dois pontos em tris) teste para abater pontos aleatórios que estão fora.

Answer 8

Será que os pontos precisam ser uniformemente distribuída, ou é qualquer ok distribuição?

Pode o polígono ser côncava, ou é guarenteed ser convexo?

Se a resposta a ambas acima não é, em seguida, escolher qualquer um dos dois vértices e escolher um ponto aleatório no segmento de linha entre eles. Esta é limitada aos segements linha que liga os vértices (ou seja, muito não uniformes); você pode fazer um pouco melhor, escolhendo um terceiro vértice e, em seguida, escolher um ponto entre isso e o primeiro ponto - ainda não uniforme, mas pelo menos qualquer ponto do polígono é possível

Escolher um ponto aleatório sobre uma linha entre dois pontos é fácil, apenas A + p (B-A), em que A e B são os pontos e o símbolo p representa um número aleatório entre 0,0 e 1,0

Answer 9

Que tipo de distribuição que você quer que os pontos de ter? Se você não se importa, os métodos acima irá funcionar bem. Se você quer uma distribuição uniforme, o seguinte procedimento irá funcionar: Divida o polígono em dois triângulos, a e b. Deixe-A (a) e A (b) ser suas áreas. Amostra um ponto p a partir da distribuição uniforme no intervalo entre 0 e A (a) + A (b). Se p

Answer 10

A função MATLAB cprnd gera pontos da distribuição uniforme em um polytope convexo geral. Para a sua pergunta um algoritmo mais especializada baseada na decomposição do quadrilátero em triângulos é mais eficiente.

Answer 11

Para PostGIS, é isso que eu estou usando (você pode querer uma enfermaria para possíveis loops infinitos). Você pode exportar o algoritmo para sua linguagem de programação:

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;