| 63 | |
| 64 | template <typename VectorType> |
| 65 | static void removeOneLeastError(VectorType *_poly) { |
| 66 | bitset<256> keep; |
| 67 | VectorType &poly = *_poly; |
| 68 | keep.assign(poly.size(), 1); |
| 69 | const int n = poly.size(); |
| 70 | NumberT bestErr = FL_INFINITY_DOUBLE; |
| 71 | int bestIdx = -1; |
| 72 | |
| 73 | // scan all interior “alive” points |
| 74 | for (int i = 1; i + 1 < n; ++i) { |
| 75 | if (!keep[i]) |
| 76 | continue; |
| 77 | |
| 78 | // find previous alive |
| 79 | int L = i - 1; |
| 80 | while (L >= 0 && !keep[L]) |
| 81 | --L; |
| 82 | // find next alive |
| 83 | int R = i + 1; |
| 84 | while (R < n && !keep[R]) |
| 85 | ++R; |
| 86 | |
| 87 | if (L < 0 || R >= n) |
| 88 | continue; // endpoints |
| 89 | |
| 90 | // compute perp‐distance² to the chord L→R |
| 91 | NumberT dx = poly[R].x - poly[L].x; |
| 92 | NumberT dy = poly[R].y - poly[L].y; |
| 93 | NumberT vx = poly[i].x - poly[L].x; |
| 94 | NumberT vy = poly[i].y - poly[L].y; |
| 95 | NumberT len2 = dx * dx + dy * dy; |
| 96 | NumberT err = |
| 97 | (len2 > NumberT(0)) |
| 98 | ? ((dx * vy - dy * vx) * (dx * vy - dy * vx) / len2) |
| 99 | : (vx * vx + vy * vy); |
| 100 | |
| 101 | if (err < bestErr) { |
| 102 | bestErr = err; |
| 103 | bestIdx = i; |
| 104 | } |
| 105 | } |
| 106 | |
| 107 | // now “remove” that one point |
| 108 | if (bestIdx >= 0) |
| 109 | // keep[bestIdx] = 0; |
| 110 | poly.erase(poly.begin() + bestIdx); |
| 111 | } |
| 112 | |
| 113 | private: |
| 114 | template <typename VectorType> void simplifyInplaceT(VectorType *polyLine) { |