Рассчитать ограничивающую рамку произвольного пиксельного рисунка

Question

Учитывая непрерывное рисование произвольных пикселей (например, на холсте HTML5), существует ли какой-либо алгоритм для нахождения ограничивающей оси выравнивающей оси, который более эффективен, чем просто просмотр каждого пикселя и запись мин / макс х /значения y ?

Answer 1

Просто отсканируйте линию сверху слева, направо и вниз, чтобы получить вершину y, и аналогичный алгоритм с остальными направлениями.

---

Редактировать Phrogz:

Вот реализация псевдокода. Включенная оптимизация гарантирует, что каждая строка сканирования не смотрит на пиксели, покрытые предыдущим проходом:

function boundingBox()
  w = getWidth()            # Assuming graphics address goes from [0,w)
  h = getHeight()           # Assuming graphics address goes from [0,h)
  for y=h-1 to 0 by -1      # Iterate from last row upwards
    for x=w-1 to 0 by -1    # Iterate across the entire row
      if pxAt(x,y) then
        maxY=y
        break               # Break out of both loops

  if maxY===undefined then  # No pixels, no bounding box
    return               

  for x=w-1 to 0 by -1      # Iterate from last column to first
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        maxX=x
        break               # Break out of both loops

  for x=0 to maxX           # Iterate from first column to maxX
    for y=0 to maxY         # Iterate down the column, up to maxY
      if pxAt(x,y) then
        minX=x
        break               # Break out of both loops

  for y=0 to maxY           # Iterate down the rows, up to maxY
    for x=0 to maxX         # Iterate across the row, up to maxX
      if pxAt(x,y) then
        minY=y
        break               # Break out of both loops

  return minX, minY, maxX, maxY

Результат (на практике) работает примерно так же, как алгоритм грубой силы для одного пикселя, и значительно лучше, когда объект становится больше.

Демо: http://phrogz.net/tmp/canvas_bounding_box2.html

Для забавы, вот наглядное представление о том, как работает этот алгоритм:

Неважно, в каком порядке вы выбираете обработку сторон, вам просто нужно убедиться, что вы учли предыдущие результаты, чтобы не выполнять двойное сканирование углов.

Answer 2

Вы можете использовать какой-либо бинарный поиск или выборку на грубой сетке, а затем на более тонкой сетке.Правильность этого метода зависит от того, разрешены ли в вашем чертеже «дыры».