PostGIS  3.1.6dev-r@@SVN_REVISION@@

◆ ptarray_simplify_in_place()

void ptarray_simplify_in_place ( POINTARRAY pa,
double  tolerance,
uint32_t  minpts 
)
Parameters
minptsminimum number of points to retain, if possible.

Definition at line 1638 of file ptarray.c.

1639 {
1640  /* Do not try to simplify really short things */
1641  if (pa->npoints < 3 || pa->npoints <= minpts)
1642  return;
1643 
1644  if (tolerance == 0 && minpts <= 2)
1645  {
1647  return;
1648  }
1649 
1650  /* We use this array to keep track of the points we are keeping, so
1651  * we store just TRUE / FALSE in their position */
1652  uint8_t *kept_points = lwalloc(sizeof(uint8_t) * pa->npoints);
1653  memset(kept_points, LW_FALSE, sizeof(uint8_t) * pa->npoints);
1654  kept_points[0] = LW_TRUE;
1655  kept_points[pa->npoints - 1] = LW_TRUE;
1656  uint32_t keptn = 2;
1657 
1658  /* We use this array as a stack to store the iterators that we are going to need
1659  * in the following steps.
1660  * This is ~10% faster than iterating over @kept_points looking for them
1661  */
1662  uint32_t *iterator_stack = lwalloc(sizeof(uint32_t) * pa->npoints);
1663  iterator_stack[0] = 0;
1664  uint32_t iterator_stack_size = 1;
1665 
1666  uint32_t it_first = 0;
1667  uint32_t it_last = pa->npoints - 1;
1668 
1669  const double tolerance_sqr = tolerance * tolerance;
1670  /* For the first @minpts points we ignore the tolerance */
1671  double it_tol = keptn >= minpts ? tolerance_sqr : -1.0;
1672 
1673  while (iterator_stack_size)
1674  {
1675  uint32_t split = ptarray_dp_findsplit_in_place(pa, it_first, it_last, it_tol);
1676  if (split == it_first)
1677  {
1678  it_first = it_last;
1679  it_last = iterator_stack[--iterator_stack_size];
1680  }
1681  else
1682  {
1683  kept_points[split] = LW_TRUE;
1684  keptn++;
1685 
1686  iterator_stack[iterator_stack_size++] = it_last;
1687  it_last = split;
1688  it_tol = keptn >= minpts ? tolerance_sqr : -1.0;
1689  }
1690  }
1691 
1692  const size_t pt_size = ptarray_point_size(pa);
1693  /* The first point is already in place, so we don't need to copy it */
1694  size_t kept_it = 1;
1695  if (keptn == 2)
1696  {
1697  /* If there are 2 points remaining, it has to be first and last as
1698  * we added those at the start */
1699  memcpy(pa->serialized_pointlist + pt_size * kept_it,
1700  pa->serialized_pointlist + pt_size * (pa->npoints - 1),
1701  pt_size);
1702  }
1703  else if (pa->npoints != keptn) /* We don't need to move any points if we are keeping them all */
1704  {
1705  for (uint32_t i = 1; i < pa->npoints; i++)
1706  {
1707  if (kept_points[i])
1708  {
1709  memcpy(pa->serialized_pointlist + pt_size * kept_it,
1710  pa->serialized_pointlist + pt_size * i,
1711  pt_size);
1712  kept_it++;
1713  }
1714  }
1715  }
1716  pa->npoints = keptn;
1717 
1718  lwfree(kept_points);
1719  lwfree(iterator_stack);
1720 }
#define LW_FALSE
Definition: liblwgeom.h:108
void lwfree(void *mem)
Definition: lwutil.c:242
void * lwalloc(size_t size)
Definition: lwutil.c:227
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:107
static size_t ptarray_point_size(const POINTARRAY *pa)
Definition: lwinline.h:58
static uint32_t ptarray_dp_findsplit_in_place(const POINTARRAY *pts, uint32_t it_first, uint32_t it_last, double max_distance_sqr)
Definition: ptarray.c:1531
static void ptarray_simplify_in_place_tolerance0(POINTARRAY *pa)
Definition: ptarray.c:1596
uint32_t npoints
Definition: liblwgeom.h:441
uint8_t * serialized_pointlist
Definition: liblwgeom.h:448

References LW_FALSE, LW_TRUE, lwalloc(), lwfree(), POINTARRAY::npoints, ptarray_dp_findsplit_in_place(), ptarray_point_size(), ptarray_simplify_in_place_tolerance0(), and POINTARRAY::serialized_pointlist.

Referenced by lwgeom_simplify_in_place().

Here is the call graph for this function:
Here is the caller graph for this function: