2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 8  След.
 
 Re: Алгоритм "поиска" многоугольника
Сообщение27.04.2020, 19:34 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение27.04.2020, 19:52 


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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение27.04.2020, 21:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение28.04.2020, 13:14 


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

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение28.04.2020, 13:19 
Заслуженный участник


27/04/09
28128
Примерно так, но надо чтобы точка не была окружена $\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 --

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 12:40 


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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 13:27 
Заслуженный участник


27/04/09
28128
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 --

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 14:31 


21/05/16
4292
Аделаида
arseniiv в сообщении #1458827 писал(а):
1111 — это же для точки внутри фигуры

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 14:37 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 14:39 


21/05/16
4292
Аделаида
arseniiv в сообщении #1458844 писал(а):
Она же внутренняя, у неё со всех сторон закрашенные в растровом исходном изображении пиксели.

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 14:47 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 15:08 


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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 15:49 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 16:16 


21/05/16
4292
Аделаида
arseniiv в сообщении #1458864 писал(а):
В общем проверьте алгоритм в действии, его же не так долго писать должно быть. Если он действительно не до конца работает, мы хотя бы с вами будем иметь результат неправильной работы, чтобы я понял, что в нём сломано. :-)

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

 Профиль  
                  
 
 Re: Алгоритм "поиска" многоугольника
Сообщение29.04.2020, 17:33 


21/05/16
4292
Аделаида
Итак, вот программа:
код: [ скачать ] [ спрятать ]
Используется синтаксис 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:])
 

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 116 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 8  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group