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

[arseniiv]

Начальной первой границы или текущей?

[kotenok gav]

Текущей.

[arseniiv]

А чтобы дойти до сравнения «текущая = начальная», надо попасть в неё, а вдруг она отмечена как пройденная и не считается доступной? Вроде на тот случай исключение и кидалось?

[kotenok gav]

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

а вдруг она отмечена как пройденная и не считается доступной?

Нет, такого нет. Пройденные - это только для выбора точки для новой границы.

[kotenok gav]

Вот еще пример, кстати:

Ломается снова на четвертом шаге, оно начинает с точки, окруженной пикселями (почему-то не срабатывает проверка на это!) и, очевидно, ломается.
Выводит "M 54 42 L 54 43 L 53 43 L 53 44 L 52 44 L 52 45 L 51 45 L 51 46 L 50 46 L 50 47 L 49 47 L 49 48 L 49 49 L 48 49 L 48 50 L 48 51 L 47 51 L 47 52 L 47 53 L 46 53 L 46 54 L 46 55 L 45 55 L 45 56 L 45 57 L 44 57 L 44 58 L 44 59 L 44 60 L 43 60 L 43 61 L 43 62 L 42 62 L 42 63 L 42 64 L 41 64 L 41 65 L 40 65 L 40 66 L 39 66 L 39 67 L 38 67 L 38 68 L 37 68 L 37 69 L 36 69 L 36 70 L 35 70 L 34 70 L 34 71 L 33 71 L 33 72 L 32 72 L 31 72 L 30 72 L 29 72 L 29 73 L 28 73 L 27 73 L 27 72 L 26 72 L 25 72 L 24 72 L 24 71 L 23 71 L 22 71 L 21 71 L 20 71 L 19 71 L 19 72 L 18 72 L 18 73 L 18 74 L 18 75 L 18 76 L 19 76 L 19 77 L 20 77 L 20 78 L 21 78 L 21 79 L 22 79 L 22 80 L 23 80 L 24 80 L 25 80 L 26 80 L 27 80 L 28 80 L 29 80 L 30 80 L 31 80 L 32 80 L 32 79 L 33 79 L 34 79 L 34 78 L 35 78 L 36 78 L 36 77 L 37 77 L 37 76 L 38 76 L 39 76 L 39 75 L 40 75 L 40 74 L 41 74 L 41 73 L 42 73 L 42 72 L 43 72 L 43 71 L 44 71 L 44 70 L 45 70 L 45 69 L 46 69 L 46 68 L 47 68 L 47 67 L 48 67 L 48 66 L 48 65 L 49 65 L 49 64 L 50 64 L 51 64 L 51 63 L 51 62 L 51 61 L 51 60 L 51 59 L 51 58 L 51 57 L 52 57 L 52 56 L 52 55 L 52 54 L 52 53 L 52 52 L 52 51 L 53 51 L 53 50 L 53 49 L 53 48 L 53 47 L 54 47 L 54 46 L 54 45 L 54 44 L 55 44 L 55 43 L 56 43 L 56 42 L 55 42 z M 53 46 L 53 47 L 52 47 L 52 46 z M 45 67 L 45 68 L 45 69 L 44 69 L 44 70 L 43 70 L 43 71 L 42 71 L 42 72 L 41 72 L 41 73 L 40 73 L 40 74 L 39 74 L 38 74 L 38 75 L 37 75 L 36 75 L 36 76 L 35 76 L 35 77 L 34 77 L 33 77 L 33 78 L 32 78 L 31 78 L 31 79 L 30 79 L 29 79 L 28 79 L 27 79 L 26 79 L 25 79 L 24 79 L 23 79 L 23 78 L 22 78 L 22 77 L 21 77 L 21 76 L 20 76 L 20 75 L 19 75 L 19 74 L 19 73 L 19 72 L 20 72 L 21 72 L 22 72 L 23 72 L 23 73 L 24 73 L 25 73 L 26 73 L 26 74 L 27 74 L 28 74 L 29 74 L 30 74 L 30 73 L 31 73 L 32 73 L 33 73 L 33 72 L 34 72 L 35 72 L 35 71 L 36 71 L 36 70 L 37 70 L 37 69 L 38 69 L 38 68 L 39 68 L 39 67 L 40 67 L 40 66 L 41 66 L 41 65 L 42 65 L 42 64 L 43 64 L 43 63 L 44 63 L 44 62 L 44 61 L 44 60 L 45 60 L 45 59 L 45 58 L 46 58 L 46 57 L 46 56 L 47 56 L 47 55 L 47 54 L 48 54 L 48 53 L 48 52 L 49 52 L 49 51 L 49 50 L 50 50 L 50 49 L 50 48 L 51 48 L 51 47 L 52 47 L 52 48 L 52 49 L 52 50 L 52 51 L 51 51 L 51 52 L 51 53 L 51 54 L 51 55 L 51 56 L 50 56 L 50 57 L 50 58 L 50 59 L 50 60 L 50 61 L 50 62 L 50 63 L 49 63 L 49 62 L 49 61 L 48 61 L 48 62 L 48 63 L 48 64 L 47 64 L 47 65 L 47 66 L 46 66 L 46 67 z".
В итоге должно получиться что-то типа https://jsfiddle.net/qnupfm2t/ (не точно, можете это рассматривать как то, что именно должен закрашивать фигуру SVG).

-- 08 май 2020, 22:44 --

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

оно начинает с точки, окруженной пикселями (почему-то не срабатывает проверка на это!) и, очевидно, ломается.

Нет, все же не окруженной. Меня спутало из-за

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

И оно немного неверные границы выдает:
kotenok gav в сообщении #1458931

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

.

[arseniiv]

Да, центры пикселей живут в отдельном мире от их (квадратов) вершин. Но я же это вроде говорил. Я боюсь, нельзя сделать удовлетворительный алгоритм, пользуясь (только) центрами пикселей.

[kotenok gav]

Я понял, почему оно ломается! Моя программа проверяет, не окружен ли пиксель другими пикселями, а вовсе не точка.

-- 08 май 2020, 23:13 --

Итак, теперь оно не ломается и успешно выводит "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 M 142 31 z M 141 36 z M 142 33 z M 121 38 z M 142 32 z". Ща кину исправленный код.

-- 08 май 2020, 23:14 --

Используется синтаксис 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
borders = []
SVG = ''
while (notVisited != []):
    pixel = notVisited[0]
    cLUP = (add(pixel, (-1, -1)) in polygonPixels)
    cRUP = (add(pixel, (0, -1)) in polygonPixels)
    cLDP = (add(pixel, (-1, 0)) in polygonPixels)
    cRDP = (add(pixel, (0, 0)) in polygonPixels)
    if (cLUP and cRUP and cLDP and cRDP):
        SVG += ' M ' + str(pixel[0]) + ' ' + str(pixel[1]) + ' z'
        notVisited = list(set(notVisited).difference({pixel}))
        borders.append([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'
        borders.append(border)
print(SVG[1:])
 

-- 08 май 2020, 23:18 --

Итак, оно выводит https://jsfiddle.net/w5zyodes/. Это не совсем то.

[arseniiv]

Подозреваю, что оно должно быть залито внутри? (Но это не стыкуется с разговором про лесенку…) Если так, можно просто не искать внутренние границы, ограничившись внешней. Тогда внутри всё будет залито.

[kotenok gav]

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

Подозреваю, что оно должно быть залито внутри?

Ну, это да, я ведь говорю:

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

В итоге должно получиться что-то типа https://jsfiddle.net/qnupfm2t/ (не точно, можете это рассматривать как то, что именно должен закрашивать фигуру SVG).

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

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

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

-- 09 май 2020, 01:42 --

Хм, изменил. Одноточковые пути не отображаются....

[kotenok gav]

Вот что делать с такими одноточковыми путями?

[arseniiv]

Не создавать их. Я думал, с ними всё стало хорошо, и честно говоря я не понимаю как у них выходит создаваться вообще.

[kotenok gav]

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

[arseniiv]

Я окончательно запутался. Как в точности должна соотноситься исходная растровая картинка и результирующая векторная?

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

-- Вс май 10, 2020 23:37:17 --

Может, найдётся небольшой пример пикселей эдак 10×10 с обводкой всех интересующих областей и той проблемой не входящих во внешнюю границу пикселей? (Или не примыкающих к ней? Граница-то шла по сетке, разделяющей внутренности пикселей.)

[kotenok gav]

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

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

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

[arseniiv]

Я подожду примера, а то всё-таки так и не понял.