amarao (amarao_san) wrote,
amarao
amarao_san

Category:

математика не прощает

Если кто-то помнит, некоторое время назад я писал пост о том, что нельзя просто так "подмухлевать" и получить консистеный результат в математики. Сейчас оно меня снова укусило.

Я пишу код "попробовать" вместо QuadTree, NxN tree (т.е. делить область на более чем попалам по каждой координате). С учётом, что хранение "хвоста" точек до ~10-15 шт в виде массива быстрее, чем раскладывание их по дереву, есть мысль, что векторизация разделения дерева тоже будет эффективнее (мой эстимейт - 4х4, т.к. это ближе всего к тем же 15).

В ходе обобщения существующего кода мне нужно было переписать функцию find_subrange. Функция берёт итервал [start;end], точку coords, и используя глобальную константу SPLITS возвращает "подинтервал" в котором находится точка и номер (считая с нуля).

Старый код, заточенный под SPLITS=2 делал так:
let middle =(start + end)/SPLITS as f64; 
if coord <= middle {
    (start, middle, 0) }
else {
    (middle, end, 1)
}

Грубо и эффективно.

Теперь попробуем обобщить этот код.

Введём обозначения:
L = end - start (длина исходного отрезка).
D = coord - start (длина отрезка от начала исходного отрезка до точки)
Ls = L/SPLITS (длина одного подинтервала)

ии... и всё взрывается.
Формула для индекса: i = [D/Ls] (целая часть от деления длины исходного отрезка на длину одного подинтервала).

Эта формула почти правильная. Кроме ситуации, когда coord = end. Разумеется, она возвращает SPLITS, т.е. если мы считаем с нуля, она возвращает "число подотрезков в интервале +1". Абсолютно разумное понятное поведение, которое говорит нам, что нельзя работать с отрезками "просто так".

Объяснение в цифрах. Пусть у нас исходный отрезок [0;2], SPLITS=2. Ожидаем два подинтервала [0;1] и [1;2]
Теперь, вопросы:
0.5 левый.
1.5 - правый.
А вот кому принадлежат точки 0, 1, и 2 - это вопрос открытый. Я буду пробовать с 1.0 и говорить про последствия для 0 и 2.

Если 1 - это левый отрезок, то тогда 2 - правый (всё хоршо), а вот 0 - вне отрезка.
Если 1 - это правый отрезок, то тогда 0 - в левом отрезке (всё хорошо), а 2 - вне отрезка.
Если 1 - это и в левом и правом (что решит проблему и 0 и 2), то у нас проблема ещё большего масштаба, мы-то хотим один отрезок для точки, и два нам точно всё сделает ещё хуже.

... Мышки плакали, кололись, но продолжали жрать кактус.

let i = std::cmp::min(SPLITS-1, (D/LS) as usize);

Enjoy your math. Тесты прошли. Пока что. Но я уверен, что мне эта проблема ещё 100500 раз аукнется.

... Или, сцепить зубы, и заявить что мы всё-таки работаем с полу-интервалами? Тогда вся математика отлично сходится, но в граничных точках начинаются неприятные эффекты. Возможно, при отказе от массива корней внутри пикселов оно станет не таким уж сложным?
Tags: equart
Subscribe

  • фурикури

    Я тут его ещё раз пересмотрел, и за гламурным дребезгом (который хорош), я, наконец-таки, рассмотрел сюжет. Первые три серии (я про оригинальный…

  • поздне-анимешное

    Один из интересных водоразделов между западной и восточной (японской, японской) культурой я вижу в районе толстовской фразы "Все счастливые семьи…

  • berserk 2017

    Внезапно, если кто не заметил, уже аж 4 серии нового сезона. И он не менее офигенен, чем предыдущий. При том, что местами анимация провисает, история…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments