Как рассчитывается расстояние между двумя строками LineString?

Я работаю над университетским проектом и использую библиотеку GeoTools. Моя задача - реализовать алгоритм AGNES (aglomerative nesting), учитывающий пространственные данные. Для этого мне нужно рассчитать расстояния между пространственными объектами, например. точки, кривые, многоугольники.

LineString, который можно преобразовать в Curve, - это класс GeoTools, наследующий методы Geometry, включая distance (). У меня вопрос: как рассчитывается расстояние между двумя объектами LineString? Это самый короткий отрезок, соединяющий обе кривые? Также мне любопытно, как это делается с полигонами.


java gis geotools
person Piotrek Hryciuk    schedule 04.01.2015    source источник
comment
Кратчайшее расстояние между двумя многоугольниками легко, потому что кратчайшее расстояние должно быть от вершины до вершины. Все, что вам нужно, это 2 вложенных цикла по двум наборам вершин. Кратчайшее расстояние между двумя кривыми - это расстояние самого короткого отрезка линии, соединяющего их. Это намного сложнее, так как это зависит от типов кривых. Я подозреваю, что они делают что-то вроде аппроксимации кривых, используя кривые Безье, а затем численно решают полученные уравнения. Вам нужно будет посмотреть исходный код.   -  person Paul Boddington    schedule 04.01.2015
comment
Здорово! Спасибо за ответ. Это именно то, что я хотел знать.   -  person Piotrek Hryciuk    schedule 04.01.2015
comment
не забывайте, что GeoTools имеет открытый исходный код, поэтому вы можете посмотреть код, чтобы убедиться, как что-то рассчитывается. Если вы не используете проецируемую систему координат, distance (), вероятно, неправильный ответ.   -  person Ian Turton    schedule 05.01.2015
comment
Боюсь, что @PaulBoddington ошибается. Минимальное расстояние между двумя полигонами может быть достигнуто внутри одного из краев полигона. Например, расстояние между треугольником A: (-1,0), (1,0) (- 1, -1) и треугольником B: (0,1), (-1, -2), (1 , 2) достигается в точках (0,0) и (0,1) от A и B соответственно. Точка (0,0) находится внутри ребра, определенного как (-1,0), (1,0).   -  person eguaio    schedule 28.10.2016

Ответы (1)


arrow_upward
0
arrow_downward

Алгоритм с объяснением можно найти в ответе на этот вопрос найти кратчайший путь от одной геометрии к другой по форме. Расстояние не обязательно достигается в двух вершинах.

Алгоритм в основном вычисляет расстояние между каждой парой ребер, включая случай, когда расстояние достигается внутри ребра (путем проецирования вершинных точек одного ребра на другое ребро).

Код написан на Python, но геометрическая библиотека, которую он использует, shapely, основана на библиотеке GEOS, которая, в свою очередь, является перенесенной версией JTS.

person eguaio    schedule 28.10.2016