نقاط عشوائية داخل متوازي الاضلاع

Question

لدي 4 الجانب محدب مضلع يحددها 4 نقاط في 2D و أريد أن تكون قادرة على توليد نقاط عشوائية في داخله.

إذا كان حقا يبسط المشكلة, أنا يمكن أن تحد من المضلع إلى متوازي الاضلاع, ولكن أكثر عمومية الجواب هو المفضل.

توليد نقاط عشوائية حتى واحد داخل المضلع لن ينجح لأنه حقا لا يمكن التنبؤ بها في الوقت الذي يستغرقه.

Answer 1

A.إذا كنت يمكن أن تحد من المدخلات الخاصة بك إلى متوازي أضلاع هذا هو حقا بسيطة:

1. تأخذ اثنين من أرقام عشوائية بين 0 و 1.سنتصل ثم u و v.

2. إذا كان الخاص بك متوازي الاضلاع هو تعريف نقاط ABCD بحيث AB, BC, CD و دا هم الجانبين ، ثم تأخذ نقطة على النحو التالي:

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

حيث AB هو متجه من A إلى B ، AD ناقلات من D.

ب.الآن, إذا كنت لا تستطيع, لا يزال بإمكانك استخدام إحداثيات مركز على الجاذبية.فإن على الجاذبية الإحداثيات تتوافق عن رباعية ، 4 الإحداثيات (a,b,c,d) مثل أن a+b+c+d=1.ثم أي نقطة P ضمن رباعية يمكن وصفها من قبل 4-بعض هذه:

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

في الحالة الخاصة بك ، يمكنك رسم 4 أرقام عشوائية وتطبيع لهم بحيث تضيف ما يصل إلى 1.التي سوف تعطيك نقطة.علما أن توزيع النقاط لن تكون موحدة في هذه الحالة.

C.كما يمكنك ، على النحو المقترح في مكان آخر ، تتحلل رباعية إلى مثلثين و استخدام نصف متوازي الاضلاع الطريقة (أي متوازي الاضلاع ولكن يمكنك إضافة شرط u+v=1) أو على الجاذبية الإحداثيات مثلثات.ومع ذلك ، إذا كنت تريد توزيع موحد ، واحتمال وجود نقطة في المثلث يجب أن تساوي مساحة المثلث مقسوما على مساحة رباعية.

Answer 2

سؤال المرجع هو غامض قليلا لذا فإن السؤال سوف الجواب هو: كيفية إنشاء نقطة توزيع موحد داخل التعسفي الرباعي, الذي هو في الواقع التعميم كيفية إنشاء نقطة توزيع موحد داخل التعسفي (محدب) المضلع.الجواب هو على أساس حالة توليد عينة من توزيع موحد في مثلث (انظر http://mathworld.wolfram.com/TrianglePointPicking.html, التي لديها لطيف جدا التفسير).

من أجل إنجاز هذا نحن:

1. تثليث المضلع (أيتوليد مجموعة من غير تداخل الثلاثي المناطق التي تغطي المضلع).عن حالة الرباعي إنشاء حافة عبر أي اثنين من غير القمم المجاورة.عن غيرها من المضلعات ، انظر http://en.wikipedia.org/wiki/Polygon_triangulation عن نقطة انطلاق ، أو http://www.cgal.org/ إذا كنت تحتاج فقط إلى المكتبة.

   

2. اختيار واحد من المثلثات بشكل عشوائي ، دعونا تعيين المؤشر إلى كل مثلث (أي0,1,2,...).بالنسبة الرباعي ، سيتم 0,1.لكل مثلث نحن تعيين الوزن متساوية على النحو التالي:

   

3. ثم توليد عشوائي مؤشر أنا من المتناهي توزيع أكثر من فهارس نظرا الأوزان.بالنسبة الرباعي ، وهذا هو توزيع برنولي:

   

4. اسمحوا v0, v1, v2 تكون رؤوس مثلث (ممثلة نقطة المواقع ، بحيث v0 = (x0,y0) ، الخ.بعد ذلك علينا توليد اثنين من أرقام عشوائية a0 و a1 ، سواء رسمها بشكل موحد من الفترة [0,1].ثم نقوم بحساب نقطة عشوائية x x = a0 (v1-v0) + a1 (v2-v0).

   

5. مع ملاحظة أن احتمال 0.5 x تقع خارج المثلث ، ومع ذلك إذا كان كذلك ، فإنه يكمن في داخل متوازي الاضلاع تتألف من اتحاد المثلث مع انها صورة بعد دوران بي حول نقطة الوسط (v1,v2) (الخطوط المتقطعة في الصورة).في هذه الحالة يمكننا توليد جديدة النقطة x = v0 + R(pi)(x - v3) ، حيث R(pi) هو دوران pi (180 درجة).النقطة x' سوف يكون داخل المثلث.

6. ونلاحظ كذلك أنه إذا كان الرباعي بالفعل متوازي الاضلاع, ثم ليس لدينا لاختيار مثلث عشوائيا ، يمكننا اختيار أي واحد deterministically ، ثم اختر النقطة x من دون اختبار أنه داخل المصدر انه مثلث.

Answer 3

وعلى افتراض انك تريد توزيع موحد: نموذج مثلثين من المضلع. اختيار ومثلث لتوليد نقطة في وفقا لنسبة منطقتهم.

واتصل زوايا المثلث A، B، C، ناقلات الجانب AB، BC، AC وتوليد رقمين عشوائية في [0،1] دعا u و v. دعونا ع = ش * AB + ت * AC.

إذا A + p غير داخل المثلث، وعودة A + ص

إذا A + ص خارج المثلث، والعودة A + AB + AC - ص

(وهذا هو في الأساس صيغة PierreBdR ما عدا لتجهيزها والخطوة الأخيرة أن تطوي هذه النقطة مرة أخرى إلى المثلث، وبالتالي فإنه يمكن التعامل مع الأشكال الأخرى من متوازيات الأضلاع).

Answer 4

ومضلع الخاص بك هو مثلثين، فلماذا لا اختيار عشوائي واحدة من تلك، ثم العثور على نقطة عشوائية في المثلث.

وربما لا يكون أفضل حل، لكنه سوف يعمل.

Answer 5

وهناك أقل النهج إلى حد ما " السذاجة " سيكون لاستخدام < وأ href = "http://alienryderflex.com/polygon_fill/" يختلط = "نوفولو noreferrer"> تعبئة المضلع خوارزمية ، ثم حدد نقطة من خطوط تعبئة عشوائيا.

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

وبواسطة "عام" هل يعني كل غير متوازي الاضلاع-المضلعات 4-الجانب بشكل عام أو كل المضلعات ممكنة؟

وماذا عن رسم خط عشوائي يربط بين الجانبين 4 على سبيل المثال إذا كان لديك هذا:

.BBBB.
A    C
A    C
.DDDD.

وثم توليد نقطة عشوائية على الساحة حدة، ثم وضع علامة نقطة على السطر B و D في نسبة المسافة على X المحور. تفعل الشيء نفسه على خط وC باستخدام قيمة من المحور Y.

وثم ربط نقطة على خط إلى خط C و 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);

}

Answer 7

يعمل هذا العام ، محدبة رباعيات:

يمكنك استعارة بعض المفاهيم من طريقة العناصر المحدودة ، وتحديدا الرباعي (4-sided) العناصر (يرجى الرجوع إلى القسم 16.5 هنا).في الأساس هناك خطيه والثوابت التي خرائط مربع في u-v الفضاء (على u, v \في [-1, 1] في هذه الحالة) إلى الرباعي الذي يتكون من نقاط p_i (for i = 1,2,3,4).علما أنه في توفير مرجع المعلمات تسمى \eta و \الحادي عشر.

الوصفة الأساسية:

1. اختيار مناسبة مولد رقم عشوائي توليد موزعة جيدا نقاط في مربع 2D المجال
2. توليد عشوائية u-v أزواج في مجموعة [-1, 1]
3. لكل u-v زوج المقابلة نقطة عشوائية في رباعية = 1/4 * ((1-u)(1-v) * p_1 + (1+u)(1-v) * p_2 + (1+u)(1+ت) * p_3 + (1-u)(1+ت) * p_4)

المشكلة الوحيدة هي أن توزع بشكل موحد نقطة في u-v الفضاء لن تنتج موزعة بشكل متجانس نقطة في رباعية (في الإقليدية المعنى).إذا كان هذا هو المهم ، يمكنك العمل مباشرة في 2D داخل المربع المحيط من رباعية وكتابة نقطة في رباعية (ربما عن طريق تقسيم المشكلة إلى نقطتين في تريس) اختبار اعدام عشوائي النقاط التي هي خارج.

Answer 8

هل تحتاج ليتم توزيعها بشكل موحد النقاط، أو أي توزيع موافق؟

ويمكن أن يكون المضلع المقعر، أو هو مقارعة أن تكون محدبة؟

وإذا كان الجواب على كل ما سبق هو لا، ثم اختيار أي اثنين من الذروات واختيار نقطة عشوائية على شريحة الخط الفاصل بينهما. ويقتصر هذا على segements خط يربط بين الذروات (أي VERY غير موحدة)؛ يمكنك أن تفعل أفضل قليلا عن طريق التقاط قمة الثالثة ومن ثم اختيار نقطة بين ذلك وبين النقطة الأولى - ما زالت غير موحدة، ولكن أي ما لا يقل عن نقطة في المضلع ممكن

واختيار نقطة عشوائية على خط بين نقطتين هو سهل، فقط A + ص (B-A)، حيث ألف وباء هي نقاط و p هو رقم عشوائي بين 0.0 و 1.0

Answer 9

ما هو نوع من التوزيع هل تريد النقاط لديك؟ إذا كنت لا تهتم، فإن الأساليب المذكورة أعلاه تعمل بشكل جيد. إذا كنت ترغب في توزيع موحد، فإن الإجراء التالي يعمل: تقسيم المضلع إلى مثلثين، أ و ب. دعونا A (أ) و A (ب) تكون مناطقهم. عينة ع نقطة من توزيع موحد على الفاصل الزمني بين 0 و A (أ) A + (ب). إذا ف

Answer 10

cprnd يولد نقطة من توزيع موحد على متعدد مقام محدب العام. بالنسبة لسؤالك خوارزمية أكثر تخصصا على أساس متحللة الرباعي إلى مثلثات هو أكثر كفاءة.

Answer 11

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