ptarray_simplify_in_place()

void ptarray_simplify_in_place	(	POINTARRAY *	pa,
		double	tolerance,
		uint32_t	minpts
	)

Parameters

minpts

minimum number of points to retain, if possible.

Definition at line 1844 of file ptarray.c.

{
        /* Do not try to simplify really short things */
        if (pa->npoints < 3 || pa->npoints <= minpts)
                return;
 
        if (tolerance == 0 && minpts <= 2)
        {
                ptarray_simplify_in_place_tolerance0(pa);
                return;
        }
 
        /* We use this array to keep track of the points we are keeping, so
         * we store just TRUE / FALSE in their position */
        uint8_t *kept_points = lwalloc(sizeof(uint8_t) * pa->npoints);
        memset(kept_points, LW_FALSE, sizeof(uint8_t) * pa->npoints);
        kept_points[0] = LW_TRUE;
        kept_points[pa->npoints - 1] = LW_TRUE;
        uint32_t keptn = 2;
 
        /* We use this array as a stack to store the iterators that we are going to need
         * in the following steps.
         * This is ~10% faster than iterating over @kept_points looking for them
         */
        uint32_t *iterator_stack = lwalloc(sizeof(uint32_t) * pa->npoints);
        iterator_stack[0] = 0;
        uint32_t iterator_stack_size = 1;
 
        uint32_t it_first = 0;
        uint32_t it_last = pa->npoints - 1;
 
        const double tolerance_sqr = tolerance * tolerance;
        /* For the first @minpts points we ignore the tolerance */
        double it_tol = keptn >= minpts ? tolerance_sqr : -1.0;
 
        while (iterator_stack_size)
        {
                uint32_t split = ptarray_dp_findsplit_in_place(pa, it_first, it_last, it_tol);
                if (split == it_first)
                {
                        it_first = it_last;
                        it_last = iterator_stack[--iterator_stack_size];
                }
                else
                {
                        kept_points[split] = LW_TRUE;
                        keptn++;
 
                        iterator_stack[iterator_stack_size++] = it_last;
                        it_last = split;
                        it_tol = keptn >= minpts ? tolerance_sqr : -1.0;
                }
        }
 
        const size_t pt_size = ptarray_point_size(pa);
        /* The first point is already in place, so we don't need to copy it */
        size_t kept_it = 1;
        if (keptn == 2)
        {
                /* If there are 2 points remaining, it has to be first and last as
                 * we added those at the start */
                memcpy(pa->serialized_pointlist + pt_size * kept_it,
                       pa->serialized_pointlist + pt_size * (pa->npoints - 1),
                       pt_size);
        }
        else if (pa->npoints != keptn) /* We don't need to move any points if we are keeping them all */
        {
                for (uint32_t i = 1; i < pa->npoints; i++)
                {
                        if (kept_points[i])
                        {
                                memcpy(pa->serialized_pointlist + pt_size * kept_it,
                                       pa->serialized_pointlist + pt_size * i,
                                       pt_size);
                                kept_it++;
                        }
                }
        }
        pa->npoints = keptn;
 
        lwfree(kept_points);
        lwfree(iterator_stack);
}

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(), and test_ptarray_simplify().

Here is the call graph for this function:

Here is the caller graph for this function: