평행사변형 내부의 임의의 점

https://stackoverflow.com/questions/240778

04-07-2019
|

문제

2D에서 4개의 점으로 정의된 4면 볼록 다각형이 있고 그 안에 임의의 점을 생성할 수 있기를 원합니다.

문제를 정말 단순화한다면 다각형을 평행사변형으로 제한할 수 있지만 보다 일반적인 대답이 선호됩니다.

다각형 내부에 포함될 때까지 임의의 점을 생성하는 것은 소요되는 시간을 예측할 수 없기 때문에 작동하지 않습니다.

해결책

A. 입력을 평행 사변형으로 제한 할 수 있다면 정말 간단합니다.

0과 1 사이에 두 개의 랜덤 숫자를 가져옵니다. 그런 다음 호출하겠습니다. u 그리고 v.
평행 사변형이 AB, BC, CD 및 DA가 측면이되도록 ABCD 포인트로 정의되면 다음과 같은 점을 취하십시오.
```
 p = A + (u * AB) + (v * AD)
```

어디에 AB 벡터는 A에서 B로입니다 AD A에서 D 로의 벡터

B. 이제 할 수 없다면 여전히 바리 센트 코디네이트를 사용할 수 있습니다. 바리 중심 좌표는 쿼드에 대해 4 개의 좌표에 해당합니다. (a,b,c,d) 그렇게 a+b+c+d=1. 그런 다음, 어떤 지점이든 P 쿼드 내에서는 4-uple에 의해 설명 될 수 있습니다.

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

귀하의 경우, 4 개의 랜덤 숫자를 그려서 1에 추가되도록 정규화 할 수 있습니다. 이 경우 점의 분포는 균일하지 않습니다.

C. 다른 곳에서 제안한대로 쿼드를 두 개의 삼각형으로 분해하고 반 알리그램 방법을 사용할 수 있습니다 (예 : 평행 사변형이지만 조건을 추가 할 수 있습니다. u+v=1) 또는 삼각형의 바리 센트 코디네이션. 그러나 균일 한 분포를 원한다면 삼각형 중 하나에 포인트가있을 확률은 삼각형의 영역을 쿼드 영역으로 나눈 값과 같아야합니다.

다른 팁

OP의 질문은 약간 모호하기 때문에 내가 대답 할 질문은 다음과 같습니다. 임의의 사변형 내에서 균일 분포에서 점을 생성하는 방법, 이것은 실제로 일반화입니다 임의의 (볼록) 다각형 내에서 균일 분포에서 점을 생성하는 방법. 답은 삼각형의 균일 분포에서 샘플을 생성하는 경우를 기준으로합니다 (참조 http://mathworld.wolfram.com/trianglepointpicking.html, 아주 좋은 설명이 있습니다).

이를 달성하기 위해 우리는 다음을 수행합니다.

삼각형 다각형 (즉, 다각형을 덮는 비 겹치는 삼각 영역의 모음을 생성). 사변형의 경우 두 개의 비 판결 정점에서 가장자리를 만듭니다. 다른 다각형은 참조하십시오 http://en.wikipedia.org/wiki/polygon_triangulation 출발점의 경우 또는 http://www.cgal.org/ 도서관이 필요한 경우.
삼각형 중 하나를 무작위로 선택하려면 각 삼각형에 색인을 할당하겠습니다 (예 : 0,1,2, ...). 사변형의 경우 0,1이됩니다. 각 삼각형에 대해 우리는 다음과 같은 무게를 할당합니다.
그런 다음 가중치가 주어진 인덱스에 대한 유한 분포에서 랜덤 인덱스 I을 생성합니다. 사변형의 경우 이것은 Bernoulli 분포입니다.
V0, v1, v2를 삼각형의 정점으로 두십시오 (포인트 위치로 표시되어 v0 = (x0, y0) 등이 두 개의 랜덤 숫자 A0과 A1을 생성합니다. ]. 그런 다음 x = a0 (v1-v0) + a1 (v2-v0)으로 랜덤 포인트 x를 계산합니다.
확률이 0.5 인 경우 X는 삼각형 외부 외부에 놓여 있지만, 그렇다면 (v1, v2)의 중간 점 주위의 PI 회전 후 이미지와 함께 삼각형의 결합으로 구성된 평행 사변형 내부에 있습니다 (대시 선 라인. 이미지에서). 이 경우, 우리는 새로운 포인트 x '= v0 + r (pi) (x -v3)를 생성 할 수 있으며, 여기서 r (pi)는 Pi (180 ℃)에 의한 회전이다. 포인트 X '는 삼각형 안에 있습니다.
또한 사변형이 이미 평행 사변형 인 경우, 우리는 무작위로 삼각형을 선택할 필요가 없으며, 하나를 결정적으로 선택한 다음 소스 삼각형 내부에 있음을 테스트하지 않고 포인트 X를 선택할 수 있습니다.

균일한 분포를 원한다고 가정하면 다음과 같습니다.다각형으로 두 개의 삼각형을 만듭니다.면적 비율에 따라 점을 생성할 삼각형을 선택합니다.

삼각형 A, B, C의 모서리, 측면 벡터 AB, BC, AC를 호출하고 [0,1]에서 u와 v라는 두 개의 난수를 생성합니다.p = u * AB + v * AC라고 가정합니다.

A+p가 삼각형 안에 있으면 A+p를 반환합니다.

A+p가 삼각형 밖에 있으면 A + AB + AC - p를 반환합니다.

(이것은 전처리와 점을 다시 삼각형으로 접어서 평행사변형 이외의 다른 모양을 처리할 수 있는 마지막 단계를 제외하고는 기본적으로 PierreBdR의 공식입니다.)

당신의 다각형은 두 개의 삼각형이므로, 그 중 하나를 무작위로 선택한 다음 삼각형에서 임의의 지점을 찾으십시오.

아마도 최상의 솔루션은 아니지만 작동했습니다.

다소 덜 "순진한"접근 방식은 a를 사용하는 것입니다 다각형 채우기 알고리즘, 그런 다음 채우기 라인에서 점을 무작위로 선택하십시오.

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.

"일반"이라는 의미는 모든 비 평면도 4면 다각형을 일반적으로 또는 가능한 모든 다각형을 의미합니까?

4면을 연결하는 임의의 선을 그리는 것은 어떻습니까?

.BBBB.
A    C
A    C
.DDDD.

그런 다음 단위 정사각형에서 임의의 지점을 생성 한 다음 라인 B와 D의 점을 x 축의 거리의 백분율로 표시합니다. y 축에서 값을 사용하여 라인 A와 C에서 동일하게 수행하십시오.

그런 다음 라인 A의 지점을 라인 C에 연결하고 B 라인 B를 라인 D에 연결하면 교차점을 랜덤 포인트로 사용합니다.

반올림 오류는 특정 지점에 도움이되므로 균일하지 않지만 부동 소수점 값으로 작업하는 경우 가까워 야합니다.

이미 다각형으로 작업하고 있기 때문에 구현은 다소 쉬워야합니다. 이미 간단한 작업을 수행하는 코드가 있어야합니다.

다음은 빠른 의사 코드입니다.

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

}

