PostGIS  2.5.0dev-r@@SVN_REVISION@@

◆ ptarray_simplify_in_place()

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

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

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