ptarray_dp_findsplit_in_place()

static uint32_t ptarray_dp_findsplit_in_place ( const POINTARRAY *  pts, uint32_t  it_first, uint32_t  it_last, double  max_distance_sqr  )

static

Definition at line 1745 of file ptarray.c.

{
        uint32_t split = it_first;
        if ((it_first - it_last) < 2)
                return it_first;
 
        const POINT2D *A = getPoint2d_cp(pts, it_first);
        const POINT2D *B = getPoint2d_cp(pts, it_last);
 
        if (distance2d_sqr_pt_pt(A, B) < DBL_EPSILON)
        {
                /* If p1 == p2, we can just calculate the distance from each point to A */
                for (uint32_t itk = it_first + 1; itk < it_last; itk++)
                {
                        const POINT2D *pk = getPoint2d_cp(pts, itk);
                        double distance_sqr = distance2d_sqr_pt_pt(pk, A);
                        if (distance_sqr > max_distance_sqr)
                        {
                                split = itk;
                                max_distance_sqr = distance_sqr;
                        }
                }
                return split;
        }
 
        /* This is based on distance2d_sqr_pt_seg, but heavily inlined here to avoid recalculations */
        double ba_x = (B->x - A->x);
        double ba_y = (B->y - A->y);
        double ab_length_sqr = (ba_x * ba_x + ba_y * ba_y);
        /* To avoid the division by ab_length_sqr in the 3rd path, we normalize here
         * and multiply in the first two paths [(dot_ac_ab < 0) and (> ab_length_sqr)] */
        max_distance_sqr *= ab_length_sqr;
        for (uint32_t itk = it_first + 1; itk < it_last; itk++)
        {
                const POINT2D *C = getPoint2d_cp(pts, itk);
                double distance_sqr;
                double ca_x = (C->x - A->x);
                double ca_y = (C->y - A->y);
                double dot_ac_ab = (ca_x * ba_x + ca_y * ba_y);
 
                if (dot_ac_ab <= 0.0)
                {
                        distance_sqr = distance2d_sqr_pt_pt(C, A) * ab_length_sqr;
                }
                else if (dot_ac_ab >= ab_length_sqr)
                {
                        distance_sqr = distance2d_sqr_pt_pt(C, B) * ab_length_sqr;
                }
                else
                {
                        double s_numerator = ca_x * ba_y - ca_y * ba_x;
                        distance_sqr = s_numerator * s_numerator; /* Missing division by ab_length_sqr on purpose */
                }
 
                if (distance_sqr > max_distance_sqr)
                {
                        split = itk;
                        max_distance_sqr = distance_sqr;
                }
        }
        return split;
}

References distance2d_sqr_pt_pt(), getPoint2d_cp(), POINT2D::x, and POINT2D::y.

Referenced by ptarray_simplify_in_place().

Here is the call graph for this function:

Here is the caller graph for this function: