2014-04-06 8 views
0

Задача: У меня есть (lat-long) координаты множества точек a, b, c, d. , , в базе данных. Теперь, когда я выбираю точку a, мне нужно рассчитать расстояния точки a от каждой из других точек и получить ближайшую для eg. Эта математика требует вычисления cos и tan точек. Так что это кажется довольно дорогим на стороне бит.3 баллов стратегия расчета расстояний

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

У меня есть 3 известных точки (x, y, z), известное расстояние между одной точкой до другой. В этом примере допустим, что оно равно 10. т. Е. Расстояние от x до y = 10; y до z = 10; z до x = 10. (это образует равносторонний треугольник, но реальный сценарий может быть не так)

Теперь давайте скажем, что у нас есть две точки a и b. мы вычисляем расстояния точки a до x, y и z и сохраняем соответственно и так для точки b. (Скажем, логика приложения)

так что мы имеем:

  • для точки а: Ax, Ay и Az
  • для точки Ь: Bx, By и Bz

Что касается стратегии , вопрос в том, как мы можем рассчитать расстояние между точкой а до точки б.

Что касается самой проблемы, если я применил вышеприведенную стратегию к моему, вопрос: я упрощаю или затрудняю ситуацию?

Заранее благодарим за ваш ответ.

+0

Я бы сказал, что вы довольно усложняете ситуацию. Если у вас есть точки в 3d системе координат, просто используйте pythagoras для расчета расстояния и затем найдите ближайшую точку в списке расстояний. – Sam

+0

Расчет расстояния между двумя двумерными точками очень прост, и для него вам даже не нужен cos/sin. d = sqrt (Xd^2 + Yd^2) – wvdz

+0

@popovitsj я должен был быть немного более конкретным относительно координат, которые находятся в широте и долготе. Вот почему я был заинтересован использовать тригоны. – Vimal

ответ

0

Вы можете рассчитать расстояние между двумя точками, используя теорему Пифагора, если они указаны в декартовых координатах, при этом не требуется затратная тригонометрия.

Но это, вероятно, по-прежнему будет дорого, если у вас есть тысячи или миллионы баллов. В зависимости от используемой базы данных он может предлагать пространственные типы данных и эффективно обрабатывать ваш запрос. См. Например, spatial data in SQL Server.

Если ваша база данных не поддерживает пространственные данные, проблема становится довольно сложной. Вам нужен пространственный индекс с эффективной поддержкой для запросов ближайшего соседа. Вы можете начать с Wikipedia article on spatial databases, чтобы узнать, как эта проблема обычно решается.

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

Смежные вопросы