इंटरनेट के हिल्बर्ट मानचित्र को कार्यान्वित करना

Question

XKCD comic 195 में इंटरनेट पता स्थान के मानचित्र के लिए एक डिज़ाइन Hilbert curve का उपयोग करके सुझाया गया है ताकि एक ही आईपी एड्रेस से आइटम एक साथ क्लस्टर हो जाए।

आईपी पता देखते हुए, मैं इस मानचित्र पर अपने 2 डी निर्देशांक (शून्य से एक तक) की गणना कैसे करूं?

Answer 1

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

प्रत्येक वर्ग में वक्र के बुनियादी आकार घोड़े की नाल की तरह है:

 
0 3 
1 2 

जहां संख्या शीर्ष दो बिट्स के अनुरूप है और इसलिए ट्रेवर्सल क्रम निर्धारित। Xkcd मानचित्र में, यह वर्ग उच्चतम स्तर पर ट्रैवर्सल ऑर्डर है। संभवतः घूर्णन और/या परिलक्षित, यह आकार प्रत्येक 2x2 वर्ग में मौजूद है।

प्रत्येक सबक्वेयर में "घोड़े की नाल" को उन्मुख करने का निर्धारण एक नियम द्वारा निर्धारित किया जाता है: 00 वर्ग के कोने बड़े वर्ग के कोने में है।इस प्रकार, subsquare ऊपर 0 करने के लिए इसी क्रम

 
0 1 
3 2 

में चल जाना चाहिए और पूरे पिछले वर्ग देख रही है और दिखा चार बिट पर हम पाते हैं वर्ग के अगले विभाजन के लिए निम्नलिखित आकार:

 
00 01 32 33 
03 02 31 30 
10 13 20 23 
11 12 21 22 

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

वास्तविक निर्देशांक निर्धारित करने के लिए, प्रत्येक दो बिट वास्तविक संख्या निर्देशांक में बाइनरी परिशुद्धता का एक बिट निर्धारित करते हैं। तो, पहले स्तर पर, द्विआधारी बिंदु के बाद पहली बिट x में समन्वय (यह मानते हुए [0,1] रेंज में निर्देशांक) 0 है अगर पता के पहले दो बिट्स 0 या 1, और 1 अन्यथा मान है। इसी तरह, y समन्वय में पहला बिट 0 है यदि पहले दो बिट्स के पास 1 या 2 है। यह निर्धारित करने के लिए कि 0 या 1 बिट को निर्देशांक में जोड़ने के लिए, आपको उस स्तर पर घोड़े की नाल के अभिविन्यास की जांच करनी होगी।

संपादित करें: मैंने एल्गोरिदम को काम करना शुरू कर दिया और यह पता चला कि यह सब के बाद मुश्किल नहीं है, इसलिए यहां कुछ छद्म-सी है। यह छद्म है क्योंकि मैं b बाइनरी स्थिरांक के लिए प्रत्यय का उपयोग करता हूं और बिट्स के सरणी के रूप में पूर्णांक का इलाज करता हूं, लेकिन इसे उचित सी में बदलना बहुत मुश्किल नहीं होना चाहिए।

कोड में, pos अभिविन्यास के लिए 3-बिट पूर्णांक है। पहले दो बिट्स वर्ग में 0 के x और y निर्देशांक हैं और तीसरा बिट इंगित करता है कि 1 में 0 के समान x समन्वय है या नहीं। pos का प्रारंभिक मान 011b है, जिसका अर्थ है कि 0 के निर्देशांक (0, 1) और 1 के समान x समन्वय 0 है। ad पता है, जिसे n-2-बिट पूर्णांक के एलेमेंट सरणी के रूप में माना जाता है, और सबसे महत्वपूर्ण बिट्स से शुरू होता है।

double x = 0.0, y = 0.0; 
double xinc, yinc; 
pos = 011b; 
for (int i = 0; i < n; i++) { 
    switch (ad[i]) { 
     case 0: xinc = pos[0]; yinc = pos[1]; pos[2] = ~pos[2]; break; 
     case 1: xinc = pos[0]^~pos[2]; yinc = pos[1]^pos[2]; break; 
     case 2: xinc = ~pos[0]; yinc = ~pos[1]; break; 
     case 3: xinc = pos[0]^pos[2]; yinc = pos[1]^~pos[2]; 
      pos = ~pos; break; 
    } 
    x += xinc/(1 << (i+1)); y += yinc/(1 << (i+1)); 
} 

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

Answer 2

अनिवार्य रूप से आप बिट्स के जोड़े, एमएसबी से एलएसबी का उपयोग करके संख्या को विघटित करेंगे। बिट्स की जोड़ी आपको बताती है कि यदि स्थान ऊपरी बाएं (0) लोअर बाएं (1) लोअर राइट (2) या ऊपरी दाएं (3) चतुर्भुज में है, तो उस पैमाने पर जो आप संख्या के माध्यम से स्थानांतरित हो जाते हैं।

इसके अतिरिक्त, आपको "अभिविन्यास" को ट्रैक करने की आवश्यकता है। यह घुमावदार है जिसका उपयोग उस पैमाने पर किया जाता है जिस पर आप हैं; प्रारंभिक घुमाव उपरोक्त (यूएल, एलएल, एलआर, यूआर) जैसा है, और आप जिस क्वाड्रंट को समाप्त करते हैं उसके आधार पर, अगले पैमाने पर घुमावदार (घुमावदार -90, 0, 0, + 9 0) आपके वर्तमान घुमाव से है ।

तो तुम जमा कर सकता है ऑफसेट:

मैं 0,0 पर शुरू लगता है, और पहली जोड़ी मुझे एक 2 देता है, मैं 0.5 करने के लिए ऑफसेट बदलाव, 0.5। निचले दाएं भाग में घुमाव मेरे शुरुआती एक जैसा ही है। अगली जोड़ी पैमाने को कम कर देती है, इसलिए मेरे समायोजन लंबाई में 0.25 होने जा रहे हैं।

यह जोड़ी एक 3 है, इसलिए मैं केवल अपने एक्स समन्वय का अनुवाद करता हूं और मैं .75, .5 पर हूं। घुमाव अब घूमता है और मेरा अगला स्तर नीचे होगा (एलआर, एलएल, उल, यूआर)। स्केल अब है .125, और इतने पर और जब तक मैं अपने पते में बिट्स से बाहर नहीं चला जाता।

Answer 3

मुझे उम्मीद है कि wikipedia code for a Hilbert curve पर आधारित आप अपनी वर्तमान स्थिति (एक (एक्स, वाई) समन्वय के रूप में) ट्रैक कर सकते हैं और एन कोशिकाओं का दौरा करने के बाद उस स्थिति को वापस कर सकते हैं। फिर [0..1] पर स्केल की गई स्थिति इस बात पर निर्भर करेगी कि हिल्बर्ट वक्र कितना उच्च और व्यापक हो रहा है।

from turtle import left, right, forward 

size = 10 

def hilbert(level, angle): 
    if level: 
     right(angle) 
     hilbert(level - 1, -angle) 
     forward(size) 
     left(angle) 
     hilbert(level - 1, angle) 
     forward(size) 
     hilbert(level - 1, angle) 
     left(angle) 
     forward(size) 
     hilbert(level - 1, -angle) 
     right(angle) 

मान्य रूप से, यह एक बंद फॉर्म समाधान के बजाय एक क्रूर बल समाधान होगा।