Midpoint circle algorithm
કોમ્પ્યુટર ગ્રાફિક્સમાં, મધ્યબિંદુ વર્તુળ અલ્ગોરિધમ એ એક અલ્ગોરિધમ છે જેનો ઉપયોગ વર્તુળને રાસ્ટરાઇઝ કરવા માટે જરૂરી બિંદુઓ નક્કી કરવા માટે થાય છે. તે બ્રેસેનહામના લાઇન અલ્ગોરિધમનું સામાન્યીકરણ છે. અલ્ગોરિધમનોને શંકુ વિભાગોમાં વધુ સામાન્ય બનાવી શકાય છે. અને વેન અકેન. મશીનિંગ (સી. એન. સી.) માં, તેને ગોળાકાર પ્રક્ષેપણ તરીકે ઓળખવામાં આવે છે. સારાંશ આ અલ્ગોરિધમ દરેક મુખ્ય દિશા (0°, 90°, 180°, 270°) થી શરૂ કરીને તમામ આઠ અષ્ટકો એકસાથે ખેંચે છે અને 45° (45°, 135°, 225°, 325°) ના નજીકના ગુણાંક સુધી પહોંચવા માટે બંને રીતે વિસ્તરે છે. તે નક્કી કરી શકે છે કે ક્યાં રોકવું કારણ કે ક્યારે =, તે 45° સુધી પહોંચી ગયું છે. આ ખૂણાઓનો ઉપયોગ કરવાનું કારણ ઉપરના ચિત્રમાં દર્શાવવામાં આવ્યું છેઃ જેમ જેમ વધારો થાય છે તેમ તેમ તે 45° સુધી પહોંચે ત્યાં સુધી કોઈ પણ મૂલ્યને છોડતું નથી કે પુનરાવર્તન કરતું નથી. તેથી વાઇલ લૂપ દરમિયાન, દરેક પુનરાવર્તનમાં 1 નો વધારો થાય છે, અને પ્રસંગે 1 નો ઘટાડો થાય છે, એક પુનરાવર્તનમાં ક્યારેય 1 થી વધુ નહીં. આ 45° પર બદલાય છે કારણ કે તે તે બિંદુ છે જ્યાં સ્પર્શક વધે છે = દોડે છે. જ્યારે ઊઠો> પહેલાં દોડો અને ઊઠો <પાછળ દોડો. સમસ્યાનો બીજો ભાગ, નિર્ધારક, વધુ જટિલ છે. આ નક્કી કરે છે કે ક્યારે ઘટાડો કરવો. તે સામાન્ય રીતે દરેક પુનરાવર્તનમાં પિક્સેલ્સ દોર્યા પછી આવે છે, કારણ કે તે ક્યારેય પ્રથમ પિક્સેલ પર ત્રિજ્યાની નીચે જતું નથી. કારણ કે સતત કાર્યમાં, ગોળા માટેનું કાર્ય એ ત્રિજ્યા (અથવા જે પણ ત્રીજું ચલ છે) પર આધારિત વર્તુળ માટેનું કાર્ય છે, તે કારણભૂત છે કે સ્વતંત્ર (વોક્સેલ) ગોળા માટેનું અલ્ગોરિધમ પણ આ મધ્યબિંદુ વર્તુળ અલ્ગોરિધમ પર આધાર રાખે છે. પરંતુ જ્યારે ગોળાને જોવામાં આવે છે, ત્યારે કેટલાક નજીકના વર્તુળોની પૂર્ણાંક ત્રિજ્યા સમાન હોય છે, પરંતુ તે જ ગોળાર્ધમાં તેની બાજુમાં સમાન ચોક્કસ વર્તુળ હોવાની અપેક્ષા નથી. તેના બદલે, સમાન ત્રિજ્યાના વર્તુળને એક અલગ નિર્ધારકની જરૂર હોય છે, જેથી વળાંક કેન્દ્રની સહેજ નજીક આવે અથવા વધુ દૂર વિસ્તરે. અલ્ગોરિધમ અલ્ગોરિધમનો ઉદ્દેશ પિક્સેલનો ઉપયોગ કરીને વળાંકનો અંદાજ કાઢવાનો છે; સામાન્ય માણસની દ્રષ્ટિએ દરેક પિક્સેલ કેન્દ્રથી લગભગ સમાન અંતર હોવું જોઈએ. દરેક તબક્કે, નજીકના પિક્સેલને પસંદ કરીને પાથ લંબાવવામાં આવે છે જે સંતોષ આપે છે પરંતુ મહત્તમ કરે છે. ઉમેદવાર પિક્સેલ્સ અડીને હોવાથી, પછીની અભિવ્યક્તિની ગણતરી કરવા માટે અંકગણિત સરળ બનાવવામાં આવે છે, જેમાં માત્ર થોડી પાળી અને ઉમેરાઓની જરૂર પડે છે. પરંતુ બિટ્સશિફ્ટને સમજવા માટે સરળીકરણ કરી શકાય છે. ધ્યાનમાં રાખો કે દ્વિસંગી આંકડાની ડાબી બાજુની બિટશિફ્ટ એ 2 સાથે ગુણાકાર કરવા સમાન છે. તેથી, ત્રિજ્યાની ડાબી બાજુની બિટ્સશિફ્ટ માત્ર વ્યાસ ઉત્પન્ન કરે છે જેને ત્રિજ્યા ગુણ્યા બે તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. આ અલ્ગોરિધમ વર્તુળ સમીકરણથી શરૂ થાય છે. સરળતા માટે, ધારો કે વર્તુળનું કેન્દ્ર છે. પહેલા માત્ર પ્રથમ અષ્ટકને ધ્યાનમાં લો, અને એક વળાંક દોરો જે બિંદુથી શરૂ થાય છે અને ઘડિયાળની વિરુદ્ધ દિશામાં આગળ વધે છે, જે 45 ના ખૂણા સુધી પહોંચે છે. અહીં ઝડપી દિશા (મૂલ્યમાં વધુ વધારો સાથેનો આધાર વેક્ટર) એ દિશા છે. અલ્ગોરિધમ હંમેશા હકારાત્મક દિશામાં (ઉપરની તરફ) એક પગલું લે છે, અને ક્યારેક ધીમી દિશામાં (નકારાત્મક દિશા) એક પગલું લે છે. વર્તુળ સમીકરણમાંથી રૂપાંતરિત સમીકરણ મેળવવામાં આવે છે, જ્યાં પ્રારંભિકકરણ દરમિયાન માત્ર એક જ વાર ગણતરી કરવામાં આવે છે. વર્તુળ પરના બિંદુઓને બિંદુ સુધી વેક્ટરના કોઓર્ડિનેટ્સનો ક્રમ (સામાન્ય ધોરણે) થવા દો. પોઇંટ્સને દોરેલા ક્રમ અનુસાર ક્રમાંકિત કરવામાં આવે છે, જેમાં પ્રથમ બિંદુને સોંપવામાં આવે છે. દરેક બિંદુ માટે, નીચેના ધારોઃ આને આ રીતે ફરીથી ગોઠવી શકાય છેઃ અને તે જ રીતે આગામી બિંદુ માટેઃ કારણ કે પ્રથમ અષ્ટક માટે આગામી બિંદુ હંમેશા છેલ્લા કરતા ઓછામાં ઓછું 1 પિક્સેલ વધારે હશે (પરંતુ સાતત્ય જાળવવા માટે વધુમાં વધુ 1 પિક્સેલ વધારે હશે), તે સાચું છે કેઃ તેથી, વર્તુળની સાતત્યતાને કારણે અને બંને અક્ષો સાથે મહત્તમ સમાન હોવાને કારણે, સ્પષ્ટપણે તે ક્રમમાં આગળ વધતાં તે બિંદુઓને છોડશે નહીં કારણ કે તે અનુક્રમમાં આગળ વધે છે. સામાન્ય રીતે તે સમાન સંકલન પર રહે છે, અને કેટલીકવાર એક દ્વારા આગળ વધે છે. પરિણામી સંકલન પછી મધ્યબિંદુ કોઓર્ડિનેટ્સ ઉમેરીને અનુવાદિત થાય છે. આ વારંવારના પૂર્ણાંક ઉમેરાઓ કામગીરીને વધુ મર્યાદિત કરતા નથી, કારણ કે તે ચોરસ (મૂળ) ગણતરીઓ બદલામાં આંતરિક લૂપમાં બચી શકાય છે. ફરીથી, રૂપાંતરિત વર્તુળ સમીકરણમાં શૂન્યને ભૂલ શબ્દ દ્વારા બદલવામાં આવે છે. ભૂલ શબ્દની શરૂઆત શરૂઆતમાં 1⁄2 પિક્સેલના ઓફસેટમાંથી કરવામાં આવે છે. લંબ રેખા સાથેના આંતરછેદ સુધી, આ ભૂલની મુદતમાં સંચિત મૂલ્ય તરફ દોરી જાય છે, જેથી આ મૂલ્યનો ઉપયોગ આરંભીકરણ માટે થાય છે. વર્તુળ સમીકરણ, ત્રિકોણમિતીય સમીકરણો અને વર્ગમૂળોમાં ચોરસની વારંવારની ગણતરીઓને ફરીથી દરેક વસ્તુને એક જ પગલામાં વિસર્જન કરીને અને અગાઉના પુનરાવર્તનોમાંથી દ્વિઘાત શબ્દોની પુનરાવર્તિત ગણતરીનો ઉપયોગ કરીને ટાળી શકાય છે. પૂર્ણાંક-આધારિત અંકગણિત સાથેનો તફાવત જેમ કે બ્રેસેનહામના રેખા અલ્ગોરિધમ સાથે, આ અલ્ગોરિધમને પૂર્ણાંક-આધારિત ગણિત માટે ઑપ્ટિમાઇઝ કરી શકાય છે. સમપ્રમાણતાને કારણે, જો કોઈ અલ્ગોરિધમ મળી શકે છે જે માત્ર એક અષ્ટક માટે પિક્સેલ્સની ગણતરી કરે છે, તો પિક્સેલ્સ આખા વર્તુળને મેળવવા માટે પ્રતિબિંબિત થઈ શકે છે. આપણે ત્રિજ્યાની ભૂલને વર્તુળની ચોક્કસ રજૂઆત અને દરેક પિક્સેલના કેન્દ્ર બિંદુ (અથવા પિક્સેલ પરના કોઈપણ અન્ય મનસ્વી ગાણિતિક બિંદુ, જ્યાં સુધી તે તમામ પિક્સેલ્સમાં સુસંગત હોય) વચ્ચેના તફાવત તરીકે વ્યાખ્યાયિત કરીને શરૂ કરીએ છીએ. કેન્દ્ર સાથેના કોઈપણ પિક્સેલ માટે, ત્રિજ્યા ભૂલને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ સ્પષ્ટતા માટે, વર્તુળ માટેનું આ સૂત્ર મૂળ પર મેળવવામાં આવે છે, પરંતુ અલ્ગોરિધમ કોઈપણ સ્થાન માટે સુધારી શકાય છે. હકારાત્મક એક્સ-અક્ષ પરના બિંદુથી શરૂઆત કરવી ઉપયોગી છે. કારણ કે ત્રિજ્યા પિક્સેલ્સની સંપૂર્ણ સંખ્યા હશે, સ્પષ્ટપણે ત્રિજ્યા ભૂલ શૂન્ય હશેઃ કારણ કે તે પ્રથમ ઘડિયાળની વિરુદ્ધ દિશામાં હકારાત્મક અષ્ટકથી શરૂ થાય છે, તે સૌથી મોટી મુસાફરી, વાય દિશા સાથે દિશામાં પગલું ભરશે, તેથી તે સ્પષ્ટ છે. ઉપરાંત, કારણ કે તે ફક્ત આ અષ્ટક સાથે સંબંધિત છે, મૂલ્યો પાસે માત્ર 2 વિકલ્પો છેઃ અગાઉના પુનરાવર્તનની જેમ જ રહેવું, અથવા 1 નો ઘટાડો કરવો. એક નિર્ણય ચલ બનાવી શકાય છે જે નક્કી કરે છે કે નીચેની બાબતો સાચી છે કે કેમઃ જો આ અસમાનતા જળવાઈ રહે, તો આલેખ બનાવો; જો નહીં, તો આલેખ બનાવો. તો, આ અસમાનતા છે કે નહીં તે કેવી રીતે નક્કી કરવું? ત્રિજ્યા ભૂલની વ્યાખ્યા સાથે પ્રારંભ કરોઃ નિરપેક્ષ મૂલ્ય કાર્ય મદદ કરતું નથી, તેથી બંને બાજુઓને વર્ગ કરો, કારણ કે વર્ગ હંમેશા હકારાત્મક હોય છેઃ> 0 થી, શબ્દ, તેથી વિભાજન મળે છેઃ આમ, નિર્ણય માપદંડ ફ્લોટિંગ-પોઇન્ટ કામગીરીના ઉપયોગથી સરળ પૂર્ણાંક ઉમેરો, બાદબાકી અને બીટ સ્થળાંતર (2 કામગીરી દ્વારા ગુણાકાર માટે) માં બદલાય છે. જો, તો પછી મૂલ્યમાં ઘટાડો કરો. જો, તો પછી તે જ મૂલ્ય રાખો. ફરીથી, આ બિંદુઓને તમામ અષ્ટકોમાં પ્રતિબિંબિત કરવાથી, પૂર્ણ વર્તુળ પરિણમે છે. આપણે અગાઉના પગલામાં તેના મૂલ્યથી આ નિર્ણય સૂત્રના મૂલ્યો વચ્ચેના ડેલ્ટાની ગણતરી કરીને ગણતરી ઘટાડી શકીએ છીએ. આપણે સૂત્રનું પ્રારંભિક મૂલ્ય કોણ છે તે નિર્ધારિત કરીને શરૂ કરીએ છીએ, પછી દરેક તબક્કે ઉપરની જેમ જો આપણે તેને (અને ઘટાડો) તરીકે અપડેટ કરીએ, અન્યથા ત્યાંથી હંમેશની જેમ વધારો થાય છે. જેસ્કોની પદ્ધતિ અલ્ગોરિધમ પહેલેથી જ મોટા પ્રમાણમાં સમજાવવામાં આવ્યું છે, પરંતુ ત્યાં વધુ ઓપ્ટિમાઇઝેશન છે. નવી પ્રસ્તુત પદ્ધતિ પગલું દીઠ માત્ર 5 અંકગણિત કામગીરીઓ (8 પિક્સેલ્સ માટે) સાથે મેળવે છે અને આમ તે માત્ર ઓછી કામગીરી કરતી સિસ્ટમો માટે શ્રેષ્ઠ યોગ્ય છે. "જો" ઓપરેશનમાં, માત્ર નિશાની તપાસવામાં આવે છે (સકારાત્મક? હા અથવા ના) અને એક ચલ સોંપણી છે, જેને અંકગણિત કામગીરી પણ ગણવામાં આવતી નથી. પ્રથમ પંક્તિમાં આરંભીકરણ (4 બિટ્સ દ્વારા જમણી તરફ સ્થળાંતર) માત્ર સુંદરતાને કારણે છે અને ખરેખર જરૂરી નથી. તેથી આપણને મુખ્ય લૂપમાં ગણી શકાય તેવી કામગીરીઓ મળે છેઃ સરખામણી x> = y (સબસ્ટ્રેક્શન તરીકે ગણવામાં આવે છેઃ x-y> = 0) y = y + 1 [y + +] t1 + y t1-x સરખામણી t2> = 0 ગણવામાં આવતી નથી કારણ કે કોઈ વાસ્તવિક અંકગણિત થતું નથી. વાસણોની બે-પૂરક રજૂઆતમાં માત્ર સાઇન બીટ તપાસવું પડે છે. x = x-1 [x--] કામગીરીઓઃ 5 t1 = r/16 x = r y = 0 પુનરાવર્તન કરો જ્યાં સુધી x <y પિક્સેલ (x, y) અને તમામ સપ્રમાણ પિક્સેલ્સ રંગીન (8 વખત) ન હોય ત્યાં સુધી y = y + 1 t1 = t1 + y t2 = t1-x જો t2> = 0 t1 = t2 x = x-1 અપૂર્ણ અષ્ટકો દોરવા ઉપરના અમલીકરણ હંમેશા માત્ર સંપૂર્ણ અષ્ટકો અથવા વર્તુળો ખેંચે છે. ખૂણાથી ખૂણા સુધી માત્ર ચોક્કસ ચાપ દોરવા માટે, અલ્ગોરિધમને પહેલા આ અંતિમ બિંદુઓના અને કોઓર્ડિનેટ્સની ગણતરી કરવાની જરૂર છે, જ્યાં ત્રિકોણમિતિ અથવા વર્ગમૂળની ગણતરીઓનો આશરો લેવો જરૂરી છે (જુઓ વર્ગમૂળની ગણતરીની પદ્ધતિઓ). પછી બ્રેસેનહામ અલ્ગોરિધમ સંપૂર્ણ અષ્ટક અથવા વર્તુળ પર ચલાવવામાં આવે છે અને જો તેઓ ઇચ્છિત અંતરાલમાં આવે તો જ પિક્સેલ્સ સુયોજિત કરે છે. આ ચાપ પૂર્ણ કર્યા પછી, અલ્ગોરિધમનો અકાળે અંત લાવી શકાય છે. જો ખૂણાઓ ઢોળાવ તરીકે આપવામાં આવે છે, તો પછી કોઈ ત્રિકોણમિતિ અથવા વર્ગમૂળની જરૂર નથીઃ ફક્ત તે તપાસો કે તે ઇચ્છિત ઢોળાવો વચ્ચે છે. સામાન્યીકરણ પેરાબોલા, લંબગોળ અથવા અન્ય કોઈપણ દ્વિ-પરિમાણીય વળાંકને રાસ્ટરાઇઝ કરવા માટે સમાન ખ્યાલનો ઉપયોગ કરવો પણ શક્ય છે. સંદર્ભો બાહ્ય કડીઓ રેખાંકન વર્તુળો-રેખાંકન વર્તુળો પરનો એક લેખ, જે કેટલીક પ્રોગ્રામિંગ ભાષાઓમાં એક સરળ યોજનાથી કાર્યક્ષમ એક મધ્યબિંદુ વર્તુળ અલ્ગોરિધમ સુધી ઉતરી આવ્યો છે.