🕐 👰🏻 👩🏾‍🤝‍👨🏼 छोटों के लिए स्थानिक हैशिंग 🔪 🌡️ 🤳🏿

स्थानिक हैशिंग एक सरल तकनीक है जो डेटाबेस, भौतिक और ग्राफिक इंजन, कण सिमुलेशन, और आमतौर पर जहां भी आपको कुछ करने की आवश्यकता होती है, वहां उपयोग किया जाता है। संक्षेप में, लब्बोलुआब यह है कि हम अंतरिक्ष को कोशिकाओं में वस्तुओं से तोड़ते हैं और वस्तुओं को उनमें डालते हैं। फिर, मूल्य द्वारा खोज के बजाय, हम जल्दी से हैश द्वारा खोजते हैं।

मान लीजिए कि आपके पास कई ऑब्जेक्ट हैं और आपको यह पता लगाने की आवश्यकता है कि क्या उनके बीच कोई टक्कर है। सबसे सरल उपाय यह है कि प्रत्येक वस्तु से अन्य सभी वस्तुओं की दूरी की गणना की जाए। हालांकि, इस दृष्टिकोण के साथ, आवश्यक गणनाओं की संख्या बहुत तेजी से बढ़ती है। यदि एक दर्जन वस्तुओं को सौ जांचें करनी हैं, तो सौ वस्तुओं में पहले से ही हजारों जांचें हैं। यह एल्गोरिथम का कुख्यात द्विघात जटिलता है।

इसके बाद, छद्म कोड का उपयोग किया जाता है, संदिग्ध रूप से C # के समान है, लेकिन यह सिर्फ एक भ्रम है। यह कोड लेख के अंत में है।

//    foreach (var obj in objects) { if (Distance(this.position, obj.position) < t) { //    } }

यदि आप ग्रिड का उपयोग करके अंतरिक्ष को तोड़ते हैं तो आप स्थिति में सुधार कर सकते हैं। फिर प्रत्येक वस्तु कुछ ग्रिड सेल में गिर जाएगी और पड़ोसी कोशिकाओं को उनकी पूर्णता की जांच करने के लिए खोजना काफी सरल होगा। उदाहरण के लिए, हम यह सुनिश्चित कर सकते हैं कि कम से कम एक सेल द्वारा अलग किए जाने पर दो ऑब्जेक्ट टकराए नहीं।

ग्रिड पहले से ही अच्छा है, लेकिन ग्रिड को अपडेट करने में समस्या है। कोशिकाओं में निर्देशांक का लगातार स्थानांतरण दो आयामों में अच्छी तरह से काम कर सकता है, लेकिन तीन में यह पहले से ही धीमा करना शुरू कर देता है। हम हैशिंग का उपयोग करके बहुआयामी खोज स्थान को एक-आयामी में कम कर सकते हैं। हाशिंग हमें कोशिकाओं को तेज़ी से भरने और उन्हें खोजने की अनुमति देगा। यह कैसे काम करता है?

हाशिंग एक बड़ी मात्रा में डेटा को एक निश्चित में परिवर्तित करने की प्रक्रिया है, स्रोत डेटा में मामूली अंतर के परिणामस्वरूप एक निश्चित एक में एक बड़ा अंतर होता है। यह अनिवार्य रूप से हानिपूर्ण संपीड़न है। हम प्रत्येक सेल को एक पहचानकर्ता प्रदान कर सकते हैं, और जब हम वस्तुओं के निर्देशांक को संकुचित करते हैं, तो चित्रों के साथ एक सादृश्य आरेखित करते हैं, उनके रिज़ॉल्यूशन को कम करते हैं, फिर हम स्वचालित रूप से वांछित सेल के निर्देशांक प्राप्त करते हैं। सभी कोशिकाओं को इस तरह से भरना, हम तब आसानी से किसी भी निर्देशांक के आसपास की वस्तुओं को प्राप्त कर सकते हैं। हम सिर्फ निर्देशांक हैश करते हैं और वस्तुओं के साथ सेल की पहचान करते हैं।

एक निश्चित आकार के दो आयामी ग्रिड के लिए एक हैश फ़ंक्शन कैसा दिख सकता है? उदाहरण के लिए इस प्रकार है:

 hashId = (Math.Floor(position.x / ellSize)) + (Math.Floor(position.y / ellSize)) * width;

हम एक्स-समन्वय को सेल के आकार से विभाजित करते हैं और आंशिक भाग को काटते हैं, फिर वाई के साथ भी ऐसा ही करते हैं और ग्रिड की चौड़ाई से गुणा करते हैं। यह नीचे दिए गए चित्र की तरह एक आयामी सरणी को दर्शाता है।

वास्तव में, हमारे पास पहले की तरह ही ग्रिड है, लेकिन गणना के सरलीकरण के कारण खोज तेज है। सच है, टकराव की उपस्थिति के कारण उनका सरलीकरण किया जाता है, जब एक बहुत दूर की वस्तु का समन्वय हैश एक करीबी के समन्वय वाले हैश के साथ मेल कर सकता है। इसलिए, एक अच्छा वितरण और एक स्वीकार्य टक्कर आवृत्ति के साथ एक हैश फ़ंक्शन चुनना महत्वपूर्ण है। विकिपीडिया पर अधिक पढ़ें मैं आपको बेहतर दिखाता हूं कि व्यवहार में त्रि-आयामी स्थानिक हैश को कैसे लागू किया जाए।

हैश के बारे में थोड़ा जोड़ें
2 * 3.14 या 2 * 3.1415926535897932384626433832795028841971 की गणना करने के लिए क्या तेज है ...? बेशक, पहला। हमें एक कम सटीक परिणाम मिलता है, लेकिन कौन परवाह करता है? इसी तरह, हैश के साथ। हम गणनाओं को सरल करते हैं, सटीकता खो देते हैं, लेकिन उच्च संभावना के साथ हमें अभी भी एक परिणाम मिलता है जो हमें सूट करता है। यह हैश चिप और उनकी ताकत का स्रोत है।

आइए सबसे महत्वपूर्ण बात से शुरू करें - हैश तीन-आयामी निर्देशांक के लिए कार्य करता है। एनवीडिया वेबसाइट पर एक बहुत ही प्रभावशाली लेख में वे निम्नलिखित विकल्प प्रदान करते हैं:

 GLuint hash = ((GLuint)(pos.x / CELLSIZE) << XSHIFT) | ((GLuint)(pos.y / CELLSIZE) << YSHIFT) | ((GLuint)(pos.z / CELLSIZE) << ZSHIFT);

हम प्रत्येक अक्ष पर निर्देशांक लेते हैं, सेल के आकार से विभाजित करते हैं, थोड़ा सा बदलाव करते हैं और उनके बीच परिणाम होते हैं। लेख के लेखक यह निर्दिष्ट नहीं करते हैं कि किस आकार में बदलाव होना चाहिए, इसके अलावा, बिट गणित पूरी तरह से "सबसे छोटे के लिए" नहीं है। इस प्रकाशन में वर्णित एक फ़ंक्शन थोड़ा आसान है। यदि आप इसे कोड में अनुवादित करते हैं, तो आपको कुछ ऐसा मिलता है:

 hash = (Floor(pos.x / cellSize) * 73856093) ^ (Floor(pos.y / cellSize) * 19349663) ^ (Floor(pos.z / cellSize) * 83492791);

प्रत्येक अक्ष पर सेल निर्देशांक ढूंढें, एक बड़ी अभाज्य संख्या और XOR द्वारा गुणा करें। ईमानदारी से, बहुत आसान नहीं है, लेकिन कम से कम अज्ञात बदलाव के बिना।

एक स्थानिक हैश के साथ काम करने के लिए, दो कंटेनरों के लिए सुविधाजनक है: एक कोशिकाओं में वस्तुओं के भंडारण के लिए, दूसरा वस्तुओं की सेल संख्याओं को संग्रहीत करने के लिए। हैशटेबल्स सबसे जल्दी मुख्य कंटेनरों के रूप में काम करते हैं, वे शब्दकोशों हैं, वे हैशमैप भी हैं या जैसा कि उन्हें आपकी पसंदीदा भाषा में भी कहा जाता है। उनमें से एक में, हम हैश कुंजी द्वारा संग्रहीत ऑब्जेक्ट प्राप्त करते हैं, और ऑब्जेक्ट कुंजी द्वारा दूसरे में सेल नंबर। साथ में, ये दो कंटेनर आपको पड़ोसियों को जल्दी से खोजने और कोशिकाओं की पूर्णता की जांच करने की अनुमति देते हैं।

 private Dictionary<int, List<T>> dict; private Dictionary<T, int> objects;

