Làm thế nào tôi có thể tìm thấy tất cả các hình chữ nhật ràng buộc các vùng trong một bitmap?

Question

Tôi gặp vấn đề: Tôi cần một thuật toán cho công cụ lát gạch của mình.

Tôi có một mảng 2d lưu trữ các ô không thể truy cập của mình.

Bây giờ tôi muốn thực hiện một động cơ nhẹ, nhưng động cơ này cần vỏ bóng.

Vì vậy, tôi cần một thuật toán sẽ tạo ra các lớp vỏ bóng này.

Tôi cần một tập hợp các hình chữ nhật đó ràng buộc các phần un-lối đi của mảng (các tế bào có 1 s)
Ví dụ:

Các ngói đen là 1 s; Tôi cần phải tìm tập hợp các hình chữ nhật màu đỏ hoàn toàn bao bọc chúng.

Answer 1

Sau khi suy nghĩ thêm, tôi đã tìm ra một giải pháp nhanh hơn:

1. Tạo một bất biến Range struct với StartX, StartY, và EndY tài sản.

2. Duy trì một mảng thưa thớt hiện tại Range s, với chiều dài bằng chiều cao của hình ảnh và một biến currentRange có thể vô hiệu hóa duy nhất.mảng này sẽ chứa phạm vi, nếu có, mà bắt đầu từ mỗi Y phối hợp

3. Đối với mỗi cột,

   1. Rõ ràng currentRange

   2. Đối với mỗi ô trong cột:

      1. Nếu không có currentRange, hoặc nếu có nhưng nó đã kết thúc trước ô này (nếu currentRange.EndY <= y), hãy đặt currentRange thành thành phần thứ y trong mảng phạm vi.
         Do đó, currentRange sẽ luôn tham chiếu đến phạm vi chứa ô hiện tại hoặc null nếu ô hiện tại không nằm trong dải ô.

      2. Nếu ô hiện tại là 1:

         1. Nếu chúng ta đang ở trong một phạm vi, không làm gì cả – phạm vi đang tiếp tục vào cột tiếp theo.

         2. Nếu chúng tôi không ở trong một phạm vi, hãy vòng xuống cột cho đến khi chúng tôi đạt được số 0 hoặc cuối cột, sau đó tạo một phạm vi mới kéo dài từ 1 mà chúng tôi vừa tìm thấy cho đến cuối vòng lặp.
            Sau đó, chuyển sang bước tiếp theo nếu (vì ô hiện tại là 0 hoặc cuối cột và chúng tôi không nằm trong phạm vi)
            Nếu bạn nhấn vào phạm vi hiện tại khi bạn lặp lại để tạo phạm vi mới , bạn có thể dừng phạm vi mới và để phạm vi hiện tại tiếp tục bên dưới phạm vi hiện tại (tốt nhất cho các cạnh mờ) hoặc đóng phạm vi hiện tại (xem bên dưới) và để phạm vi mới kéo dài xuống để tiếp nhận từ phạm vi hiện tại.

      3. Nếu ô hiện tại là 0:
         1. Nếu chúng ta đang ở trong một phạm vi, đóng khoảng:
            1. Return một hình chữ nhật mới kéo dài từ đầu X của phạm vi và Y với Y hiện tại và kết thúc của phạm vi X.
            2. Xóa phạm vi khỏi dãy phạm vi hoạt động.

thuật toán này là O(x * y) trong tính toán và O(y) trong không gian. Tôi tin rằng đây là giải pháp nhanh nhất cho vấn đề này.

Bạn cũng có thể xoay thuật toán này và quét hàng thay vì cột (để các dải đó sẽ được kéo dài xuống dưới chứ không phải là phải), sẽ là O(x) trong bộ nhớ.

Đây là một C# thực hiện:

class BoxFinder { 
    class Range { 
     public Range(int startX, int startY, int endY) { 
      StartX = startX; 
      StartY = startY; 
      EndY = endY; 
     } 

     public int StartX { get; private set; } 
     public int StartY { get; private set; } 
     public int EndY { get; private set; } 
    } 
    public BoxFinder(int[,] data) { 
     Data = data; 
     Width = data.GetLength(0); 
     Height = data.GetLength(1); 
     ranges = new Range[Height]; 
    } 

    public int[,] Data { get; private set; } 
    public int Width { get; private set; } 
    public int Height { get; private set; } 

    private Range[] ranges; 
    public IEnumerable<Rectangle> GetBoxes() { 
     for (int x = 0; x < Width; x++) { 
      Range currentRange = null; 
      for (int y = 0; y < Height; y++) { 
       Func<Range, Rectangle> CloseRange = r => { 
        currentRange = null; 
        ranges[r.StartY] = null; 
        return new Rectangle(
         r.StartY, 
         r.StartX, 
         x - r.StartX, 
         r.EndY - r.StartY 
        ); 
       }; 

       if (currentRange == null || currentRange.EndY <= y) 
        currentRange = ranges[y]; 

       if (Data[x, y] == 1) { 
        if (currentRange == null) { 
         int startY = y; 
         for (; y < Height && Data[x, y] == 1; y++) { 
          if (ranges[y] != null) 
           yield return CloseRange(ranges[y]); 
          //If there are fuzzy edges, break; instead 
         } 
         ranges[startY] = new Range(x, startY, y); 
         if (y == Height) 
          continue; 
         //Otherwise, continue to the next if in case a previous range just ended 
        } 
       } 
       //No else; we can get here after creating a range 
       if(Data[x, y] == 0) { 
        if (currentRange != null) 
         yield return CloseRange(currentRange); 
       } 
      } 
     } 
    } 
} 

Answer 2

Hãy thử một cái gì đó như thế này:

1. Tạo một danh sách có chứa tất cả các điểm mong muốn. (Trong trường hợp của bạn, tọa độ của mỗi 1)

2. Đối với mỗi điểm trong danh sách này:

   1. Vòng xuống trục Y từ thời điểm này cho đến khi bạn nhấn một điểm không mong muốn (một 0)
   2. Lặp lại ngay dọc theo trục X cho đến khi bạn nhấn tọa độ X có giá trị 0 tại bất kỳ giá trị Y nào giữa điểm và tọa độ Y kết thúc bạn nhận được từ bước 1.
   3. Thêm hình chữ nhật mà bạn vừa tìm thấy vào danh sách hình chữ nhật
   4. Xóa mọi điểm trong hình chữ nhật khỏi danh sách gốc.

Đây có lẽ không phải là cách nhanh nhất để làm điều này, nhưng nó sẽ hoạt động.