Переиндексировать массив, проиндексированный другим массивом, элементы которого удалены из обоих - PullRequest
Новая
       13

Переиндексировать массив, проиндексированный другим массивом, элементы которого удалены из обоих

0 голосов
/ 01 июля 2019

Я просто работаю над оптимизатором 3d-сетки и достиг блока кодера. Это то, что я должен решить за час, но вместо этого я застрял весь день.

index содержит координаты вершин треугольника, расположенные в attribute. Если он говорит -1, -1, -1, это означает, что этот треугольник был удален и будет удален в новом индексе. Вершины могут быть разделены между треугольниками, но если на них больше нет ссылок в index, они должны быть удалены из нового массива атрибутов, а их адреса обновлены в новом индексе. 

// -1 are removed elements
const index = [
  -1, -1, -1,
  5, 2, 0,
  2, 0, 4,
  2, 5, 0,
  -1, -1, -1,
];

const attribute = [
  1234, 1341, 1432, // vertex 0

  2123, 2531, 2121, // vertex 1

  3532, 3123, 3441, // vertex 2

  4112, 4311, 4122, // vertex 3

  5112, 5311, 5122, // vertex 4

  6112, 6311, 6122, // vertex 5
];

Кто знает, может быть, я отправлю ответ на этот вечер, но если вопрос все еще здесь, я потерпел неудачу.

Вот как должен выглядеть результат 

// -1 are removed elements
const newIndex = [
  // removed
  3, 1, 0,
  1, 0, 2,
  1, 3, 0,
  // removed
];

const newAttribute = [
  1234, 1341, 1432, // still 0

  // removed

  3532, 3123, 3441, // 2 became 1

  // removed

  5112, 5311, 5122, // 4 became 2

  6112, 6311, 6122, // 5 became 3
];

Редактировать: я только что установил песочницу с юнит-тестами https://codesandbox.io/s/reindex-array-by-array-m4llg

1 Ответ

0 голосов
/ 01 июля 2019

Хорошо, с TDD мне удалось получить правильный вывод. Не слишком эффективно, но я сомневаюсь, что это проблема, которую многие люди будут пытаться решить. 

    function reindex(index, attribute) {
      const uniqueVertices = [];
      const mapNewToOld = [];
      const mapOldToNew = [];
      // find unique indices
      for (let i = 0; i < index.length / 3; i++) {
        const offset = i * 3;
        if (index[offset] === -1) continue;
        for (let j = 0; j < 3; j++) {
          if (!uniqueVertices.includes(index[offset + j])) {
            mapNewToOld[uniqueVertices.length] = index[offset + j];
            // mapOldToNew[index[offset + j]] = uniqueVertices.length;
            uniqueVertices.push(index[offset + j]);
          }
        }
      }
      mapNewToOld.sort();

      const newIndex = [];
      let newIndexCount = 0;
      for (let i = 0; i < index.length / 3; i++) {
        const offset = i * 3;

        if (index[offset] === -1) continue;
        newIndex[newIndexCount * 3] = mapNewToOld.indexOf(index[offset]);
        newIndex[newIndexCount * 3 + 1] = mapNewToOld.indexOf(index[offset + 1]);
        newIndex[newIndexCount * 3 + 2] = mapNewToOld.indexOf(index[offset + 2]);
        newIndexCount++;
      }

      const newAttribute = [];
      for (let i = 0; i < uniqueVertices.length; i++) {
        const offset = i * 3;

        const address = mapNewToOld[i] * 3;
        newAttribute[offset] = attribute[address];
        newAttribute[offset + 1] = attribute[address + 1];
        newAttribute[offset + 2] = attribute[address + 2];
      }

      return [newIndex, newAttribute];
    }
...