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

[kotenok gav]

Ладно, завтра кину пример.

[kotenok gav]

arseniiv
Вот внешняя граница с одноточковыми путями:
https://jsfiddle.net/Lhpn63c1/1/
Она никак не отличается от просто внешней границы:
https://jsfiddle.net/Lhpn63c1/2/
А надо, чтобы точки на невнешних границах тоже не были закрашены.

[arseniiv]

А в исходной растровой картинке были одноточечные дырки?

Если бы вы ещё её приложили, а то я надеялся смотря на неё понять…

[kotenok gav]

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

Если бы вы ещё её приложили

[arseniiv]

А, та самая! Хм, я даже не знаю, что там может идти настолько не так, что для этого примера получаются одноточечные пути…

[kotenok gav]

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

Хм, я даже не знаю, что там может идти настолько не так, что для этого примера получаются одноточечные пути…

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

[arseniiv]

Просто эффективно это их игнорирует, и раз результат не тот и с проигнорированными внутренними границами, и с не проигнорированными, я не знаю, что ещё можно подкрутить.

[kotenok gav]

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

[kotenok gav]

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

[kotenok gav]

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

[arseniiv]

Чёрт возьми, до меня кажется дошло!

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

-- Сб май 16, 2020 20:06:18 --

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

Чтобы определить, какая граница какая, можно присвоить пикселям уровни по таким правилам:
(1) Cначала крайние белые пиксели картинки получают уровень 0, а крайние чёрные — 1. (И те, и те, потому что каких-то может не быть.)
(2) Все соседи того же цвета пикселя с уровнем $a$ получают уровень $a$.
(3) Теперь если остались ещё пиксели без определённого уровня, рассматриваем сейчас те из них, у соседей которых наименьший определённый уровень $a$. Этим пикселям приписываем уровень $a + 1$. Повторяем (3).

В (1) и (3) у нас есть возможность провести кусочек границы, а так же соединить кусочки границ, которые уже были проведены, так что в принципе так можно будет получить и все границы, притом с правильным направлением обхода (таким, что если переходить из пикселя чётного уровня в пиксель нечётного, направление обхода границы будет получено поворотом на 90° в одну и ту же сторону для всех случаев). Но можно получить все границы и по-старинке.

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

Теперь зачем нам уровни: в вашей задаче, если я понял её наконец как надо, нам нужны границы между уровнями $n, n+1$ для $n\geqslant1$, а границы между уровнями $0, 1$ надо выбросить, и это единственное условие. Все (вообще все, даже если компонент связности много) оставшиеся границы можно будет засунуть в один path и всё будет нормально закрашиваться.

[kotenok gav]

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

Вам не нужно заливать изначально закрашенные пиксели, но вам нужно залить все незакрашенные, лежащие внутри границ, образованных закрашенными?

Да.

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

Чтобы определить, какая граница какая, можно присвоить пикселям уровни по таким правилам:
(1) Cначала крайние белые пиксели картинки получают уровень 0, а крайние чёрные — 1. (И те, и те, потому что каких-то может не быть.)
(2) Все соседи того же цвета пикселя с уровнем $a$ получают уровень $a$.
(3) Теперь если остались ещё пиксели без определённого уровня, рассматриваем сейчас те из них, у соседей которых наименьший определённый уровень $a$. Этим пикселям приписываем уровень $a + 1$. Повторяем (3).

Завтра реализую и посмотрю...

[kotenok gav]

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

from PIL import Image, ImageDraw
def add(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 map(lambda x: add(pixel, x), [(0, 1), (1, 0), (0, -1), (-1, 0)])
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))
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())):
            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)
    print('============================================================')
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)
 

На первой итерации выводит

(скрыто для возможности отредактировать сообщение)

, потом почему-то не переходит к (3), и поэтому выводит то же самое. Посмотрю...

-- 18 май 2020, 01:46 --

Хм, нет, он как раз переходит к (3) (и выводит то, что я написал, а на первой итерации он выводит немного другое).

-- 18 май 2020, 01:46 --

А, я понял. Не max(levelByPixel.values()), а max(levelByPixel.values()) + 1.

-- 18 май 2020, 01:51 --

Итак, оно выводит

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001122222221110000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000112222222222211000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001222222222222221100000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000012222222222222222100000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000122222222222222222110000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000122222222222222222211110000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000122222222222222222222110000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000122222222222222222221110000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000122222222222222222222110000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011122222222222221111222100000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000122232222222222222221111100000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011122222222222222222221100000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111122222222222222211000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000112222222222211111110000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111112221110000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

.

[arseniiv]

(Вот потому я и предлагал уменьшить картинку.)

Если не упустил деталь, уровни расставились как я и ожидал, да.

[kotenok gav]

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