simplifyInternal()

template<typename NumberT = float>

void fl::LineSimplifier< NumberT >::simplifyInternal ( const fl::span< const Point > & polyLine )

inlineprivate

Definition at line 130 of file line_simplification.h.

                                                               {
        mSimplified.clear();
        int n = polyLine.size();
        if (n < 2) {
            if (n) {
                mSimplified.assign(polyLine.data(), polyLine.data() + n);
            }
            return;
        }
        const NumberT minDist2 = mMinDistance * mMinDistance;
 
        // mark all points as “kept” initially
        keep.assign(n, 1);
 
        // explicit stack of (start,end) index pairs
        indexStack.clear();
        // indexStack.reserve(64);
        indexStack.push_back({0, n - 1});
 
        // process segments
        while (!indexStack.empty()) {
            // auto [i0, i1] = indexStack.back();
            auto pair = indexStack.back();
            int i0 = pair.first;
            int i1 = pair.second;
            indexStack.pop_back();
            const bool has_interior = (i1 - i0) > 1;
            if (!has_interior) {
                // no interior points, just keep the endpoints
                // keep[i0] = 1;
                // keep[i1] = 1;
                continue;
            }
 
            // find farthest point in [i0+1 .. i1-1]
            NumberT maxDist2 = 0;
            int split = i0;
            for (int i = i0 + 1; i < i1; ++i) {
                if (!keep[i])
                    continue;
                NumberT d2 = PerpendicularDistance2(polyLine[i], polyLine[i0],
                                                    polyLine[i1]);
 
                // FL_WARN("Perpendicular distance2 between "
                //              << polyLine[i] << " and " << polyLine[i0]
                //              << " and " << polyLine[i1] << " is " << d2);
 
                if (d2 > maxDist2) {
                    maxDist2 = d2;
                    split = i;
                }
            }
 
            if (maxDist2 > minDist2) {
                // need to keep that split point and recurse on both halves
                indexStack.push_back({i0, split});
                indexStack.push_back({split, i1});
            } else {
                // drop all interior points in this segment
                for (int i = i0 + 1; i < i1; ++i) {
                    keep[i] = 0;
                }
            }
        }
 
        // collect survivors
        mSimplified.clear();
        mSimplified.reserve(n);
        for (int i = 0; i < n; ++i) {
            if (keep[i])
                mSimplified.push_back(polyLine[i]);
        }
    }

References fl::span< T, Extent >::data(), fl::pair< T1, T2 >::first, indexStack, keep, mMinDistance, mSimplified, PerpendicularDistance2(), fl::pair< T1, T2 >::second, and fl::span< T, Extent >::size().

Referenced by simplifyT().

Here is the call graph for this function:

Here is the caller graph for this function: