Nút tứ giác nhỏ nhất

Question

Tôi đang viết một cấu trúc quadtree dựa trên số nguyên được xây dựng từ nút và không xuống. Để làm điều này, tôi cần khám phá nút lớn nhất tiếp theo chứa tất cả các phần tử của tôi. Nếu tôi có một nút đã xác định trước, sau đó thử thêm một mục bên ngoài các giới hạn của nút đó, nó cần tạo một nút lớn hơn để bao gồm cả hai nút đó. Tôi có (những gì tôi nghĩ là thông minh) mã cho việc tìm kiếm hộp bounding xung quanh một điểm duy nhất:

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; 
} 

[Lưu ý rằng hộp xung quanh điểm (0,0) là một kích thước boxof (1,1) tại vị trí (0,0), không phải tại vị trí (-.5, -. 5), vì tất cả đều dựa trên số nguyên]

Điều này luôn luôn (từ những gì tôi có thể nói) trả về một hộp phù hợp với một quadtree như một nút. Ví dụ: new Rectangle(0,0,2,2) sẽ được chấp nhận, như là new Rectangle(2,2,2,2), nhưng new Rectangle(1,1,2,2) sẽ không được chấp nhận.

Vấn đề của tôi là tôi không thể tìm ra cách để thực hiện điều này cho một hình chữ nhật, thay vì một điểm. Giải pháp duy nhất tôi có thể nghĩ đến là lặp qua các hộp tăng cường độ lớn, nhưng tôi chắc rằng có một số giải pháp O (1) mà tôi không thể nghĩ ra.

---

Ví dụ:

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) 

---

Thực hiện:

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

Hãy xem xét các phiên bản một chiều của đầu tiên này. Thay vì một hình chữ nhật, chúng tôi có một bù đắp và chiều dài.

'Độ lớn' của hình chữ nhật giới hạn cho bạn biết số lượng bit cần bỏ qua.

Giả sử offset = 1234 và length = 56. Chúng tôi muốn bỏ qua các bit đủ để bản đồ 'offset' (1234) và 'offset + length-1' (1289) đến cùng một số.

1234 = 10011010010 
1289 = 10100001001 

Rõ ràng, chúng ta cần bỏ qua tất cả trừ 2 bit đầu tiên ở đây (bỏ qua 9 bit).

Chúng ta có thể tìm thấy điều này lập trình với 1234 XOR 1289 (đó là 475)

1234 = 10011010010 
1289 = 10100001001 
475 = 00111011011 

và sau đó tìm kiếm các bit bộ quan trọng nhất của 475. Hầu hết các bộ vi xử lý có hướng dẫn này (trên Windows, nó _BitScanReverse).

Bây giờ, đối với trường hợp 2D của bạn, chúng tôi cần lấy XOR cho cả trục X và trục Y. Sau đó, chúng tôi HOẶC hai kết quả đó lại với nhau. Cuối cùng, tìm bit thiết lập quan trọng nhất.

Vì vậy, trong pseudo-code:

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

Để có được hình chữ nhật thực tế, chỉ cần sử dụng các chức năng trong bài viết của bạn. Vượt qua điểm mới (X, Y).