Как построить контур по координатам вершин фигуры, состоящей из квадратов?

Рейтинг: 1Ответов: 1Опубликовано: 04.02.2023

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

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

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

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

массивы алгоритм геометрия
Источник: Stack Overflow на русском

Ответы

▲ 0

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