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

[kotenok gav]

Хотя не, первую границу он выдает правильно:

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

border = findBorder((127, 24))
for y in range(height):
    s = ''
    for x in range(width):
        if (x, y) in border:
            s += '+'
        elif (x, y) in polygonPixels:
            s += '*'
        else:
            s += '.'
    print(s)

-- 30 апр 2020, 02:16 --

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

[arseniiv]

А как она может выйти незамкнутая?

[kotenok gav]

Хотя, все же, первая граница не совсем правильна... К примеру, там есть пиксель (126, 24), которого, на самом деле, нет.

-- 30 апр 2020, 02:41 --

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

А как она может выйти незамкнутая?

Хм, да. Надо будет тщательнее посмотреть...

-- 30 апр 2020, 02:43 --

kotenok gav в сообщении #1458931 писал(а):

К примеру, там есть пиксель (126, 24), которого, на самом деле, нет.

Это из-за того, что там граница состоит из точек, которых я обозначаю пикселями, правыми верхними вершинами которых они являются. Так что еще есть задача по превращению точек в пиксели...

[arseniiv]

А почему правыми верхними, а не левыми верхними? Тогда вроде будет обычное соотношение, которое между ними принимается: пиксель с индексами $(x, y)$ — квадрат $[x; x+1]\times[y; y+1]$.

[kotenok gav]

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

А почему правыми верхними, а не левыми верхними? Тогда вроде будет обычное соотношение, которое между ними принимается: пиксель с индексами $(x, y)$ — квадрат $[x; x+1]\times[y; y+1]$.

Хорошо, перепишу.

-- 30 апр 2020, 03:25 --

Переписал:

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

from PIL import Image, ImageDraw
leftPixelDict = {(0, 1): (0, 0), (0, -1): (-1, -1), (1, 0): (0, -1), (-1, 0): (-1, 0)}
rightPixelDict = {(0, 1): (-1, 0), (0, -1): (0, -1), (1, 0): (0, 0), (-1, 0): (-1, -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 left 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]
    print(pixel)
    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:])
 

Теперь ломается лишь на четвертом шаге.

[kotenok gav]

Ой, я понял, в чем ошибка (неправильно выбираю порядок тестируемых направлений (у меня $x$, $ix$, $-x$, $-ix$, а надо $x$, $ix$, $-ix$)).

[kotenok gav]

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

from PIL import Image, ImageDraw
leftPixelDict = {(0, 1): (0, 0), (0, -1): (-1, -1), (1, 0): (0, -1), (-1, 0): (-1, 0)}
rightPixelDict = {(0, 1): (-1, 0), (0, -1): (0, -1), (1, 0): (0, 0), (-1, 0): (-1, -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
    if testDirection(point, direction):
        return direction
    direction = mult(direction)
    if testDirection(point, direction):
        return direction
    direction = mult(mult(direction))
    if testDirection(point, direction):
        return direction
    raise Exception
def findBorder(startPoint):
    #Point is uniquely defined by a pixel, which left 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]
    print(pixel)
    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:])
 

Ломается на том же шаге.

[arseniiv]

Собрался проверить, а у PIL нету версии для третьего питона.

Можете пока результирующий SVG показать? Я наложу на ту картинку и попробую понять так.

[kotenok gav]

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

PIL нету версии для третьего питона

Как же нет, когда есть.

-- 02 май 2020, 01:57 --

pip install Pillow

-- 02 май 2020, 01:58 --

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

Можете пока результирующий SVG показать?

Так ведь ломается программа. Но на последнем рабочем шаге - M 127 24 L 127 25 L 126 25 L 125 25 L 125 26 L 124 26 L 123 26 L 123 27 L 122 27 L 122 28 L 121 28 L 121 29 L 120 29 L 120 30 L 120 31 L 120 32 L 120 33 L 120 34 L 119 34 L 118 34 L 118 35 L 117 35 L 117 36 L 118 36 L 118 37 L 119 37 L 120 37 L 120 38 L 120 39 L 121 39 L 121 40 L 122 40 L 123 40 L 124 40 L 125 40 L 126 40 L 127 40 L 127 41 L 128 41 L 129 41 L 130 41 L 131 41 L 132 41 L 132 40 L 133 40 L 134 40 L 134 39 L 135 39 L 136 39 L 137 39 L 138 39 L 139 39 L 140 39 L 140 38 L 141 38 L 141 37 L 142 37 L 142 36 L 142 35 L 142 34 L 143 34 L 143 33 L 143 32 L 143 31 L 143 30 L 142 30 L 141 30 L 140 30 L 140 29 L 139 29 L 139 28 L 139 27 L 138 27 L 138 26 L 137 26 L 137 25 L 136 25 L 135 25 L 135 24 L 134 24 L 133 24 L 132 24 L 131 24 L 130 24 L 129 24 L 128 24 z M 141 33 L 141 34 L 141 35 L 140 35 L 139 35 L 138 35 L 138 34 L 137 34 L 136 34 L 135 34 L 134 34 L 134 35 L 135 35 L 136 35 L 137 35 L 137 36 L 138 36 L 139 36 L 140 36 L 140 37 L 139 37 L 139 38 L 138 38 L 137 38 L 136 38 L 135 38 L 134 38 L 133 38 L 133 39 L 132 39 L 131 39 L 131 40 L 130 40 L 129 40 L 128 40 L 128 39 L 127 39 L 126 39 L 125 39 L 124 39 L 123 39 L 122 39 L 122 38 L 123 38 L 124 38 L 124 37 L 123 37 L 122 37 L 121 37 L 121 36 L 122 36 L 122 35 L 121 35 L 121 34 L 121 33 L 121 32 L 121 31 L 121 30 L 121 29 L 122 29 L 122 28 L 123 28 L 123 27 L 124 27 L 125 27 L 125 26 L 126 26 L 127 26 L 127 25 L 128 25 L 129 25 L 130 25 L 131 25 L 132 25 L 133 25 L 134 25 L 134 26 L 135 26 L 136 26 L 136 27 L 137 27 L 137 28 L 138 28 L 138 29 L 138 30 L 139 30 L 139 31 L 140 31 L 141 31 L 141 32 L 140 32 L 140 33 z M 119 36 L 118 36 L 118 35 L 119 35 L 120 35 L 121 35 L 121 36 L 120 36 z.

-- 02 май 2020, 02:01 --

И оно немного неверные границы выдает:

kotenok gav в сообщении #1458931 писал(а):

Хотя, все же, первая граница не совсем правильна... К примеру, там есть пиксель (127, 25) (UPD), которого, на самом деле, нет.

Т.е. в лесенке оно добавляет пиксели.

[arseniiv]

kotenok gav в сообщении #1459436 писал(а):

Как же нет, когда есть.

Ааа. Опять модуль называется не так как импортируется. Хорошо.

kotenok gav в сообщении #1459436 писал(а):

Так ведь ломается программа.

А, понятно. Поглядим…

-- Пт май 01, 2020 21:19:35 --

Вот картинка, которую я слепил на основании своего запуска и вашего. https://i.postimg.cc/ydhNkMX8/Screenshot-2244.png. Оранжевый контур — то, что выдало у меня (видно, что дырочка слева в нём отсутствует), а чёрный — ваш. Всё очерчено. Вполне может быть, что исключение возникает тогда, когда больше некуда идти, хотя я ещё недостаточно читал код.

-- Пт май 01, 2020 21:22:00 --

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

[kotenok gav]

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

то, что выдало у меня

То, что моя программа выдала? Я ведь привел то, что она выдала.

[arseniiv]

Да, чёрным я нарисовал ваш результат, а оранжевым то, как она запустилась у меня — почему-то меньше, но это уж я не знаю.

[kotenok gav]

И как чинить алгоритм/программу?

[arseniiv]

Ммм… Ну как я понял, там проблема в том, что мы всё обошли, все границы нашли, а почему-то предполагается, что надо идти дальше, и вот в этом бы случае выдать результат. А при каком условии в текущей реализации предлагалось выводить результат?

Надо будет мне опять почитать этот код…

[kotenok gav]

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

А при каком условии в текущей реализации предлагалось выводить результат?

Если текущая точка совпадает с начальной.