@gd1xza

Как осуществить поиск квадрата в массиве?

Нужно на картинке(пикселях) найти квадрат с заданной гранью на пример 5. Сам придумать как, не могу.
Есть строка пикселей (можно и в 2мерный массив перевести) в строке каждые 3 байта - 1 пиксель.
Известны ширина и высота изображения.
Нужно найти квадрат из одинаковых пикселей. Например хочу квадрат с гранью 2 тогда надо проверить 1 пиксель и следующий и снизу и снизу следующий ну если 2 то еще можно вручную а мне надо чтобы можно было легко и 2 и 10 и 15 пикселей.
Хочу написать функцию куда передаешь весь массив пикселей с экрана и ширину грани а на выходе координата 1 пикселя квадрата 1ого цвета.
Надеюсь понятно обьяснил.
  • Вопрос задан
  • 164 просмотра
Пригласить эксперта
Ответы на вопрос 1
x67
@x67
Опишу для простейшего случая где квадрат не имеет наклона относительно осей и точки надо находить только на вершинах квадрата, а не на их гранях. У каждой точки есть минимум 2 координаты Х и У
Метод работает очень просто - находятся все возможные центры квадрата, которым может принадлежать точка, для каждого из них точка добавляется в список
После чего перебираем все центры и находим те, у которых ровно 4 точки, а значит есть квадрат, они же и возвращаются
Преимущества - очень быстро работает, невысокая вычислительная сложность (ДЗ - посчитать ее для этого алгоритма)
Особенности - работает только с уникальными точками, для не уникальных с одинаковыми координатами надо писать обвязку и чуть модифицировать алгоритм; Могут быть проблемы при работе с плавающей точкой - это надо учесть (как модифицировать код, чтобы все работало и с ними - ДЗ №2)
Также этот код не учитывает цвета пикселей, но это можно сделать предварительно разделив список пикселей на несколько списков по цветам или модифицировав функцию
def get_squares(pts, side_length):
    '''
    pts - список точек в виде кортежей (x,y)
    side_length - длина стороны квадрата
    '''

    def shift(pt, dx, dy):
        return tuple([pt[0] + dx, pt[1] + dy])

    hl = side_length / 2
    if hl == 0:
        return None  # нет квадратов со стороной 0
    dirs = ((hl, hl), (-hl, -hl), (-hl, hl), (hl, -hl),)  # направления
    pts = set(pts)  # убираем дубли точек и ускоряем 
    cs = dict()  # центры потенциальных квадратов
    for pt in pts:
        for dir in dirs:
            center = shift(pt, *dir)
            cs[center] = cs.get(center, list()) + [pt]
    squares = list(filter(lambda q: len(q) == 4, cs.values()))
    return squares
# проверка
mx=10
side_len=5
pts_cnt=500
l=list()
for i in range(pts_cnt):
    l.append((randint(0,mx),randint(0,mx)))
sq=get_squares(l,side_len)
print(sq)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы