Space partitioning
جیومیٹری میں، خلائی تقسیم ایک پوری جگہ (عام طور پر ایک یوکلڈین جگہ) کو دو یا زیادہ جداگانہ ذیلی سیٹوں میں تقسیم کرنے کا عمل ہے (کسی سیٹ کی تقسیم بھی دیکھیں)۔ دوسرے لفظوں میں، جگہ کی تقسیم کسی جگہ کو غیر اوور لیپنگ علاقوں میں تقسیم کرتی ہے۔ اس کے بعد خلا میں کسی بھی نقطہ کی شناخت بالکل کسی ایک علاقے میں ہونے کے طور پر کی جا سکتی ہے۔ خلا کی تقسیم کے نظام اکثر درجہ بندی کے ہوتے ہیں، جس کا مطلب ہے کہ ایک جگہ (یا خلا کا ایک خطہ) کو کئی خطوں میں تقسیم کیا جاتا ہے، اور پھر اسی جگہ کی تقسیم کا نظام اس طرح بنائے گئے ہر خطے پر بار بار لاگو ہوتا ہے۔ خطوں کو ایک درخت میں منظم کیا جا سکتا ہے، جسے خلائی تقسیم کرنے والا درخت کہا جاتا ہے۔ زیادہ تر خلائی تقسیم کے نظام خلا کو تقسیم کرنے کے لیے طیاروں (یا، اعلی جہتوں میں، ہائپرپلین) کا استعمال کرتے ہیں: ہوائی جہاز کے ایک طرف کے نکات ایک خطہ بناتے ہیں، اور دوسری طرف کے نکات دوسرے کی تشکیل کرتے ہیں۔ بالکل ہوائی جہاز پر پوائنٹس عام طور پر من مانی طور پر ایک یا دوسری طرف تفویض کیے جاتے ہیں۔ اس طرح طیاروں کا استعمال کرتے ہوئے جگہ کو بار بار تقسیم کرنے سے بی ایس پی ٹری پیدا ہوتا ہے، جو جگہ کی تقسیم کی سب سے عام شکلوں میں سے ایک ہے۔ کمپیوٹر گرافکس میں استعمال اسپیس پارٹیشننگ کمپیوٹر گرافکس میں خاص طور پر اہم ہے، خاص طور پر رے ٹریسنگ میں بہت زیادہ استعمال ہوتا ہے، جہاں یہ اکثر ورچوئل سین میں اشیاء کو منظم کرنے کے لیے استعمال ہوتا ہے۔ ایک عام منظر لاکھوں کثیر الاضلاعات پر مشتمل ہو سکتا ہے۔ ہر ایک کے ساتھ رے/پولیگن انٹرسیکشن ٹیسٹ انجام دینا کمپیوٹیشنل طور پر ایک بہت مہنگا کام ہوگا۔ اسپیس پارٹیشننگ ڈیٹا اسٹرکچر (مثال کے طور پر کے-ڈی ٹری یا بی ایس پی ٹری) میں اشیاء کو ذخیرہ کرنے سے مخصوص قسم کے جیومیٹری کے سوالات انجام دینا آسان اور تیز ہوجاتا ہے-مثال کے طور پر اس بات کا تعین کرنے میں کہ آیا کوئی کرن کسی شے کو کاٹتی ہے، اسپیس پارٹیشننگ انٹرسیکشن ٹیسٹ کی تعداد کو صرف چند فی پرائمری رے تک کم کر سکتی ہے، جس سے کثیر الاضحی کی تعداد کے حوالے سے لوگرتھمک ٹائم کی پیچیدگی پیدا ہوتی ہے۔ اسپیس پارٹیشننگ کو اکثر اسکین لائن الگورتھم میں بھی استعمال کیا جاتا ہے تاکہ کیمرے کے دیکھنے والے فریسٹم سے کثیر الاضحی کو ختم کیا جا سکے، جس سے پائپ لائن کے ذریعے پروسیس شدہ کثیر الاضحی کی تعداد محدود ہو جاتی ہے۔ تصادم کا پتہ لگانے میں بھی ایک استعمال ہے: اس بات کا تعین کرنا کہ آیا دو اشیاء ایک دوسرے کے قریب ہیں، اسپیس پارٹیشننگ کا استعمال کرتے ہوئے بہت تیز ہو سکتا ہے۔ انٹیگریٹڈ سرکٹ ڈیزائن میں، ایک اہم مرحلہ ڈیزائن رول چیک ہے۔ یہ مرحلہ اس بات کو یقینی بناتا ہے کہ مکمل شدہ ڈیزائن تیار کرنے کے قابل ہے۔ چیک میں وہ اصول شامل ہوتے ہیں جو چوڑائی اور وقفے اور جیومیٹری کے دیگر نمونوں کی وضاحت کرتے ہیں۔ ایک جدید ڈیزائن میں اربوں کثیر الاضحی ہو سکتے ہیں جو تاروں اور ٹرانجسٹروں کی نمائندگی کرتے ہیں۔ موثر جانچ جیومیٹری کے استفسار پر بہت زیادہ انحصار کرتی ہے۔ مثال کے طور پر، ایک قاعدہ اس بات کی وضاحت کر سکتا ہے کہ کسی بھی کثیر الاضحی کو کسی دوسرے کثیر الاضحی سے کم از کم n نینو میٹر کا ہونا چاہیے۔ یہ تمام اطراف میں ایک کثیر الاضحی کو n/2 سے بڑھا کر جیومیٹری استفسار میں تبدیل کیا جاتا ہے اور تمام انٹرسیکٹنگ کثیر الاضحی کو تلاش کرنے کے لیے استفسار کیا جاتا ہے۔ امکانات اور شماریاتی سیکھنے کے نظریہ میں خلائی تقسیم میں اجزاء کی تعداد امکانات کے نظریہ میں کچھ نتائج میں مرکزی کردار ادا کرتی ہے۔ مزید تفصیلات کے لیے گروتھ فنکشن دیکھیں۔ جغرافیہ اور جی آئی ایس میں بہت سے مطالعات اور ایپلی کیشنز ہیں جہاں جغرافیائی مقامی حقیقت کو ہائیڈرولوجیکل معیار، انتظامی معیار، ریاضیاتی معیار یا بہت سے دیگر کے ذریعہ تقسیم کیا جاتا ہے۔ کارٹوگرافی اور جی آئی ایس-جیوگرافک انفارمیشن سسٹم کے تناظر میں، معیاری کوڈز کے ذریعے پارٹیشن کے خلیوں کی شناخت کرنا عام ہے۔ مثال کے طور پر ہائیڈرو گرافیکل بیسن اور ذیلی بیسن کی شناخت کرنے والے ایچ یو سی کوڈ، ممالک اور اس کے ذیلی ڈویژنوں کی شناخت کرنے والے آئی ایس او 3166-2 کوڈ، یا من مانی ڈی جی جی-کواڈرینٹس یا مقامات کی شناخت کرنے والے مجرد عالمی گرڈ۔ اعداد و شمار کے ڈھانچے عام خلائی تقسیم کے نظام میں شامل ہیں: بی ایس پی کے درخت کواڈٹریس آکٹریز کے-ڈی درخت ڈبے آر-درخت اجزاء کی تعداد فرض کریں کہ این-جہتی یوکلڈین کی جگہ کو ہائپرپلینوں کے ذریعہ تقسیم کیا گیا ہے جو-جہتی ہیں۔ تقسیم میں اجزاء کی تعداد کتنی ہے؟ اجزاء کی سب سے بڑی تعداد اس وقت حاصل ہوتی ہے جب ہائپرپلین عام پوزیشن میں ہوتے ہیں، یعنی کوئی دو متوازی نہیں ہوتے اور نہ ہی تینوں کا چوراہا ایک جیسا ہوتا ہے۔ اجزاء کی اس زیادہ سے زیادہ تعداد کو اس سے ظاہر کریں۔ پھر، درج ذیل تکرار کا تعلق برقرار رہتا ہے:-جب کوئی جہت نہیں ہوتی ہے، تو ایک ہی نقطہ ہوتا ہے۔ - جب کوئی ہائپرپلین نہیں ہوتے ہیں، تو تمام جگہ ایک جزو ہوتی ہے۔ اور اس کا حل یہ ہے: اگر (مثال کے طور پر۔ عمودی ہائپرپلین ؛ ہر اضافی ہائپرپلین ہر موجودہ جزو کو 2 میں تقسیم کرتا ہے)۔ جس کی اوپری حد اس طرح ہے: بائنری اسپیس پارٹیشننگ ڈسکریٹ گلوبل گرڈ پولیگن پارٹیشن ٹیسلیشن حوالہ جات کمپیوٹر گرافکس جیومیٹرک الگورتھم بھی دیکھیں۔