Какой самый эффективный способ работы с расстояниями между двумя координатами?

Question

У меня есть 2063 местоположения, хранящиеся в таблице MySQL. В одном из моих процессов мне нужно исключить определенные результаты, основанные на том, как далеко они находятся от заданной точки происхождения. Проблема в том, что мне нужно будет фильтровать пару сотен, может быть, пару тысяч результатов за раз.

Так, что было бы лучшим способом сделать математику расстояния. Должен ли я сделать это во время выполнения

1. Find all points connecting to my point of origin
2. loops through the connecting points
3. calculate the distance between the point of origin and the connecting point
4. exclude the connecting point if the distance if too great

или я должен создать справочную таблицу с уже рассчитанными расстояниями между каждой точкой. Я могу избежать дублирования строк, так как расстояние между p1 и p2 будет таким же, как расстояние между p2 и p1, но это все равно приведет к паре миллионов строк в таблице.

Или .. есть еще лучший способ сделать это?

Answer 1

Вы можете использовать пространственные расширения MySQL для вычисления расстояния и даже создать индекс данных R-дерева для данных, чтобы оптимизировать поиск точки в некотором диапазоне.

Подробности смотрите в документации по пространственным расширениям MySQL: http://dev.mysql.com/doc/refman/5.1-maria/en/spatial-extensions.html

Answer 2

Поскольку ваши данные находятся в таблице mysql, вам действительно нужно решение, с которым SQL сможет вам помочь.

Я предполагаю, что у каждого местоположения есть координаты x и y. Сохраните их как отдельные записи в таблице.

Вы можете быстро сузить поле поиска до поля с центром в интересующей вас области. например,

WHERE X > (MyPosX - Range) AND X < MyPosX + Range) 
AND Y > (MyPosY - Range) AND Y < MyPosY + Range)

Если у вас есть меньший набор предметов, которые могут быть в пределах досягаемости, вы можете использовать более итеративный подход

Редактировать: Избегайте расчетов квадратного корня при расчете фактических расстояний, поскольку они дороги. например, вместо

sqrt(x*x + y*y) < distance

попробуй

(x*x + y*y) < distance*distance    
// distance*distance is a constant and can be calculated once

Answer 3

Как насчет этого:

1. Loop through all points:
  2. If abs(a-b) &lt distance && abs(a-b) &lt distance then:
    3. Do the fancy distance calculation between a and b.

т.е. предполагая, что большинство точек будет находиться за пределами «рамки», определяемой интересующим вас расстоянием, вы можете очень быстро отфильтровать большинство точек с помощью шага 2 и рассчитать реальное расстояние только для гораздо меньшего числа точек.