Получить путь границ смежных областей в 2D-массиве

Скажем, у меня есть такой массив:

import numpy as np

arr = np.array([
   [1, 1, 3, 3, 1],
   [1, 3, 3, 1, 1],
   [4, 4, 3, 1, 1],
   [4, 4, 1, 1, 1]
])

Есть 4 отдельных области: верхняя левая 1s, 3s, 4s и правая 1s.

Как мне получить пути для границ каждого региона? Координаты вершин области по порядку.

Например, для верхней левой единицы это (0, 0), (0, 2), (1, 2), (1, 1), (2, 1), (2, 0)

(В конечном итоге я хочу получить что-то вроде start at 0, 0. Right 2. Down 1. Right -1. Down 1. Right -1. Down -2., но это легко преобразовать, так как это просто разница между соседними вершинами)

Я могу разделить его на регионы с помощью scipy.ndimage.label:

from scipy.ndimage import label

regions = {}
# region_value is the number in the region
for region_value in np.unique(arr):
    labeled, n_regions = label(arr == region_value)
    regions[region_value] = [labeled == i for i in range(1, n_regions + 1)]

Что больше похоже на это:

{1: [
    array([
        [ True,  True, False, False, False],
        [ True, False, False, False, False],
        [False, False, False, False, False],
        [False, False, False, False, False]
    ], dtype=bool),  # Top left 1s region
    array([
        [False, False, False, False,  True],
        [False, False, False,  True,  True],
        [False, False, False,  True,  True],
        [False, False,  True,  True,  True]
    ], dtype=bool)  # Right 1s region
 ],
 3: [
    array([
        [False, False,  True,  True, False],
        [False,  True,  True, False, False],
        [False, False,  True, False, False],
        [False, False, False, False, False]
    ], dtype=bool)  # 3s region
 ],
 4: [
    array([
        [False, False, False, False, False],
        [False, False, False, False, False],
        [ True,  True, False, False, False],
        [ True,  True, False, False, False]
    ], dtype=bool)  # 4s region
 ]
}

Итак, как мне преобразовать это в путь?


python numpy multidimensional-array ndimage
person Artyer    schedule 26.09.2018    source источник
comment
Просто случайная идея. Используйте существующий код контурной линии: stackoverflow.com/a/18309914/7207392   -  person Paul Panzer    schedule 26.09.2018

Ответы (1)


arrow_upward
0
arrow_downward

идея псевдокода заключалась бы в следующем:

scan multi-dim array horizontally and then vertically until you find True value (for second array it is (0,4))
output that as a start coord
since you have been scanning as determined above your first move will be to go right.
repeat until you come back:
    move one block in the direction you are facing.
    you are now at coord x,y
    check values of ul=(x-1, y-1), ur=(x-1, y), ll=(x, y-1), lr=(x,y)
    # if any of above is out of bounds, set it as False
    if ul is the only True:
         if previous move right:
             next move is up
         else:
             next move is left
         output previous move
         move by one
   ..similarly for other single True cells..
   elif ul and ur only True or ul and ll only True or ll and lr only True or ur and lr only True:
        repeat previous move
   elif ul and lr only True:
        if previous move left:
            next move down
        elif previous move right:
            next move up
        elif preivous move down:
            next move left:
        else:
            next move right
        output previous move
        move one
   elif ul, ur, ll only Trues:
        if previous move left:
            next move down
        else:
            next move right
        output previous move, move by one
   ...similarly for other 3 True combos...

для второго массива он сделает следующее:

finds True val at 0,4
start at 0,4
only lower-right cell is True, so moves right to 0,5 (previous move is None, so no output)
now only lower-left cell is True, so moves down to 1,5 (previous move right 1 is output)
now both left cells are True, so repeat move (moves down to 2,5)
..repeat until hit 4,5..
only upper-left cell is True, so move left (output down 4)
both upper cells are true, repeat move (move left to 3,4)
both upper cells are true, repeat move (move left to 2,4)
upper right cell only true, so move up (output right -3)
..keep going until back at 0,4..

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

person Landar    schedule 26.09.2018