이것은 일반적인 볼록 사변형에 대해 작동합니다.

유한 요소 방법, 특히 사변형 (4면) 요소에 대해 일부 개념을 빌릴 수 있습니다.여기에서 섹션 16.5를 참조하십시오). 기본적으로, UV 공간의 정사각형 (이 경우 u, v in -1, 1]을 맵핑하는 이중선 매개 변수화가 있습니다. ). 제공된 참조에서 매개 변수를 eta 및 xi라고합니다.

기본 레시피 :

제곱 2D 도메인에서 잘 분산 된 지점을 생성하려면 적절한 랜덤 번호 생성기를 선택하십시오.
범위에서 임의의 UV 쌍을 생성합니다 [-1, 1
각 UV 쌍에 대해 쿼드의 해당 랜덤 포인트 = 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)

유일한 문제는 UV 공간에서 균일하게 분산 된 지점이 쿼드 (유클리드 의미에서)에서 균일하게 분산 된 지점을 생성하지 않는다는 것입니다. 그것이 중요하다면, 당신은 쿼드의 경계 상자 내에서 2D에서 직접 작업하고 (Tris에서 문제를 TRIS의 2 지점으로 나누어서) 테스트를 외부에있는 랜덤 포인트로 쓸 수 있습니다.

포인트가 균일하게 분산되어야합니까, 아니면 분포가 괜찮습니까?

다각형이 오목할 수 있습니까, 아니면 볼록한 것으로 보증됩니까?

위의 두 가지에 대한 대답이 아니오 인 경우, 두 개의 정점을 골라 줄 세그먼트에서 임의의 지점을 선택하십시오. 이것은 정점을 연결하는 라인 SEGEMENTS (즉, 매우 불균일)로 제한됩니다. 세 번째 vertex를 선택한 다음 그 점과 첫 번째 포인트를 선택하여 조금 더 잘할 수 있습니다.

두 점 사이의 임의 포인트를 선택하는 것은 쉽습니다. a + p (ba) 만 쉽습니다. 여기서 A와 B는 점이며 P는 0.0에서 1.0 사이의 임의 수입니다.

어떤 종류의 분포를 원하십니까? 신경 쓰지 않으면 위의 방법이 잘 작동합니다. 균일 한 분포를 원한다면 다음 절차가 작동합니다. 다각형을 두 개의 삼각형 A 및 B로 나눕니다. A (a)와 a (b)가 그들의 영역이되게하십시오. 0과 a (a)+a (b) 사이의 간격에서 균일 분포에서 A 점 P를 샘플링하십시오. p <a (a) 인 경우 삼각형 a를 선택하십시오. 그렇지 않으면 삼각형을 선택하십시오. b. 선택한 삼각형의 정점 V를 선택하고 C와 D를 삼각형의 측면에 해당하는 벡터가되도록하십시오. 단위 평균으로 지수 분포에서 두 숫자 x와 y를 샘플링하십시오. 그런 다음 포인트 (xc+yd)/(x+y)는 다각형의 균일 분포의 샘플입니다.

MATLAB 기능 cprnd 일반적인 볼록 폴리 테프의 균일 분포에서 점을 생성합니다. 질문의 경우 사변형을 삼각형으로 분해하는 데 기반한보다 전문화 된 알고리즘이 더 효율적입니다.

Postgis의 경우 이것이 제가 사용하는 것입니다 (가능한 무한 루프를위한 와드를 원할 수도 있습니다). 알고리즘을 프로그래밍 언어로 내보낼 수 있습니다.

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;

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow