# Changes between Version 1 and Version 2 of NewDistCalcSubGeom

Show
Ignore:
Timestamp:
11/08/09 08:48:10 (4 years ago)
Comment:

--

Unmodified
Removed
Modified
• ## NewDistCalcSubGeom

v1 v2
22== Handling of subgeometries ==
33Calculating distances is quite a costly process. Because of that it is often worth the effort to sort the geometries depending on how the bounding boxes are related to each other. This example is a little extreme in the amount of subgeometries and vertexes but then the gain will really show. The example is a distance-calculation between Texas and Alaska.
4
5[[Image(illustration1.png, 300)]]
6
7In postgis 1.4 this would cause 178137 * 12167 = 2 167 392 879 iterations.
8With the faster algorithm described in [wiki:NewDistCalcGeom2Geom How the distance calculations is done] the iterations will be very much reduced and then takes about 7 seconds. But even now there is a lot of unnecessary work done when calculating the exact distance to each and every of the sub geometries. This is how we now instead uses bounding boxes to only calculate a selection of geometries.
9
10[[Image(illustration2.png, 300)]]
11
12Here is the bounding boxes of the two states. The first thing we do is to iterate through all combinations of bounding boxes to find the “smallest max distance” between the boxes. What we know from this value is that the distance we get here is longer or the same (if two inputed points) than the min distance we are looking  for
13The result is the distance along a line like this:
14
15[[Image(illustration3.png, 300)]]
16
17Now we iterate through all the combinations again and store all combinations with smaller min distance than the earlier found in a list. We also order the list so we get the smallest min distance first.
18
19Now we are ready to calculate real distances beginning with the bounding boxes closest to each other. We continue the process until the next “min distance between bounding boxes” is longer than the min distance between real geometries we have found.
20
21The result is then the distance along a line like this returned in about 600ms.
22
23[[Image(illustration4.png, 300)]]