Space partitioning
জ্যামিতিতে, স্থান বিভাজন হল একটি সম্পূর্ণ স্থানকে (সাধারণত একটি ইউক্লিডীয় স্থান) দুই বা ততোধিক বিচ্ছিন্ন উপসেটে বিভক্ত করার প্রক্রিয়া (একটি সেটের বিভাজনও দেখুন)। অন্য কথায়, স্থান বিভাজন একটি স্থানকে নন-ওভারল্যাপিং অঞ্চলে বিভক্ত করে। স্থানের যে কোনও বিন্দু তখন ঠিক একটি অঞ্চলে অবস্থিত বলে চিহ্নিত করা যেতে পারে। স্থান-বিভাজন ব্যবস্থা প্রায়শই শ্রেণিবদ্ধ হয়, যার অর্থ একটি স্থান (বা স্থানের একটি অঞ্চল) বিভিন্ন অঞ্চলে বিভক্ত হয় এবং তারপরে একই স্থান-বিভাজন ব্যবস্থা এইভাবে তৈরি প্রতিটি অঞ্চলে পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা হয়। অঞ্চলগুলিকে একটি গাছে সাজানো যেতে পারে, যাকে স্থান-বিভাজনকারী গাছ বলা হয়। বেশিরভাগ স্থান-বিভাজন ব্যবস্থা স্থান ভাগ করার জন্য সমতল (বা, উচ্চতর মাত্রায়, হাইপারপ্লেন) ব্যবহার করেঃ সমতলের এক পাশের বিন্দুগুলি একটি অঞ্চল গঠন করে এবং অন্যদিকে বিন্দুগুলি অন্যটি গঠন করে। সমতলের ঠিক পয়েন্টগুলি সাধারণত নির্বিচারে এক বা অন্য দিকে বরাদ্দ করা হয়। এইভাবে প্লেন ব্যবহার করে পুনরাবৃত্তিমূলকভাবে স্থান বিভাজন একটি বিএসপি ট্রি তৈরি করে, যা স্থান বিভাজনের সবচেয়ে সাধারণ রূপগুলির মধ্যে একটি। ব্যবহার কম্পিউটার গ্রাফিক্সে স্পেস পার্টিশনিং কম্পিউটার গ্রাফিক্সে বিশেষভাবে গুরুত্বপূর্ণ, বিশেষত রে ট্রেসিংয়ে ব্যাপকভাবে ব্যবহৃত হয়, যেখানে এটি প্রায়শই একটি ভার্চুয়াল দৃশ্যে বস্তুগুলিকে সংগঠিত করতে ব্যবহৃত হয়। একটি সাধারণ দৃশ্যে লক্ষ লক্ষ বহুভুজ থাকতে পারে। প্রত্যেকটির সাথে একটি রশ্মি/বহুভুজ ছেদ পরীক্ষা করা গণনামূলকভাবে একটি অত্যন্ত ব্যয়বহুল কাজ হবে। একটি স্থান-বিভাজনকারী তথ্য কাঠামোতে বস্তু সংরক্ষণ করা (উদাহরণস্বরূপ কে-ডি ট্রি বা বিএসপি ট্রি) নির্দিষ্ট ধরনের জ্যামিতি প্রশ্নগুলি সম্পাদন করা সহজ এবং দ্রুত করে তোলে-উদাহরণস্বরূপ একটি রশ্মি কোনও বস্তুকে ছেদ করে কিনা তা নির্ধারণ করার ক্ষেত্রে, স্থান বিভাজন প্রতি প্রাথমিক রশ্মি প্রতি ছেদ পরীক্ষার সংখ্যাকে মাত্র কয়েকটিতে হ্রাস করতে পারে, যা বহুভুজের সংখ্যার সাপেক্ষে একটি লগারিদমিক সময় জটিলতা প্রদান করে। স্পেস পার্টিশনিং প্রায়শই স্ক্যানলাইন অ্যালগরিদমগুলিতে ক্যামেরার দেখার ফ্রাস্টাম থেকে বহুভুজগুলি নির্মূল করতে ব্যবহৃত হয়, পাইপলাইন দ্বারা প্রক্রিয়াজাত বহুভুজের সংখ্যা সীমিত করে। সংঘর্ষ সনাক্তকরণেও একটি ব্যবহার রয়েছেঃ স্থান বিভাজন ব্যবহার করে দুটি বস্তু একে অপরের কাছাকাছি কিনা তা নির্ধারণ করা অনেক দ্রুত হতে পারে। ইন্টিগ্রেটেড সার্কিট ডিজাইনে, একটি গুরুত্বপূর্ণ পদক্ষেপ হল ডিজাইনের নিয়ম পরীক্ষা করা। এই পদক্ষেপটি নিশ্চিত করে যে সম্পূর্ণ নকশাটি উৎপাদনযোগ্য। চেকটিতে এমন নিয়ম রয়েছে যা প্রস্থ এবং ব্যবধান এবং অন্যান্য জ্যামিতি নিদর্শন নির্দিষ্ট করে। একটি আধুনিক নকশায় কোটি কোটি বহুভুজ থাকতে পারে যা তার এবং ট্রানজিস্টরের প্রতিনিধিত্ব করে। দক্ষ পরীক্ষা জ্যামিতি প্রশ্নের উপর ব্যাপকভাবে নির্ভর করে। উদাহরণস্বরূপ, একটি নিয়ম নির্দিষ্ট করতে পারে যে কোনও বহুভুজ অবশ্যই অন্য কোনও বহুভুজ থেকে কমপক্ষে এন ন্যানোমিটার হতে হবে। এটি একটি জ্যামিতি অনুসন্ধানে রূপান্তরিত হয় একটি বহুভুজকে সমস্ত দিকে n/2 দ্বারা প্রসারিত করে এবং সমস্ত ছেদকারী বহুভুজ খুঁজে বের করার জন্য অনুসন্ধান করে। সম্ভাব্যতা এবং পরিসংখ্যানগত শিক্ষণ তত্ত্বে একটি স্থান বিভাজনের উপাদানের সংখ্যা সম্ভাব্যতা তত্ত্বের কিছু ফলাফলে কেন্দ্রীয় ভূমিকা পালন করে। আরও বিস্তারিত জানতে গ্রোথ ফাংশন দেখুন। ভূগোল এবং জিআইএস-এ এমন অনেক গবেষণা এবং প্রয়োগ রয়েছে যেখানে ভৌগলিক স্থানিক বাস্তবতা জলবিদ্যুৎ মানদণ্ড, প্রশাসনিক মানদণ্ড, গাণিতিক মানদণ্ড বা আরও অনেক কিছু দ্বারা বিভক্ত করা হয়। কার্টোগ্রাফি এবং জিআইএস-এর প্রসঙ্গে-ভৌগোলিক তথ্য ব্যবস্থা, স্ট্যান্ডার্ড কোড দ্বারা বিভাজনের কোষগুলি সনাক্ত করা সাধারণ। উদাহরণস্বরূপ, এইচইউসি কোড হাইড্রোগ্রাফিক্যাল অববাহিকা এবং উপ-অববাহিকা চিহ্নিত করার জন্য, আইএসও 3166-2 কোড দেশ এবং এর উপবিভাগগুলি চিহ্নিত করার জন্য, বা নির্বিচারে ডিজিজি-চতুর্ভুজ বা অবস্থানগুলি চিহ্নিত করার জন্য পৃথক বৈশ্বিক গ্রিড। তথ্য কাঠামো সাধারণ স্থান-বিভাজন ব্যবস্থার মধ্যে রয়েছেঃ বি. এস. পি গাছ চতুর্ভুজ কে-ডি গাছ বিন আর-গাছ উপাদানের সংখ্যা মনে করুন এন-মাত্রিক ইউক্লিডীয় স্থানটি-মাত্রিক হাইপারপ্লেন দ্বারা বিভক্ত। পার্টিশনে উপাদানের সংখ্যা কত? যখন হাইপারপ্লেনগুলি সাধারণ অবস্থানে থাকে তখন সর্বাধিক সংখ্যক উপাদান অর্জন করা হয়, অর্থাৎ, কোনও দুটি সমান্তরাল নয় এবং কোনও তিনটির একই ছেদ নেই। এই সর্বাধিক সংখ্যক উপাদানকে দ্বারা চিহ্নিত করুন। তারপর, নিম্নলিখিত পুনরাবৃত্তি সম্পর্কটি ধারণ করেঃ-যখন কোনও মাত্রা থাকে না, তখন একটি একক বিন্দু থাকে। - যখন কোনও হাইপারপ্লেন থাকে না, তখন সমস্ত স্থান একটি একক উপাদান। এবং এর সমাধান হলঃ যদি (উদাহরণস্বরূপ বিবেচনা করুন। লম্ব হাইপারপ্লেন; প্রতিটি অতিরিক্ত হাইপারপ্লেন প্রতিটি বিদ্যমান উপাদানকে 2 দিয়ে ভাগ করে। যা এইভাবে উচ্চ-সীমাবদ্ধঃ আরও দেখুন বাইনারি স্পেস পার্টিশনিং ডিসক্রিট গ্লোবাল গ্রিড পলিগন পার্টিশন টেসেলেশন রেফারেন্স কম্পিউটার গ্রাফিক্স জ্যামিতিক অ্যালগরিদম