सबसे छोटा बाउंडिंग क्वाड्री नोड

Question

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

public static Rectangle BoundingRectangle(Point p, int magnitude) 
{ 
    Rectangle bounds = new Rectangle() 
    { 
     X = (p.X & ~((1 << magnitude) - 1)), 
     Y = (p.Y & ~((1 << magnitude) - 1)), 
     Width = (1 << magnitude), 
     Height = (1 << magnitude) 
    }; 
    return bounds; 
} 

[ध्यान दें कि बिंदु के आसपास बॉक्स (0,0) एक boxof आकार है (1,1) स्थान पर (0,0), स्थान पर (-.5, - 5), क्योंकि यह सभी पूर्णांक-आधारित है]

यह हमेशा (जो मैं बता सकता हूं,) एक बॉक्स लौटाता हूं जो एक नोड के रूप में एक quadtree में फिट। उदाहरण के लिए, new Rectangle(0,0,2,2) स्वीकार्य होगा, जैसा कि new Rectangle(2,2,2,2) होगा, लेकिन new Rectangle(1,1,2,2) नहीं होगा।

मेरी समस्या यह है कि मैं यह समझ नहीं सकता कि एक बिंदु के बजाय आयताकार के लिए इसे कैसे पूरा किया जाए। एकमात्र समाधान जो मैं सोच सकता हूं, बढ़ती परिमाण के बक्से के माध्यम से लूप करना होगा, लेकिन मुझे यकीन है कि कुछ ओ (1) समाधान होना चाहिए जो मैं सोचने में सक्षम नहीं हूं।

---

उदाहरण:

Rectangle(X,Y,1,1) -> Rectangle(X,Y,1,1) 
Rectangle(0,0,2,2) -> Rectangle(0,0,2,2) 
Rectangle(1,1,2,2) -> Rectangle(0,0,4,4) 
Rectangle(1,1,3,3) -> Rectangle(0,0,4,4) 
Rectangle(0,5,2,2) -> Rectangle(0,4,4,4) 
Rectangle(3,3,2,2) -> Rectangle(0,0,8,8) 

---

कार्यान्वयन:

private static int BitScanReverse(int mask) 
{ 
    int index = 0; 
    while (mask > 1) 
    { 
     mask >>= 1; 
     index++; 
    } 
    return index; 
} 

public static Rectangle BoundingRectangle(Point p, int magnitude) 
{ 
    Rectangle bounds = new Rectangle() 
    { 
     X = (p.X & ~((1 << magnitude) - 1)), 
     Y = (p.Y & ~((1 << magnitude) - 1)), 
     Width = (1 << magnitude), 
     Height = (1 << magnitude) 
    }; 
    return bounds; 
} 

public static Rectangle BoundingRectangle(Rectangle r, int magnitude) 
{ 
    int msb = BitScanReverse((r.X^(r.X + r.Width - 1)) | (r.Y^(r.Y + r.Height - 1))); 
    return BoundingRectangle(r.Location, Math.Max(msb + 1, magnitude)); 
} 

Answer 1

के इस पहले की एक आयामी संस्करण पर विचार करें। एक आयताकार के बजाय, हमारे पास ऑफसेट और लंबाई होती है।

आपके बाध्य आयताकार की 'परिमाण' आपको बता रही है कि कितने बिट्स को अनदेखा करना है।

आइए ऑफसेट = 1234 और लंबाई = 56. हम पर्याप्त बिट्स को अनदेखा करना चाहते हैं ताकि 'ऑफ़सेट' (1234) और 'ऑफसेट + लम्बाई -1' (1289) मानचित्र उसी नंबर पर हो।

1234 = 10011010010 
1289 = 10100001001 

स्पष्ट रूप से, हमें यहां पहले 2 बिट्स (9 बिट्स को अनदेखा करें) के अलावा सभी को अनदेखा करने की आवश्यकता है।

हम यह निर्देश है 1234 XOR 1289 (जो 475 है)

1234 = 10011010010 
1289 = 10100001001 
475 = 00111011011 

और फिर 475. अधिकांश प्रोसेसर का सबसे महत्वपूर्ण सेट बिट पाने के साथ प्रोग्राम के रूप में इस पा सकते हैं (Windows पर, यह _BitScanReverse है)।

अब, आपके 2 डी मामले के लिए, हमें एक्स-अक्ष और वाई-अक्ष दोनों के लिए एक्सओआर प्राप्त करने की आवश्यकता है। फिर, हम या उन दो परिणामों को एक साथ। अंत में, सबसे महत्वपूर्ण सेट बिट खोजें।

तो, छद्म कोड में:

magnitude = MSBof((X^(X+width-1)) | (Y^(Y+height-1))) 

वास्तविक आयत के लिए, बस अपनी पोस्ट में समारोह का उपयोग करें। नए प्वाइंट (एक्स, वाई) में पास करें।