Алгоритм "поиска" многоугольника

[arseniiv]

Определяем все границы (внешнюю и внутренние для дырок по обе стороны от лесенки) и выписываем их туда. При этом внутренние границы автоматически получатся в правильном направлении. Единственная нетривиальная часть — это придумать как не слишком долго искать любую точку всех внутренних границ фигуры. Ну тут придётся все пиксели внутри внешней границы фигуры обойти, чтобы удостовериться, что все дырки покрыты, так что для общего случая оптимизировать нечего. Если же мы знаем, что в фигуре не больше $c$ довольно больших дырок, можно вместо этого найти какие-нибудь точки внутри дыр найти делением пополам (точнее, на 4 части: пополам по вертикали и по горизонтали) и потом причаливать ко внутренней границе дыры, идя в любом направлении, так же как мы будем делать и в поисках внешней границы фигуры.

Если же фигура всегда состоит из почти однопиксельных линий, можно попробовать придумать что-то хитрее (находить точки на внутренних границах, ища рядом с внешней, пытаясь прыгнуть куда-то внутрь, но не прерывая обход внешней границы если что-то найдём, а складывая эти точки на потом), но вряд ли оно без должного тестирования покроет вообще любой случай.

[kotenok gav]

Хорошо, а как модифицировать ваш алгоритм для нахождения внутренних границ? Ведь он находит только внешнюю.

[arseniiv]

Нее, любую. С точки какой границы начать, ту и найдёт. Остаётся только приземлиться на хоть какую-то, ну и как я написал выше, каждая внутренняя связана с дыркой (непокрашенными пикселями). Хотя я забыл учесть возможные острова внутри дырок, но они опять же найдутся при переборе всех точек внутри внешней границы, что нам и так требуется.

[kotenok gav]

Если, он, скажем, попадет на лесенку, то он может выдать вместе с ней еще и внутреннюю границу...

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

[arseniiv]

Примерно так, но надо чтобы точка не была окружена $\begin{smallmatrix} 0 & 0 \\ 0 & 0 \end{smallmatrix}$ или $\begin{smallmatrix} 1 & 1 \\ 1 & 1 \end{smallmatrix}$, то есть она должна быть граничной. Но при переборе всех точек мы как раз легко отберём граничные.

-- Вт апр 28, 2020 15:23:09 --

И каждая из них будет входить ровно в одну или две границы (две — как раз случай точки на лесенке).

-- Вт апр 28, 2020 15:24:04 --

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

[kotenok gav]

Ну, 0000 не будет (фигура связная). А вот 1111 вполне может быть, причем желательно, чтобы это тоже входило в границу (т.е. не закрашивалось)...

[arseniiv]

1111 — это же для точки внутри фигуры, вот например пример:

   
   0 0 0 0 0 0 0 0 0
      +-+-+-+-+
   0 0|1 1 1 1|0 0 0
    +-+ +-+-+ +-+
   0|1 1|0 0|1 1|0 0
    +-+ +-+ + ⋅ +-+
   0 0|1 1|0|1 1 1|0
      +-+ +-+-+ +-+
   0 0 0|1 1|0|1|0 0
        + ⋅ +-+ +
   0 0 0|1 1 1 1|0 0
        +-+-+-+-+
   0 0 0 0 0 0 0 0 0
   

Тут ⋅ — внутренние точки (здесь всего две), + — граничные, и - | — отрезки границы.

-- Ср апр 29, 2020 15:29:02 --

(Хм, у меня в редакторе лучше читается. И наверно в пайнте быстрее бы нарисовал, однако.)

[kotenok gav]

arseniiv в сообщении #1458827 писал(а):

1111 — это же для точки внутри фигуры

Это я понимаю, но если эта точка не будет границей, то SVG ее ошибочно закрасит. Хотя, можно все такие точки отделять в специальные одноклеточные границы...

[arseniiv]

А почему ошибочно закрасит? Она же внутренняя, у неё со всех сторон закрашенные в растровом исходном изображении пиксели.

[kotenok gav]

arseniiv в сообщении #1458844 писал(а):

Она же внутренняя, у неё со всех сторон закрашенные в растровом исходном изображении пиксели.

Это как раз незакрашенные. Точнее, это черные пиксели, а внутренность фигуры SVG должен сам закрасить (другим цветом).

[arseniiv]

Так мы же вроде считали чёрные пиксели закрашенными пикселями фигуры, а белые — незакрашенными, фигуре не принадлежащими? Я запутался.

[kotenok gav]

Ну... Это мы ведь определяем границу фигуры, чтобы потом SVG закрасил все точки внутри ее (фигуры, а не границы).

[arseniiv]

Мне стоило писать «в фигуре». Я считаю что фигура образована объединением замкнутых квадратиков, а искомые границы — собственно границы её как множества в метрическом пространстве, и тогда внутри границ[ы] = «внутри» фигуры. Даже когда интересуют только центры пикселей, они будут попадать или не попадать в закрашенную часть плоскости при моём алгоритме нахождения границ ровно тогда, когда попадают объемлющие их квадратики.

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

[kotenok gav]

arseniiv в сообщении #1458864 писал(а):

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

Ок, пойду реализую его.

[kotenok gav]

Итак, вот программа:

Используется синтаксис Python

from PIL import Image, ImageDraw
leftPixelDict = {(0, 1): (1, 0), (0, -1): (0, -1), (1, 0): (1, -1), (-1, 0): (0, 0)}
rightPixelDict = {(0, 1): (0, 0), (0, -1): (1, -1), (1, 0): (1, 0), (-1, 0): (0, -1)}
def add(vector1, vector2):
    return (vector1[0] + vector2[0], vector1[1] + vector2[1])
def mult(vector):
    return (-vector[1], vector[0])
def testDirection(point, direction):
    point = add(point, direction)
    leftPixel = add(point, leftPixelDict[direction])
    rightPixel = add(point, rightPixelDict[direction])
    if (leftPixel in polygonPixels) and (rightPixel not in polygonPixels):
        return True
    return False
def getDirection(point, oldDirection):
    direction = oldDirection
    for i in range(4):
        if testDirection(point, direction):
            return direction
        direction = mult(direction)
    raise Exception
def findBorder(startPoint):
    #Point is uniquely defined by a pixel, which right upper vertice is this point
    border = [startPoint]
    direction = getDirection(startPoint, (0, 1))
    point = add(startPoint, direction)
    while (point != startPoint):
        border.append(point)
        direction = getDirection(startPoint, direction)
        point = add(point, direction)
    return border
image = Image.open("test.png")
draw = ImageDraw.Draw(image)
width = image.size[0]
height = image.size[1]
pixels = image.load()
polygonPixels = []
for y in range(height):
    for x in range(width):
        pixel = pixels[x, y]
        if pixel[0:3] == (0, 0, 255):
            polygonPixels.append((x, y))
print(findBorder((127, 24)))
##notVisited = polygonPixels
##SVG = ''
##while (notVisited != []):
##    pixel = notVisited[0]
##    cLP = (add(pixel, (-1, 0)) in polygonPixels)
##    cRP = (add(pixel, (1, 0)) in polygonPixels)
##    cUP = (add(pixel, (0, -1)) in polygonPixels)
##    cDP = (add(pixel, (0, 1)) in polygonPixels)
##    if (cLP and cRP and cUP and cDP):
##        SVG += ' M ' + str(pixel[0]) + ' ' + str(pixel[1]) + ' z'
##        notVisited = list(set(notVisited).difference({pixel}))
##    else:
##        border = findBorder(pixel)
##        notVisited = list(set(notVisited).difference(set(border)))
##        SVG += ' M '
##        for pix in border:
##            SVG += str(pix[0]) + ' ' + str(pix[1]) + ' L'
##        SVG = SVG[:-1] + 'z'
##print(SVG[1:])
 

Закомментированное - основная часть программы, она ломается на самом первом пикселе ((127, 24)), это демонстрирует строчка print(findBorder((127, 24))).
Программу запускал на реальном примере:

Пойду дебажить ее.

-- 30 апр 2020, 01:17 --

Исправил:

Используется синтаксис Python

from PIL import Image, ImageDraw
leftPixelDict = {(0, 1): (1, 0), (0, -1): (0, -1), (1, 0): (1, -1), (-1, 0): (0, 0)}
rightPixelDict = {(0, 1): (0, 0), (0, -1): (1, -1), (1, 0): (1, 0), (-1, 0): (0, -1)}
def add(vector1, vector2):
    return (vector1[0] + vector2[0], vector1[1] + vector2[1])
def mult(vector):
    return (-vector[1], vector[0])
def testDirection(point, direction):
    leftPixel = add(point, leftPixelDict[direction])
    rightPixel = add(point, rightPixelDict[direction])
    if (leftPixel in polygonPixels) and (rightPixel not in polygonPixels):
        return True
    return False
def getDirection(point, oldDirection):
    direction = oldDirection
    for i in range(4):
        if testDirection(point, direction):
            return direction
        direction = mult(direction)
    raise Exception
def findBorder(startPoint):
    #Point is uniquely defined by a pixel, which right upper vertice is this point
    border = [startPoint]
    direction = getDirection(startPoint, (0, 1))
    point = add(startPoint, direction)
    while (point != startPoint):
        border.append(point)
        direction = getDirection(startPoint, direction)
        point = add(point, direction)
    return border
image = Image.open("test.png")
draw = ImageDraw.Draw(image)
width = image.size[0]
height = image.size[1]
pixels = image.load()
polygonPixels = []
for y in range(height):
    for x in range(width):
        pixel = pixels[x, y]
        if pixel[0:3] == (0, 0, 255):
            polygonPixels.append((x, y))
print(findBorder((127, 24)))
##notVisited = polygonPixels
##SVG = ''
##while (notVisited != []):
##    pixel = notVisited[0]
##    cLP = (add(pixel, (-1, 0)) in polygonPixels)
##    cRP = (add(pixel, (1, 0)) in polygonPixels)
##    cUP = (add(pixel, (0, -1)) in polygonPixels)
##    cDP = (add(pixel, (0, 1)) in polygonPixels)
##    if (cLP and cRP and cUP and cDP):
##        SVG += ' M ' + str(pixel[0]) + ' ' + str(pixel[1]) + ' z'
##        notVisited = list(set(notVisited).difference({pixel}))
##    else:
##        border = findBorder(pixel)
##        notVisited = list(set(notVisited).difference(set(border)))
##        SVG += ' M '
##        for pix in border:
##            SVG += str(pix[0]) + ' ' + str(pix[1]) + ' L'
##        SVG = SVG[:-1] + 'z'
##print(SVG[1:])
 

Теперь оно не выдает ошибку, а впадает в бесконечный цикл.

-- 30 апр 2020, 01:26 --

Используется синтаксис Python

from PIL import Image, ImageDraw
leftPixelDict = {(0, 1): (1, 0), (0, -1): (0, -1), (1, 0): (1, -1), (-1, 0): (0, 0)}
rightPixelDict = {(0, 1): (0, 0), (0, -1): (1, -1), (1, 0): (1, 0), (-1, 0): (0, -1)}
def add(vector1, vector2):
    return (vector1[0] + vector2[0], vector1[1] + vector2[1])
def mult(vector):
    return (-vector[1], vector[0])
def testDirection(point, direction):
    leftPixel = add(point, leftPixelDict[direction])
    rightPixel = add(point, rightPixelDict[direction])
    if (leftPixel in polygonPixels) and (rightPixel not in polygonPixels):
        return True
    return False
def getDirection(point, oldDirection):
    direction = oldDirection
    for i in range(4):
        if testDirection(point, direction):
            return direction
        direction = mult(direction)
    raise Exception
def findBorder(startPoint):
    #Point is uniquely defined by a pixel, which right upper vertice is this point
    border = [startPoint]
    direction = getDirection(startPoint, (0, 1))
    point = add(startPoint, direction)
    while (point != startPoint):
        border.append(point)
        direction = getDirection(point, direction)
        point = add(point, direction)
    return border
image = Image.open("test.png")
draw = ImageDraw.Draw(image)
width = image.size[0]
height = image.size[1]
pixels = image.load()
polygonPixels = []
for y in range(height):
    for x in range(width):
        pixel = pixels[x, y]
        if pixel[0:3] == (0, 0, 255):
            polygonPixels.append((x, y))
##notVisited = polygonPixels
##SVG = ''
##while (notVisited != []):
##    pixel = notVisited[0]
##    cLP = (add(pixel, (-1, 0)) in polygonPixels)
##    cRP = (add(pixel, (1, 0)) in polygonPixels)
##    cUP = (add(pixel, (0, -1)) in polygonPixels)
##    cDP = (add(pixel, (0, 1)) in polygonPixels)
##    if (cLP and cRP and cUP and cDP):
##        SVG += ' M ' + str(pixel[0]) + ' ' + str(pixel[1]) + ' z'
##        notVisited = list(set(notVisited).difference({pixel}))
##    else:
##        border = findBorder(pixel)
##        notVisited = list(set(notVisited).difference(set(border)))
##        SVG += ' M '
##        for pix in border:
##            SVG += str(pix[0]) + ' ' + str(pix[1]) + ' L '
##        SVG = SVG[:-2] + 'z'
##print(SVG[1:])
 

Теперь он нормально работает на первом пикселе (выдает большую границу, но, кажется, неправильную), и ломается только на втором шаге.