计算任意基于像素的绘图的边界框 [英] Calculate bounding box of arbitrary pixel-based drawing

问题描述

给定一个任意像素的连续绘图（例如，在HTML5 Canvas上），是否有任何算法可以找到轴对齐的边界框，它比简单的查看每个像素并记录最小/最大x / y值？ 解决方案

只需从左上​​角到右下角的扫描线，然后按下y键即可获得顶部，其余部分使用不同方向的类似算法。

---

由Phrogz编辑：

这是一个伪代码实现。包含的优化功能可确保每条扫描线不会看到先前传递的像素。

 函数boundingBox（）
w = getWidth（）＃假设图形地址从[0，w）开始
h = getHeight（）＃假设图形地址从[0，h）
变为y = h -1到0 by -1＃最后一行向上迭代
 x = w-1到0 by -1＃遍历整行
如果pxAt（x，y）则
 maxY = y 
 break＃跳出两个循环
 
 if maxY === undefined然后＃没有像素，没有边界框
返回
 
 for x = w-1到0 by -1＃从最后一列到第一个
迭代y = 0到maxY＃迭代列，直到maxY 
如果pxAt（x，y）那么
 maxX = x 
 break＃跳出两个循环
 
（从x = 0到maxX）＃从第一个co如果pxAt（x，y）然后是
 minX = x 
 break＃列表中的最后一列为maxX 
，那么y = 0到maxY＃两个循环
 
 for y = 0 to maxY＃迭代下行，max = 
 for x = 0 to maxX＃遍历整行，最大为maxX 
如果pxAt （x，y）然后
 minY = y 
 break＃分两个循环
 
返回minX，minY，maxX，maxY 
  

结果（实际上）与单个像素的蛮力算法大致相同，并且随着对象变大而显着更好。 / p>

演示： http://phrogz.net/tmp /canvas_bounding_box2.html

为了好玩，下面是该算法工作原理的直观表示：

       

       

       

       

       

没关系按照你选择做什么样的顺序，你只需要确保你考虑到以前的结果，这样你就不会再对角落进行双重扫描。

Given a contiguous drawing of arbitrary pixels (e.g. on an HTML5 Canvas) is there any algorithm for finding the axis-aligned bounding box that is more efficient than simply looking at every pixel and recording the min/max x/y values?

解决方案

Just scanline from top left to right and down to get y top,and similar algorithm with different directions for the rest.

---

Edit by Phrogz:

Here's a pseudo-code implementation. An included optimization ensures that each scan line does not look at pixels covered by an earlier pass:

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

The result (in practice) performs about the same as the brute-force algorithm for a single pixel, and significantly better as the object gets larger.

Demo: http://phrogz.net/tmp/canvas_bounding_box2.html

For fun, here's a visual representation of how this algorithm works:

       
       
       
       
       

It doesn't matter in what order you choose to do the sides, you just have to make sure that you take the previous results into account so that you are not double-scanning the corners.

这篇关于计算任意基于像素的绘图的边界框的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！