इन कंटेनरों के साथ काम करना कैसा लगता है? हम दो मापदंडों का उपयोग करके वस्तुओं को सम्मिलित करते हैं: निर्देशांक और स्वयं वस्तु।

 public void Insert(Vector3 vector, T obj) { var key = Key(vector); if (dict.ContainsKey(key)) { dict[key].Add(obj); } else { dict[key] = new List<T> { obj }; } objects[obj] = key; }

निर्देशांक को हैश करें, शब्दकोश में कुंजी की जांच करें, वस्तु के साथ वस्तु और कुंजी के साथ वस्तु को रटना। जब हमें निर्देशांक को अद्यतन करने की आवश्यकता होती है, तो हम ऑब्जेक्ट को पुराने सेल से हटाते हैं और इसे नए में डालते हैं।

 public void UpdatePosition(Vector3 vector, T obj) { if (objects.ContainsKey(obj)) { dict[objects[obj]].Remove(obj); } Insert(vector, obj); }

यदि एक बार में कई ऑब्जेक्ट अपडेट किए जाते हैं, तो सभी शब्दकोशों को साफ़ करना और उन्हें हर बार फिर से भरना आसान होता है।

 public void Clear() { var keys = dict.Keys.ToArray(); for (var i = 0; i < keys.Length; i++) dict[keys[i]].Clear(); objects.Clear(); }

यही है, नीचे पूर्ण वर्ग कोड प्रस्तुत किया गया है। यह यूनिटी इंजन से वेक्टर 3 का उपयोग करता है, लेकिन कोड को आसानी से एक्सएनए या किसी अन्य ढांचे के लिए अनुकूलित किया जा सकता है। हैश का कार्य एक निश्चित "क्विक राउंडिंग" का उपयोग करता है, मैं इसके काम के लिए प्रतिज्ञा नहीं कर सकता।

SpatialHash.cs

 using System.Linq; using UnityEngine; using System.Collections.Generic; public class SpatialHash<T> { private Dictionary<int, List<T>> dict; private Dictionary<T, int> objects; private int cellSize; public SpatialHash(int cellSize) { this.cellSize = cellSize; dict = new Dictionary<int, List<T>>(); objects = new Dictionary<T, int>(); } public void Insert(Vector3 vector, T obj) { var key = Key(vector); if (dict.ContainsKey(key)) { dict[key].Add(obj); } else { dict[key] = new List<T> { obj }; } objects[obj] = key; } public void UpdatePosition(Vector3 vector, T obj) { if (objects.ContainsKey(obj)) { dict[objects[obj]].Remove(obj); } Insert(vector, obj); } public List<T> QueryPosition(Vector3 vector) { var key = Key(vector); return dict.ContainsKey(key) ? dict[key] : new List<T>(); } public bool ContainsKey(Vector3 vector) { return dict.ContainsKey(Key(vector)); } public void Clear() { var keys = dict.Keys.ToArray(); for (var i = 0; i < keys.Length; i++) dict[keys[i]].Clear(); objects.Clear(); } public void Reset() { dict.Clear(); objects.Clear(); } private const int BIG_ENOUGH_INT = 16 * 1024; private const double BIG_ENOUGH_FLOOR = BIG_ENOUGH_INT + 0.0000; private static int FastFloor(float f) { return (int)(f + BIG_ENOUGH_FLOOR) - BIG_ENOUGH_INT; } private int Key(Vector3 v) { return ((FastFloor(vx / cellSize) * 73856093) ^ (FastFloor(vy / cellSize) * 19349663) ^ (FastFloor(vz / cellSize) * 83492791)); } }

इंटरैक्टिव डेमो में, इस लिंक का पालन करके देखें कि हैश स्पेस कैसे वितरित किया जाता है। पीली गेंद के निर्देशांक को एक टाइमर द्वारा हैशेड किया जाता है, जिसके बाद यह गोले के अंदर एक यादृच्छिक बिंदु पर चला जाता है। पीले क्यूब्स निर्देशांक का संकेत देते हैं जो एक ही सेल में आते हैं। नीली कुंजियाँ पहले से ही बनाई गई कुंजियों को इंगित करती हैं ताकि आप मेमोरी भरने की प्रक्रिया को देख सकें। माउस को घुमाया जा सकता है।

गिटहब पर सूत्र | एकता वेब प्लेयर के मालिकों के लिए ऑनलाइन संस्करण

दिलचस्प संबंधित लिंक

http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf
http://www.beosil.com/download/CollisionDetectionHashing_VMV03.pdf
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html

छोटों के लिए स्थानिक हैशिंग

दिलचस्प संबंधित लिंक

More articles: