После дальнейших размышлений я нашел более быстрое решение:
Создание неизменяемой структуры Range со свойствами StartX, StartY и EndY.
Поддерживает разреженный массив текущих Range s, длина которого равна высоте изображения, и единственная переменная currentRange, допускающая значение NULL.Этот массив будет содержать диапазон, если он есть, который начинается с каждой координаты Y
Для каждого столбца
- Очистить
currentRange Для каждой ячейки в столбце:
Если нет currentRange, или если он есть, но он закончился до этой ячейки (если currentRange.EndY <= y), установите currentRange наy '-ый элемент в массиве диапазонов.
Таким образом, currentRange всегда будет ссылаться на диапазон, содержащий текущую ячейку, или null, если текущая ячейка не находится в диапазоне.
Если текущая ячейка 1:
Если мы в диапазоне, ничего не делать - диапазон продолжается в следующем столбце.
Если мы не находимся в диапазоне, зацикливайте столбец до тех пор, пока не достигнете 0 или конца столбца, а затем создайте новый диапазон, растягиваясь от 1, который мы простонайдено до конца цикла.
Затем перейдите к следующему if (поскольку текущая ячейка теперь 0 или конец столбца, а мы не в диапазоне)
Если вы нажмете существующий диапазон, когда создаете новый диапазон, вы можете либо остановить новый диапазон и оставить существующий диапазон ниже его (лучше всего для нечетких краев), либо закрыть существующий диапазон (см. Ниже) ипусть новый диапазон растягивается вниз, чтобы заменить существующий диапазон.
- Если текущая ячейка равна
0: - Если мы находимся вrange, закройте диапазон:
- Верните новый прямоугольник, растягивающийся от начала X и Y диапазона до текущего Y и конца X диапазона.
- Очистите диапазон из массива активных диапазонов.
Этот алгоритм O(x * y) в вычислениях и O(y) в пространстве.Я считаю, что это самое быстрое решение проблемы.
Вы также можете вращать этот алгоритм и сканировать строки, а не столбцы (чтобы диапазоны были растянуты вниз, а не вправо), что будет O(x) вместо хранения.
Вот реализация C #:
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);
}
}
}
}
}