0

I am working on my university project, and I use GeoTools library. My task is to implement AGNES (agglomerative nesting) algorithm that considers spatial data. To do this I need to calculate distances between spatial objects e.g. points, curves, polygons.

LineString which can be converted to Curve is a GeoTools class that inherits Geometry methods including distance(). My question is how is the distance between two LineString objects calculated? Is it the shortest line segment connecting both curves? Also, I am curious how similar is done with polygons.

luk2302
  • 55,258
  • 23
  • 97
  • 137
Piotrek Hryciuk
  • 785
  • 10
  • 23
  • 1
    The shortest distance between two polygons is easy because the shortest distance must be from a vertex to a vertex. All you need is 2 nested loops over the two vertex sets. The shortest distance between two curves is the distance of the shortest line segment connecting them. That's much more complicated as it depends on the types of curves. I suspect they do something like approximate the curves using Bezier curves and then solving the resulting equations numerically. You'd have to look at the source code. – Paul Boddington Jan 04 '15 at 18:41
  • Great! Thank you for the answer. This is exactly what I wanted to know. – Piotrek Hryciuk Jan 04 '15 at 18:43
  • don't forget GeoTools is open source, so you can look at the code to be sure how something is calculated. Unless you are using a projected coordinate system distance() is probably not the correct answer. – Ian Turton Jan 05 '15 at 08:34
  • I'm afraid that @PaulBoddington is wrong. The minimun distance between two polygons can be achieved inside one of the polygons edges. For example, the distance between the triangle A: (-1,0),(1,0)(-1,-1) and the triangle B: (0,1), (-1,-2), (1,2) is achieved in points (0,0) and (0,1) from A and B respectively. The point (0,0) is inside the edge defined by (-1,0),(1,0). – eguaio Oct 28 '16 at 14:27

1 Answers1

0

An algorithm with an explanation can be found in the answer of this question find-shortest-path-from-one-geometry-to-other-on-shapely. The distance is not necessarily achieved in two vertex.

The algorithm basically computes the distance between each pair of edges, including the case where the distance is achieved in the interior of the edge (by projecting vertex points of one edge to the other edge).

The code is in python, but the geometric library it uses is shapely, that is based on GEOS library, which in turn is a ported version of JTS.

Community
  • 1
  • 1
eguaio
  • 3,754
  • 1
  • 24
  • 38