PostGIS  2.3.7dev-r@@SVN_REVISION@@
static void g_box_consider_split ( ConsiderSplitContext context,
int  dimNum,
float  rightLower,
int  minLeftCount,
float  leftUpper,
int  maxLeftCount 
)
inlinestatic

Definition at line 1535 of file gserialized_gist_2d.c.

References ConsiderSplitContext::boundingBox, ConsiderSplitContext::dim, ConsiderSplitContext::entriesCount, ConsiderSplitContext::first, ConsiderSplitContext::leftUpper, LIMIT_RATIO, non_negative(), ConsiderSplitContext::overlap, ConsiderSplitContext::range, ConsiderSplitContext::ratio, and ConsiderSplitContext::rightLower.

Referenced by gserialized_gist_picksplit_2d().

1538 {
1539  int leftCount,
1540  rightCount;
1541  float4 ratio,
1542  overlap;
1543  float range;
1544 
1545  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1546  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1547  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1548 
1549  /*
1550  * Calculate entries distribution ratio assuming most uniform distribution
1551  * of common entries.
1552  */
1553  if (minLeftCount >= (context->entriesCount + 1) / 2)
1554  {
1555  leftCount = minLeftCount;
1556  }
1557  else
1558  {
1559  if (maxLeftCount <= context->entriesCount / 2)
1560  leftCount = maxLeftCount;
1561  else
1562  leftCount = context->entriesCount / 2;
1563  }
1564  rightCount = context->entriesCount - leftCount;
1565 
1566  /*
1567  * Ratio of split - quotient between size of lesser group and total
1568  * entries count.
1569  */
1570  ratio = ((float4) Min(leftCount, rightCount)) /
1571  ((float4) context->entriesCount);
1572 
1573  if (ratio > LIMIT_RATIO)
1574  {
1575  bool selectthis = false;
1576 
1577  /*
1578  * The ratio is acceptable, so compare current split with previously
1579  * selected one. Between splits of one dimension we search for minimal
1580  * overlap (allowing negative values) and minimal ration (between same
1581  * overlaps. We switch dimension if find less overlap (non-negative)
1582  * or less range with same overlap.
1583  */
1584  if (dimNum == 0)
1585  range = context->boundingBox.xmax - context->boundingBox.xmin;
1586  else
1587  range = context->boundingBox.ymax - context->boundingBox.ymin;
1588 
1589  overlap = (leftUpper - rightLower) / range;
1590 
1591  /* If there is no previous selection, select this */
1592  if (context->first)
1593  selectthis = true;
1594  else if (context->dim == dimNum)
1595  {
1596  /*
1597  * Within the same dimension, choose the new split if it has a
1598  * smaller overlap, or same overlap but better ratio.
1599  */
1600  if (overlap < context->overlap ||
1601  (overlap == context->overlap && ratio > context->ratio))
1602  selectthis = true;
1603  }
1604  else
1605  {
1606  /*
1607  * Across dimensions, choose the new split if it has a smaller
1608  * *non-negative* overlap, or same *non-negative* overlap but
1609  * bigger range. This condition differs from the one described in
1610  * the article. On the datasets where leaf MBRs don't overlap
1611  * themselves, non-overlapping splits (i.e. splits which have zero
1612  * *non-negative* overlap) are frequently possible. In this case
1613  * splits tends to be along one dimension, because most distant
1614  * non-overlapping splits (i.e. having lowest negative overlap)
1615  * appears to be in the same dimension as in the previous split.
1616  * Therefore MBRs appear to be very prolonged along another
1617  * dimension, which leads to bad search performance. Using range
1618  * as the second split criteria makes MBRs more quadratic. Using
1619  * *non-negative* overlap instead of overlap as the first split
1620  * criteria gives to range criteria a chance to matter, because
1621  * non-overlapping splits are equivalent in this criteria.
1622  */
1623  if (non_negative(overlap) < non_negative(context->overlap) ||
1624  (range > context->range &&
1625  non_negative(overlap) <= non_negative(context->overlap)))
1626  selectthis = true;
1627  }
1628 
1629  if (selectthis)
1630  {
1631  /* save information about selected split */
1632  context->first = false;
1633  context->ratio = ratio;
1634  context->range = range;
1635  context->overlap = overlap;
1636  context->rightLower = rightLower;
1637  context->leftUpper = leftUpper;
1638  context->dim = dimNum;
1639  POSTGIS_DEBUG(5, "split selected");
1640  }
1641  }
1642 }
static float non_negative(float val)
#define LIMIT_RATIO

Here is the call graph for this function:

Here is the caller graph for this function: