| 80 | // Values around 20 - 200 are reasonable. |
| 81 | template <typename DistanceFn, typename Iter, typename Out> |
| 82 | void SimplifyNearOptimal(int maxFalseLookAhead, Iter beg, Iter end, double epsilon, DistanceFn distFn, Out out) |
| 83 | { |
| 84 | int32_t const n = static_cast<int32_t>(end - beg); |
| 85 | if (n <= 2) |
| 86 | { |
| 87 | for (Iter it = beg; it != end; ++it) |
| 88 | out(*it); |
| 89 | return; |
| 90 | } |
| 91 | |
| 92 | std::vector<simpl::SimplifyOptimalRes> F(n); |
| 93 | F[n - 1] = simpl::SimplifyOptimalRes(n, 1); |
| 94 | for (int32_t i = n - 2; i >= 0; --i) |
| 95 | { |
| 96 | for (int32_t falseCount = 0, j = i + 1; j < n && falseCount < maxFalseLookAhead; ++j) |
| 97 | { |
| 98 | uint32_t const newPointCount = F[j].m_PointCount + 1; |
| 99 | if (newPointCount < F[i].m_PointCount) |
| 100 | { |
| 101 | if (simpl::MaxDistance(beg + i, beg + j, distFn).first < epsilon) |
| 102 | { |
| 103 | F[i].m_NextPoint = j; |
| 104 | F[i].m_PointCount = newPointCount; |
| 105 | } |
| 106 | else |
| 107 | { |
| 108 | ++falseCount; |
| 109 | } |
| 110 | } |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | for (int32_t i = 0; i < n; i = F[i].m_NextPoint) |
| 115 | out(*(beg + i)); |
| 116 | } |
| 117 | |
| 118 | // Additional points filter to use in simplification. |
| 119 | // SimplifyDP can produce points that define degenerate triangle. |