PostGIS  2.5.2dev-r@@SVN_REVISION@@

◆ ptarray_simplify_in_place()

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

Definition at line 1576 of file ptarray.c.

References int_cmp(), lwalloc(), lwfree(), POINTARRAY::npoints, ptarray_copy_point(), and ptarray_dp_findsplit_in_place().

Referenced by lwgeom_simplify_in_place().

1577 {
1578  static size_t stack_size = 256;
1579  int *stack, *outlist; /* recursion stack */
1580  int stack_static[stack_size];
1581  int outlist_static[stack_size];
1582  int sp = -1; /* recursion stack pointer */
1583  int p1, split;
1584  uint32_t outn = 0;
1585  int pai = 0;
1586  uint32_t i;
1587  double dist;
1588  double eps_sqr = epsilon * epsilon;
1589 
1590  /* Do not try to simplify really short things */
1591  if (pa->npoints < 3) return;
1592 
1593  /* Only heap allocate book-keeping arrays if necessary */
1594  if (pa->npoints > stack_size)
1595  {
1596  stack = lwalloc(sizeof(int) * pa->npoints);
1597  outlist = lwalloc(sizeof(int) * pa->npoints);
1598  }
1599  else
1600  {
1601  stack = stack_static;
1602  outlist = outlist_static;
1603  }
1604 
1605  p1 = 0;
1606  stack[++sp] = pa->npoints-1;
1607 
1608  /* Add first point to output list */
1609  outlist[outn++] = 0;
1610  do
1611  {
1612  ptarray_dp_findsplit_in_place(pa, p1, stack[sp], &split, &dist);
1613 
1614  if ((dist > eps_sqr) || ((outn + sp+1 < minpts) && (dist >= 0)))
1615  {
1616  stack[++sp] = split;
1617  }
1618  else
1619  {
1620  outlist[outn++] = stack[sp];
1621  p1 = stack[sp--];
1622  }
1623  }
1624  while (!(sp<0));
1625 
1626  /* Put list of retained points into order */
1627  qsort(outlist, outn, sizeof(int), int_cmp);
1628  /* Copy retained points to front of array */
1629  for (i = 0; i < outn; i++)
1630  {
1631  int j = outlist[i];
1632  /* Indexes the same, means no copy required */
1633  if (j == pai)
1634  {
1635  pai++;
1636  continue;
1637  }
1638  /* Indexes different, copy value down */
1639  ptarray_copy_point(pa, j, pai++);
1640  }
1641 
1642  /* Adjust point count on array */
1643  pa->npoints = outn;
1644 
1645  /* Only free if arrays are on heap */
1646  if (stack != stack_static)
1647  lwfree(stack);
1648  if (outlist != outlist_static)
1649  lwfree(outlist);
1650 
1651  return;
1652 }
void lwfree(void *mem)
Definition: lwutil.c:244
void ptarray_copy_point(POINTARRAY *pa, uint32_t from, uint32_t to)
Definition: lwgeom_api.c:450
unsigned int uint32_t
Definition: uthash.h:78
static int int_cmp(const void *a, const void *b)
Definition: ptarray.c:1566
static void ptarray_dp_findsplit_in_place(const POINTARRAY *pts, int p1, int p2, int *split, double *dist)
Definition: ptarray.c:1519
void * lwalloc(size_t size)
Definition: lwutil.c:229
uint32_t npoints
Definition: liblwgeom.h:373
Here is the call graph for this function:
Here is the caller graph for this function: