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

Question

У меня есть прямоугольник с действительными вершинами (x0,y0), (x1,y1), (x2,y2), (x3,y3), который может быть ориентирован под любым углом на плоскости.Я ищу эффективный способ найти (или перебрать) все пиксели (то есть квадраты 1x1), которые хотя бы частично находятся внутри этого прямоугольника.

Это просто для прямоугольников, которые ориентированы ортогонально,и также тривиально проверить, находится ли какой-либо конкретный пиксель в прямоугольнике.Я мог бы проверить каждый пиксель в пределах прямоугольника, но в худшем случае я бы проверил O (n ^ 2) пикселей, когда только O (n) будет в пределах целевого прямоугольника.(Это когда целевой прямоугольник находится под углом 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 ^ 2 для больших n. В качестве альтернативы может быть достаточно двухмерного дерева диапазонов, хотя я думаю, что это все равно будет n log n

EDIT: На самом деле, вы можете использовать углы между 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)]