查找至少部分位于任意方向矩形内的所有像素

Question

我有一个带有实值顶点 (x0,y0)、(x1,y1)、(x2,y2)、(x3,y3)，它可以在平面上以任何角度定向。我正在寻找一种有效的方法来查找（或迭代）至少部分位于该矩形内的所有像素（即 1x1 正方形）。

对于正交定向的矩形来说，执行此操作很简单，并且检查任何特定像素是否在矩形内也很简单。我可以检查矩形边界框中的每个像素，但在最坏的情况下，当目标矩形内只有 O(n) 时，我将检查 O(n^2) 个像素。 （这是当目标矩形处于 45 度且非常长且窄时的情况。）

Answer 1

您可以计算 x 方向的范围（最小 x 坐标的下限，到最大 x 坐标的上限）。对于该范围内的每个 x，您可以计算 y 方向的范围。在一般情况下，您需要考虑几种不同的情况，具体取决于矩形的方向。

本质上，你有一个最左边的点，一个最右边的点，一个上面的点和一个下面的点。 y1 将从最左边开始，穿过下部，最后在最右边的点结束。 y2 将穿过上点。

为了包含所有接触的像素，我们需要在所有方向上查看半个像素。我选择使用每个像素的中心作为坐标。这样做是为了让最终图像看起来更自然。

以下是一些要演示的 F# 代码：

let plot_rectangle p0 p1 p2 p3 =
    seq {
        // sort by x-coordinate
        let points = List.sortBy fst [p0; p1; p2; p3]
        let pLeft, pMid1, pMid2, pRight =
            points.[0], points.[1], points.[2], points.[3]

        // sort 2 middle points by y-coordinate
        let points = List.sortBy snd [pMid1; pMid2]
        let pBottom, pTop = points.[0], points.[1]

        // Easier access to the coordinates
        let pLeftX, pLeftY = pLeft
        let pRightX, pRightY = pRight
        let pBottomX, pBottomY = pBottom
        let pTopX, pTopY = pTop
        let pMid1X, pMid1Y = pMid1
        let pMid2X, pMid2Y = pMid2

        // Function: Get the minimum Y for a given X
        let getMinY x0 y0 x1 y1 x =
            let slope = (y1 - y0)/(x1 - x0)
            // Step half a pixel left or right, but not too far
            if slope >= 0.0 then
                let xl = max x0 (x - 0.5)
                y0 + slope * (xl - x0)
                |> round
                |> int
            else
                let xr = min x1 (x + 0.5)
                y0 + slope * (xr - x0)
                |> round
                |> int

        // Function: Get the maximum Y for a given X
        let getMaxY x0 y0 x1 y1 x =
            let slope = (y1 - y0)/(x1 - x0)
            // Step half a pixel left or right, but not too far
            if slope >= 0.0 then
                let xr = min x1 (x + 0.5)
                y0 + slope * (xr - x0)
                |> round
                |> int
            else
                let xl = max x0 (x - 0.5)
                y0 + slope * (xl - x0)
                |> round
                |> int

        let x1 = int (pLeftX + 0.5)
        let x2 = int (pRightX + 0.5)
        for x = x1 to x2 do
            let xf = float x
            if xf < pMid1X then
                // Phase I: Left to Top and Bottom
                // Line from pLeft to pBottom
                let y1 = getMinY pLeftX pLeftY pBottomX pBottomY xf
                // Line from pLeft to pTop
                let y2 = getMaxY pLeftX pLeftY pTopX pTopY xf
                for y = y1 to y2 do
                    yield (x, y)

            elif xf < pMid2X && pMid1Y < pMid2Y then
                // Phase IIa: left/bottom --> top/right
                // Line from pBottom to pRight
                let y1 = getMinY pBottomX pBottomY pRightX pRightY xf
                // Line from pLeft to pTop (still)
                let y2 = getMaxY pLeftX pLeftY pTopX pTopY xf
                for y = y1 to y2 do
                    yield (x, y)

            elif xf < pMid2X && pMid1Y >= pMid2Y then
                // Phase IIb: left/top --> bottom/right
                // Line from pLeft to pBottom (still)
                let y1 = getMinY pLeftX pLeftY pBottomX pBottomY xf
                // Line from pTop to pRight
                let y2 = getMaxY pTopX pTopY pRightX pRightY xf
                for y = y1 to y2 do
                    yield (x, y)

            else
                // Phase III: bottom/top --> right
                // Line from pBottom to pRight
                let y1 = getMinY pBottomX pBottomY pRightX pRightY xf
                // Line from pTop to pRight
                let y2 = getMaxY pTopX pTopY pRightX pRightY xf
                for y = y1 to y2 do
                    yield (x, y)
    }

示例：

Answer 2

你能使用格雷厄姆扫描之类的东西吗？
您可以使用 5 个点的集合（像素 + 4 个顶点），然后检查 4 个顶点是否定义了凸包的边界。这在最坏的情况下是 O(n log n)，这对于大 n 来说是对 n^2 的显着改进。
或者，二维范围树可能就足够了，尽管我认为这仍然是 n log n

编辑：
实际上，您可以使用 4 个顶点之间的角度来创建像素可能位于的 4 个“范围”，然后只需取这 4 个范围的交集即可。这将是一个恒定时间操作，并且检查像素是否位于该范围内也是恒定时间 - 只需将它与每个顶点形成的角度与上述角度集进行比较即可。
作为另一种选择，使用 4 条边界线（相邻顶点之间的线）并在它们之间“行走”。一旦到达该线，任何进一步向下的点都不会位于该边界内，等等。矩形内的像素数量是 O(n)，并且应该可以通过简单的广度优先搜索轻松解决

Answer 3

以下是一些基于 的 Python 代码MizardX 的答案 正是我想要的：

#!/usr/bin/python

import math

def minY(x0, y0, x1, y1, x):
  if x0 == x1:
    # vertical line, y0 is lowest
    return int(math.floor(y0))

  m = (y1 - y0)/(x1 - x0)

  if m >= 0.0:
    # lowest point is at left edge of pixel column
    return int(math.floor(y0 + m*(x - x0)))
  else:
    # lowest point is at right edge of pixel column
    return int(math.floor(y0 + m*((x + 1.0) - x0)))

def maxY(x0, y0, x1, y1, x):
  if x0 == x1:
    # vertical line, y1 is highest
    return int(math.ceil(y1))

  m = (y1 - y0)/(x1 - x0)

  if m >= 0.0:
    # highest point is at right edge of pixel column
    return int(math.ceil(y0 + m*((x + 1.0) - x0)))
  else:
    # highest point is at left edge of pixel column
    return int(math.ceil(y0 + m*(x - x0)))


# view_bl, view_tl, view_tr, view_br are the corners of the rectangle
view_bl = (0.16511327500123524, 1.2460844930844697)
view_tl = (1.6091354363329917, 0.6492542948962687)
view_tr = (1.1615128085358943, -0.4337622756706583)
view_br = (-0.2825093527958621, 0.16306792251754265)

pixels = []

# find l,r,t,b,m1,m2
view = [ view_bl, view_tl, view_tr, view_br ]

l, m1, m2, r = sorted(view, key=lambda p: (p[0],p[1]))
b, t = sorted([m1, m2], key=lambda p: (p[1],p[0]))

lx, ly = l
rx, ry = r
bx, by = b
tx, ty = t
m1x, m1y = m1
m2x, m2y = m2

xmin = 0
ymin = 0
xmax = 10
ymax = 10

# outward-rounded integer bounds
# note that we're clamping the area of interest to (xmin,ymin)-(xmax,ymax)
lxi = max(int(math.floor(lx)), xmin)
rxi = min(int(math.ceil(rx)), xmax)
byi = max(int(math.floor(by)), ymin)
tyi = min(int(math.ceil(ty)), ymax)

x1 = lxi 
x2 = rxi 

for x in range(x1, x2):
  xf = float(x)

  if xf < m1x:
    # Phase I: left to top and bottom
    y1 = minY(lx, ly, bx, by, xf)
    y2 = maxY(lx, ly, tx, ty, xf)

  elif xf < m2x:
    if m1y < m2y:
      # Phase IIa: left/bottom --> top/right
      y1 = minY(bx, by, rx, ry, xf)
      y2 = maxY(lx, ly, tx, ty, xf)

    else:
      # Phase IIb: left/top --> bottom/right
      y1 = minY(lx, ly, bx, by, xf)
      y2 = maxY(tx, ty, rx, ry, xf)

  else:
    # Phase III: bottom/top --> right
    y1 = minY(bx, by, rx, ry, xf)
    y2 = maxY(tx, ty, rx, ry, xf)

  y1 = max(y1, byi)
  y2 = min(y2, tyi)

  for y in range(y1, y2):
    pixels.append((x,y))

print pixels

输出：

[(0, 0), (0, 1), (1, 0)]