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


الشكل 1. طريقة مباشرة جديدة لبناء تسلسل شبه عشوائي (غير محدود) مفتوح مع اختلاف متباين في مثلث الشكل والحجم التعسفي. يوضح الشكل توزيع النقاط في خمسة عشر مثلثًا عشوائيًا لأول 150 نقطة.

مراجعة قصيرة

تمت دراسة متواليات التباين المنخفضة التي تأخذ عينة / تملأ مربعًا بشكل نشط منذ ما يقرب من مائة عام. يمكن توسيع معظم هذه التسلسلات شبه العشوائية لتشمل المستطيلات عن طريق التمدد البسيط ، دون الإضرار بشكل كبير بالتناقض.

ومع ذلك ، سننظر في هذا المنشور في امتداد مثير للاهتمام ومهم للتسلسلات مع وجود تباعد منخفض في مثلث تعسفي.

بقدر ما أستطيع أن أفهم ، تم إيلاء القليل من الاهتمام لبناء مجموعات من النقاط والتسلسلات موزعة بشكل موحد في مثلث. تمثل الأعمال الجديرة بالملاحظة في الأعوام الأخيرة لكل من Basu [2014] و Pillands [2005] و Brandolini [2013] المقالات الرئيسية ، إن لم تكن الوحيدة حول هذا الموضوع.

عادةً ما ينظر هؤلاء المؤلفون في هذه المشكلة من زاوية نظرية وتحليلية للغاية ، ويقومون دائمًا بحلها من أجل مثلث منتظم واحد. على النقيض من ذلك ، يهدف منصبي بشكل أساسي إلى تطوير تقنيات عملية في تقديم الرسومات.

يصف المنشور طريقة بسيطة للبناء المباشر ، والتي لا تتطلب القبول / الاستبعاد ، أو التخلي أو العودية ؛ والأهم من ذلك ، يمكن تطبيقه على مثلثات ذات حجم وشكل اعتباطيين.

يتألف المنشور من أربعة أقسام:

1. سلاسل عشوائية مربعة
2. تراكب مربع وحدة على مثلث.
3. الحد من تشويه
4. تعميمات أخرى

1. شبه عشوائي تسلسل النقاط

قد تعتقد أن وضع 100 نقطة في مربع بحيث تبقى المسافة بين النقاط المجاورة كبيرة قدر الإمكان. ولكن ماذا لو كنت بحاجة لوضع 13 نقطة؟ 47؟ ماذا عن 2019 نقطة؟

اتضح أن تسلسل النقاط ذات التباعد المنخفض يوفر طريقة منتظمة لحل هذه المشكلة. هناك العديد من التسلسلات شبه العشوائية ذات التباعد المنخفض ، من تسلسل Holton البسيط إلى تسلسل Sable أكثر تعقيدًا. كل من هذه التسلسلات لها مزاياها وعيوبها. على سبيل المثال ، يتضح أن تسلسل Holton يكون أكثر فائدة عند وضع كائنات في منطقة ما ، لأنه يحتوي على مقاييس مسافة محلية محسنة مثل أقرب الجيران. تسلسل Sable عرضة لتكوين "أكثر ازدحامًا" ، لكن التوزيع العالمي للنقاط متساوٍ للغاية ، لذلك يحتوي على خصائص تربيع ممتازة.

هناك تسلسل آخر أود استخدامه ، مع خصائص محلية وعالمية ممتازة. هذا هو التسلسل $$ الموصوفة بالتفصيل في مشاركتي السابقة "كفاءة غير متوقعة من تسلسل شبه عشوائي" .

باختصار ، نحدد تسلسل ثنائي الأبعاد لانهائي $$ مثل هذا

$$

$$\ pmb {t} _n = \ left \ {n \ pmb {\ alpha} \ right \} \ quad n = 1،2،3، ... \ pmb {t} _n = \ left \ {n \ pmb {\ alpha} \ right \} \ quad n = 1،2،3، ...$$

$$

$$\ textrm {where} \ quad \ pmb {\ alpha} = \ left (\ frac {1} {g} ، \ frac {1} {g ^ 2} \ right) ،$$

$$

$$\ textrm {and} \؛ g \ simeq 1.32471795572 \ tag {1}$$

اقرأ المزيد عن هذا المعنى الخاص. $$$g$ ، والذي يُطلق عليه غالبًا "البلاستيك الثابت" ، يمكن قراءته على Wikipedia أو Mathworld .

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


الشكل 2. الشكل التوضيحي من أول 150 عضوا من مختلف تسلسل شبه التباعد شبه العشوائي. لاحظ أنها جميعًا تنشئ نقاط موزعة بالتساوي في الفضاء أكثر من توزيع عشوائي بسيط (أسفل اليسار).

2. فرض مربع وحدة على مثلث

هناك ثلاث طرق معروفة لضمان أخذ عينات عشوائية من مثلث:

1. طريقة متوازي الاضلاع
2. طريقة كرامر و
3. طريقة توزيع الاحتمالات العكسية.

الشكل 3. طريقة متوازي الاضلاع

طريقة متوازي الاضلاع هي كما يلي.

للمثلث $$$\ pmb {ABC}$ النظر في متوازي الاضلاع $$$\ pmb {ABCA '}$ .

للحصول على نقطة من وحدة مربع $$$(r_1 ، r_2)$ وضع مثل هذه النقطة $$$\ pmb {P}$ ذلك $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ .

هذه النقطة ستكون دائما داخل متوازي الاضلاع. ومع ذلك ، إذا ظهر في مثلث إضافي $$$\ pmb {ABC '}$ ثم نحن بحاجة إلى قلبها مرة أخرى إلى المثلث $$$\ pmb {ABC}$ .

هذا هو ، إذا $$$r_1 + r_2 <1$ اذن $$$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ لكن لو $$$r_1 + r_2> 1 دولا$ اذن $$$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$ .

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

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

وبالمثل ، فإن طريقة توزيع الاحتمالات العكسية تطبق التشوه اللاخطي على النقاط. في تسلسلات Holton و Sable ، هذا يعني أن نقطتين غالباً ما تدفعان ببعضهما البعض بشكل وثيق.

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


الشكل 4. مقارنة التحول من مختلف سلاسل شبه عشوائية في مثلث. أعلاه هو تسلسل Holton ، في الوسط هو تسلسل Sable ، أدناه هو التسلسل $$ . يمكن ملاحظة أن هناك ازدحامًا كبيرًا للنقاط يحدث في تسلسل هولتون ، وتشكيل شريط مهم في تسلسل سوبول. مقارنة بهم ، في التسلسل $$ يتم توزيع النقاط بشكل متساوٍ للغاية ، ولا يوجد تقريبًا أي حشود أو خطوط ملحوظة.

من بين ثلاث طرق مختلفة للتثليث والعديد من التتابعات شبه العشوائية المختلفة ، تم تطبيق طريقة متوازي الاضلاع على طريقة التتابع $$ هي المجموعة الوحيدة التي تخلق باستمرار نتائج مقبولة من حيث الحفاظ على التباين المنخفض دون تشويه.

يمكن فحص النتائج الممتازة لهذا المزيج بمزيد من التفصيل في الشكل 5.


الشكل 5. يمكنك أن ترى أن تسلسل المحولة $$ يوفر طريقة بسيطة للغاية ولكنها فعالة لتوزيع العديد من $$$N$ نقاط في المثلث. وهو يعمل مع مثلثات بزاوية حادة وزاوية منفرجة. (اللون يشير إلى الترتيب).

3. جوانب أخرى

تشويه

تتطلب طريقة متوازي الاضلاع اختيار وجهي المثلث متجهين أساسيين.

إذا كانت القمم مرتبة بترتيب عشوائي ، فإن أنماط النقاط تشبه عادة تلك الموضحة في الشكل 6.


الشكل 6. أنماط النقاط التي تم الحصول عليها عن طريق اختيار عشوائي ترتيب القمم. لاحظ أنه في معظم الحالات ، يكون التشويه ملحوظًا بشكل واضح.

ومع ذلك ، اتضح أنه مع الاختيار الدقيق لترتيب القمم ، يمكن تقليل التشوهات بشكل كبير. وأبرزها ، إذا قمت بتسمية المثلث بحيث $$$دولا$ هي أكبر زاوية (أي أكبر جانب ضدها) ، ثم الجانبين $$$\ pmb {AB}$ و $$$\ pmb {AC}$ تستخدم كوجهين من متوازي الاضلاع.

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

ومع ذلك ، حتى مع وجود ترتيب معين من القمم ، في بعض الحالات ، لا تزال آثار التشويه ملحوظة. تكون أكثر وضوحًا عندما تكون إحدى زوايا المثلثات صغيرة جدًا. في حالة المثلثات المنفصلة ، عندما تكون أصغر زاوية أقل من 30 درجة ، يكون بعض التشوه ملحوظًا ، وفي حالة المثلثات الزاوية الحادة ، عندما تكون أصغر زاوية أقل من 20 درجة ، يصبح التشوه واضحًا. (إذا كانت المثلثات التي تم أخذ عينات منها جزءًا من شبكة Delaunay ، فإن مشكلات التشويه هذه قد تكون ضئيلة ، لأن Tria Triangulation Delaunay مصمم خصيصًا لتقليل عدد المثلثات ذات الزوايا الصغيرة.)

اشكال اخرى

لسوء الحظ ، لا يمكن استخدام تقنية متوازي الاضلاع لأشكال أخرى ، لأنها تستخدم تناظر المثلث. بالنسبة لبعض الأشكال ، يمكن الحصول على نتائج جيدة باستخدام طريقة توزيع الاحتمالات العكسية. فيما يلي مثال عن كيفية التسلسل $$$R_2R_2$ مع اختلاف التباعد ، يمكنك التحويل إلى منطقة يحدها منحنى غاوسي مع الحفاظ على مسافة موحدة بين النقاط.