Вопрос по программированию (язык не важен)

Question

Вопрос по программированию (язык не важен)

Ор Борщ Мыслитель (5841), на голосовании 1 год назад

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

Answer 1

Вот пример массива:
<code>let arr = [
[1, 1, 1, 0],
[1, 0, 1, 0],
[1, 0, 1, 0],
[1, 1, 1, 0]
];
</code>
Ответ: <code>[{x:0; y:0}, {x:3; y:0}, {x:3; y:3}, {x:0; y:3}]</code>

<code>let arr = [
[1, 1, 1, 0],
[1, 0, 1, 0],
[1, 0, 1, 0],
[1, 1, 1 ,0]
];
let result = [];
for (let i = 0; i < arr.length; i++) {
for (let j = arr[i].length - 1; j >= 0 ; j--) {
if (arr[i][j] === 1) {
result.push({x : j , y : i});
break;
}
}
} </code>

Answer 2

партнер [www.a77r.ru] Мыслитель (8983) 1 год назад

"Короче есть двумерный массив..." - уверен?

Ор БорщМыслитель (5841) 1 год назад

Ну да

партнер [www.a77r.ru] Мыслитель (8983) Ор Борщ, я вижу задачу немного по другому: 'Короче есть некоторая фигура', которая определена в одной системе координат. Требуется определить вершины фигуры в другой системе координат.

Answer 3

Учитывая, что ты изначально даешь матрицу, то и вот тебе код соответствующий. Алгоритм в целом будет именно таким.

 const shapeA = [ 
   [0,0,0,0,0], 
   [0,0,0,1,0], 
   [0,0,0,1,1], 
   [0,1,1,1,1] 
]; 
 
let shapeB = shapeA.flat(); 
let shapeC = []; 
let x1 = 1; 
let y1 = 1; 
let l1 = shapeA.length; 
let l2 = shapeB.length; 
let l3 = l2 / l1; 
 
shapeB.forEach((e,i) => { 
   if (i % l3 == 0) x1 = 1; 
   if (e == 1) shapeC.push({ x:x1, y:y1 }); 
   if (i % l3 == l1) y1++; 
   if (i % l3 <= l1) x1++; 
}) 
 
console.log(shapeC); 
 
// [ 
//   { x: 4, y: 2 }, 
//   { x: 4, y: 3 }, 
//   { x: 5, y: 3 }, 
//   { x: 2, y: 4 }, 
//   { x: 3, y: 4 }, 
//   { x: 4, y: 4 }, 
//   { x: 5, y: 4 } 
// ]

Самое банальное, что приходит на ум для более реальной реализации поиска углов/вершин, это нарисованная фигура в canvas. Там можно использовать цикл вкупе с методом isPointInPath()... однако это очень локальный случай, и даже не вижу смысла заморачиваться.