Delaunay refinement
મેશ જનરેશનમાં, ડેલાઉને રિફાઇનમેન્ટ્સ એ મેશ જનરેશન માટેના અલ્ગોરિધમ્સ છે જે મેશ કરવાના ઇનપુટની ભૂમિતિમાં સ્ટેઇનર પોઇન્ટ્સ ઉમેરવાના સિદ્ધાંત પર આધારિત છે, જે રીતે ડેલાઉને ત્રિકોણ અથવા સંવર્ધિત ઇનપુટના મર્યાદિત ડેલાઉને ત્રિકોણને મેશિંગ એપ્લિકેશનની ગુણવત્તાની જરૂરિયાતોને પહોંચી વળવા માટેનું કારણ બને છે. વિલંબિત શુદ્ધિકરણ પદ્ધતિઓમાં ચ્યુ અને રુપર્ટ દ્વારા પદ્ધતિઓનો સમાવેશ થાય છે. ચ્યુની બીજી અલ્ગોરિધમ ચ્યુની બીજી અલ્ગોરિધમ પીસવાઇઝ રેખીય પ્રણાલી (પી. એલ. એસ.) લે છે અને માત્ર ગુણવત્તાવાળા ત્રિકોણોનું મર્યાદિત ડેલાઉને ત્રિકોણ આપે છે જ્યાં ગુણવત્તા ત્રિકોણમાં લઘુત્તમ ખૂણા દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે. એલ. પોલ ચ્યુ દ્વારા ત્રિ-પરિમાણીય જગ્યામાં જડિત મેશિંગ સપાટીઓ માટે વિકસિત, ચ્યુના બીજા અલ્ગોરિધમને અમુક કિસ્સાઓમાં રૂપર્ટના અલ્ગોરિધમ પર વ્યવહારુ ફાયદાઓને કારણે દ્વિ-પરિમાણીય મેશ જનરેટર તરીકે અપનાવવામાં આવ્યું છે અને તે મુક્તપણે ઉપલબ્ધ ત્રિકોણ પેકેજમાં અમલમાં મૂકાયેલ મૂળભૂત ગુણવત્તાવાળું મેશ જનરેટર છે. ચ્યુના બીજા અલ્ગોરિધમનો લગભગ 28.6 ડિગ્રી સુધીના લઘુતમ ખૂણા સાથે સ્થાનિક સુવિધાના કદ-શ્રેણીબદ્ધ જાળીઓને સમાપ્ત કરવાની અને ઉત્પન્ન કરવાની ખાતરી આપે છે. અલ્ગોરિધમ ઇનપુટ શિરોબિંદુઓના મર્યાદિત ડેલાઉને ત્રિકોણ સાથે શરૂ થાય છે. દરેક તબક્કે, નબળી ગુણવત્તાવાળા ત્રિકોણનું પરિઘ કેન્દ્ર એક અપવાદ સાથે ત્રિકોણમાં દાખલ કરવામાં આવે છેઃ જો પરિઘ કેન્દ્ર નબળી ગુણવત્તાવાળા ત્રિકોણ તરીકે ઇનપુટ સેગમેન્ટની વિરુદ્ધ બાજુએ આવેલું હોય, તો ખંડનું મધ્યબિંદુ દાખલ કરવામાં આવે છે. વધુમાં, મૂળ ખંડના વ્યાસના દડાની અંદર અગાઉ દાખલ કરવામાં આવેલા કોઈપણ પરિઘ કેન્દ્રો (તે વિભાજિત થાય તે પહેલાં) ત્રિકોણમાંથી દૂર કરવામાં આવે છે. જ્યાં સુધી કોઈ નબળી ગુણવત્તાવાળા ત્રિકોણ અસ્તિત્વમાં ન હોય ત્યાં સુધી સર્કમસેન્ટર દાખલ કરવાનું પુનરાવર્તન કરવામાં આવે છે. રૂપર્ટનું અલ્ગોરિધમ રૂપર્ટનું અલ્ગોરિધમ સમતલીય સીધી-રેખા આલેખ (અથવા બે કરતા વધુ પરિમાણમાં એક પીસવાઇઝ રેખીય પ્રણાલી) લે છે અને માત્ર ગુણવત્તાયુક્ત ત્રિકોણોનું અનુરૂપ ડેલાઉને ત્રિકોણ આપે છે. ત્રિકોણને નબળી ગુણવત્તાનો ગણવામાં આવે છે જો તેનો પરિઘાકાર અને ટૂંકી ધારનો ગુણોત્તર અમુક નિર્ધારિત સીમા કરતાં મોટો હોય. 1990 ના દાયકાની શરૂઆતમાં જિમ રુપર્ટ દ્વારા શોધાયેલ, "દ્વિ-પરિમાણીય ગુણવત્તાની જાળી પેઢી માટે રૂપર્ટનું અલ્ગોરિધમ કદાચ વ્યવહારમાં ખરેખર સંતોષકારક હોય તેવું પ્રથમ સૈદ્ધાંતિક રીતે બાંયધરીકૃત મેશિંગ અલ્ગોરિધમ છે". પ્રેરણા કોમ્પ્યુટેશનલ ફ્લુઇડ ડાયનામિક્સ જેવા કોમ્પ્યુટર સિમ્યુલેશન કરતી વખતે, પાંખ વિભાગના 2D રૂપરેખા જેવા મોડેલથી શરૂઆત થાય છે. 2D મર્યાદિત તત્વ પદ્ધતિનું ઇનપુટ ત્રિકોણના સ્વરૂપમાં હોવું જરૂરી છે જે બધી જગ્યા ભરે છે, અને દરેક ત્રિકોણ એક પ્રકારની સામગ્રીથી ભરેલો હોવો જોઈએ-આ ઉદાહરણમાં, કાં તો "હવા" અથવા "પાંખ". લાંબા, પાતળા ત્રિકોણોનું સચોટ રીતે અનુકરણ કરી શકાતું નથી. સિમ્યુલેશનનો સમય સામાન્ય રીતે ત્રિકોણની સંખ્યાના પ્રમાણમાં હોય છે, અને તેથી કોઈ ત્રિકોણની સંખ્યાને ઘટાડવા માંગે છે, જ્યારે હજુ પણ વ્યાજબી રીતે સચોટ પરિણામો આપવા માટે પૂરતા ત્રિકોણનો ઉપયોગ કરે છે-સામાન્ય રીતે અનસ્ટ્રક્ચર્ડ ગ્રીડનો ઉપયોગ કરીને. કોમ્પ્યુટર મર્યાદિત તત્વ પદ્ધતિ માટે યોગ્ય ત્રિકોણમાં બહુકોણીય મોડેલને રૂપાંતરિત કરવા માટે રૂપર્ટના અલ્ગોરિધમનો (અથવા કેટલાક સમાન મેશિંગ અલ્ગોરિધમનો) ઉપયોગ કરે છે. અલ્ગોરિધમ અલ્ગોરિધમ ઇનપુટ શિરોબિંદુઓના ડેલાઉને ત્રિકોણથી શરૂ થાય છે અને પછી તેમાં બે મુખ્ય કામગીરીઓનો સમાવેશ થાય છે. બિન-ખાલી વ્યાસ વર્તુળોવાળા ખંડના મધ્યબિંદુને ત્રિકોણમાં દાખલ કરવામાં આવે છે. નબળી ગુણવત્તાવાળા ત્રિકોણનું પરિઘ કેન્દ્ર ત્રિકોણમાં દાખલ કરવામાં આવે છે, સિવાય કે આ પરિઘ કેન્દ્ર કોઈ ખંડના વ્યાસ વર્તુળમાં હોય. આ કિસ્સામાં, તેના બદલે અતિક્રમણ કરેલ સેગમેન્ટ વિભાજિત થાય છે. જ્યાં સુધી કોઈ નબળી ગુણવત્તાવાળા ત્રિકોણ અસ્તિત્વમાં ન હોય અને તમામ વિભાગોનું અતિક્રમણ ન થાય ત્યાં સુધી આ કામગીરીઓનું પુનરાવર્તન કરવામાં આવે છે. સ્યુડોકોડ ફંક્શન રૂપર્ટ (બિંદુઓ, સેગમેન્ટ્સ, થ્રેશોલ્ડ) એ T: = ડિલાઉને ત્રિકોણ (બિંદુઓ) Q: = અતિક્રમણ કરેલા સેગમેન્ટ્સનો સમૂહ અને નબળી ગુણવત્તાવાળા ત્રિકોણ જ્યારે Q ખાલી નથીઃ// મુખ્ય લૂપ જો Q માં સેગમેન્ટ s હોય તોઃ S નું મધ્યબિંદુ T માં દાખલ કરો અન્યથા Q માં નબળી ગુણવત્તાનો ત્રિકોણ t હોયઃ જો t નું પરિઘ કેન્દ્ર એક સેગમેન્ટ s ને અતિક્રમણ કરે તોઃ S ને Q માં ઉમેરો; અન્યથાઃ T ના પરિઘ કેન્દ્રને T અંતમાં દાખલ કરો જો અંત હોય તો Q અંતને અપડેટ કરો જ્યારે T અંત રૂપર્ટ પરત કરો. ફેરફાર વિના વ્યવહારુ ઉપયોગ રુપર્ટના અલ્ગોરિધમને બિન-તીવ્ર ઇનપુટ અને લગભગ 20.7 ડિગ્રીથી ઓછી કોઈપણ નબળી-ગુણવત્તાની મર્યાદા માટે ગુણવત્તાયુક્ત જાળી સમાપ્ત કરવાની અને ઉત્પન્ન કરવાની ખાતરી આપવામાં આવે છે. આ પ્રતિબંધોને હળવા કરવા માટે વિવિધ નાના સુધારા કરવામાં આવ્યા છે. નાના ઇનપુટ ખૂણાઓની નજીક ગુણવત્તાની જરૂરિયાતને હળવી કરીને, કોઈપણ સીધી-લાઇન ઇનપુટને નિયંત્રિત કરવા માટે અલ્ગોરિધમનો વિસ્તાર કરી શકાય છે. વક્ર ઇનપુટને પણ સમાન તકનીકોનો ઉપયોગ કરીને જોડી શકાય છે. રૂપર્ટના અલ્ગોરિધમને કુદરતી રીતે ત્રણ પરિમાણો સુધી વિસ્તૃત કરી શકાય છે, જો કે સ્લિવર પ્રકારનાં ટેટ્રાહેડ્રોનને કારણે તેની આઉટપુટ બાંયધરીઓ થોડી નબળી છે. બે પરિમાણોમાં રૂપર્ટના અલ્ગોરિધમનો વિસ્તાર મુક્તપણે ઉપલબ્ધ ત્રિકોણ પેકેજમાં લાગુ કરવામાં આવે છે. આ પેકેજમાં રુપર્ટના અલ્ગોરિધમનોના બે પ્રકારો લગભગ 26.5 ડિગ્રીની નબળી-ગુણવત્તાની મર્યાદા માટે સમાપ્ત થવાની ખાતરી આપે છે. વ્યવહારમાં આ અલ્ગોરિધમ્સ 30 ડિગ્રીથી વધુની નબળી ગુણવત્તાની મર્યાદાઓ માટે સફળ છે. જો કે, ઉદાહરણો જાણીતા છે જે અલ્ગોરિધમને 29.06 ડિગ્રી કરતા વધુ થ્રેશોલ્ડ સાથે નિષ્ફળ થવાનું કારણ બને છે. આ પણ જુઓ સ્થાનિક લક્ષણ કદ બહુકોણ જાળીદાર ટેટજેન વોરોનોઈ આકૃતિ સંદર્ભો વધુ વાંચન જાળીદાર પેઢી ત્રિકોણ (ભૂમિતિ) વિડિયો ક્લિપ્સ ધરાવતા લેખો