Changes between Version 3 and Version 4 of NewDistCalcSubGeom

Timestamp:

Nov 8, 2009, 12:23:06 PM (14 years ago)

Author:

nicklas

Comment:

—

NewDistCalcSubGeom

@@ -5 +5 @@
 [[Image(illustration1.png, 300, border=1)]]
 
-In postgis 1.4 this would cause 178137 * 12167 = 2 167 392 879 iterations. 
-With 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.
+In postgis 1.4 this would cause 178137 * 12167 = 2 167 392 879 iterations. This uses about 1440 seconds (22 minutes and 20 seconds). With 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.
 
 [[Image(illustration2.png, 300, border=1)]]
 
-Here 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 
-The result is the distance along a line like this:
+Here is the bounding boxes of the two states. Because postgis can handle nested geometrycollections, the first thing we have to du is "unwind" the collection or multi geometries so we get them in a "flat list" with all sub geometries without hierarchical order. Then we 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. The result is the distance along a line like this:
 
 [[Image(illustration3.png, 300, border=1)]]