PostGIS  3.0.0dev-r@@SVN_REVISION@@

◆ g_box_consider_split()

static void g_box_consider_split ( ConsiderSplitContext context,
int  dimNum,
float  rightLower,
int  minLeftCount,
float  leftUpper,
int  maxLeftCount 
)
inlinestatic

Definition at line 1683 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().

1686 {
1687  int leftCount,
1688  rightCount;
1689  float4 ratio,
1690  overlap;
1691  float range;
1692 
1693  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1694  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1695  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1696 
1697  /*
1698  * Calculate entries distribution ratio assuming most uniform distribution
1699  * of common entries.
1700  */
1701  if (minLeftCount >= (context->entriesCount + 1) / 2)
1702  {
1703  leftCount = minLeftCount;
1704  }
1705  else
1706  {
1707  if (maxLeftCount <= context->entriesCount / 2)
1708  leftCount = maxLeftCount;
1709  else
1710  leftCount = context->entriesCount / 2;
1711  }
1712  rightCount = context->entriesCount - leftCount;
1713 
1714  /*
1715  * Ratio of split - quotient between size of lesser group and total
1716  * entries count.
1717  */
1718  ratio = ((float4) Min(leftCount, rightCount)) /
1719  ((float4) context->entriesCount);
1720 
1721  if (ratio > LIMIT_RATIO)
1722  {
1723  bool selectthis = false;
1724 
1725  /*
1726  * The ratio is acceptable, so compare current split with previously
1727  * selected one. Between splits of one dimension we search for minimal
1728  * overlap (allowing negative values) and minimal ration (between same
1729  * overlaps. We switch dimension if find less overlap (non-negative)
1730  * or less range with same overlap.
1731  */
1732  if (dimNum == 0)
1733  range = context->boundingBox.xmax - context->boundingBox.xmin;
1734  else
1735  range = context->boundingBox.ymax - context->boundingBox.ymin;
1736 
1737  overlap = (leftUpper - rightLower) / range;
1738 
1739  /* If there is no previous selection, select this */
1740  if (context->first)
1741  selectthis = true;
1742  else if (context->dim == dimNum)
1743  {
1744  /*
1745  * Within the same dimension, choose the new split if it has a
1746  * smaller overlap, or same overlap but better ratio.
1747  */
1748  if (overlap < context->overlap ||
1749  (overlap == context->overlap && ratio > context->ratio))
1750  selectthis = true;
1751  }
1752  else
1753  {
1754  /*
1755  * Across dimensions, choose the new split if it has a smaller
1756  * *non-negative* overlap, or same *non-negative* overlap but
1757  * bigger range. This condition differs from the one described in
1758  * the article. On the datasets where leaf MBRs don't overlap
1759  * themselves, non-overlapping splits (i.e. splits which have zero
1760  * *non-negative* overlap) are frequently possible. In this case
1761  * splits tends to be along one dimension, because most distant
1762  * non-overlapping splits (i.e. having lowest negative overlap)
1763  * appears to be in the same dimension as in the previous split.
1764  * Therefore MBRs appear to be very prolonged along another
1765  * dimension, which leads to bad search performance. Using range
1766  * as the second split criteria makes MBRs more quadratic. Using
1767  * *non-negative* overlap instead of overlap as the first split
1768  * criteria gives to range criteria a chance to matter, because
1769  * non-overlapping splits are equivalent in this criteria.
1770  */
1771  if (non_negative(overlap) < non_negative(context->overlap) ||
1772  (range > context->range &&
1773  non_negative(overlap) <= non_negative(context->overlap)))
1774  selectthis = true;
1775  }
1776 
1777  if (selectthis)
1778  {
1779  /* save information about selected split */
1780  context->first = false;
1781  context->ratio = ratio;
1782  context->range = range;
1783  context->overlap = overlap;
1784  context->rightLower = rightLower;
1785  context->leftUpper = leftUpper;
1786  context->dim = dimNum;
1787  POSTGIS_DEBUG(5, "split selected");
1788  }
1789  }
1790 }
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: