PostGIS  2.5.1dev-r@@SVN_REVISION@@

◆ nd_box_array_distribution()

static int nd_box_array_distribution ( const ND_BOX **  nd_boxes,
int  num_boxes,
const ND_BOX extent,
int  ndims,
double *  distribution 
)
static

Calculate how much a set of boxes is homogenously distributed or contentrated within one dimension, returning the range_quintile of of the overlap counts per cell in a uniform partition of the extent of the dimension.

A uniform distribution of counts will have a small range and will require few cells in a selectivity histogram. A diverse distribution of counts will have a larger range and require more cells in a selectivity histogram (to distinguish between areas of feature density and areas of feature sparseness. This measurement should help us identify cases like X/Y/Z data where there is lots of variability in density in X/Y (diversely in a multi-kilometer range) and far less in Z (in a few-hundred meter range).

Definition at line 769 of file gserialized_estimate.c.

References ND_BOX_T::max, MAX_DIMENSION_WIDTH, ND_BOX_T::min, NUM_BINS, and range_quintile().

Referenced by compute_gserialized_stats_mode().

770 {
771  int d, i, k, range;
772  int counts[NUM_BINS];
773  double smin, smax; /* Spatial min, spatial max */
774  double swidth; /* Spatial width of dimension */
775 #if POSTGIS_DEBUG_LEVEL >= 3
776  double average, sdev, sdev_ratio;
777 #endif
778  int bmin, bmax; /* Bin min, bin max */
779  const ND_BOX *ndb;
780 
781  /* For each dimension... */
782  for ( d = 0; d < ndims; d++ )
783  {
784  /* Initialize counts for this dimension */
785  memset(counts, 0, sizeof(counts));
786 
787  smin = extent->min[d];
788  smax = extent->max[d];
789  swidth = smax - smin;
790 
791  /* Don't try and calculate distribution of overly narrow */
792  /* or overly wide dimensions. Here we're being pretty geographical, */
793  /* expecting "normal" planar or geographic coordinates. */
794  /* Otherwise we have to "handle" +/- Inf bounded features and */
795  /* the assumptions needed for that are as bad as this hack. */
796  if ( swidth < MIN_DIMENSION_WIDTH || swidth > MAX_DIMENSION_WIDTH )
797  {
798  distribution[d] = 0;
799  continue;
800  }
801 
802  /* Sum up the overlaps of each feature with the dimensional bins */
803  for ( i = 0; i < num_boxes; i++ )
804  {
805  double minoffset, maxoffset;
806 
807  /* Skip null entries */
808  ndb = nd_boxes[i];
809  if ( ! ndb ) continue;
810 
811  /* Where does box fall relative to the working range */
812  minoffset = ndb->min[d] - smin;
813  maxoffset = ndb->max[d] - smin;
814 
815  /* Skip boxes that are outside our working range */
816  if ( minoffset < 0 || minoffset > swidth ||
817  maxoffset < 0 || maxoffset > swidth )
818  {
819  continue;
820  }
821 
822  /* What bins does this range correspond to? */
823  bmin = floor(NUM_BINS * minoffset / swidth);
824  bmax = floor(NUM_BINS * maxoffset / swidth);
825 
826  /* Should only happen when maxoffset==swidth */
827  bmax = bmax >= NUM_BINS ? NUM_BINS-1 : bmax;
828 
829  POSTGIS_DEBUGF(4, " dimension %d, feature %d: bin %d to bin %d", d, i, bmin, bmax);
830 
831  /* Increment the counts in all the bins this feature overlaps */
832  for ( k = bmin; k <= bmax; k++ )
833  {
834  counts[k] += 1;
835  }
836 
837  }
838 
839  /* How dispersed is the distribution of features across bins? */
840  range = range_quintile(counts, NUM_BINS);
841 
842 #if POSTGIS_DEBUG_LEVEL >= 3
843  average = avg(counts, NUM_BINS);
844  sdev = stddev(counts, NUM_BINS);
845  sdev_ratio = sdev/average;
846 
847  POSTGIS_DEBUGF(3, " dimension %d: range = %d", d, range);
848  POSTGIS_DEBUGF(3, " dimension %d: average = %.6g", d, average);
849  POSTGIS_DEBUGF(3, " dimension %d: stddev = %.6g", d, sdev);
850  POSTGIS_DEBUGF(3, " dimension %d: stddev_ratio = %.6g", d, sdev_ratio);
851 #endif
852 
853  distribution[d] = range;
854  }
855 
856  return true;
857 }
#define NUM_BINS
static int range_quintile(int *vals, int nvals)
The difference between the fourth and first quintile values, the "inter-quintile range".
float4 max[ND_DIMS]
float4 min[ND_DIMS]
#define MAX_DIMENSION_WIDTH
Maximum width of a dimension that we&#39;ll bother trying to compute statistics on.
N-dimensional box type for calculations, to avoid doing explicit axis conversions from GBOX in all ca...
Here is the call graph for this function:
Here is the caller graph for this function: