| 997 | } |
| 998 | |
| 999 | std::vector<std::vector<Point3d>> subtract(const std::vector<Point3d>& polygon, const std::vector<std::vector<Point3d>>& holes, double tol) { |
| 1000 | std::vector<std::vector<Point3d>> result; |
| 1001 | |
| 1002 | // convert vertices to boost rings |
| 1003 | std::vector<Point3d> allPoints; |
| 1004 | |
| 1005 | boost::optional<BoostPolygon> initialBoostPolygon = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol); |
| 1006 | if (!initialBoostPolygon) { |
| 1007 | return result; |
| 1008 | } |
| 1009 | |
| 1010 | std::vector<BoostPolygon> boostPolygons; |
| 1011 | boostPolygons.push_back(*initialBoostPolygon); |
| 1012 | |
| 1013 | for (const auto& hole : holes) { |
| 1014 | boost::optional<BoostPolygon> boostHole = nonIntersectingBoostPolygonFromVertices(hole, allPoints, tol); |
| 1015 | if (!boostHole) { |
| 1016 | return result; |
| 1017 | } |
| 1018 | |
| 1019 | std::vector<BoostPolygon> newBoostPolygons; |
| 1020 | |
| 1021 | for (const BoostPolygon& boostPolygon : boostPolygons) { |
| 1022 | std::vector<BoostPolygon> diffResult; |
| 1023 | boost::geometry::difference(boostPolygon, *boostHole, diffResult); |
| 1024 | newBoostPolygons.reserve(newBoostPolygons.size() + diffResult.size()); |
| 1025 | newBoostPolygons.insert(newBoostPolygons.end(), std::make_move_iterator(diffResult.begin()), std::make_move_iterator(diffResult.end())); |
| 1026 | } |
| 1027 | boostPolygons = std::move(newBoostPolygons); |
| 1028 | } |
| 1029 | |
| 1030 | // Remove the holes and spikes and convert back to our data types |
| 1031 | for (const BoostPolygon& boostPolygon : boostPolygons) { |
| 1032 | const BoostPolygon removedSpikes = removeSpikes(boostPolygon); |
| 1033 | const std::vector<BoostPolygon>& removedHoles = removeHoles(removedSpikes); |
| 1034 | result.reserve(result.size() + removedHoles.size()); |
| 1035 | for (const BoostPolygon& removedHole : removedHoles) { |
| 1036 | result.push_back(verticesFromBoostPolygon(removedHole, allPoints, tol)); |
| 1037 | } |
| 1038 | } |
| 1039 | |
| 1040 | return result; |
| 1041 | } |
| 1042 | |
| 1043 | bool selfIntersects(const std::vector<Point3d>& polygon, double tol) { |
| 1044 | // convert vertices to boost rings |