PostGIS  2.2.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 1430 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().

1433 {
1434  int leftCount,
1435  rightCount;
1436  float4 ratio,
1437  overlap;
1438  float range;
1439 
1440  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1441  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1442  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1443 
1444  /*
1445  * Calculate entries distribution ratio assuming most uniform distribution
1446  * of common entries.
1447  */
1448  if (minLeftCount >= (context->entriesCount + 1) / 2)
1449  {
1450  leftCount = minLeftCount;
1451  }
1452  else
1453  {
1454  if (maxLeftCount <= context->entriesCount / 2)
1455  leftCount = maxLeftCount;
1456  else
1457  leftCount = context->entriesCount / 2;
1458  }
1459  rightCount = context->entriesCount - leftCount;
1460 
1461  /*
1462  * Ratio of split - quotient between size of lesser group and total
1463  * entries count.
1464  */
1465  ratio = ((float4) Min(leftCount, rightCount)) /
1466  ((float4) context->entriesCount);
1467 
1468  if (ratio > LIMIT_RATIO)
1469  {
1470  bool selectthis = false;
1471 
1472  /*
1473  * The ratio is acceptable, so compare current split with previously
1474  * selected one. Between splits of one dimension we search for minimal
1475  * overlap (allowing negative values) and minimal ration (between same
1476  * overlaps. We switch dimension if find less overlap (non-negative)
1477  * or less range with same overlap.
1478  */
1479  if (dimNum == 0)
1480  range = context->boundingBox.xmax - context->boundingBox.xmin;
1481  else
1482  range = context->boundingBox.ymax - context->boundingBox.ymin;
1483 
1484  overlap = (leftUpper - rightLower) / range;
1485 
1486  /* If there is no previous selection, select this */
1487  if (context->first)
1488  selectthis = true;
1489  else if (context->dim == dimNum)
1490  {
1491  /*
1492  * Within the same dimension, choose the new split if it has a
1493  * smaller overlap, or same overlap but better ratio.
1494  */
1495  if (overlap < context->overlap ||
1496  (overlap == context->overlap && ratio > context->ratio))
1497  selectthis = true;
1498  }
1499  else
1500  {
1501  /*
1502  * Across dimensions, choose the new split if it has a smaller
1503  * *non-negative* overlap, or same *non-negative* overlap but
1504  * bigger range. This condition differs from the one described in
1505  * the article. On the datasets where leaf MBRs don't overlap
1506  * themselves, non-overlapping splits (i.e. splits which have zero
1507  * *non-negative* overlap) are frequently possible. In this case
1508  * splits tends to be along one dimension, because most distant
1509  * non-overlapping splits (i.e. having lowest negative overlap)
1510  * appears to be in the same dimension as in the previous split.
1511  * Therefore MBRs appear to be very prolonged along another
1512  * dimension, which leads to bad search performance. Using range
1513  * as the second split criteria makes MBRs more quadratic. Using
1514  * *non-negative* overlap instead of overlap as the first split
1515  * criteria gives to range criteria a chance to matter, because
1516  * non-overlapping splits are equivalent in this criteria.
1517  */
1518  if (non_negative(overlap) < non_negative(context->overlap) ||
1519  (range > context->range &&
1520  non_negative(overlap) <= non_negative(context->overlap)))
1521  selectthis = true;
1522  }
1523 
1524  if (selectthis)
1525  {
1526  /* save information about selected split */
1527  context->first = false;
1528  context->ratio = ratio;
1529  context->range = range;
1530  context->overlap = overlap;
1531  context->rightLower = rightLower;
1532  context->leftUpper = leftUpper;
1533  context->dim = dimNum;
1534  POSTGIS_DEBUG(5, "split selected");
1535  }
1536  }
1537 }
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: