PostGIS  2.1.10dev-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 1404 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().

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