PostGIS  2.1.10dev-r@@SVN_REVISION@@
POINTARRAY* ptarray_simplify ( POINTARRAY inpts,
double  epsilon,
unsigned int  minpts 
)
Parameters
minptsminimun number of points to retain, if possible.

Definition at line 1495 of file ptarray.c.

References POINTARRAY::flags, FLAGS_GET_M, FLAGS_GET_Z, FLAGS_NDIMS, getPoint4d_p(), LW_FALSE, lwalloc(), LWDEBUG, LWDEBUGF, lwfree(), POINTARRAY::npoints, ptarray_append_point(), ptarray_construct_empty(), and ptarray_dp_findsplit().

Referenced by lwline_simplify(), and lwpoly_simplify().

1496 {
1497  int *stack; /* recursion stack */
1498  int sp=-1; /* recursion stack pointer */
1499  int p1, split;
1500  double dist;
1501  POINTARRAY *outpts;
1502  POINT4D pt;
1503 
1504  double eps_sqr = epsilon * epsilon;
1505 
1506  /* Allocate recursion stack */
1507  stack = lwalloc(sizeof(int)*inpts->npoints);
1508 
1509  p1 = 0;
1510  stack[++sp] = inpts->npoints-1;
1511 
1512  LWDEBUGF(2, "Input has %d pts and %d dims", inpts->npoints,
1513  FLAGS_NDIMS(inpts->flags));
1514 
1515  /* Allocate output POINTARRAY, and add first point. */
1516  outpts = ptarray_construct_empty(FLAGS_GET_Z(inpts->flags), FLAGS_GET_M(inpts->flags), inpts->npoints);
1517  getPoint4d_p(inpts, 0, &pt);
1518  ptarray_append_point(outpts, &pt, LW_FALSE);
1519 
1520  LWDEBUG(3, "Added P0 to simplified point array (size 1)");
1521 
1522  do
1523  {
1524 
1525  ptarray_dp_findsplit(inpts, p1, stack[sp], &split, &dist);
1526 
1527  LWDEBUGF(3, "Farthest point from P%d-P%d is P%d (dist. %g)", p1, stack[sp], split, dist);
1528 
1529  if (dist > eps_sqr || ( outpts->npoints+sp+1 < minpts && dist >= 0 ) )
1530  {
1531  LWDEBUGF(4, "Added P%d to stack (outpts:%d)", split, sp);
1532  stack[++sp] = split;
1533  }
1534  else
1535  {
1536  getPoint4d_p(inpts, stack[sp], &pt);
1537  LWDEBUGF(4, "npoints , minpoints %d %d", outpts->npoints, minpts);
1538  ptarray_append_point(outpts, &pt, LW_FALSE);
1539 
1540  LWDEBUGF(4, "Added P%d to simplified point array (size: %d)", stack[sp], outpts->npoints);
1541 
1542  p1 = stack[sp--];
1543  }
1544 
1545  LWDEBUGF(4, "stack pointer = %d", sp);
1546  }
1547  while (! (sp<0) );
1548 
1549  lwfree(stack);
1550  return outpts;
1551 }
void lwfree(void *mem)
Definition: lwutil.c:190
int npoints
Definition: liblwgeom.h:327
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
int ptarray_append_point(POINTARRAY *pa, const POINT4D *pt, int repeated_points)
Append a point to the end of an existing POINTARRAY If allow_duplicate is LW_TRUE, then a duplicate point will not be added.
Definition: ptarray.c:141
#define LW_FALSE
Definition: liblwgeom.h:52
uint8_t flags
Definition: liblwgeom.h:325
#define FLAGS_GET_Z(flags)
Macros for manipulating the 'flags' byte.
Definition: liblwgeom.h:106
POINTARRAY * ptarray_construct_empty(char hasz, char hasm, uint32_t maxpoints)
Create a new POINTARRAY with no points.
Definition: ptarray.c:57
#define FLAGS_GET_M(flags)
Definition: liblwgeom.h:107
void * lwalloc(size_t size)
Definition: lwutil.c:175
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
#define FLAGS_NDIMS(flags)
Definition: liblwgeom.h:118
int getPoint4d_p(const POINTARRAY *pa, int n, POINT4D *point)
Definition: lwgeom_api.c:217
static void ptarray_dp_findsplit(POINTARRAY *pts, int p1, int p2, int *split, double *dist)
Definition: ptarray.c:1446

Here is the call graph for this function:

Here is the caller graph for this function: