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

[arseniiv]

Правда это может быть немного несовместимым с описанным алгоритмом построения границ, потому что теперь один пиксель уровня 3 воспринимается как остров (в принципе и должен был), но старый алгоритм выдаст не одну внутреннюю границу, внутри которой он будет сидеть, а две, с какой точки зрения он должен был бы иметь уровень 1. Тут можно или границы считать чуть иначе, не ходя по диагонали, или при определении уровней считать соседние по диагонали чёрные пиксели соседними (но соседние по диагонали белые соседними не считать! — и потому я бы оставил определение уровней исходным).

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

И как их теперь преобразовать в path?

Да просто по-старинке можно, как я писал двумя постами выше. А можно конечно по-новому, но мне лень продумывать в деталях. Главное тут, что отрезок границы будет ровно там, где соседствуют пиксели с разными уровнями, и ориентация этого отрезка будет зависеть от того, с какой стороны чётный; ещё определяя уровни, мы можем сразу выделить отрезки везде, где нужно, и остаётся только проблема объединения отрезков в ломаные. Тут довольно просто, каждую ломаную можно сразу и хранить как список вершин в порядке обхода, и при появлении каждого нового отрезка просто проверять, совпадает ли его начало или конец с началом или концом какой-то из имеющихся ломаных. Тогда есть несколько случаев:

• Только конец/начало совпадает с началом/концом одной ломаной ⟹ делаем эту ломаную длиннее, прибавив начало/конец нашего отрезка с соответствующей стороны.

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

• Конец совпадает с началом ломаной, и начало совпадает с концом той же самой ломаной ⟹ мы нашли замкнутую границу, можем выписать эту ломаную куда-то в другое место и здесь больше о ней не думать. (На этом же шаге мы можем отказаться выписывать эту ломаную, если она соседствует с уровнями 0 и 1, но лучше бы держать алгоритм универсальным, чтобы он выдавал ломаные с разделяемыми ими уровнями, а уже другая часть кода фильтровала ненужные границы.)

• Конец совпадает с концом какой-то или начало совпадает с началом какой-то ⟹ ошибка где-то в другой части алгоритма, но не фатальная, и можно это игнорировать, особенно если мы не будем сильно следить за тем, чтобы не находить отрезки иногда больше одного раза, см. прямо ниже.

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

-- Вс май 17, 2020 22:25:01 --

Что меня радует, так это то, что эти алгоритмы почти в таком виде переносятся на произвольные разбиения плоскости на многоугольники, а то и может быть пространства другой размерности, ну и вообще на клеточные комплексы.

[kotenok gav]

Ок, постараюсь завтра реализовать...

[kotenok gav]

Кстати, а что делать, если у нескольких ломаных конец совпадает с началом отрезка?

[arseniiv]

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

[kotenok gav]

Вот код:

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

from PIL import Image, ImageDraw
def add(vector1, vector2):
    return (vector1[0] + vector2[0], vector1[1] + vector2[1])
def substract(vector1, vector2):
    return (vector1[0] - vector2[0], vector1[1] - vector2[1])
def sortByX(pixel):
    return pixel[0]
def sortByY(pixel):
    return pixel[1]
def neighbours(pixel):
    return list(map(lambda x: add(pixel, x), [(0,1), (1, 0), (0, -1), (-1, 0)]))
def cyclicMap(function, iterable):
    iterableList = []
    for i in iterable:
        iterableList.append(i)
    mapList = []
    for i in range(len(iterableList) - 1):
        mapList.append(function(iterableList[i], iterableList[i + 1]))
    mapList.append(function(iterableList[-1], iterableList[0]))
    return mapList
def neighbourLines(pixel):
    lines = cyclicMap(lambda x, y: [add(pixel, x), add(pixel, y)],
                      [(0, 0), (1, 0), (1, -1), (0, -1)])
    for i in range(3, -1, -1):
        if levelByPixel[add(pixel, {0: (0, -1), 1: (1, 0), 2: (0, 1),
                                    3: (-1, 0)}[i])] == levelByPixel[pixel]:
            del lines[i]
    return lines
def neighbourPixels(line):
    gradient = substract(line[1], line[0])
    return list(map(lambda x: add(line[0], x), {(1, 0): [(0, -1), (0, 0)],
                                                (-1, 0): [(-1, -1), (-1, 0)],
                                                (0, 1): [(-1, 0), (0, 0)],
                                                (0, -1):
                                                [(-1, -1), (0, -1)]}[gradient]))
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 = ''
levelByPixel = {(0, 0): 0, (width - 1, 0): 0, (0, height - 1): 0, (width - 1, height - 1): 0}
polygonPixels.sort(key = sortByX)
levelByPixel[polygonPixels[0]] = 1
levelByPixel[polygonPixels[1]] = 1
polygonPixels.sort(key = sortByY)
levelByPixel[polygonPixels[0]] = 1
levelByPixel[polygonPixels[1]] = 1
levelNotSetted = [pixel for pixel in [(i, j) for i in range(width) for j in
                                      range(height)] if not pixel in
                  levelByPixel.keys()]
levelSetted = list(levelByPixel.keys())
while levelNotSetted != []:
    error = True
    for pixel in levelSetted:
        for pix in neighbours(pixel):
            if ((pix in levelNotSetted) and
                (pixels[pixel[0], pixel[1]][0:3]
                 == pixels[pix[0], pix[1]][0:3])):
                error = False
                levelNotSetted.remove(pix)
                levelSetted.append(pix)
                levelByPixel[pix] = levelByPixel[pixel]
    if error:
        for level in range(max(levelByPixel.values()) + 1):
            for pixel in levelSetted:
                if levelByPixel[pixel] == level:
                    for pix in neighbours(pixel):
                        if pix in levelNotSetted:
                            levelNotSetted.remove(pix)
                            levelSetted.append(pix)
                            levelByPixel[pix] = level + 1
for y in range(height):
    s = ''
    for x in range(width):
        if (x, y) in levelSetted:
            s += str(levelByPixel[(x, y)])
        else:
            s += '.'
    print(s)
openPaths = []
closedPaths = []
for x in range(1, width - 1):
    for y in range(1, height - 1):
        for line in neighbourLines((x, y)):
            begin = line[0]
            end = line[1]
            neighboursPixelsToLine = neighbourPixels([begin, end])
            if (levelByPixel[neighboursPixelsToLine[0]] ==
                levelByPixel[neighboursPixelsToLine[1]]):
                continue
            paths1 = [] #paths, such that path[1] of them is begin
            paths2 = [] #paths, such that path[0] of them is end
            for path in openPaths:
                if path[1] == begin:
                    paths1.append(path)
                elif path[0] == end:
                    paths2.append(path)
            if (len(paths1) == 0) and (len(paths2) == 0):
                openPaths.append(line)
            elif len(paths1) > 0:
                paths = []
                for path in paths1:
                    neighboursPixelsToPath = neighbourPixels([path[0], path[1]])
                    if ((levelByPixel[neighboursPixelsToLine[0]] ==
                        levelByPixel[neighboursPixelsToPath[0]]) and
                    (levelByPixel[neighboursPixelsToLine[1]] ==
                        levelByPixel[neighboursPixelsToPath[1]])):
                        paths.append(path)
                if (len(paths) == 0):
                    openPaths.append(line)
                else:
                    path = paths[0]
                    openPaths.remove(path)
                    if path[0] == end:
                        closedPaths.append(path)
                    else:
                        if len(paths2) > 0:
                            paths = []
                            for path2 in paths2:
                                neighboursPixelsToLine =\
                                neighbourPixels([path2[0], path2[1]])
                                if (levelByPixel[neighboursPixelsToLine[0]] ==
                                    levelByPixel[neighboursPixelsToLine[1]]):
                                    paths.append(path2)
                            if len(paths) == 0:
                                path.append(end)
                            else:
                                path = path + paths[0]
                        openPaths.append(path)
            elif len(paths2) > 0:
                paths = []
                for path in paths2:
                    neighboursPixelsToLine = neighbourPixels([path[0], path[1]])
                    if (levelByPixel[neighboursPixelsToLine[0]] ==
                        levelByPixel[neighboursPixelsToLine[1]]):
                        paths.append(path)
                if (len(paths) == 0):
                    openPaths.append(line)
                else:
                    path = paths[0]
                    openPaths.remove(path)
                    if path[1] == begin:
                        closedPaths.append(path)
                    else:
                        if len(paths1) > 0:
                            paths = []
                            for path1 in paths1:
                                neighboursPixelsToLine =\
                                neighbourPixels([path1[0], path1[1]])
                                if (levelByPixel[neighboursPixelsToLine[0]] ==
                                    levelByPixel[neighboursPixelsToLine[1]]):
                                    paths.append(path1)
                            if len(paths) == 0:
                                path = [begin] + path
                            else:
                                path = paths[0] + path
                        openPaths.append(path)
print(openPaths, closedPaths)
 

Выводит [[(117, 35), (118, 35)], [(117, 36), (118, 36)], [(118, 34), (118, 35)], [(119, 35), (118, 35)], [(118, 36), (119, 36)], [(118, 37), (119, 37)], [(120, 35), (121, 35), (121, 34)], [(120, 36), (121, 36)], [(120, 39), (121, 39)], [(121, 34), (121, 35)], [(121, 36), (122, 36)], [(122, 35), (121, 35)], [(122, 28), (123, 28)], [(121, 37), (122, 37)], [(123, 37), (122, 37)], [(121, 40), (122, 40)], [(122, 39), (123, 39)], [(124, 26), (125, 26)], [(123, 27), (124, 27)], [(123, 40), (124, 40)], [(125, 25), (125, 26)], [(124, 39), (125, 39)], [(125, 25), (126, 25)], [(125, 26), (126, 26)], [(125, 40), (126, 40)], [(126, 39), (127, 39)], [(128, 39), (127, 39)], [(127, 25), (128, 25)], [(127, 41), (128, 41)], [(128, 24), (129, 24)], [(128, 40), (129, 40)], [(129, 25), (130, 25)], [(130, 40), (131, 40)], [(129, 41), (130, 41)], [(130, 24), (131, 24)], [(131, 41), (132, 41)], [(131, 25), (132, 25)], [(132, 39), (133, 39)], [(132, 24), (133, 24)], [(133, 25), (134, 25)], [(132, 40), (133, 40)], [(134, 26), (135, 26)], [(134, 34), (135, 34)], [(134, 35), (135, 35)], [(134, 38), (135, 38)], [(134, 39), (135, 39)], [(135, 25), (136, 25)], [(137, 25), (136, 25)], [(136, 27), (137, 27)], [(136, 35), (137, 35)], [(137, 28), (138, 28)], [(136, 34), (137, 34)], [(138, 34), (137, 34)], [(136, 38), (137, 38)], [(136, 39), (137, 39)], [(138, 27), (139, 27)], [(138, 30), (139, 30)], [(138, 38), (139, 38)], [(138, 35), (139, 35)], [(139, 36), (140, 36)], [(140, 35), (139, 35)], [(138, 39), (139, 39)], [(139, 31), (140, 31)], [(140, 32), (141, 32)], [(141, 31), (140, 31)], [(140, 35), (141, 35)], [(140, 38), (141, 38)], [(141, 37), (142, 37)], [(141, 30), (142, 30)]] и [[(118, 34), (119, 34)], [(118, 36), (118, 35)], [(119, 34), (120, 34)], [(119, 35), (120, 35)], [(120, 30), (120, 29)], [(120, 31), (120, 30)], [(120, 32), (120, 31)], [(120, 33), (120, 32)], [(120, 38), (120, 37)], [(121, 29), (121, 28)], [(121, 30), (121, 29)], [(121, 31), (121, 30)], [(121, 32), (121, 31)], [(121, 33), (121, 32)], [(121, 34), (121, 33)], [(121, 36), (121, 35)], [(122, 28), (122, 27)], [(122, 38), (123, 38)], [(123, 27), (123, 26)], [(123, 37), (124, 37)], [(123, 38), (124, 38)], [(127, 25), (127, 24)], [(131, 39), (132, 39)], [(133, 38), (134, 38)], [(134, 24), (135, 24)], [(137, 26), (138, 26)], [(137, 36), (138, 36)], [(138, 29), (138, 28)], [(138, 36), (139, 36)], [(139, 28), (139, 27)], [(139, 29), (140, 29)], [(139, 37), (140, 37)], [(140, 30), (141, 30)], [(140, 33), (141, 33)], [(141, 34), (141, 33)], [(142, 35), (142, 34)], [(142, 36), (142, 35)], [(143, 31), (143, 30)], [(143, 32), (143, 31)], [(143, 33), (143, 32)]]. Что-то это совсем не похоже на правду...

[arseniiv]

Да, странно, отрезки не соединяются друг с другом вовремя. Надо бы последить, когда соседний отрезок с каким-то из них определяется, почему он не приклеивается, если подходит. Может, ориентация неправильно определяется или что-то такое?

[kotenok gav]

Больше всего меня удивляет, почему он относит незамкнутые пути в множество замкнутых...

[arseniiv]

Видимо мне придётся самому попробовать уже наконец написать велосипед (но я буду без PIL, просто буду загружать картинку, нарисованную символами строки, и выдавать в консоль результат обводки). Через какое-то время…

[kotenok gav]

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

-- 29 май 2020, 00:50 --

Хотя не, лучше проверка, обрабатывали ли мы уже эту линию.

[arseniiv]

Я тут ещё понял, что можно алгоритм куда проще придумать: представим, что картинка изначально пустая. Добавим туда один пиксель — и заодно добавим границу вокруг него. Добавим другой — снова с границей, притом если он соседствует с первым, мы противонаправленные части границ удалим и сольём оставшиеся куски. И так можно надобавлять все закрашенные пиксели картинки в любом порядке. Правда так мы получим только границы, но не уровни. Просто интересно — до простых алгоритмов доходишь часто ой не сразу…

Можно попробовать такие границы считать «полуграницами» и добавлять также и белые пиксели, тоже с полуграницами, ориентированными наоборот. Тогда при встрече белого с чёрным между ними появится кусок обычной одинарной границы, и возможно тогда же можно будет произвести какие-то вычисления с подгонкой уровней… хм…

Зашли бы сюда знающие вычислительные геометры и наставили бы мои советы на путь истинный.

-- Чт май 28, 2020 20:26:02 --

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

Хотя не, лучше проверка, обрабатывали ли мы уже эту линию.

Да, или так, или изначально не создавать отрезок со стороны соседа того же цвета.

[kotenok gav]

Код:

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

(вырезано из-за лимита символов)
 

Теперь [[(118, 35), (117, 35)], [(118, 34), (118, 35)], [(118, 36), (117, 36)], [(118, 35), (118, 36)], [(119, 34), (118, 34)], [(119, 35), (118, 35)], [(119, 36), (118, 36)], [(119, 37), (118, 37)], [(120, 29), (120, 30)], [(120, 31), (120, 32)], [(120, 34), (119, 34)], [(120, 35), (119, 35)], [(120, 36), (119, 36)], [(120, 37), (119, 37)], [(120, 37), (120, 38)], [(121, 29), (120, 29)], [(121, 28), (121, 29)], [(121, 29), (121, 30)], [(121, 31), (121, 32)], [(121, 35), (120, 35)], [(121, 36), (120, 36)], [(121, 35), (121, 36)], [(121, 39), (120, 39)], [(122, 28), (121, 28)], [(122, 27), (122, 28)], [(122, 29), (121, 29)], [(122, 35), (121, 35)], [(122, 36), (121, 36)], [(122, 37), (121, 37)], [(122, 40), (121, 40)], [(123, 27), (122, 27)], [(123, 26), (123, 27)], [(123, 28), (122, 28)], [(123, 37), (122, 37)], [(123, 38), (122, 38)], [(123, 39), (122, 39)], [(123, 40), (122, 40)], [(124, 26), (123, 26)], [(124, 27), (123, 27)], [(124, 37), (123, 37)], [(124, 38), (123, 38)], [(124, 39), (123, 39)], [(124, 40), (123, 40)], [(125, 26), (124, 26)], [(125, 25), (125, 26)], [(125, 27), (124, 27)], [(125, 39), (124, 39)], [(125, 40), (124, 40)], [(126, 25), (125, 25)], [(126, 26), (125, 26)], [(126, 39), (125, 39)], [(126, 40), (125, 40)], [(127, 25), (126, 25)], [(127, 24), (127, 25)], [(127, 26), (126, 26)], [(127, 39), (126, 39)], [(127, 40), (126, 40)], [(128, 24), (127, 24)], [(128, 25), (127, 25)], [(128, 39), (127, 39)], [(128, 41), (127, 41)], [(129, 24), (128, 24)], [(129, 25), (128, 25)], [(129, 40), (128, 40)], [(129, 41), (128, 41)], [(130, 24), (129, 24)], [(130, 25), (129, 25)], [(130, 40), (129, 40)], [(130, 41), (129, 41)], [(131, 24), (130, 24)], [(131, 25), (130, 25)], [(131, 40), (130, 40)], [(131, 41), (130, 41)], [(132, 24), (131, 24)], [(132, 25), (131, 25)], [(132, 39), (131, 39)], [(132, 41), (131, 41)], [(133, 24), (132, 24)], [(133, 25), (132, 25)], [(133, 39), (132, 39)], [(133, 40), (132, 40)], [(134, 24), (133, 24)], [(134, 25), (133, 25)], [(134, 38), (133, 38)], [(134, 40), (133, 40)], [(135, 24), (134, 24)], [(135, 26), (134, 26)], [(135, 34), (134, 34)], [(135, 35), (134, 35)], [(135, 38), (134, 38)], [(135, 39), (134, 39)], [(136, 25), (135, 25)], [(136, 26), (135, 26)], [(136, 34), (135, 34)], [(136, 35), (135, 35)], [(136, 38), (135, 38)], [(136, 39), (135, 39)], [(137, 25), (136, 25)], [(137, 27), (136, 27)], [(137, 34), (136, 34)], [(137, 35), (136, 35)], [(137, 38), (136, 38)], [(137, 39), (136, 39)], [(138, 26), (137, 26)], [(138, 28), (137, 28)], [(138, 28), (138, 29)], [(138, 34), (137, 34)], [(138, 36), (137, 36)], [(138, 38), (137, 38)], [(138, 39), (137, 39)], [(139, 27), (138, 27)], [(139, 27), (139, 28)], [(139, 30), (138, 30)], [(139, 35), (138, 35)], [(139, 36), (138, 36)], [(139, 38), (138, 38)], [(139, 39), (138, 39)], [(140, 29), (139, 29)], [(140, 31), (139, 31)], [(140, 35), (139, 35)], [(140, 36), (139, 36)], [(140, 37), (139, 37)], [(140, 39), (139, 39)], [(141, 30), (140, 30)], [(141, 31), (140, 31)], [(141, 32), (140, 32)], [(141, 33), (140, 33)], [(141, 33), (141, 34)], [(141, 35), (140, 35)], [(141, 38), (140, 38)], [(142, 30), (141, 30)], [(142, 34), (142, 35)], [(142, 37), (141, 37)], [(143, 30), (142, 30)], [(143, 30), (143, 31)], [(143, 32), (143, 33)], [(143, 34), (142, 34)]] и [[(121, 33), (121, 34), (121, 35)]] (хотя эта граница все равно, очевидно, незамкнутая...).

-- 29 май 2020, 00:59 --

А, я нашел баг. Самое обидное, что я его починил, но не заметил еще в трех местах его же...

-- 29 май 2020, 01:04 --

Код:

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

from PIL import Image, ImageDraw
def add(vector1, vector2):
    return (vector1[0] + vector2[0], vector1[1] + vector2[1])
def substract(vector1, vector2):
    return (vector1[0] - vector2[0], vector1[1] - vector2[1])
def sortByX(pixel):
    return pixel[0]
def sortByY(pixel):
    return pixel[1]
def neighbours(pixel):
    return list(map(lambda x: add(pixel, x), [(0,1), (1, 0), (0, -1), (-1, 0)]))
def cyclicMap(function, iterable):
    iterableList = []
    for i in iterable:
        iterableList.append(i)
    mapList = []
    for i in range(len(iterableList) - 1):
        mapList.append(function(iterableList[i], iterableList[i + 1]))
    mapList.append(function(iterableList[-1], iterableList[0]))
    return mapList
def neighbourLines(pixel):
    lines = cyclicMap(lambda x, y: [add(pixel, x), add(pixel, y)],
                      [(0, 0), (1, 0), (1, -1), (0, -1)])
    for i in range(3, -1, -1):
        if levelByPixel[add(pixel, {0: (0, -1), 1: (1, 0), 2: (0, 1),
                                    3: (-1, 0)}[i])] == levelByPixel[pixel]:
            del lines[i]
    return lines
def neighbourPixels(line):
    gradient = substract(line[1], line[0])
    return list(map(lambda x: add(line[0], x), {(1, 0): [(0, -1), (0, 0)],
                                                (-1, 0): [(-1, -1), (-1, 0)],
                                                (0, 1): [(-1, 0), (0, 0)],
                                                (0, -1):
                                                [(-1, -1), (0, -1)]}[gradient]))
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 = ''
levelByPixel = {(0, 0): 0, (width - 1, 0): 0, (0, height - 1): 0, (width - 1, height - 1): 0}
polygonPixels.sort(key = sortByX)
levelByPixel[polygonPixels[0]] = 1
levelByPixel[polygonPixels[1]] = 1
polygonPixels.sort(key = sortByY)
levelByPixel[polygonPixels[0]] = 1
levelByPixel[polygonPixels[1]] = 1
levelNotSetted = [pixel for pixel in [(i, j) for i in range(width) for j in
                                      range(height)] if not pixel in
                  levelByPixel.keys()]
levelSetted = list(levelByPixel.keys())
while levelNotSetted != []:
    error = True
    for pixel in levelSetted:
        for pix in neighbours(pixel):
            if ((pix in levelNotSetted) and
                (pixels[pixel[0], pixel[1]][0:3]
                 == pixels[pix[0], pix[1]][0:3])):
                error = False
                levelNotSetted.remove(pix)
                levelSetted.append(pix)
                levelByPixel[pix] = levelByPixel[pixel]
    if error:
        for level in range(max(levelByPixel.values()) + 1):
            for pixel in levelSetted:
                if levelByPixel[pixel] == level:
                    for pix in neighbours(pixel):
                        if pix in levelNotSetted:
                            levelNotSetted.remove(pix)
                            levelSetted.append(pix)
                            levelByPixel[pix] = level + 1
for y in range(height):
    s = ''
    for x in range(width):
        if (x, y) in levelSetted:
            s += str(levelByPixel[(x, y)])
        else:
            s += '.'
    print(s)
openPaths = []
closedPaths = []
checkedLines = []
for x in range(1, width - 1):
    for y in range(1, height - 1):
        for line in neighbourLines((x, y)):
            if line in checkedLines:
                continue
            line2 = line
            line2.reverse()
            if line2 in checkedLines:
                continue
            begin = line[0]
            end = line[1]
            neighboursPixelsToLine = neighbourPixels([begin, end])
            if (levelByPixel[neighboursPixelsToLine[0]] ==
                levelByPixel[neighboursPixelsToLine[1]]):
                continue
            paths1 = [] #paths, such that path[1] of them is begin
            paths2 = [] #paths, such that path[0] of them is end
            for path in openPaths:
                if path[1] == begin:
                    paths1.append(path)
                elif path[0] == end:
                    paths2.append(path)
            if (len(paths1) == 0) and (len(paths2) == 0):
                openPaths.append(line)
            elif len(paths1) > 0:
                paths = []
                for path in paths1:
                    neighboursPixelsToPath = neighbourPixels([path[0], path[1]])
                    if ((levelByPixel[neighboursPixelsToLine[0]] ==
                        levelByPixel[neighboursPixelsToPath[0]]) and
                    (levelByPixel[neighboursPixelsToLine[1]] ==
                        levelByPixel[neighboursPixelsToPath[1]])):
                        paths.append(path)
                if (len(paths) == 0):
                    openPaths.append(line)
                else:
                    path = paths[0]
                    openPaths.remove(path)
                    if path[0] == end:
                        closedPaths.append(path)
                    else:
                        if len(paths2) > 0:
                            paths = []
                            for path2 in paths2:
                                neighboursPixelsToPath =\
                                neighbourPixels([path2[0], path2[1]])
                                if ((levelByPixel[neighboursPixelsToLine[0]] ==
                                    levelByPixel[neighboursPixelsToPath[0]]) and
                                (levelByPixel[neighboursPixelsToLine[1]] ==
                                    levelByPixel[neighboursPixelsToPath[1]])):
                                    paths.append(path2)
                            if len(paths) == 0:
                                path.append(end)
                            else:
                                path = path + paths[0]
                        openPaths.append(path)
            elif len(paths2) > 0:
                paths = []
                for path in paths2:
                    neighboursPixelsToPath = neighbourPixels([path[0], path[1]])
                    if ((levelByPixel[neighboursPixelsToLine[0]] ==
                        levelByPixel[neighboursPixelsToPath[0]]) and
                    (levelByPixel[neighboursPixelsToLine[1]] ==
                        levelByPixel[neighboursPixelsToPath[1]])):
                        paths.append(path)
                if (len(paths) == 0):
                    openPaths.append(line)
                else:
                    path = paths[0]
                    openPaths.remove(path)
                    if path[1] == begin:
                        closedPaths.append(path)
                    else:
                        if len(paths1) > 0:
                            paths = []
                            for path1 in paths1:
                                neighboursPixelsToPath =\
                                neighbourPixels([path1[0], path1[1]])
                                if ((levelByPixel[neighboursPixelsToLine[0]] ==
                                    levelByPixel[neighboursPixelsToPath[0]]) and
                                (levelByPixel[neighboursPixelsToLine[1]] ==
                                    levelByPixel[neighboursPixelsToPath[1]])):
                                    paths.append(path1)
                            if len(paths) == 0:
                                path = [begin] + path
                            else:
                                path = paths[0] + path
                        openPaths.append(path)
            checkedLines.append(line)
print(openPaths, closedPaths)
 

[[(118, 35), (117, 35)], [(118, 36), (117, 36)], [(118, 35), (118, 36)], [(120, 31), (120, 32)], [(119, 34), (118, 34)], [(119, 36), (118, 36)], [(119, 37), (118, 37)], [(120, 37), (120, 38)], [(120, 29), (120, 30)], [(121, 31), (121, 32)], [(120, 35), (119, 35)], [(121, 33), (121, 34)], [(121, 36), (120, 36)], [(121, 39), (120, 39)], [(121, 28), (121, 29)], [(121, 29), (121, 30)], [(121, 35), (121, 36)], [(122, 36), (121, 36)], [(122, 27), (122, 28)], [(123, 28), (122, 28)], [(122, 37), (121, 37)], [(122, 40), (121, 40)], [(123, 26), (123, 27)], [(124, 37), (123, 37)], [(123, 38), (122, 38)], [(123, 39), (122, 39)], [(125, 26), (124, 26)], [(124, 27), (123, 27)], [(124, 40), (123, 40)], [(125, 39), (124, 39)], [(126, 25), (125, 25)], [(126, 26), (125, 26)], [(126, 40), (125, 40)], [(127, 24), (127, 25)], [(127, 39), (126, 39)], [(128, 25), (127, 25)], [(128, 41), (127, 41)], [(129, 24), (128, 24)], [(129, 40), (128, 40)], [(130, 25), (129, 25)], [(131, 40), (130, 40)], [(130, 41), (129, 41)], [(131, 24), (130, 24)], [(132, 41), (131, 41)], [(132, 25), (131, 25)], [(132, 39), (131, 39)], [(133, 24), (132, 24)], [(134, 25), (133, 25)], [(133, 40), (132, 40)], [(135, 24), (134, 24)], [(134, 38), (133, 38)], [(135, 26), (134, 26)], [(135, 34), (134, 34)], [(135, 35), (134, 35)], [(135, 39), (134, 39)], [(136, 25), (135, 25)], [(137, 27), (136, 27)], [(137, 35), (136, 35)], [(136, 38), (135, 38)], [(138, 26), (137, 26)], [(138, 28), (137, 28)], [(138, 28), (138, 29)], [(137, 34), (136, 34)], [(137, 39), (136, 39)], [(139, 27), (138, 27)], [(139, 27), (139, 28)], [(139, 30), (138, 30)], [(138, 36), (137, 36)], [(138, 38), (137, 38)], [(140, 29), (139, 29)], [(139, 35), (138, 35)], [(140, 36), (139, 36)], [(140, 37), (139, 37)], [(139, 39), (138, 39)], [(140, 31), (139, 31)], [(141, 32), (140, 32)], [(141, 33), (140, 33)], [(141, 33), (141, 34)], [(141, 35), (140, 35)], [(141, 38), (140, 38)], [(141, 30), (140, 30)], [(142, 37), (141, 37)], [(143, 30), (142, 30)], [(143, 30), (143, 31)], [(143, 32), (143, 33)], [(142, 34), (142, 35)]] и [], все равно не так...

-- 29 май 2020, 01:49 --

Хм, вот вижу, что, скажем, есть линия [(123, 39), (122, 39)], затем линия [(124, 39), (123, 39)] почему-то не добавляется, затем линия [(125, 39), (124, 39)] добавляется отдельно.

[kotenok gav]

Нашел ошибку, код теперь такой:

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

from PIL import Image, ImageDraw
def add(vector1, vector2):
    return (vector1[0] + vector2[0], vector1[1] + vector2[1])
def substract(vector1, vector2):
    return (vector1[0] - vector2[0], vector1[1] - vector2[1])
def sortByX(pixel):
    return pixel[0]
def sortByY(pixel):
    return pixel[1]
def neighbours(pixel):
    return list(map(lambda x: add(pixel, x), [(0,1), (1, 0), (0, -1), (-1, 0)]))
def cyclicMap(function, iterable):
    iterableList = []
    for i in iterable:
        iterableList.append(i)
    mapList = []
    for i in range(len(iterableList) - 1):
        mapList.append(function(iterableList[i], iterableList[i + 1]))
    mapList.append(function(iterableList[-1], iterableList[0]))
    return mapList
def neighbourLines(pixel):
    lines = cyclicMap(lambda x, y: [add(pixel, x), add(pixel, y)],
                      [(0, 0), (1, 0), (1, -1), (0, -1)])
    for i in range(3, -1, -1):
        if levelByPixel[add(pixel, {0: (0, -1), 1: (1, 0), 2: (0, 1),
                                    3: (-1, 0)}[i])] == levelByPixel[pixel]:
            del lines[i]
    return lines
def neighbourPixels(line):
    gradient = substract(line[1], line[0])
    return list(map(lambda x: add(line[0], x), {(1, 0): [(0, -1), (0, 0)],
                                                (-1, 0): [(-1, -1), (-1, 0)],
                                                (0, 1): [(-1, 0), (0, 0)],
                                                (0, -1):
                                                [(-1, -1), (0, -1)]}[gradient]))
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 = ''
levelByPixel = {(0, 0): 0, (width - 1, 0): 0, (0, height - 1): 0, (width - 1, height - 1): 0}
polygonPixels.sort(key = sortByX)
levelByPixel[polygonPixels[0]] = 1
levelByPixel[polygonPixels[1]] = 1
polygonPixels.sort(key = sortByY)
levelByPixel[polygonPixels[0]] = 1
levelByPixel[polygonPixels[1]] = 1
levelNotSetted = [pixel for pixel in [(i, j) for i in range(width) for j in
                                      range(height)] if not pixel in
                  levelByPixel.keys()]
levelSetted = list(levelByPixel.keys())
while levelNotSetted != []:
    error = True
    for pixel in levelSetted:
        for pix in neighbours(pixel):
            if ((pix in levelNotSetted) and
                (pixels[pixel[0], pixel[1]][0:3]
                 == pixels[pix[0], pix[1]][0:3])):
                error = False
                levelNotSetted.remove(pix)
                levelSetted.append(pix)
                levelByPixel[pix] = levelByPixel[pixel]
    if error:
        for level in range(max(levelByPixel.values()) + 1):
            for pixel in levelSetted:
                if levelByPixel[pixel] == level:
                    for pix in neighbours(pixel):
                        if pix in levelNotSetted:
                            levelNotSetted.remove(pix)
                            levelSetted.append(pix)
                            levelByPixel[pix] = level + 1
for y in range(height):
    s = ''
    for x in range(width):
        if (x, y) in levelSetted:
            s += str(levelByPixel[(x, y)])
        else:
            s += '.'
    print(s)
openPaths = []
closedPaths = []
checkedLines = []
for x in range(1, width - 1):
    for y in range(1, height - 1):
        for line in neighbourLines((x, y)):
            if line in checkedLines:
                continue
            line2 = line
            line2.reverse()
            if line2 in checkedLines:
                continue
            begin = line[0]
            end = line[1]
            neighboursPixelsToLine = neighbourPixels([begin, end])
            if (levelByPixel[neighboursPixelsToLine[0]] ==
                levelByPixel[neighboursPixelsToLine[1]]):
                continue
            paths1 = [] #paths, such that path[1] of them is begin
            paths2 = [] #paths, such that path[0] of them is end
            for path in openPaths:
                if path[1] == begin:
                    paths1.append(path)
                elif path[0] == end:
                    paths2.append(path)
            if (len(paths1) == 0) and (len(paths2) == 0):
                openPaths.append(line)
            elif len(paths1) > 0:
                paths = []
                for path in paths1:
                    neighboursPixelsToPath = neighbourPixels([path[0], path[1]])
                    if ((levelByPixel[neighboursPixelsToLine[0]] ==
                        levelByPixel[neighboursPixelsToPath[0]]) and
                    (levelByPixel[neighboursPixelsToLine[1]] ==
                        levelByPixel[neighboursPixelsToPath[1]])):
                        paths.append(path)
                if (len(paths) == 0):
                    openPaths.append(line)
                else:
                    path = paths[0]
                    openPaths.remove(path)
                    if path[0] == end:
                        closedPaths.append(path)
                    else:
                        if len(paths2) > 0:
                            paths = []
                            for path2 in paths2:
                                neighboursPixelsToPath =\
                                neighbourPixels([path2[0], path2[1]])
                                if ((levelByPixel[neighboursPixelsToLine[0]] ==
                                    levelByPixel[neighboursPixelsToPath[0]]) and
                                (levelByPixel[neighboursPixelsToLine[1]] ==
                                    levelByPixel[neighboursPixelsToPath[1]])):
                                    paths.append(path2)
                            if len(paths) == 0:
                                path.append(end)
                            else:
                                path = path + paths[0]
                        else:
                            path.append(end)
                            openPaths.append(path)
            elif len(paths2) > 0:
                paths = []
                for path in paths2:
                    neighboursPixelsToPath = neighbourPixels([path[0], path[1]])
                    if ((levelByPixel[neighboursPixelsToLine[0]] ==
                        levelByPixel[neighboursPixelsToPath[0]]) and
                    (levelByPixel[neighboursPixelsToLine[1]] ==
                        levelByPixel[neighboursPixelsToPath[1]])):
                        paths.append(path)
                if (len(paths) == 0):
                    openPaths.append(line)
                else:
                    path = paths[0]
                    openPaths.remove(path)
                    if path[1] == begin:
                        closedPaths.append(path)
                    else:
                        if len(paths1) > 0:
                            paths = []
                            for path1 in paths1:
                                neighboursPixelsToPath =\
                                neighbourPixels([path1[0], path1[1]])
                                if ((levelByPixel[neighboursPixelsToLine[0]] ==
                                    levelByPixel[neighboursPixelsToPath[0]]) and
                                (levelByPixel[neighboursPixelsToLine[1]] ==
                                    levelByPixel[neighboursPixelsToPath[1]])):
                                    paths.append(path1)
                            if len(paths) == 0:
                                path = [begin] + path
                            else:
                                path = paths[0] + path
                        else:
                            path = [begin] + path
                            openPaths.append(path)
            checkedLines.append(line)
print(openPaths, closedPaths)
 

-- 29 май 2020, 02:00 --

Теперь выводит [[(118, 36), (117, 36)], [(120, 34), (119, 34), (118, 34), (118, 35), (117, 35)], [(120, 37), (119, 37), (118, 37)], [(120, 37), (120, 38)], [(120, 30), (120, 29)], [(121, 35), (120, 35), (119, 35), (118, 35), (118, 36)], [(121, 36), (120, 36), (119, 36), (118, 36)], [(121, 39), (120, 39)], [(122, 29), (121, 29), (121, 30), (121, 31)], [(121, 30), (121, 29)], [(122, 35), (121, 35), (121, 36)], [(122, 36), (121, 36)], [(123, 28), (122, 28)], [(124, 37), (123, 37), (122, 37), (121, 37)], [(124, 38), (123, 38), (122, 38)], [(125, 27), (124, 27), (123, 27)], [(127, 26), (126, 26), (125, 26)], [(127, 40), (126, 40), (125, 40), (124, 40), (123, 40), (122, 40), (121, 40)], [(128, 39), (127, 39), (126, 39), (125, 39), (124, 39), (123, 39), (122, 39)], [(131, 40), (130, 40), (129, 40), (128, 40)], [(132, 41), (131, 41), (130, 41), (129, 41), (128, 41), (127, 41)], [(133, 39), (132, 39), (131, 39)], [(134, 25), (133, 25), (132, 25), (131, 25), (130, 25), (129, 25), (128, 25), (127, 25)], [(134, 40), (133, 40), (132, 40)], [(135, 24), (134, 24), (133, 24), (132, 24), (131, 24), (130, 24), (129, 24), (128, 24), (127, 24), (127, 25), (126, 25), (125, 25), (125, 26), (124, 26), (123, 26), (123, 27), (122, 27), (122, 28), (121, 28), (121, 29), (120, 29), (120, 30), (120, 31)], [(136, 26), (135, 26), (134, 26)], [(137, 25), (136, 25), (135, 25)], [(137, 27), (136, 27)], [(137, 35), (136, 35), (135, 35), (134, 35)], [(138, 26), (137, 26)], [(138, 28), (137, 28)], [(138, 28), (138, 29)], [(138, 34), (137, 34), (136, 34), (135, 34), (134, 34)], [(139, 27), (138, 27)], [(139, 27), (139, 28)], [(139, 30), (138, 30)], [(139, 38), (138, 38), (137, 38), (136, 38), (135, 38), (134, 38), (133, 38)], [(140, 29), (139, 29)], [(140, 36), (139, 36), (138, 36), (137, 36)], [(140, 37), (139, 37)], [(140, 39), (139, 39), (138, 39), (137, 39), (136, 39), (135, 39), (134, 39)], [(141, 31), (140, 31), (139, 31)], [(141, 32), (140, 32)], [(141, 33), (140, 33)], [(141, 33), (141, 34)], [(141, 35), (140, 35), (139, 35), (138, 35)], [(141, 38), (140, 38)], [(142, 37), (141, 37)], [(143, 30), (142, 30), (141, 30), (140, 30)], [(143, 32), (143, 33)], [(143, 34), (142, 34), (142, 35), (142, 36)], [(142, 35), (142, 34)]][\tt] и [tt][[(120, 31), (120, 32), (120, 33)], [(121, 31), (121, 32), (121, 33)], [(143, 30), (143, 31), (143, 32)]]. С замкнутыми путями все равно что-то не то... Еще странно [(143, 34), (142, 34), (142, 35), (142, 36)] и [(142, 35), (142, 34)] одновременно.

[kotenok gav]

Я даже не могу понять, как образовывается [(143, 34), (142, 34), (142, 35), (142, 36)], ведь line никогда не является [(143, 34), (142, 34)], но может являться [(142, 34), (143, 34)]...

[arseniiv]

Мой код наконец-то стал находить циклы правильно, осталось обогатить его уровнями или чем-то аналогичным — и выложу. Пока можно полюбоваться на аски-арт: https://hatebin.com/ksmezwqait.

-- Вс май 31, 2020 02:38:06 --

А именно, там сначала показываются все циклы разом для такой картинки:

                    D
    A A A A A A      
  A A           A A  
  A A   B       A A  
    A     C C     A  
    A           A A  
    A A A A A A A    

и потом каждый цикл по отдельности вместе с его строчным представлением.

UPD:

                                           →
   0   0   0   0   0   0   0   0   0   0 ↑ 1 ↓
           →   →   →   →   →   →           ←
   0   0 ↑ 1   1   1   1   1   1 ↓ 0   0   0
       →       ←   ←   ←   ←   ←   →   →
   0 ↑ 1   1 ↓ 2   2   2   2   2 ↑ 1   1 ↓ 0
                   →
   0 ↑ 1   1 ↓ 2 ↑ 3 ↓ 2   2   2 ↑ 1   1 ↓ 0
       ←           ←   →   →       ←
   0   0 ↑ 1 ↓ 2   2 ↑ 3   3 ↓ 2   2 ↑ 1 ↓ 0
                       ←   ←       →
   0   0 ↑ 1 ↓ 2   2   2   2   2 ↑ 1   1 ↓ 0
               →   →   →   →   →       ←
   0   0 ↑ 1   1   1   1   1   1   1 ↓ 0   0
           ←   ←   ←   ←   ←   ←   ←

[arseniiv]

Вот наконец немного кода с примером (в main):

https://gist.github.com/arseniiv/301e3f0b39ceaa095b2b7bdd6426675e

А сам алгоритм — find_cycles. У Picture можно добавить способ инициализироваться из обычной картинки, но мне было удобно из строки и рисовать это в консоли — а так Picture.str_with_edges можно игнорировать. Z2 — это $\mathbb Z^2$ как $\mathbb Z$-модуль вообще и по совместительству обозначает координаты вершин пикселей при работе с рёбрами. (В комментарии на самом верху приведено рабочее соответствие.)

-- Вс май 31, 2020 05:33:14 --

Алгоритм немного видоизменён по сравнению с предыдущими описаниями, например не пришлось подглядывать уровни у соседей, чтобы проставить пикселю, или не приходится смотреть, какие рёбра были уже обработаны, потому что для каждого пикселя свой набор ориентированных, и пиксель сам обрабатывается лишь раз. Та проблемная ситуация, когда есть несколько вариантов продолжить и окрестность $\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}$, тоже учтена твёрдо, в чём мне помог следующий эскиз ситуации неправильного соединения двух отрезков, которую надо избежать:

Остаётся потестировать на других хитрых растрах. Мой пример там в коде довольно хитрый, но не самый.