anmipo

R. На хабре есть вводные статьи.

Ваша задача любопытна, кроме всего прочего, своей нетрадиционностью: известно точное расстояние до «кубиков», их точное положение, но между собой они неразличимы. Обычно в задачах позиционирования всё наоборот: известен ID станции (GSM cell ID, Wi-Fi MAC), но расстояние до неё можно только грубо прикинуть (по силе сигнала или времени его распространения), а где она находится — вообще непонятно.

Итак, входные данные: карта расположения кубиков, и набор из пяти расстояний x₁...x₅ до каких-то из этих кубиков (пусть с некоторой точностью ±Δ).

1. Берём карту, накладываем на неё прозрачный слой (в терминах графических редакторов).
2. Берём первое расстояние из набора, x₁ и вокруг каждого кубика на карте рисуем сплошное кольцо с внутренним радиусом x₁-Δ и внешним x₁+Δ.
   Кольца представляют множество всех возможных положений пользователя на основе одного измеренного расстояния.
3. Накладываем ещё один слой, рисуем кольца для x₂±Δ.
4. Производим объединение этого слоя с предыдущим, используя операцию AND, — то есть находим пересечение множеств. Результат будет множеством возможных положений пользователя с учётом двух измеренных растояний.
5. Повторяем шаги 3-4 для x₃...x₅.
6. Получившееся изображение показывает возможные положения пользователя с учётом пяти измеренных расстояний. Вполне вероятно, что таких положений будет несколько — значит, задача не имела однозначного решения. Не исключено также, что результат будет пустым множеством, — в таком случае стоит увеличить значение Δ.

Разумеется, расчёт пересечения колец — занятие не особо быстрое. Поэтому каждое кольцо можно заменить парой квадратов (вписанным и описанным) — и вся задача сведётся к поиску пересечений прямоугольников. А это даже микроконтроллер посчитает за десяток тактов :)