2014 dxdy logo

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

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




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


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

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


21/05/16
4292
Аделаида
Текущей.

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


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

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


21/05/16
4292
Аделаида
arseniiv в сообщении #1460431 писал(а):
а вдруг она отмечена как пройденная и не считается доступной?

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

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


21/05/16
4292
Аделаида
Вот еще пример, кстати:
Изображение
Ломается снова на четвертом шаге, оно начинает с точки, окруженной пикселями (почему-то не срабатывает проверка на это!) и, очевидно, ломается.
Выводит "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), которого, на самом деле, нет.
Т.е. в лесенке оно добавляет пиксели.
.

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


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

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


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

-- 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/. Это не совсем то.

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


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

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


21/05/16
4292
Аделаида
arseniiv в сообщении #1461169 писал(а):
Подозреваю, что оно должно быть залито внутри?

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


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

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

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

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

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


21/05/16
4292
Аделаида
Вот что делать с такими одноточковыми путями?

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


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

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


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

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


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

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

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

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

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


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

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

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


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

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

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



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

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


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

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