Как в MongoDB найти почти равные углы?

Question

[Константин Китманов]

В MongoDB лежат объекты, у которых одно из свойств — угол в градусах, целые числа от 0 до 359 (если совсем честно, то это азимут).

Мне нужно находить объекты, угол у которых отличается от заданного не более чем на 22.5 градуса. Первая версия такова:

var directionTolerance = 45 / 2;

var query = {
    $or: [
        {
            direction: {
                $gte: newDirection - directionTolerance, // newDirection -- искомый угол
                $lte: newDirection + directionTolerance
            }
        },
        {
            direction: {
                $gte: 360 + newDirection - directionTolerance,
                $lte: 360 + newDirection + directionTolerance
            }
        },
        {
            direction: {
                $gte: 360 - newDirection - directionTolerance,
                $lte: 360 - newDirection + directionTolerance
            }
        }
    ]
};

К сожалению, этот запрос иногда дает false positive: например, может вернуть объект с углом 0 при угле в запросе 173.
Как сделать правильно?

Answer 1

[lega]

Операция "$or" медленная, можно её выкинуть и сделать так - хранить координату в нескольких разрезах:
{
direction: 350,
direction_index: [-10, 350]
}
и искать уже по индексу:
.find({direction_index: { $lte: -22, $gte: 22}})
в итоге вам нужно что-бы фильтр укладывался в -360..360

Comments

[Константин Китманов]

Спасибо, если не будет идет получше, буду создавать такой индекс.

[lega]

Либо использовать положительный диапазон: 0..720, тогда для примера выше direction_index=[350, 710], ну и поиск 360-22, 360+22

[Константин Китманов]

lega: вот это, наверное, самая интересная идея.
В итоге решил по-другому, но вам все равно спасибо и плюсик в карму за толковый ответ.

Answer 2

[Mikhail Osher]

Понятия не имею, а там синусы/косинусы есть? Может тригонометрия поможет?)

Comments

[Константин Китманов]

Хм, и как она должна помочь, по вашей мысли?

Answer 3

[Philipp]

Обычно в NoSQL применяют предварительную квантификацию данных.
Т.е. у вас есть погрешность π/8, а круг 2π, то ваш квантификатор будет массивом от 0 до 16. У каждого объекта будет свойство quantified_direction, хранящее нужное значени и выборка будет примитивной.
Более простое объяснение - разбейте круг на 16 секторов и записывайте номер для каждого сектора прямо в объект. При поиске просто используйте этот номер. Также вы можете увеличить значение до 32 и делать поиск по двум секторам одновремено. После построения индекса для quantified_direction вы будет получать результаты за доли секунды на огромных базах.
А в целом у вас ошибка в подготовке условия. Нарисуйте круг, вырежьте сектор из бумаги и поработайте с граничными условиями. Задача на самом деле простая.

Comments

[Константин Китманов]

Спасибо за развернутый ответ.

Ага, а для пущей точности можно делить не на 16 и даже не на 32 сектора, а на 360. Ой...
Ну, во-первых, это оптимизация. В данном случае, преждевременная: вы не знаете, сколько у меня в этой коллекции объектов и тормозит ли именно эта выборка.
Во-вторых, как это связано с NoSQL? Точно так же можно и в MySQL и в Postgre сделать. Разница только в том, что в Postgre я бы сделал хранимку, которая правильно считает разницу азимутов, и не задавал бы идиотских вопросов.
В-третьих, проверять надо не попадание в данный сектор, а именно что разница между углами не больше данной константы.
В-четвертых, я не спорю, что задача простая, и, поверьте, с нарисованным кругом я уже посидел. Если бы я мог ее решить сам, я бы не беспокоил народ своими вопросами.

[Philipp]

direction in [0,360)

newDirection in [0,360)

tolerance = 22

examples:


newDirection = 0

if newDirection < tolerance

	direction belongs (360-newDirection+tolerance, 360] or  [0,newDirection+tolerance)

else
	if newDirection > 360-tolerance

		direction belongs [newDirection-tolerance, 360] or [0,newDirection+tolerance-360)

	else
	
		direction belongs [newDirection-tolerance, newDirection+tolerance]