Рубрика «вычислительная физика»

Вычисление центра масс за O(1) с помощью интегральных изображений - 1

Интегральное изображение ― алгоритм, позволяющий эффективно вычислять сумму значений, заключенных в прямоугольном подмножестве многомерного массива. Сама его идея восходит к исследованиям многомерных функций распределения вероятностей, и до сих пор он находил успешное применение в тех областях, которые непосредственно используют теорию вероятностей в качестве основного инструментария. Например, в распознавании образов.

Сегодня мы рассмотрим любопытный случай, как применить интегральные изображения в кардинально другой сфере ― вычислительной физике. А именно ― посмотрим, что будет, если вычислить с их помощью центр масс поля импульсов, и какую выгоду можно извлечь из этого симбиоза.

В этой статье я расскажу:

  • Что за задача такая, о которой идет речь;
  • Подробнее об интегральных изображениях;
  • Как использовать интегральные изображения для приближенного решения гравитационной задачи N тел применительно к дискретному полю импульсов (масс-скоростей);
  • Какой недостаток имеет это решение и как его исправить;
  • И, наконец, как за константное время вычислить центр масс для произвольного региона.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js