شبکه بندی بی سازمان به روش دلانی و جبهه پیش رونده

Advanced Front And Delaunay Triangulation Unstructured Grid Generation

در شبکه بندی بی سازمان به روش دلانی و جبهه پیش رونده، توزیع نقاط ممکن است از سوی مرز داخلی یا از سوی مرز خارجی و یا از هر دو سوی مرز داخلی و خارجی گسترش یابد که بوسیله تابع فاصله نقاط زمینه کنترل می‌شود. پس از تولید نقاط، فرایند حذف و ادغام روی هر یک از نقاط بررسی شده و در نهایت پس از قطعی شدن، نقاط تولید شده مثلث‌بندی می‌شوند. با پایان یافتن تولید نقاط و مثلث‌بندی نهایی، شبکه هموارسازی می‌شود. با توجه به این مطالب می‌توان فرآیند کلی تولید شبکه بی‌سازمان را طبق مراحل زیر خلاصه نمود [1] و [2]:

1-تولید نقاط مرزی داخلی و خارجی،

2-تشکیل اَبَرمثلث (Super Triangle)،

3-انجام فرایند مثلث‌بندی دلانی،

4-مشخص نمودن تابع فاصله یا همان تابع توزیع(Distribution Function) نقاط مرزی،

5-حذف مثلثهای خارج از مرز خارجی،

6-سازماندهی اطلاعات هر المان، از قبیل شماره، رئوس، همسایه‌ها و خوب یا بد بودن،

7-تولید نقاط جدید برای المانهای بد،

8-مشخص کردن المانی که دربرگیرنده نقطه جدید می‌باشد (همانند بخش اول توضیح داده شده مربوط به شکل(2) در بند 3)،

9-حذف نقاط بسیار نزدیک به نقاط زمینه،

10-ادغام نقاط تولید شده در صورتی که نقاط یاد شده بیش از اندازه به یکدیگر نزدیک باشند،

11-سازماندهی کردن نقاط باقیمانده و افزایش آنها به نقاط زمینه،

12-تولید المانهای جدید بوسیله مثلث‌بندی دلانی،

13-تکرار مراحل 12-7 تا زمانی که هیچ نقطه جدیدی تولید نشود و یا تمام نقاط تولید شده حذف و یا در هم ادغام شوند و

14-انجام فرآیند هموارسازی.

1- تولید نقاط مرزی

اولین گام برای تولید شبکه مشخص نمودن نقاط مرزهای داخلی و خارجی می‌باشد. اصولاً در آئرودینامیک خارجی، مرزهای خارجی بیانگر دامنه بی‌نهایت و داخلی بیانگر سطح جسم می‌باشد. در جریان‌های خارجی، مرز خارجی می‌تواند دایره، بیضی، مستطیل و غیره (جریانهای دوبعدی) یا استوانه، بیضوی و کروی (جریانهای سه بعدی) باشد. در چنین مسائلی برای تولید نقاط روی مرزهای خارجی، توزیع کسینوسی مناسبتر است.‌ اما، در مورد مرز داخلی اگر جسم مورد نظر یک ایرفویل ساده باشد، بازهم توزیع کسینوسی پیشنهاد می‌شود.

همچنین، در صورتیکه جسم پیچیده‌ای همانند ایرفویل چند تکه باشد برای دستیابی به جواب بهتر، باید در لبه‌ها و نواحی که تغییرات هندسی شدید است، تعداد نقاط را افزایش داد. این مهم برای جریانهای داخلی و روی سطوح مدل نیز صادق است. بطور کلی توزیع نقاط روی مرزها باید به گونه‌ای باشد که بتواند گرادیانهای جریان را با دقت مناسبی مدل کند. چگونگی تولید نقاط روی لبه (خط) به طور کامل در اینجا بررسی شده است.

2- تشکیل اَبَر مثلث

