जेड-ऑर्डर-वक्र समन्वय

Question

मैं जेड-ऑर्डर का उपयोग करके डेटा को कैसे एक्सेस कर सकता हूं जिसमें सरणी में ओ (1) समय जटिलता है? मुझे अपने निर्देशांक द्वारा प्रत्येक तत्व को तेज़ पहुंच की आवश्यकता है। बिट्स को स्थानांतरित करने के दौरान उपयोग करने से मुझे इस डेटा तक पहुंचने का कोई तेज़ तरीका है?

एक तरह से देखने तालिकाओं का उपयोग किया जाएगा (मैं डेटा के स्थिर आकार)

संपादित करें:

एक विचार मैं अभी था y * आकार + x

का उपयोग कर अनुक्रम में पत्ते स्टोर करने के लिए है

संपादित 2 .:

मैं एसटीडी में ट्रैक्टर पेड़ में बिट्स storying हूँ :: bitset। अगर कुछ डेटा उपलब्ध है तो मैं चेक करने की कोशिश कर रहा हूं। आकार 128 * 128 के matrices में। तो मैं खाली डेटा के लिए ब्रूटफोर्स मैट्रिक्स खोज छोड़ सकता हूं।

Answer 1

आप नीचे दिए गए कोड के साथ z आदेश वक्र मूल्य की गणना कर सकते हैं:

uint32_t calcZOrder(uint16_t xPos, uint16_t yPos) 
{ 
    static const uint32_t MASKS[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF}; 
    static const uint32_t SHIFTS[] = {1, 2, 4, 8}; 

    uint32_t x = xPos; // Interleave lower 16 bits of x and y, so the bits of x 
    uint32_t y = yPos; // are in the even positions and bits from y in the odd; 

    x = (x | (x << SHIFTS[3])) & MASKS[3]; 
    x = (x | (x << SHIFTS[2])) & MASKS[2]; 
    x = (x | (x << SHIFTS[1])) & MASKS[1]; 
    x = (x | (x << SHIFTS[0])) & MASKS[0]; 

    y = (y | (y << SHIFTS[3])) & MASKS[3]; 
    y = (y | (y << SHIFTS[2])) & MASKS[2]; 
    y = (y | (y << SHIFTS[1])) & MASKS[1]; 
    y = (y | (y << SHIFTS[0])) & MASKS[0]; 

    const uint32_t result = x | (y << 1); 
    return result; 
} 

यह से आप 128x128 सरणी यहाँ Bit Twiddling Hacks

से लिया गया है (या किसी अन्य आकार) आप आसानी से जेड की गणना कर सकते किसी भी स्थिति से आदेश वक्र मूल्य। उदाहरण के लिए:

xPos = 2, yPos = 3 -> z order curve value = 7 

उदाहरण कोड के लिए अधिकतम सरणी आकार 65536 * 65536 है। बस आसानी से 2 की शक्ति का उपयोग करें, उस स्थिति में अधिकतम बर्बाद जगह लगभग है। 3/4