Midpoint circle algorithm
কম্পিউটার গ্রাফিক্সে, মিডপয়েন্ট সার্কেল অ্যালগরিদম হল একটি অ্যালগরিদম যা একটি বৃত্তকে রাস্টারাইজ করার জন্য প্রয়োজনীয় পয়েন্ট নির্ধারণ করতে ব্যবহৃত হয়। এটি ব্রেসেনহ্যামের লাইন অ্যালগরিদমের একটি সাধারণীকরণ। অ্যালগরিদমটি শঙ্কু বিভাগে আরও সাধারণীকরণ করা যেতে পারে। এবং ভ্যান আকেন। মেশিনিং (সিএনসি)-এ, এটি বৃত্তাকার ইন্টারপোলেশন হিসাবে পরিচিত। সারাংশ এই অ্যালগরিদমটি প্রতিটি মূল দিক (0°, 90°, 180°, 270°) থেকে শুরু করে একই সাথে সমস্ত আটটি অষ্টক আঁকে এবং 45° (45°, 135°, 225°, 315°) এর নিকটতম গুণিতক পৌঁছানোর জন্য উভয় দিক প্রসারিত করে। এটি কোথায় থামতে হবে তা নির্ধারণ করতে পারে কারণ কখন =, এটি 45° এ পৌঁছেছে। এই কোণগুলি ব্যবহার করার কারণ উপরের ছবিতে দেখানো হয়েছেঃ যতই বৃদ্ধি পায়, 45° অবধি না পৌঁছানো পর্যন্ত এটি কোনও মান এড়িয়ে যায় না বা পুনরাবৃত্তি করে না। সুতরাং ওয়াইল লুপের সময়, প্রতিটি পুনরাবৃত্তিতে 1 দ্বারা বৃদ্ধি, এবং সময়ে সময়ে 1 দ্বারা হ্রাস, কখনও একটি পুনরাবৃত্তিতে 1 অতিক্রম করে না। এটি 45° এ পরিবর্তিত হয় কারণ এটি সেই বিন্দু যেখানে স্পর্শকটি বৃদ্ধি = রান হয়। যেখানে উত্থান> আগে দৌড়ান এবং উত্থান <পিছনে দৌড়ান। সমস্যার দ্বিতীয় অংশ, নির্ণায়ক, অনেক বেশি জটিল। এটি নির্ধারণ করে কখন হ্রাস করতে হবে। এটি সাধারণত প্রতিটি পুনরাবৃত্তিতে পিক্সেল আঁকার পরে আসে, কারণ এটি কখনই প্রথম পিক্সেলের ব্যাসার্ধের নিচে যায় না। যেহেতু একটি অবিচ্ছিন্ন ফাংশনে, একটি গোলকের জন্য ফাংশন হল একটি বৃত্তের জন্য ফাংশন যার ব্যাসার্ধ নির্ভরশীল (বা তৃতীয় পরিবর্তনশীল যাই হোক না কেন), এটি যুক্তিযুক্ত যে একটি বিচ্ছিন্ন (ভক্সেল) গোলকের জন্য অ্যালগরিদমও এই মিডপয়েন্ট সার্কেল অ্যালগরিদমের উপর নির্ভর করবে। কিন্তু একটি গোলকের দিকে তাকালে, কিছু সংলগ্ন বৃত্তের পূর্ণসংখ্যার ব্যাসার্ধ একই হয়, তবে একই গোলার্ধে তার কাছাকাছি একই সঠিক বৃত্ত থাকবে বলে আশা করা হয় না। পরিবর্তে, একই ব্যাসার্ধের একটি বৃত্তের একটি ভিন্ন নির্ধারক প্রয়োজন, যাতে বক্ররেখাটি কেন্দ্রের সামান্য কাছাকাছি আসতে পারে বা আরও দূরে প্রসারিত হতে পারে। অ্যালগরিদম অ্যালগরিদমের উদ্দেশ্য হল পিক্সেল ব্যবহার করে বক্ররেখার আনুমানিক অনুমান করা; সাধারণ মানুষের ভাষায় প্রতিটি পিক্সেল কেন্দ্র থেকে প্রায় একই দূরত্বের হওয়া উচিত। প্রতিটি ধাপে, সংলগ্ন পিক্সেলটি বেছে নিয়ে পথটি প্রসারিত করা হয় যা সন্তুষ্ট করে কিন্তু সর্বাধিক করে। যেহেতু প্রার্থী পিক্সেলগুলি সংলগ্ন, তাই পরবর্তী অভিব্যক্তিটি গণনা করার জন্য গাণিতিক পদ্ধতিটি সরলীকৃত করা হয়েছে, যার জন্য শুধুমাত্র বিট স্থানান্তর এবং সংযোজন প্রয়োজন। তবে বিটশিফ্ট বোঝার জন্য একটি সরলীকরণ করা যেতে পারে। মনে রাখবেন যে বাইনারি সংখ্যার একটি বাম বিটশিফ্ট 2 দিয়ে গুণ করার সমান। এরগো, ব্যাসার্ধের একটি বাম বিটশিফ্ট শুধুমাত্র ব্যাস তৈরি করে যা ব্যাসার্ধ গুণ দুই হিসাবে সংজ্ঞায়িত করা হয়। এই অ্যালগরিদমটি বৃত্ত সমীকরণ দিয়ে শুরু হয়। সরলতার জন্য, ধরে নিন বৃত্তের কেন্দ্রটি এ। প্রথমে শুধুমাত্র প্রথম অষ্টক বিবেচনা করুন, এবং একটি বক্ররেখা আঁকুন যা বিন্দু থেকে শুরু হয় এবং ঘড়ির কাঁটার বিপরীত দিকে অগ্রসর হয়, 45 কোণে পৌঁছায়। এখানে দ্রুত দিকটি (মূল্যের বৃহত্তর বৃদ্ধি সহ বেসিস ভেক্টর) হল দিক। অ্যালগরিদম সর্বদা ইতিবাচক দিকে (উপরের দিকে) একটি পদক্ষেপ নেয় এবং মাঝে মাঝে ধীর দিকে (নেতিবাচক দিকে) একটি পদক্ষেপ নেয়। বৃত্ত সমীকরণ থেকে রূপান্তরিত সমীকরণ পাওয়া যায়, যেখানে প্রারম্ভিককরণের সময় শুধুমাত্র একবার গণনা করা হয়। বৃত্তের বিন্দুগুলিকে ভেক্টরের বিন্দুর স্থানাঙ্কের একটি ক্রম হতে দিন (স্বাভাবিক ভিত্তিতে)। পয়েন্টগুলি টানা ক্রম অনুসারে গণনা করা হয়, প্রথম বিন্দুতে বরাদ্দ করা হয়। প্রতিটি বিন্দুর জন্য, নিম্নলিখিতটি ধারণ করেঃ এটি এইভাবে পুনর্বিন্যাস করা যেতে পারেঃ এবং একইভাবে পরবর্তী বিন্দুর জন্যঃ যেহেতু প্রথম অষ্টকটির জন্য পরবর্তী বিন্দুটি সর্বদা শেষটির চেয়ে কমপক্ষে 1 পিক্সেল বেশি হবে (তবে ধারাবাহিকতা বজায় রাখার জন্য সর্বাধিক 1 পিক্সেল বেশি), এটি সত্য যেঃ সুতরাং, প্রতিস্থাপনের মাধ্যমে পরবর্তী-বিন্দু-সমীকরণটিকে পুনরাবৃত্তিতে পুনরায় কাজ করুনঃ একটি বৃত্তের ধারাবাহিকতার কারণে এবং উভয় অক্ষ বরাবর সর্বাধিকতা একই হওয়ার কারণে, স্পষ্টতই এটি ক্রমে অগ্রসর হওয়ার সাথে সাথে পয়েন্টগুলি এড়িয়ে যাবে না। সাধারণত এটি একই স্থানাঙ্কে থাকে এবং কখনও কখনও একটির দ্বারা অগ্রসর হয়। ফলস্বরূপ স্থানাঙ্কটি তারপর মধ্যবিন্দু স্থানাঙ্ক যোগ করে অনুবাদ করা হয়। এই ঘন ঘন পূর্ণসংখ্যা সংযোজনগুলি কর্মক্ষমতাকে খুব বেশি সীমাবদ্ধ করে না, কারণ সেই বর্গ (মূল) গণনাগুলি পালাক্রমে অভ্যন্তরীণ লুপে বাদ দেওয়া যেতে পারে। আবার, রূপান্তরিত বৃত্ত সমীকরণের শূন্যটি ত্রুটি পদ দ্বারা প্রতিস্থাপিত হয়। ত্রুটি শব্দের সূচনা শুরুতে 1⁄2 পিক্সেলের অফসেট থেকে উদ্ভূত হয়। লম্ব রেখার সাথে ছেদ না হওয়া পর্যন্ত, এটি ত্রুটি পদের একটি সঞ্চিত মানের দিকে পরিচালিত করে, যাতে এই মানটি সূচনা করার জন্য ব্যবহার করা হয়। বৃত্ত সমীকরণ, ত্রিকোণমিতিক অভিব্যক্তি এবং বর্গমূলের বর্গগুলির ঘন ঘন গণনাগুলি আবার সমস্ত কিছুকে একক ধাপে দ্রবীভূত করে এবং পূর্ববর্তী পুনরাবৃত্তি থেকে দ্বিঘাত পদগুলির পুনরাবৃত্তিমূলক গণনা ব্যবহার করে এড়ানো যেতে পারে। ব্রেসেনহ্যামের লাইন অ্যালগরিদমের মতো, এই অ্যালগরিদমটি পূর্ণসংখ্যা-ভিত্তিক গণিতের জন্য অনুকূলিত করা যেতে পারে। প্রতিসাম্যের কারণে, যদি এমন একটি অ্যালগরিদম পাওয়া যায় যা শুধুমাত্র একটি অষ্টকের জন্য পিক্সেল গণনা করে, তবে পিক্সেলগুলি পুরো বৃত্তটি পেতে প্রতিফলিত হতে পারে। আমরা ব্যাসার্ধের ত্রুটিকে বৃত্তের সঠিক উপস্থাপনা এবং প্রতিটি পিক্সেলের কেন্দ্র বিন্দুর মধ্যে পার্থক্য হিসাবে সংজ্ঞায়িত করে শুরু করি (বা পিক্সেলের অন্য কোনও নির্বিচারে গাণিতিক বিন্দু, যতক্ষণ না এটি সমস্ত পিক্সেল জুড়ে সামঞ্জস্যপূর্ণ হয়)। কেন্দ্রের যে কোনও পিক্সেলের জন্য, ব্যাসার্ধের ত্রুটিটি এইভাবে সংজ্ঞায়িত করা হয়ঃ স্বচ্ছতার জন্য, একটি বৃত্তের জন্য এই সূত্রটি উৎপত্তিস্থলে উদ্ভূত হয়, তবে অ্যালগরিদমটি যে কোনও অবস্থানের জন্য সংশোধন করা যেতে পারে। ধনাত্মক এক্স-অক্ষের বিন্দু দিয়ে শুরু করা দরকারী। যেহেতু ব্যাসার্ধটি পিক্সেলের একটি সম্পূর্ণ সংখ্যা হবে, স্পষ্টতই ব্যাসার্ধের ত্রুটি শূন্য হবেঃ যেহেতু এটি প্রথম ঘড়ির কাঁটার বিপরীতমুখী ধনাত্মক অষ্টকে শুরু হয়, তাই এটি সর্বাধিক ভ্রমণ, ওয়াই দিকের দিকে পদক্ষেপ নেবে, তাই এটি স্পষ্ট যে। এছাড়াও, যেহেতু এটি শুধুমাত্র এই অষ্টক সম্পর্কিত, তাই মানগুলির মাত্র 2টি বিকল্প রয়েছেঃ পূর্ববর্তী পুনরাবৃত্তির মতোই থাকা, অথবা 1 দ্বারা হ্রাস করা। একটি সিদ্ধান্ত পরিবর্তনশীল তৈরি করা যেতে পারে যা নিম্নলিখিতগুলি সত্য কিনা তা নির্ধারণ করেঃ যদি এই বৈষম্য বজায় থাকে, তবে প্লট করুন; যদি না হয়, তবে প্লট করুন। সুতরাং, এই বৈষম্য বজায় আছে কিনা তা কীভাবে নির্ধারণ করা যায়? ব্যাসার্ধ ত্রুটির একটি সংজ্ঞা দিয়ে শুরু করুনঃ পরম মান ফাংশনটি সাহায্য করে না, তাই উভয় পক্ষকে বর্গ করুন, যেহেতু একটি বর্গ সর্বদা ধনাত্মকঃ যেহেতু> 0, শব্দটি, তাই বিভাজন হয়ঃ সুতরাং, সিদ্ধান্তের মানদণ্ডটি ভাসমান-বিন্দু ক্রিয়াকলাপ ব্যবহার থেকে সহজ পূর্ণসংখ্যা সংযোজন, বিয়োগ এবং বিট স্থানান্তর (2 ক্রিয়াকলাপ দ্বারা গুণনের জন্য) এ পরিবর্তিত হয়। যদি, তাহলে মান হ্রাস করুন। যদি, তাহলে একই মান রাখুন। আবার, সমস্ত অষ্টকে এই বিন্দুগুলি প্রতিফলিত করে, একটি পূর্ণ বৃত্তের ফলাফল পাওয়া যায়। আমরা পূর্ববর্তী ধাপে এর মান থেকে এই সিদ্ধান্ত সূত্রের মানগুলির মধ্যে ব-দ্বীপ গণনা করে গণনা হ্রাস করতে পারি। আমরা সূত্রটির প্রাথমিক মান নির্ধারণ করে শুরু করি, তারপর উপরের মতো প্রতিটি ধাপে যদি আমরা এটিকে (এবং হ্রাস) হিসাবে আপডেট করি, অন্যথায় সেখান থেকে যথারীতি বৃদ্ধি। জেস্কোর পদ্ধতি অ্যালগরিদমটি ইতিমধ্যে অনেকাংশে ব্যাখ্যা করা হয়েছে, তবে আরও অপ্টিমাইজেশন রয়েছে। নতুন উপস্থাপিত পদ্ধতিটি প্রতি ধাপে (8 পিক্সেলের জন্য) মাত্র 5টি গাণিতিক ক্রিয়াকলাপের সাথে মিলিত হয় এবং এইভাবে শুধুমাত্র কম-কার্যকরী সিস্টেমের জন্য সবচেয়ে উপযুক্ত। "যদি" অপারেশনে, শুধুমাত্র চিহ্নটি পরীক্ষা করা হয় (পজিটিভ? হ্যাঁ বা না) এবং একটি পরিবর্তনশীল অ্যাসাইনমেন্ট রয়েছে, যা একটি গাণিতিক অপারেশন হিসাবেও বিবেচিত হয় না। প্রথম সারিতে সূচনা (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 অসম্পূর্ণ অষ্টক অঙ্কন উপরের বাস্তবায়নগুলি সর্বদা শুধুমাত্র সম্পূর্ণ অষ্টক বা বৃত্ত আঁকে। একটি কোণ থেকে একটি কোণে শুধুমাত্র একটি নির্দিষ্ট চাপ আঁকার জন্য, অ্যালগরিদমকে প্রথমে এই শেষ বিন্দুগুলির স্থানাঙ্ক এবং স্থানাঙ্ক গণনা করতে হবে, যেখানে ত্রিকোণমিতিক বা বর্গমূল গণনার অবলম্বন করা প্রয়োজন (বর্গমূল গণনার পদ্ধতি দেখুন)। তারপরে ব্রেসেনহ্যাম অ্যালগরিদমটি সম্পূর্ণ অষ্টক বা বৃত্তের উপর চালানো হয় এবং পিক্সেলগুলি কেবল তখনই সেট করে যদি সেগুলি কাঙ্ক্ষিত ব্যবধানের মধ্যে পড়ে। এই চাপটি শেষ করার পরে, অ্যালগরিদমটি অকালে শেষ করা যেতে পারে। যদি কোণগুলি ঢাল হিসাবে দেওয়া হয়, তবে কোনও ত্রিকোণমিতি বা বর্গমূলের প্রয়োজন নেইঃ কেবল পছন্দসই ঢালের মধ্যে রয়েছে কিনা তা পরীক্ষা করুন। সাধারণীকরণ একটি প্যারাবোলা, উপবৃত্তাকার বা অন্য কোনও দ্বি-মাত্রিক বক্ররেখাকে রাস্টারাইজ করার জন্য একই ধারণাটি ব্যবহার করাও সম্ভব। রেফারেন্স বাহ্যিক লিঙ্ক অঙ্কন বৃত্ত-অঙ্কন বৃত্তের উপর একটি নিবন্ধ, যা বিভিন্ন প্রোগ্রামিং ভাষায় একটি সহজ স্কিম থেকে একটি দক্ষ মিডপয়েন্ট সার্কেল অ্যালগরিদম থেকে উদ্ভূত জ্যামিতিক অ্যালগরিদম ডিজিটাল জ্যামিতি ডিঃ রাস্টারং ভন Kreisen#Midpoint-অ্যালগরিদম