به عنوان گام بعدی سه نقطه با فاصله بسیار دور از مرزهای بیرونی تعریف می‌شود. سپس با استفاده از این سه نقطه یک مثلث بزرگ (اَبَر مثلث) که تمامی نقاط مرزهای دامنه محاسباتی را در بر می‌گیرد تولید می‌شود (شکل-1).

3- مثلث بندی دلانی

پس از مشخص نمودن نقاط مرزی ودر نظر گرفتن سه نقطه بسیار دور از مرزها برای تولید یک اَبَر مثلث و مثلث بندی برای اولین نقطه (شکل-1)، مثلث‌بندی دلانی انجام می‌شود. همانطور که پیشتر اشاره شد، مثلث بندی دلانی یک روش برای تولید المانهای مثلث شکل با کیفیت بالا روی نقاط موجود است (در این مرحله شامل نقاط ابر مثلث، مرز‌ خارجی و مرز داخلی می‌باشد). روندکلی مثلث بندی دلانی را می‌توان در مراحل زیر خلاصه کرد:

یافتن المان دربرگیرنده نقطه افزوده شده «P» به داخل میدان (شکل-2)،
اتصال نقطه P به گره‌های المان دربرگیرنده آن وتولید مثلثهای جدید،
مشخص نمودن اضلاع مشکوک و
انجام فرایند جابجایی(Swaping).

یافتن المان دربرگیرنده نقطه افزوده شده «P» به داخل میدان

برای یافتن المان شامل نقطه P از روش جستجوی قدم زدنی استفاده می‌شود. توجه شود که نقطه P زمانی درون مثلثی قرار می‌گیرد که ضرب خارجی آن با تمام اضلاع مثلث کوچکتر از صفر باشد. بهمین منظور پیدا کردن نقطه P با حدسی مناسب برای یک المان (بعنوان مثال، آخرین مثلث تولید شده) شروع می‌شود. اگر ضرب خارجی نقطه P با یکی از اضلاع مثلث بزرگتر از صفر باشد، همسایه متناظر با این ضلع، بعنوان گام بعدی در نظر گرفته می‌شود و تا زمانیکه المان مورد نظر یافت شود ادامه خواهد داشت. شکل(2) نمایانگر چگونگی یافتن نقطه P از المان مفروض N با استفاده از روش جستجوی قدم زنی می‌باشد. روشهای مختلف جستجوی نقاط در مراجع بطور کامل شرح داده شده است.

مشخص نمودن اضلاع مشکوک و انجام فرایند جابجایی(Swaping)

پس از یافتن المان شامل نقطه P و اتصال این نقطه به سه راس المان و تبدیل آن به سه مثلث جدید، از الگوریتم جابجایی برای دستیابی به مثلث‌بندی دلانی استفاده می‌شود. برای انجام عمل جابجایی باید تمام مثلثهای مجاور لبه‌های مثلث دربرگیرنده نقطه P به نوبت و از آخر به این منظور که آیا نقطه P درون دایره محیطی آنها قرار دارد یا خیر، بررسی شود. اگر چنین حالتی بود، مثلثی را که نقطه P رأس آن است و مثلث مجاور آن را از یک چهار وجهی محدب که قطر آن در جهت مخالف رسم شده باید، با نقطه دیگری جایگزین کرد تا خاصیت مثلث‌بندی دلانی حفظ شود (شکل-3).

پس از تکمیل جابجایی، مثلثهایی را که اکنون در مقابلP هستند نیز باید افزوده شده و مورد بررسی قرار گیرند. این عملیات را تا بررسی کامل تمام مثلثهای مذکور ادامه می‌دهیم. توجه داشته باشید که نقطه P زمانی درون داخل دایره محیطی مثلث دلخواه ABC قرار دارد که رابطه (137) صادق باشد. طولهای بکار رفته در این معادله از روابط (138) قابل محاسبه است.

در شکلهای (4) تا (8) روند شبکه‌بندی روی ایرفویل NACA 0012 نشان داده شده است.

4- تعیین تابع فاصله نقاط مرزی در شبکه بندی بی سازمان به روش دلانی و جبهه پیش رونده

تابع فاصله هر یک از نقاط که ارزش آن‌ها نیز نامیده می‌شود، از روشهای گوناگونی محاسبه می‌گردد. معمول‌ترین روش برای یافتن تابع فاصله هر یک از نقاط مرزی میانگین فاصله بین آن نقطه و نقاط قبل و بعد آن می‌باشد که از رابطه (139) محاسبه می‌شود. در این معادله ds_i و ds_i+1 نیز طبق روابط (140) بدست می‌آیند.

5- سازماندهی اطلاعات

یکی از موضوعات مهم در شبکه بندی بی سازمان به روش دلانی و جبهه پیش رونده، سازماندهی اطلاعات بمنظور ساده سازی الگوریتم تولید شبکه و جلوگیری از انجام محاسبات اضافی و کاهش زمان اجرای برنامه می‌باشد. بطور کلی، اطلاعات اصلی را می‌توان در قالب اطلاعات مربوط به شماره گره‌ها، مختصات گره‌ها، تابع فاصله گره‌ها، شماره المانها، گره‌های مربوط به هر المان، همسایه‌های هر المان و همچنین خوب یا بد بودن هر المان خلاصه نمود. به غیر از اینها همواره اطلاعات بیشتری برای ارضاء کردن شرطهای احتمالی نیز نیاز خواهد بود.

لازم است در طول فرآیند شبکه‌بندی یک پایگاه اطلاعتی موقتی برای مشخصات یاد شده تولید شود. برای تولید ساده‌تر چنین پایگاهی می‌توان از مقدار دهی عددی برای ارزشیابی المانها استفاده کرد. بعنوان مثال، المانهای خوب را با عدد 1 و المانهای بد را با عدد صفر مقدار دهی کرد. پس از اتمام فرآیند شبکه بندی تولید یک پایگاه داده‌ای متشکل از شماره هر المان، گره‌های هر المان، همسایه‌های هرالمان و لبه‌های هر المان الزامی است.

6- تعیین خوب یا بد بودن هر المان

کیفیت هر المان دلیل اصلی تولید یا عدم تولید نقاط جدید می‌باشد. نقاط جدید همواره برای المان بد تولید می‌شود. در مراجع مختلف روابط گوناگونی برای تعریف مثلث خوب یا بد ارائه شده است در این قسمت دو تا از مهمترین معیارها به صورت زیر معرفی شده است:

الف- اگر خصوصیات مثلثی در رابطه (141) صدق کند، آن مثلث بد و اگر صدق نکند، خوب نامیده می‌شود. در این رابطه S_min طول کوتاهترین ضلع و S_max طول بلندترین ضلع مثلث می‌باشد.

ب- اگر طول یکی از اضلاع مثلث کوچکتر از 5/1برابر متوسط تابع فاصله گره‌های آن مثلث باشد، مثلث بد می‌باشد، در غیر اینصورت آن مثلث یک المان خوب بحساب می‌آید.

7- تولید نقاط جدید برای المانهای بد

در شبکه بندی بی سازمان به روش دلانی و جبهه پیش رونده، برای تولید نقاط جدیدی که از این روش استفاده می‌کنند، محل جبهه از اهمیت خاصی برخوردار است. برای تولید نقاط همواره فرض بر این است که مرز بین المانهای خوب و بد، محل جبهه می‌باشد. برای اضلاعی گره جدید تولید می‌شود که اولاً متعلق به یک المان بد باشد و ثانیاً، آن المان همسایه یک المان خوب باشد. اگر در مثلثی دو ضلع کوچکتر مجاور دو مثلث خوب باشد برای هر کدام نقطه‌ای تولید کرده و گره نهایی میانگین دو نقطه تولید شده در نظر گرفته می‌شود.

اگرهمسایه‌های هر سه ضلع یک مثلث بد، خوب باشد با توجه به خصوصیات مثلث بد، می‌توان نقطه‌ای در نظر نگرفت ویا اینکه نقطه در نظر گرفته شده وسط آن باشد. سه دو نمونه روش معمول‌تر برای یافتن مکان نقطه پیشنهادی جدید عبارتست از:

الف- تولید نقطه در وسط مثلث (محل برخورد میانه‌های مثلث)

ب- نقطه تولید شده در جایی واقع شود که دو رأس ضلع متناظر با نقطهجدید و خود نقطه جدید یک مثلث متساوی الاضلاع بوجود آورند، یعنی طول اضلاع 2- 1،P -2 و 1-P با هم برابر باشد (شکل-9).

ج- با فرض اینکه مثلثی که بر روی گره جدید و دو گره قدیمی تولید می‌شود تقریباً متساوی الاضلاع باشد (این مثلث در واقع متساوی الساقین است) و مقدار تابع فاصله در نقاط 1، 2 وP به ترتیب h₁، h₂ و h₃ باشد. برای یافتن ضلع جدید (P-1) که برابر 1 فرض شده از روابط (142 تا 144) استفاده می‌شود.

که در آن، بردار S_i بردار عمود بر ضلع روبروی راس iام، Aمساحت المان و ^n بردار یکه عمود بر ضلع 2-1 در نقطه M که وسط ضلع 2-1 واقع است (شکل-9)، می‌باشد. هر دو روش ذکر شده نتایج نسبتاً مشابهی دارند، با این تفاوت که روش اول ساده‌تر و سازمان یافته‌تر می‌باشد، ولی روش دوم پیچیده‌تر و رشد شبکه در آن سریع‌تر است.

پس از تولید هر گره، تابع فاصله آن نیز باید محاسبه گردد. تابع فاصله نقاط جدید را می‌توان با استفاده از میانیابی خطی محاسبه نمود. یکی از روشهای یافتن تابع فاصله در رابطه (143) عنوان شده است. روش الف نسبت به دو روش ب و ج که در بالا شرح داده شد ساده‌تر می‌باشد، ولی المانهای تولید شده در این روش دارای کیفیت پایین‌تری است.

9- حذف نقاط پیشنهادی

همانطوری که پیشتر اشاره شد، ملاک تولید نقاط جدید شکل المانها و تابع فاصله می‌باشد. روند تولید نقاط جدید تضمینی برای آنکه نقاط تولید شده بیش از اندازه به نقاط شبکه موجود نزدیک نباشد، ندارد. بنابراین، لازم است قبل از اینکه نقاط جدید پیشنهادی قطعی شود، مورد بررسی قرار گیرد. برای این بررسی، المان در برگیرنده نقطه پیشنهادی مشخص و سپس فاصله این نقطه با رئوس آن المان و المانهای همسایه‌های ردیف اول آن محاسبه می‌شود. اگر یکی از این فاصله‌ها کوچکتر از β*1/2(h_p+h_j) (β مضرب متغیر) باشد، نقطه مذکور خذف می‌شود. β مضربی است که میزان تجمع نقاط یک منطقه نسبت به تابع فاصله محلی را کنترل می‌کند و معمولاً کوچکتر از 0.7 است (0.1 تا 0.7 بسته به تجمع نقاط).

10- ادغام نقاط پیشنهادی

برای ادغام نقاط پیشنهادی که بیش از اندازه به یکدیگر نزدیک می‌باشند، لازم است نزدیکترین نقطه از لیست نقاط جدید پیشنهادی به هر نقطه تعیین شود. برای انجام اینکار از روشهایی که شرح داده شده می‌توان استفاده کرد. پس از تعیین نزدیکترین نقطه به نقطه در نظر گرفته شده، فاصله بین دو نقطه اگر کوچکتر از ‌ α*1/2(h_p+h_j) باشد، این دو نقطه حذف و میانگین آنها جایگزین می‌شود. مقدار α بسته به توزیع نقاط متفاوت بوده و بین 0.1 تا 0.9 می‌باشد.

11- سازماندهی نقاط باقیمانده

پس از آنکه فرآیند حذف و ادغام انجام شد، نقاط باقیمانده به لیست نقاط قطعی افزوده می‌شود. در این مرحله لازم است در فایل پایگاه دادهای موقتی که در بالا معرفی شد، تصحیحات لازم انجام شود. این تصحیحات شامل تصحیح خصوصیات گره‌ها (همچون شماره گره‌ها، موقعیت و تابع فاصله آن‌ها) در سازمان اطلاعات مربوط به گره‌ها ذخیره می‌شود.

12- تولید المانهای جدید

با پایان یافتن سازماندهی اطلاعات نقاط پیشنهادی، با استفاده از مثلث‌بندی دلانی این نقاط به ترتیب به شبکه افزوده شده، المانهای جدید تولید می‌شود و همانند قبل از فرآیند جابجایی نیز استفاده می‌شود. با پایان یافتن مثلث بندی دلانی در این مرحله، باید مراحل (4 تا 9) آنقدر تکرار شود تا هیچ گره جدیدی تولید نشود. پس از رسیدن به این مرحله فرآیند تولید شبکه تقریباً خاتمه می یابد و شبکه تنها به تصحیحات مختصری نیاز دارد که در قسمت بعدی توضیح داده می شود.

14-هموارسازی شبکه

زمانیکه تولید نقاط در مرزهای مختلف یکسان نباشد، اغلب در نواحی تداخل جبهه‌هایی که از مرزهای متفاوت پیشرفت می‌کنند، شبکه هموار نیست و با وجود تمام تلاشهایی که برای تولید نقاط مناسب در شبکه به منظور تولید المانهای خوب انجام می‌شود باز هم المانهایی با کیفییت پایین (نسبت منظری بالا) تشکیل می‌شود که عمدتاً به دلیل موقعیت نامناسب نقاط نسبت به یکدیگر است. بعلاوه، تغییر ناگهانی در اندازه المانهای مجاور بوجود می‌آید. به همین دلیل، پس از کامل شدن شبکه لازم است آن را هموارسازی نمود.

هموار سازی شبکه بخاطر افزایش کیفییت شبکه (به مقدار محدود) با جابجایی اندک نقاط می‌باشد. یکی از متداولترین روشهای هموارسازی، هموارسازی لاپلاسی است. در این جا از روش شبه لاپلاسی معادله (145) استفاده شده است.

در معادله فوق، بردار X_ipoin بردار مختصات نقطه گره، بردار X_ielem بردار مختصات مرکز المان، N تعداد المانهای اطراف و c ضریب هموارسازی می‌باشد. ضریب هموارسازی برای نقاط کاملاً درونی برابر5/0، نقاط مجاور نقاط مرزی 25/0 و برای نقاط مرزی برابر صفر است. در شکل (10) تفاوت بین کیفیت شبکه قبل و بعد از فرایند هموارسازی نشان داده شده است.

با انجام عمل هموارسازی فرآیند تولید شبکه بطور کامل پایان می‌پذیرد و بسته به توزیع نقاط روی مرزهای داخلی و بخصوص مرزهای مقعر (همچنان، تعریف تابع فاصله و ضرائب مربوط به حذف و ادغام)، شبکه‌های تولید شده دارای کیفیت متفاوتی می‌باشند.

مثال: شبکه بندی بی سازمان با روش دلانی و جبهه پیش رونده حول دایره و ایرفویل

تولید شبکه بی سازمان و حل جریان تراکم پذیر آشفته حول اجسام نامتقارن دوبعدی

:[1]

K. A. Hoffman AND S.T. Chaing, “Computational Fluid Dynamics for Engineer”, Volume 1, Engineering Education System, Wichita, Kansas, 1993

:[2]

**.Thompson, J.F., Soni, B.K., and Weatherill, N.P., “HandBook of Grid Generation”, CRC Press, London, New York and Washington D.C., 1999**

:[3]

http://nht.xjtu.edu.cn/paper/en/1999204.pdf

شبکه بندی بی سازمان به روش دلانی و جبهه پیش رونده