1

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

Язык реализации не особо важен (но желательно js), хочется просто понять алгоритм.


Изначальный массив

То, что должно получиться

2
  • 1
    Разбейте набор синих клеток на компоненты связности. В каждой компоненте отыщите левый нижний квадрат. Его левый нижний угол на границе. Из угла выходит ровно два ребра, которые разделяют синий и белый квадраты. По одному ребру перейдите к соседу, снова найдите разделяющее ребро, перейдите к соседу... Повторяйте пока не придете в исходный угол. 4 фев в 11:37
  • 1
    Отыщите все вершины у которых есть и синие и белые квадраты-соседи. Из неупорядоченного набора вершин вытягивайте цепочки вершин-соседей. Этот способ кажется проще, но есть подводные камни. 4 фев в 11:39

1 ответ 1

0

Дополнить массив где хранится фигура периметром из нолей. Затем последовательно квадратом 2х2 (с шагом в одну строку, столбец) просканировать весь дополненный массив на условие нахождения вершины фигуры в центре квадрата (вершина попадает в квадрат, если есть один угол 0 и остальные 1 или один угол 1 и остальные 0) и зафиксировать координаты вершин.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.