| 1157 | } |
| 1158 | |
| 1159 | std::vector<Point3d> simplify(const std::vector<Point3d>& vertices, bool removeCollinear, double tol) { |
| 1160 | std::vector<Point3d> allPoints; |
| 1161 | |
| 1162 | bool reversed = false; |
| 1163 | boost::optional<Vector3d> outwardNormal = getOutwardNormal(vertices); |
| 1164 | if (!outwardNormal) { |
| 1165 | return {}; |
| 1166 | } else if (outwardNormal->z() > 0) { |
| 1167 | reversed = true; |
| 1168 | } |
| 1169 | |
| 1170 | boost::optional<BoostPolygon> bp; |
| 1171 | if (reversed) { |
| 1172 | bp = boostPolygonFromVertices(reorderULC(reverse(vertices)), allPoints, tol); |
| 1173 | } else { |
| 1174 | bp = boostPolygonFromVertices(reorderULC(vertices), allPoints, tol); |
| 1175 | } |
| 1176 | |
| 1177 | if (!bp) { |
| 1178 | return {}; |
| 1179 | } |
| 1180 | |
| 1181 | boost::geometry::remove_spikes(*bp); |
| 1182 | |
| 1183 | BoostPolygon out; |
| 1184 | |
| 1185 | // this uses the Douglas-Peucker algorithm with a max difference of 0 so no non-collinear points will be removed |
| 1186 | // if we want to allow this algorithm to be called with a non-zero value I suggest naming it "approximate" or something |
| 1187 | if (!removeCollinear) { |
| 1188 | boost::geometry::simplify(*bp, out, 0.0); |
| 1189 | } else { |
| 1190 | boost::geometry::simplify(*bp, out, tol); // points within tol would already be merged |
| 1191 | } |
| 1192 | |
| 1193 | std::vector<Point3d> tmp = verticesFromBoostPolygon(out, allPoints, tol, removeCollinear); |
| 1194 | |
| 1195 | if (reversed) { |
| 1196 | tmp = reorderULC(reverse(tmp)); |
| 1197 | } else { |
| 1198 | tmp = reorderULC(tmp); |
| 1199 | } |
| 1200 | |
| 1201 | if (removeCollinear) { |
| 1202 | // collinear points already removed |
| 1203 | return tmp; |
| 1204 | } |
| 1205 | |
| 1206 | if (tmp.empty()) { |
| 1207 | return tmp; |
| 1208 | } |
| 1209 | |
| 1210 | // we want to add back in all the unique points, have to put them in the right place |
| 1211 | std::set<size_t> pointsToAdd; |
| 1212 | for (size_t i = 0; i < allPoints.size(); ++i) { |
| 1213 | bool found = false; |
| 1214 | for (const auto& tmpPoint : tmp) { |
| 1215 | if (getDistance(tmpPoint, allPoints[i]) < tol) { |
| 1216 | found = true; |