src/utilities/geometry/Intersection.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*********************************************************************************************************************** | ||
| 2 | * OpenStudio(R), Copyright (c) Alliance for Energy Innovation, LLC. | ||
| 3 | * See also https://openstudio.net/license | ||
| 4 | ***********************************************************************************************************************/ | ||
| 5 | |||
| 6 | #include "Geometry.hpp" | ||
| 7 | #include "Vector3d.hpp" | ||
| 8 | #include "Intersection.hpp" | ||
| 9 | #include "../data/Matrix.hpp" | ||
| 10 | #include "../core/Assert.hpp" | ||
| 11 | #include "../core/ContainersMove.hpp" | ||
| 12 | #include "../core/Logger.hpp" | ||
| 13 | |||
| 14 | #undef BOOST_UBLAS_TYPE_CHECK | ||
| 15 | #if defined(_MSC_VER) | ||
| 16 | # pragma warning(push) | ||
| 17 | # pragma warning(disable : 4244) | ||
| 18 | #endif | ||
| 19 | #include <boost/geometry.hpp> | ||
| 20 | #include <boost/geometry/geometry.hpp> | ||
| 21 | #include <boost/geometry/geometries/point_xy.hpp> | ||
| 22 | #include <boost/geometry/geometries/polygon.hpp> | ||
| 23 | #include <boost/geometry/geometries/ring.hpp> | ||
| 24 | #include <boost/geometry/geometries/multi_polygon.hpp> | ||
| 25 | #include <boost/geometry/geometries/adapted/boost_tuple.hpp> | ||
| 26 | #include <boost/geometry/strategies/cartesian/point_in_poly_franklin.hpp> | ||
| 27 | #include <boost/geometry/strategies/cartesian/point_in_poly_crossings_multiply.hpp> | ||
| 28 | #include <boost/geometry/algorithms/within.hpp> | ||
| 29 | #include <boost/geometry/algorithms/simplify.hpp> | ||
| 30 | #include <boost/geometry/policies/robustness/get_rescale_policy.hpp> | ||
| 31 | #include <boost/geometry/policies/robustness/robust_point_type.hpp> | ||
| 32 | #if defined(_MSC_VER) | ||
| 33 | # pragma warning(pop) | ||
| 34 | #endif | ||
| 35 | |||
| 36 | #include <algorithm> | ||
| 37 | #include <cmath> | ||
| 38 | #include <iterator> | ||
| 39 | |||
| 40 | using coordinate_type = double; | ||
| 41 | using BoostPoint = boost::geometry::model::d2::point_xy<double>; | ||
| 42 | using BoostPolygon = boost::geometry::model::polygon<BoostPoint>; | ||
| 43 | using BoostRing = boost::geometry::model::ring<BoostPoint>; | ||
| 44 | using BoostMultiPolygon = boost::geometry::model::multi_polygon<BoostPolygon>; | ||
| 45 | |||
| 46 | #include <polypartition/polypartition.h> | ||
| 47 | |||
| 48 | namespace openstudio { | ||
| 49 | |||
| 50 | // Private implementation functions | ||
| 51 | |||
| 52 | // Boost 1.73.0 has this bit in has_self_intersections.hpp: | ||
| 53 | // | ||
| 54 | // For backward compatibility | ||
| 55 | // template <typename Geometry> | ||
| 56 | // inline bool has_self_intersections(Geometry const& geometry, bool throw_on_self_intersection = true) { | ||
| 57 | // typedef typename geometry::point_type<Geometry>::type point_type; | ||
| 58 | // typedef typename geometry::rescale_policy_type<point_type>::type rescale_policy_type; | ||
| 59 | |||
| 60 | // typename strategy::intersection::services::default_strategy<typename cs_tag<Geometry>::type>::type strategy; | ||
| 61 | |||
| 62 | // rescale_policy_type robust_policy = geometry::get_rescale_policy<rescale_policy_type>(geometry, strategy); | ||
| 63 | |||
| 64 | // return has_self_intersections(geometry, strategy, robust_policy, throw_on_self_intersection); | ||
| 65 | // } | ||
| 66 | |||
| 67 | // For backward compatibility | ||
| 68 | template <typename Geometry> | ||
| 69 | 94624 | inline bool has_self_intersections(Geometry const& geometry, bool throw_on_self_intersection = true) { | |
| 70 | using point_type = typename boost::geometry::point_type<Geometry>::type; | ||
| 71 | using rescale_policy_type = typename boost::geometry::rescale_policy_type<point_type>::type; | ||
| 72 | |||
| 73 | typename boost::geometry::strategies::relate::services::default_strategy<Geometry, Geometry>::type const strategy; | ||
| 74 | |||
| 75 | // typename boost::geometry::strategy::intersection::services::default_strategy<typename boost::geometry::cs_tag<Geometry>::type>::type strategy; | ||
| 76 | |||
| 77 |
2/2bool openstudio::has_self_intersections<boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> >(boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> const&, bool):
✓ Branch 1 taken 14272 times.
bool openstudio::has_self_intersections<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >(boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> const&, bool):
✓ Branch 1 taken 80352 times.
|
94624 | auto robust_policy = boost::geometry::get_rescale_policy<rescale_policy_type>(geometry, strategy); |
| 78 | |||
| 79 |
2/2bool openstudio::has_self_intersections<boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> >(boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::vector, std::allocator, std::allocator> const&, bool):
✓ Branch 1 taken 14264 times.
bool openstudio::has_self_intersections<boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> >(boost::geometry::model::ring<boost::geometry::model::d2::point_xy<double, boost::geometry::cs::cartesian>, true, true, std::vector, std::allocator> const&, bool):
✓ Branch 1 taken 80352 times.
|
189240 | return boost::geometry::detail::overlay::has_self_intersections(geometry, strategy, robust_policy, throw_on_self_intersection); |
| 80 | } | ||
| 81 | |||
| 82 | // Some operators for Boost data types that are useful for extra logging | ||
| 83 | ✗ | std::ostream& operator<<(std::ostream& os, const BoostRing& boostRing) { | |
| 84 | ✗ | os << "["; | |
| 85 | ✗ | for (unsigned int i = 0; i < boostRing.size(); i++) { | |
| 86 | ✗ | os << "{"; | |
| 87 | ✗ | os << R"("X":)" << boostRing[i].x() << ","; | |
| 88 | ✗ | os << R"("Y":)" << boostRing[i].y() << ","; | |
| 89 | ✗ | os << R"("Z":0.0},)"; | |
| 90 | } | ||
| 91 | ✗ | os << "],"; | |
| 92 | ✗ | return os; | |
| 93 | } | ||
| 94 | |||
| 95 | ✗ | std::ostream& operator<<(std::ostream& os, const std::vector<BoostRing>& boostRings) { | |
| 96 | ✗ | os << "["; | |
| 97 | ✗ | for (const auto& ring : boostRings) { | |
| 98 | ✗ | os << ring; | |
| 99 | } | ||
| 100 | ✗ | os << "]"; | |
| 101 | ✗ | return os; | |
| 102 | } | ||
| 103 | |||
| 104 | ✗ | std::ostream& operator<<(std::ostream& os, const BoostPolygon& boostPolygon) { | |
| 105 | ✗ | os << "{"; | |
| 106 | ✗ | os << R"("Color":"Black",)"; | |
| 107 | ✗ | os << R"("OuterPath":)" << boostPolygon.outer(); | |
| 108 | ✗ | os << R"("InnerPaths":)" << boostPolygon.inners(); | |
| 109 | ✗ | os << "},"; | |
| 110 | ✗ | return os; | |
| 111 | } | ||
| 112 | |||
| 113 | ✗ | std::ostream& operator<<(std::ostream& os, const std::vector<BoostPolygon>& boostPolygons) { | |
| 114 | ✗ | os << "["; | |
| 115 | ✗ | for (const auto& poly : boostPolygons) { | |
| 116 | ✗ | os << poly; | |
| 117 | } | ||
| 118 | ✗ | os << "]"; | |
| 119 | ✗ | return os; | |
| 120 | } | ||
| 121 | |||
| 122 | ✗ | std::ostream& operator<<(std::ostream& os, const BoostMultiPolygon& boostPolygons) { | |
| 123 | ✗ | os << "["; | |
| 124 | ✗ | for (const auto& poly : boostPolygons) { | |
| 125 | ✗ | os << poly; | |
| 126 | } | ||
| 127 | ✗ | os << "]"; | |
| 128 | ✗ | return os; | |
| 129 | } | ||
| 130 | |||
| 131 | // Scale factor for parameters when converting between openstudio and boost data formats to improve the numerical accuracy of the boolean operations. | ||
| 132 | // Idea came from this comment in the boostorg/geometry repo: https://github.com/boostorg/geometry/issues/1034#issuecomment-1284180101 | ||
| 133 | // where the author indicates that scaling the values by 10 improved the result and talks about rounding to an integer grid, | ||
| 134 | // so by increasing the range of values we pass to boost we should be improving the resolution of the integer rounding | ||
| 135 | static constexpr double scaleBy = 1000.0; | ||
| 136 | |||
| 137 | // Cleans a polygon by shrinking and expanding. Can return multiple polygons | ||
| 138 | 41052 | std::vector<BoostPolygon> removeSpikesEx(const BoostPolygon& polygon) { | |
| 139 | |||
| 140 | //const double buffer_distance = 1.0; | ||
| 141 | //const int points_per_circle = 36; | ||
| 142 | 41052 | constexpr bool extraLogging = false; | |
| 143 | // The amount to shrink and expand the polygons by | ||
| 144 | 41052 | constexpr double offsetBy = 0.01; | |
| 145 | 41052 | constexpr double tol = offsetBy; | |
| 146 | // Sets the limit to how far miters are extended for sharp corners | ||
| 147 | 41052 | constexpr double mitreLimit = 100; | |
| 148 | 41052 | const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> expand(offsetBy * scaleBy); | |
| 149 | 41052 | const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> shrink(-offsetBy * scaleBy); | |
| 150 |
1/1✓ Branch 1 taken 41052 times.
|
41052 | const boost::geometry::strategy::buffer::join_miter join_strategy(mitreLimit * scaleBy); |
| 151 | const boost::geometry::strategy::buffer::end_flat end_strategy; | ||
| 152 | const boost::geometry::strategy::buffer::side_straight side_strategy; | ||
| 153 | 41052 | const boost::geometry::strategy::buffer::point_circle point_strategy; | |
| 154 | |||
| 155 | 41052 | BoostMultiPolygon resultExpand; | |
| 156 | 41052 | BoostMultiPolygon resultShrink; | |
| 157 | 41052 | BoostMultiPolygon result; | |
| 158 | |||
| 159 | // Used for extra logging | ||
| 160 | 41052 | BoostMultiPolygon shrinkExpand; | |
| 161 | // cppcheck-suppress knownConditionTrueFalse | ||
| 162 | if constexpr (extraLogging) { | ||
| 163 | shrinkExpand.push_back(polygon); | ||
| 164 | } | ||
| 165 | |||
| 166 | // Shrink the polygon | ||
| 167 |
1/1✓ Branch 1 taken 41052 times.
|
41052 | boost::geometry::buffer(polygon, resultShrink, shrink, side_strategy, join_strategy, end_strategy, point_strategy); |
| 168 | // cppcheck-suppress knownConditionTrueFalse | ||
| 169 | if constexpr (extraLogging) { | ||
| 170 | shrinkExpand.push_back(resultShrink[0]); | ||
| 171 | } | ||
| 172 | |||
| 173 | // Inflate the polygon | ||
| 174 |
1/1✓ Branch 1 taken 41052 times.
|
41052 | boost::geometry::buffer(resultShrink, resultExpand, expand, side_strategy, join_strategy, end_strategy, point_strategy); |
| 175 | // cppcheck-suppress knownConditionTrueFalse | ||
| 176 | if constexpr (extraLogging) { | ||
| 177 | shrinkExpand.push_back(resultExpand[0]); | ||
| 178 | } | ||
| 179 | |||
| 180 | // Very small tolerance to remove artifacts from the inflate | ||
| 181 | 41052 | constexpr double tol1 = 0.001; | |
| 182 |
1/1✓ Branch 1 taken 41052 times.
|
41052 | boost::geometry::simplify(resultExpand, result, tol1 * scaleBy); |
| 183 | // cppcheck-suppress knownConditionTrueFalse | ||
| 184 | if constexpr (extraLogging) { | ||
| 185 | shrinkExpand.push_back(result[0]); | ||
| 186 | LOG_FREE(Debug, "Shrink/Expand", shrinkExpand); | ||
| 187 | } | ||
| 188 | |||
| 189 | 41052 | std::vector<BoostPolygon> solution; | |
| 190 |
2/2✓ Branch 1 taken 519 times.
✓ Branch 2 taken 40533 times.
|
41052 | if (result.empty()) { |
| 191 | // There's no result because the polygon was completely removed so return nothing | ||
| 192 | 519 | return solution; | |
| 193 |
6/6✓ Branch 1 taken 40517 times.
✓ Branch 2 taken 16 times.
✓ Branch 8 taken 37709 times.
✓ Branch 9 taken 2808 times.
✓ Branch 10 taken 37709 times.
✓ Branch 11 taken 2824 times.
|
40533 | } else if (result.size() == 1 && result[0].outer().size() == polygon.outer().size()) { |
| 194 | // Number of vertices didn't change so no spikes were removed | ||
| 195 |
1/1✓ Branch 1 taken 37709 times.
|
37709 | solution.push_back(polygon); |
| 196 | 37709 | return solution; | |
| 197 | } else { | ||
| 198 |
2/2✓ Branch 5 taken 2840 times.
✓ Branch 6 taken 2824 times.
|
5664 | for (auto& boostPolygon : result) { |
| 199 | |||
| 200 | // The returned points are adjusted to the input polygon (which defines the canonical set) | ||
| 201 |
2/2✓ Branch 6 taken 18630 times.
✓ Branch 7 taken 2840 times.
|
21470 | for (auto& cleanedRing : boostPolygon.outer()) { |
| 202 |
3/3✓ Branch 1 taken 18630 times.
✓ Branch 4 taken 18630 times.
✓ Branch 7 taken 18630 times.
|
18630 | const Point3d point3d(cleanedRing.x(), cleanedRing.y(), 0.0); |
| 203 | |||
| 204 | // Outer ring of the original polygon | ||
| 205 |
2/2✓ Branch 6 taken 93660 times.
✓ Branch 7 taken 78 times.
|
93738 | for (const auto& oriRing : polygon.outer()) { |
| 206 |
3/3✓ Branch 1 taken 93660 times.
✓ Branch 4 taken 93660 times.
✓ Branch 7 taken 93660 times.
|
93660 | const Point3d p1(oriRing.x(), oriRing.y(), 0); |
| 207 | // Two points are within tolerance set the result to the original input point | ||
| 208 |
3/3✓ Branch 1 taken 93660 times.
✓ Branch 3 taken 18552 times.
✓ Branch 4 taken 75108 times.
|
93660 | if (getDistance(point3d, p1) <= tol * scaleBy) { |
| 209 |
2/2✓ Branch 1 taken 18552 times.
✓ Branch 4 taken 18552 times.
|
18552 | cleanedRing.x(oriRing.x()); |
| 210 |
2/2✓ Branch 1 taken 18552 times.
✓ Branch 4 taken 18552 times.
|
18552 | cleanedRing.y(oriRing.y()); |
| 211 | 18552 | break; | |
| 212 | } | ||
| 213 | 93660 | } | |
| 214 | 18630 | } | |
| 215 | |||
| 216 |
1/1✓ Branch 1 taken 2840 times.
|
2840 | solution.push_back(boostPolygon); |
| 217 | } | ||
| 218 | 2824 | return solution; | |
| 219 | } | ||
| 220 | 41052 | } | |
| 221 | |||
| 222 | 440 | BoostPolygon removeSpikes(const BoostPolygon& polygon) { | |
| 223 | 440 | BoostPolygon temp(polygon); | |
| 224 |
1/1✓ Branch 1 taken 440 times.
|
440 | boost::geometry::remove_spikes(temp); |
| 225 | 440 | return temp; | |
| 226 | ✗ | } | |
| 227 | |||
| 228 | 37926 | std::vector<BoostPolygon> removeSpikes(const std::vector<BoostPolygon>& polygons) { | |
| 229 | 37926 | std::vector<BoostPolygon> result; | |
| 230 |
2/2✓ Branch 4 taken 41052 times.
✓ Branch 5 taken 37926 times.
|
78978 | for (const BoostPolygon& polygon : polygons) { |
| 231 |
2/2✓ Branch 1 taken 41052 times.
✓ Branch 4 taken 41052 times.
|
41052 | openstudio::detail::concat_helper(result, removeSpikesEx(polygon)); |
| 232 | } | ||
| 233 | 37926 | return result; | |
| 234 | ✗ | } | |
| 235 | |||
| 236 | 872 | std::vector<BoostPolygon> removeHoles(const BoostPolygon& boostPolygon) { | |
| 237 | 872 | std::vector<BoostPolygon> result; | |
| 238 | |||
| 239 | // convert to vector of TPPLPoly | ||
| 240 | 872 | std::list<TPPLPoly> polys; | |
| 241 | |||
| 242 |
1/1✓ Branch 2 taken 872 times.
|
872 | BoostRing outer = boostPolygon.outer(); |
| 243 |
1/1✓ Branch 1 taken 872 times.
|
872 | TPPLPoly outerPoly; // must be counter-clockwise |
| 244 |
1/1✓ Branch 2 taken 872 times.
|
872 | outerPoly.Init(outer.size() - 1); |
| 245 | 872 | outerPoly.SetHole(false); | |
| 246 | //std::cout << "outer :"; | ||
| 247 | // Note - no scaling conversion here as this accepts boost data and returns boost data | ||
| 248 |
2/2✓ Branch 1 taken 5149 times.
✓ Branch 2 taken 872 times.
|
6021 | for (size_t i = 0; i < outer.size() - 1; ++i) { |
| 249 |
1/1✓ Branch 2 taken 5149 times.
|
5149 | outerPoly[i].x = outer[i].x(); |
| 250 |
1/1✓ Branch 2 taken 5149 times.
|
5149 | outerPoly[i].y = outer[i].y(); |
| 251 | //std::cout << "(" << outer[i].x() << ", " << outer[i].y() << ") "; | ||
| 252 | } | ||
| 253 | //std::cout << '\n'; | ||
| 254 |
1/1✓ Branch 1 taken 872 times.
|
872 | outerPoly.SetOrientation(TPPL_CCW); |
| 255 |
1/1✓ Branch 1 taken 872 times.
|
872 | polys.push_back(outerPoly); |
| 256 | |||
| 257 | 872 | const std::vector<BoostRing>& inners = boostPolygon.inners(); | |
| 258 |
2/2✓ Branch 5 taken 603 times.
✓ Branch 6 taken 872 times.
|
1475 | for (const BoostRing& inner : inners) { |
| 259 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 603 times.
|
603 | if (inner.size() < 3) { |
| 260 | ✗ | continue; | |
| 261 | } | ||
| 262 |
1/1✓ Branch 1 taken 603 times.
|
603 | TPPLPoly innerPoly; // must be clockwise |
| 263 |
1/1✓ Branch 2 taken 603 times.
|
603 | innerPoly.Init(inner.size() - 1); |
| 264 | 603 | innerPoly.SetHole(true); | |
| 265 | //std::cout << "inner :"; | ||
| 266 | // Note - no scaling conversion here as this accepts boost data and returns boost data | ||
| 267 |
2/2✓ Branch 1 taken 2448 times.
✓ Branch 2 taken 603 times.
|
3051 | for (unsigned i = 0; i < inner.size() - 1; ++i) { |
| 268 |
1/1✓ Branch 2 taken 2448 times.
|
2448 | innerPoly[i].x = inner[i].x(); |
| 269 |
1/1✓ Branch 2 taken 2448 times.
|
2448 | innerPoly[i].y = inner[i].y(); |
| 270 | //std::cout << "(" << inner[i].x() << ", " << inner[i].y() << ") "; | ||
| 271 | } | ||
| 272 | //std::cout << '\n'; | ||
| 273 |
1/1✓ Branch 1 taken 603 times.
|
603 | innerPoly.SetOrientation(TPPL_CW); |
| 274 |
1/1✓ Branch 1 taken 603 times.
|
603 | polys.push_back(innerPoly); |
| 275 | 603 | } | |
| 276 | |||
| 277 | // do partitioning | ||
| 278 | TPPLPartition pp; | ||
| 279 | 872 | std::list<TPPLPoly> resultPolys; | |
| 280 |
1/1✓ Branch 1 taken 872 times.
|
872 | const int test = pp.ConvexPartition_HM(&polys, &resultPolys); |
| 281 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 872 times.
|
872 | if (test == 0) { |
| 282 | ✗ | LOG_FREE(Error, "utilities.geometry.removeHoles", "Failed to partition polygon"); | |
| 283 | ✗ | return result; | |
| 284 | } | ||
| 285 | |||
| 286 | // convert back to BoostPolygon | ||
| 287 | 872 | std::list<TPPLPoly>::iterator it; | |
| 288 | 872 | std::list<TPPLPoly>::iterator itend; | |
| 289 |
2/2✓ Branch 4 taken 4036 times.
✓ Branch 5 taken 872 times.
|
4908 | for (it = resultPolys.begin(), itend = resultPolys.end(); it != itend; ++it) { |
| 290 |
1/1✓ Branch 1 taken 4036 times.
|
4036 | BoostPolygon newBoostPolygon; |
| 291 | //std::cout << "result :"; | ||
| 292 |
2/2✓ Branch 2 taken 15131 times.
✓ Branch 3 taken 4036 times.
|
19167 | for (long i = 0; i < it->GetNumPoints(); ++i) { |
| 293 | 15131 | const TPPLPoint& point = it->GetPoint(i); | |
| 294 |
2/2✓ Branch 1 taken 15131 times.
✓ Branch 4 taken 15131 times.
|
15131 | boost::geometry::append(newBoostPolygon, boost::make_tuple(point.x, point.y)); |
| 295 | //std::cout << "(" << point.x << ", " << point.y << ") "; | ||
| 296 | } | ||
| 297 | 4036 | const TPPLPoint& point = it->GetPoint(0); | |
| 298 |
2/2✓ Branch 1 taken 4036 times.
✓ Branch 4 taken 4036 times.
|
4036 | boost::geometry::append(newBoostPolygon, boost::make_tuple(point.x, point.y)); |
| 299 | //std::cout << "(" << point.x << ", " << point.y << ") "; | ||
| 300 | //std::cout << '\n'; | ||
| 301 | |||
| 302 |
1/1✓ Branch 1 taken 4036 times.
|
4036 | boost::geometry::correct(newBoostPolygon); |
| 303 |
1/1✓ Branch 1 taken 4036 times.
|
4036 | result.push_back(newBoostPolygon); |
| 304 | 4036 | } | |
| 305 | |||
| 306 | 872 | return result; | |
| 307 | 872 | } | |
| 308 | |||
| 309 | 22596 | std::vector<BoostPolygon> removeHoles(const std::vector<BoostPolygon>& polygons) { | |
| 310 | 22596 | std::vector<BoostPolygon> result; | |
| 311 |
2/2✓ Branch 5 taken 11202 times.
✓ Branch 6 taken 22596 times.
|
33798 | for (const BoostPolygon& polygon : polygons) { |
| 312 |
2/2✓ Branch 2 taken 10767 times.
✓ Branch 3 taken 435 times.
|
11202 | if (polygon.inners().empty()) { |
| 313 | // DLM: might also want to partition if this polygon is self intersecting? | ||
| 314 |
1/1✓ Branch 1 taken 10767 times.
|
10767 | result.push_back(polygon); |
| 315 | } else { | ||
| 316 |
1/1✓ Branch 1 taken 435 times.
|
435 | std::vector<BoostPolygon> temp = removeHoles(polygon); |
| 317 |
1/1✓ Branch 5 taken 435 times.
|
435 | result.insert(result.end(), temp.begin(), temp.end()); |
| 318 | 435 | } | |
| 319 | } | ||
| 320 | 22596 | return result; | |
| 321 | ✗ | } | |
| 322 | |||
| 323 | // convert a Point3d to a BoostPoint | ||
| 324 | 502282 | boost::tuple<double, double> boostPointFromPoint3d(const Point3d& point3d, std::vector<Point3d>& allPoints, double tol) { | |
| 325 |
2/4✓ Branch 1 taken 502282 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 502282 times.
✗ Branch 7 not taken.
|
502282 | OS_ASSERT(std::abs(point3d.z()) <= tol); |
| 326 | |||
| 327 | // simple method | ||
| 328 | //return boost::make_tuple(point3d.x(), point3d.y()); | ||
| 329 | |||
| 330 | // detailed method, try to combine points within tolerance | ||
| 331 |
1/1✓ Branch 1 taken 502282 times.
|
502282 | const Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol); |
| 332 | |||
| 333 |
3/3✓ Branch 1 taken 502282 times.
✓ Branch 4 taken 502282 times.
✓ Branch 7 taken 502282 times.
|
1004564 | return boost::make_tuple(resultPoint.x() * scaleBy, resultPoint.y() * scaleBy); |
| 334 | 502282 | } | |
| 335 | |||
| 336 | // convert vertices to a boost polygon, all vertices must lie on z = 0 plane | ||
| 337 | 6855 | boost::optional<BoostPolygon> boostPolygonFromVertices(const std::vector<Point3d>& vertices, std::vector<Point3d>& allPoints, double tol) { | |
| 338 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 6852 times.
|
6855 | if (vertices.size() < 3) { |
| 339 | 3 | return boost::none; | |
| 340 | } | ||
| 341 | |||
| 342 |
1/1✓ Branch 1 taken 6852 times.
|
6852 | BoostPolygon polygon; |
| 343 |
2/2✓ Branch 4 taken 31807 times.
✓ Branch 5 taken 6852 times.
|
38659 | for (const Point3d& vertex : vertices) { |
| 344 | |||
| 345 | // should all have zero z coordinate now | ||
| 346 |
1/1✓ Branch 1 taken 31807 times.
|
31807 | const double z = vertex.z(); |
| 347 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 31807 times.
|
31807 | if (std::abs(z) > tol) { |
| 348 | ✗ | LOG_FREE(Error, "utilities.geometry.boostPolygonFromVertices", "All points must be on z = 0 plane"); | |
| 349 | ✗ | return boost::none; | |
| 350 | } | ||
| 351 | |||
| 352 | // use helper method which combines close points | ||
| 353 |
2/2✓ Branch 1 taken 31807 times.
✓ Branch 4 taken 31807 times.
|
31807 | boost::geometry::append(polygon, boostPointFromPoint3d(vertex, allPoints, tol)); |
| 354 | } | ||
| 355 | |||
| 356 | // close polygon, use helper method which combines close points | ||
| 357 |
2/2✓ Branch 2 taken 6852 times.
✓ Branch 5 taken 6852 times.
|
6852 | boost::geometry::append(polygon, boostPointFromPoint3d(vertices[0], allPoints, tol)); |
| 358 | |||
| 359 | //boost::geometry::correct(polygon); | ||
| 360 | |||
| 361 |
2/2✓ Branch 1 taken 6852 times.
✓ Branch 4 taken 6852 times.
|
6852 | boost::optional<double> testArea = boost::geometry::area(polygon); |
| 362 |
6/7✓ Branch 1 taken 6852 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6852 times.
✓ Branch 6 taken 81 times.
✓ Branch 7 taken 6771 times.
✓ Branch 8 taken 81 times.
✓ Branch 9 taken 6771 times.
|
6852 | if (!testArea || (*testArea < 0)) { |
| 363 | // DLM: we could offer to reverse these vertices here but that might not be the best idea | ||
| 364 | 81 | return boost::none; | |
| 365 | } | ||
| 366 | |||
| 367 |
1/1✓ Branch 1 taken 6771 times.
|
6771 | return polygon; |
| 368 | 6852 | } | |
| 369 | |||
| 370 | 1053 | boost::optional<BoostPolygon> nonIntersectingBoostPolygonFromVertices(const std::vector<Point3d>& polygon, std::vector<Point3d>& allPoints, | |
| 371 | double tol) { | ||
| 372 |
1/1✓ Branch 1 taken 1053 times.
|
1053 | boost::optional<BoostPolygon> result = boostPolygonFromVertices(polygon, allPoints, tol); |
| 373 |
2/2✓ Branch 1 taken 28 times.
✓ Branch 2 taken 1025 times.
|
1053 | if (!result) { |
| 374 | 28 | return boost::none; | |
| 375 | } | ||
| 376 | // check if polygon overlaps itself | ||
| 377 | try { | ||
| 378 |
2/2✓ Branch 1 taken 1025 times.
✓ Branch 4 taken 1023 times.
|
1025 | has_self_intersections(*result); |
| 379 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
2 | } catch (const boost::geometry::overlay_invalid_input_exception&) { |
| 380 | //LOG_FREE(Error, "utilities.geometry.nonIntersectingBoostPolygonFromVertices", "Self intersecting polygon"); | ||
| 381 | 2 | return boost::none; | |
| 382 | 2 | } | |
| 383 | 1023 | return result; | |
| 384 | 1053 | } | |
| 385 | |||
| 386 | // convert vertices to a boost ring, all vertices must lie on z = 0 plane | ||
| 387 | 80495 | boost::optional<BoostRing> boostRingFromVertices(const std::vector<Point3d>& vertices, std::vector<Point3d>& allPoints, double tol) { | |
| 388 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 80495 times.
|
80495 | if (vertices.size() < 3) { |
| 389 | ✗ | return boost::none; | |
| 390 | } | ||
| 391 | |||
| 392 | 80495 | BoostRing ring; | |
| 393 |
2/2✓ Branch 4 taken 347762 times.
✓ Branch 5 taken 80469 times.
|
428231 | for (const Point3d& vertex : vertices) { |
| 394 | |||
| 395 | // should all have zero z coordinate now | ||
| 396 |
1/1✓ Branch 1 taken 347762 times.
|
347762 | const double z = vertex.z(); |
| 397 |
2/2✓ Branch 1 taken 26 times.
✓ Branch 2 taken 347736 times.
|
347762 | if (std::abs(z) > tol) { |
| 398 |
5/5✓ Branch 1 taken 26 times.
✓ Branch 4 taken 26 times.
✓ Branch 7 taken 26 times.
✓ Branch 10 taken 26 times.
✓ Branch 13 taken 26 times.
|
78 | LOG_FREE(Error, "utilities.geometry.boostRingFromVertices", "All points must be on z = 0 plane"); |
| 399 | 26 | return boost::none; | |
| 400 | } | ||
| 401 | |||
| 402 | // use helper method which combines close points | ||
| 403 |
2/2✓ Branch 1 taken 347736 times.
✓ Branch 4 taken 347736 times.
|
347736 | boost::geometry::append(ring, boostPointFromPoint3d(vertex, allPoints, tol)); |
| 404 | } | ||
| 405 | |||
| 406 | // close polygon, use helper method which combines close points | ||
| 407 |
2/2✓ Branch 2 taken 80469 times.
✓ Branch 5 taken 80469 times.
|
80469 | boost::geometry::append(ring, boostPointFromPoint3d(vertices[0], allPoints, tol)); |
| 408 | |||
| 409 | //boost::geometry::correct(ring); | ||
| 410 | |||
| 411 |
2/2✓ Branch 1 taken 80469 times.
✓ Branch 4 taken 80469 times.
|
80469 | boost::optional<double> testArea = boost::geometry::area(ring); |
| 412 |
6/7✓ Branch 1 taken 80469 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 80469 times.
✓ Branch 6 taken 117 times.
✓ Branch 7 taken 80352 times.
✓ Branch 8 taken 117 times.
✓ Branch 9 taken 80352 times.
|
80469 | if (!testArea || (*testArea < 0)) { |
| 413 | // DLM: we could offer to reverse these vertices here but that might not be the best idea | ||
| 414 | 117 | return boost::none; | |
| 415 | } | ||
| 416 | |||
| 417 |
1/1✓ Branch 1 taken 80352 times.
|
80352 | return ring; |
| 418 | 80495 | } | |
| 419 | |||
| 420 | 80495 | boost::optional<BoostRing> nonIntersectingBoostRingFromVertices(const std::vector<Point3d>& polygon, std::vector<Point3d>& allPoints, double tol) { | |
| 421 |
1/1✓ Branch 1 taken 80495 times.
|
80495 | boost::optional<BoostRing> result = boostRingFromVertices(polygon, allPoints, tol); |
| 422 |
2/2✓ Branch 1 taken 143 times.
✓ Branch 2 taken 80352 times.
|
80495 | if (!result) { |
| 423 | 143 | return boost::none; | |
| 424 | } | ||
| 425 | // check if polygon overlaps itself | ||
| 426 | try { | ||
| 427 |
2/2✓ Branch 1 taken 80352 times.
✓ Branch 4 taken 80352 times.
|
80352 | has_self_intersections(*result); |
| 428 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 429 | //LOG_FREE(Error, "utilities.geometry.nonIntersectingBoostRingFromVertices", "Self intersecting polygon"); | ||
| 430 | ✗ | return boost::none; | |
| 431 | ✗ | } | |
| 432 | 80352 | return result; | |
| 433 | 80495 | } | |
| 434 | |||
| 435 | // convert a boost polygon to vertices | ||
| 436 | 16944 | std::vector<Point3d> verticesFromBoostPolygon(const BoostPolygon& polygon, std::vector<Point3d>& allPoints, double tol, | |
| 437 | bool removeCollinear = false) { | ||
| 438 | 16944 | std::vector<Point3d> result; | |
| 439 |
1/1✓ Branch 2 taken 16944 times.
|
16944 | BoostRing outer = polygon.outer(); |
| 440 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 16944 times.
|
16944 | if (outer.empty()) { |
| 441 | ✗ | return result; | |
| 442 | } | ||
| 443 | |||
| 444 | // add point for each vertex except final vertex | ||
| 445 |
2/2✓ Branch 1 taken 79331 times.
✓ Branch 2 taken 16944 times.
|
96275 | for (unsigned i = 0; i < outer.size() - 1; ++i) { |
| 446 |
3/3✓ Branch 2 taken 79331 times.
✓ Branch 6 taken 79331 times.
✓ Branch 9 taken 79331 times.
|
79331 | const Point3d point3d(outer[i].x() / scaleBy, outer[i].y() / scaleBy, 0.0); |
| 447 | |||
| 448 | // try to combine points within tolerance | ||
| 449 |
1/1✓ Branch 1 taken 79331 times.
|
79331 | Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol); |
| 450 | |||
| 451 | // don't keep repeated vertices | ||
| 452 |
7/7✓ Branch 0 taken 62387 times.
✓ Branch 1 taken 16944 times.
✓ Branch 4 taken 62387 times.
✓ Branch 6 taken 57 times.
✓ Branch 7 taken 62330 times.
✓ Branch 8 taken 57 times.
✓ Branch 9 taken 79274 times.
|
79331 | if ((i > 0) && (result.back() == resultPoint)) { |
| 453 | 57 | continue; | |
| 454 | } | ||
| 455 |
1/1✓ Branch 2 taken 79274 times.
|
79274 | result.emplace_back(std::move(resultPoint)); |
| 456 | 79388 | } | |
| 457 | |||
| 458 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 16944 times.
|
16944 | if (!polygon.inners().empty()) { |
| 459 | ✗ | LOG_FREE(Warn, "utilities.geometry.verticesFromBoostPolygon", | |
| 460 | "Converting polygon with " << polygon.inners().size() << " inner loops to OpenStudio vertices, inner loops ignored"); | ||
| 461 | } | ||
| 462 | |||
| 463 |
2/2✓ Branch 0 taken 68 times.
✓ Branch 1 taken 16876 times.
|
16944 | if (removeCollinear) { |
| 464 |
1/1✓ Branch 1 taken 68 times.
|
68 | result = removeCollinearLegacy(result); |
| 465 | } | ||
| 466 | |||
| 467 | // don't keep repeated vertices | ||
| 468 |
3/3✓ Branch 3 taken 16944 times.
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 16933 times.
|
16944 | if (result.front() == result.back()) { |
| 469 | 11 | result.pop_back(); | |
| 470 | } | ||
| 471 | |||
| 472 |
2/2✓ Branch 1 taken 20 times.
✓ Branch 2 taken 16924 times.
|
16944 | if (result.size() < 3) { |
| 473 | 20 | return {}; | |
| 474 | } | ||
| 475 | |||
| 476 | 16924 | return result; | |
| 477 | 16944 | } | |
| 478 | |||
| 479 | // convert a boost ring to vertices | ||
| 480 | ✗ | std::vector<Point3d> verticesFromBoostRing(const BoostRing& ring, std::vector<Point3d>& allPoints, double tol) { | |
| 481 | ✗ | std::vector<Point3d> result; | |
| 482 | |||
| 483 | // add point for each vertex except final vertex | ||
| 484 | ✗ | for (unsigned i = 0; i < ring.size() - 1; ++i) { | |
| 485 | ✗ | const Point3d point3d(ring[i].x(), ring[i].y(), 0.0); | |
| 486 | |||
| 487 | // try to combine points within tolerance | ||
| 488 | ✗ | Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol); | |
| 489 | |||
| 490 | // don't keep repeated vertices | ||
| 491 | ✗ | if ((i > 0) && (result.back() == resultPoint)) { | |
| 492 | ✗ | continue; | |
| 493 | } | ||
| 494 | ✗ | result.emplace_back(std::move(resultPoint)); | |
| 495 | ✗ | } | |
| 496 | |||
| 497 | ✗ | result = removeCollinearLegacy(result); | |
| 498 | |||
| 499 | // don't keep repeated vertices | ||
| 500 | ✗ | if (result.front() == result.back()) { | |
| 501 | ✗ | result.pop_back(); | |
| 502 | } | ||
| 503 | |||
| 504 | ✗ | if (result.size() < 3) { | |
| 505 | ✗ | return {}; | |
| 506 | } | ||
| 507 | |||
| 508 | ✗ | return result; | |
| 509 | ✗ | } | |
| 510 | |||
| 511 | // struct used to sort polygons in descending order by area | ||
| 512 | struct BoostPolygonAreaGreater | ||
| 513 | { | ||
| 514 | 1 | bool operator()(const BoostPolygon& left, const BoostPolygon& right) const { | |
| 515 |
2/2✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
|
1 | boost::optional<double> leftA = boost::geometry::area(left); |
| 516 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
|
1 | if (!leftA) { |
| 517 | ✗ | leftA = 0; | |
| 518 | } | ||
| 519 |
2/2✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
|
1 | boost::optional<double> rightA = boost::geometry::area(right); |
| 520 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
|
1 | if (!rightA) { |
| 521 | ✗ | rightA = 0; | |
| 522 | } | ||
| 523 |
2/2✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
|
2 | return (*leftA > *rightA); |
| 524 | } | ||
| 525 | }; | ||
| 526 | |||
| 527 | // Public functions | ||
| 528 | |||
| 529 | 7532 | IntersectionResult::IntersectionResult(std::vector<Point3d> polygon1, std::vector<Point3d> polygon2, std::vector<std::vector<Point3d>> newPolygons1, | |
| 530 | 7532 | std::vector<std::vector<Point3d>> newPolygons2) | |
| 531 | 7532 | : m_polygon1(std::move(polygon1)), | |
| 532 | 7532 | m_polygon2(std::move(polygon2)), | |
| 533 | 7532 | m_newPolygons1(std::move(newPolygons1)), | |
| 534 | 7532 | m_newPolygons2(std::move(newPolygons2)) {} | |
| 535 | |||
| 536 | 7530 | std::vector<Point3d> IntersectionResult::polygon1() const { | |
| 537 | 7530 | return m_polygon1; | |
| 538 | } | ||
| 539 | |||
| 540 | 7027 | std::vector<Point3d> IntersectionResult::polygon2() const { | |
| 541 | 7027 | return m_polygon2; | |
| 542 | } | ||
| 543 | |||
| 544 | 7037 | std::vector<std::vector<Point3d>> IntersectionResult::newPolygons1() const { | |
| 545 | 7037 | return m_newPolygons1; | |
| 546 | } | ||
| 547 | |||
| 548 | 7029 | std::vector<std::vector<Point3d>> IntersectionResult::newPolygons2() const { | |
| 549 | 7029 | return m_newPolygons2; | |
| 550 | } | ||
| 551 | |||
| 552 | 7203 | double IntersectionResult::area1() const { | |
| 553 | 7203 | double result = 0; | |
| 554 | 7203 | boost::optional<double> d; | |
| 555 |
1/1✓ Branch 1 taken 7203 times.
|
7203 | d = getArea(m_polygon1); |
| 556 |
1/2✓ Branch 0 taken 7203 times.
✗ Branch 1 not taken.
|
7203 | if (d) { |
| 557 |
1/1✓ Branch 1 taken 7203 times.
|
7203 | result += *d; |
| 558 | } else { | ||
| 559 | ✗ | LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon1"); | |
| 560 | } | ||
| 561 | |||
| 562 |
2/2✓ Branch 5 taken 1939 times.
✓ Branch 6 taken 7203 times.
|
9142 | for (const auto& polygon : m_newPolygons1) { |
| 563 |
1/1✓ Branch 1 taken 1939 times.
|
1939 | d = getArea(polygon); |
| 564 |
1/2✓ Branch 0 taken 1939 times.
✗ Branch 1 not taken.
|
1939 | if (d) { |
| 565 |
1/1✓ Branch 1 taken 1939 times.
|
1939 | result += *d; |
| 566 | } else { | ||
| 567 | ✗ | LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon in polygons1"); | |
| 568 | } | ||
| 569 | } | ||
| 570 | |||
| 571 | 7203 | return result; | |
| 572 | } | ||
| 573 | |||
| 574 | 7221 | double IntersectionResult::area2() const { | |
| 575 | 7221 | double result = 0; | |
| 576 | 7221 | boost::optional<double> d; | |
| 577 |
1/1✓ Branch 1 taken 7221 times.
|
7221 | d = getArea(m_polygon2); |
| 578 |
1/2✓ Branch 0 taken 7221 times.
✗ Branch 1 not taken.
|
7221 | if (d) { |
| 579 |
1/1✓ Branch 1 taken 7221 times.
|
7221 | result += *d; |
| 580 | } else { | ||
| 581 | ✗ | LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon2"); | |
| 582 | } | ||
| 583 | |||
| 584 |
2/2✓ Branch 5 taken 1450 times.
✓ Branch 6 taken 7221 times.
|
8671 | for (const auto& polygon : m_newPolygons2) { |
| 585 |
1/1✓ Branch 1 taken 1450 times.
|
1450 | d = getArea(polygon); |
| 586 |
1/2✓ Branch 0 taken 1450 times.
✗ Branch 1 not taken.
|
1450 | if (d) { |
| 587 |
1/1✓ Branch 1 taken 1450 times.
|
1450 | result += *d; |
| 588 | } else { | ||
| 589 | ✗ | LOG_FREE(Warn, "utilities.geometry.IntersectionResult", "Cannot calculate area for polygon in polygons2"); | |
| 590 | } | ||
| 591 | } | ||
| 592 | |||
| 593 | 7221 | return result; | |
| 594 | } | ||
| 595 | |||
| 596 | 6 | std::vector<Point3d> removeSpikes(const std::vector<Point3d>& polygon, double tol) { | |
| 597 | // convert vertices to boost rings | ||
| 598 | 6 | std::vector<Point3d> allPoints; | |
| 599 | |||
| 600 |
1/1✓ Branch 1 taken 6 times.
|
6 | boost::optional<BoostPolygon> boostPolygon = boostPolygonFromVertices(polygon, allPoints, tol); |
| 601 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 3 times.
|
6 | if (!boostPolygon) { |
| 602 | 3 | return {}; | |
| 603 | } | ||
| 604 | |||
| 605 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 4 taken 3 times.
|
3 | const BoostPolygon boostResult = removeSpikes(*boostPolygon); |
| 606 | |||
| 607 |
1/1✓ Branch 1 taken 3 times.
|
3 | std::vector<Point3d> result = verticesFromBoostPolygon(boostResult, allPoints, tol); |
| 608 | |||
| 609 | 3 | return result; | |
| 610 | 6 | } | |
| 611 | |||
| 612 | // cppcheck-suppress constParameterReference | ||
| 613 | 20 | bool polygonInPolygon(std::vector<Point3d>& points, const std::vector<Point3d>& polygon, double tol) { | |
| 614 | |||
| 615 | // convert vertices to boost rings | ||
| 616 | 20 | std::vector<Point3d> allPoints; | |
| 617 | |||
| 618 |
1/1✓ Branch 1 taken 20 times.
|
20 | boost::optional<BoostRing> boostPolygon = nonIntersectingBoostRingFromVertices(polygon, allPoints, tol); |
| 619 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
|
20 | if (!boostPolygon) { |
| 620 | ✗ | return false; | |
| 621 | } | ||
| 622 | |||
| 623 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
|
20 | if (points.empty()) { |
| 624 | ✗ | return false; | |
| 625 | } | ||
| 626 | |||
| 627 |
2/2✓ Branch 5 taken 80 times.
✓ Branch 6 taken 20 times.
|
100 | for (const Point3d& point : points) { |
| 628 |
2/3✓ Branch 1 taken 80 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 80 times.
|
80 | if (std::abs(point.z()) > tol) { |
| 629 | ✗ | return false; | |
| 630 | } | ||
| 631 | } | ||
| 632 | |||
| 633 |
2/2✓ Branch 5 taken 78 times.
✓ Branch 6 taken 19 times.
|
97 | for (const Point3d& point : points) { |
| 634 |
1/1✓ Branch 1 taken 78 times.
|
78 | boost::tuple<double, double> p = boostPointFromPoint3d(point, allPoints, tol); |
| 635 |
3/3✓ Branch 1 taken 78 times.
✓ Branch 4 taken 78 times.
✓ Branch 7 taken 78 times.
|
78 | const BoostPoint boostPoint(p.get<0>(), p.get<1>()); |
| 636 |
2/2✓ Branch 1 taken 78 times.
✓ Branch 4 taken 78 times.
|
78 | const double distance = boost::geometry::distance(boostPoint, *boostPolygon); |
| 637 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 77 times.
|
78 | if (distance >= 0.0001) { |
| 638 | 1 | return false; | |
| 639 | } | ||
| 640 | } | ||
| 641 | 19 | return true; | |
| 642 | 20 | } | |
| 643 | |||
| 644 | 94 | bool pointInPolygon(const Point3d& point, const std::vector<Point3d>& polygon, double tol) { | |
| 645 | // convert vertices to boost rings | ||
| 646 | 94 | std::vector<Point3d> allPoints; | |
| 647 | |||
| 648 |
1/1✓ Branch 1 taken 94 times.
|
94 | boost::optional<BoostRing> boostPolygon = nonIntersectingBoostRingFromVertices(polygon, allPoints, tol); |
| 649 |
2/2✓ Branch 1 taken 56 times.
✓ Branch 2 taken 38 times.
|
94 | if (!boostPolygon) { |
| 650 | 56 | return false; | |
| 651 | } | ||
| 652 | |||
| 653 |
3/3✓ Branch 1 taken 38 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 36 times.
|
38 | if (std::abs(point.z()) > tol) { |
| 654 | 2 | return false; | |
| 655 | } | ||
| 656 | |||
| 657 |
1/1✓ Branch 1 taken 36 times.
|
36 | boost::tuple<double, double> p = boostPointFromPoint3d(point, allPoints, tol); |
| 658 |
3/3✓ Branch 1 taken 36 times.
✓ Branch 4 taken 36 times.
✓ Branch 7 taken 36 times.
|
36 | const BoostPoint boostPoint(p.get<0>(), p.get<1>()); |
| 659 | |||
| 660 | //boost::geometry::strategy::within::winding<BoostPoint> strategy; | ||
| 661 | //boost::geometry::strategy::within::franklin<BoostPoint> strategy; | ||
| 662 | //boost::geometry::strategy::within::crossings_multiply<BoostPoint> strategy; | ||
| 663 | //bool result = boost::geometry::within(boostPoint, *boostPolygon, strategy); | ||
| 664 | |||
| 665 | //bool result = boost::geometry::intersects(boostPoint, *boostPolygon); | ||
| 666 | |||
| 667 | //bool result = boost::geometry::overlaps(boostPoint, *boostPolygon); | ||
| 668 | |||
| 669 |
2/2✓ Branch 1 taken 36 times.
✓ Branch 4 taken 36 times.
|
36 | const double distance = boost::geometry::distance(boostPoint, *boostPolygon); |
| 670 | 36 | const bool result = (distance <= 0.0001); | |
| 671 | |||
| 672 | 36 | return result; | |
| 673 | 94 | } | |
| 674 | |||
| 675 | 13465 | boost::optional<std::vector<Point3d>> join(const std::vector<Point3d>& polygon1, const std::vector<Point3d>& polygon2, double tol) { | |
| 676 | // convert vertices to boost rings | ||
| 677 | 13465 | std::vector<Point3d> allPoints; | |
| 678 | |||
| 679 |
1/1✓ Branch 1 taken 13465 times.
|
13465 | boost::optional<BoostRing> boostPolygon1 = nonIntersectingBoostRingFromVertices(polygon1, allPoints, tol); |
| 680 |
2/2✓ Branch 1 taken 24 times.
✓ Branch 2 taken 13441 times.
|
13465 | if (!boostPolygon1) { |
| 681 | 24 | return boost::none; | |
| 682 | } | ||
| 683 | |||
| 684 |
1/1✓ Branch 1 taken 13441 times.
|
13441 | boost::optional<BoostRing> boostPolygon2 = nonIntersectingBoostRingFromVertices(polygon2, allPoints, tol); |
| 685 |
2/2✓ Branch 1 taken 31 times.
✓ Branch 2 taken 13410 times.
|
13441 | if (!boostPolygon2) { |
| 686 | 31 | return boost::none; | |
| 687 | } | ||
| 688 | |||
| 689 | // union the points in face coordinates, | ||
| 690 | 13410 | std::vector<BoostPolygon> unionResult; | |
| 691 | try { | ||
| 692 |
3/3✓ Branch 1 taken 13410 times.
✓ Branch 4 taken 13410 times.
✓ Branch 7 taken 13410 times.
|
13410 | boost::geometry::union_(*boostPolygon1, *boostPolygon2, unionResult); |
| 693 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 694 | ✗ | LOG_FREE(Error, "utilities.geometry.join", "overlay_invalid_input_exception"); | |
| 695 | ✗ | return boost::none; | |
| 696 | ✗ | } | |
| 697 | |||
| 698 |
1/1✓ Branch 1 taken 13410 times.
|
13410 | unionResult = removeSpikes(unionResult); |
| 699 | |||
| 700 | // should not be any holes, check for that below | ||
| 701 | |||
| 702 | // check that union is ok | ||
| 703 |
5/6✓ Branch 1 taken 13410 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12900 times.
✓ Branch 5 taken 510 times.
✓ Branch 6 taken 12900 times.
✓ Branch 7 taken 510 times.
|
13410 | if (unionResult.empty() or (unionResult.size() > 1)) { |
| 704 | 12900 | return boost::none; | |
| 705 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 510 times.
|
510 | } else if (!unionResult[0].inners().empty()) { |
| 706 | // check for holes | ||
| 707 | ✗ | LOG_FREE(Error, "utilities.geometry.join", "Union has inner loops"); | |
| 708 | ✗ | return boost::none; | |
| 709 | }; | ||
| 710 | |||
| 711 |
1/1✓ Branch 2 taken 510 times.
|
510 | std::vector<Point3d> unionVertices = verticesFromBoostPolygon(unionResult[0], allPoints, tol); |
| 712 |
2/2✓ Branch 2 taken 510 times.
✓ Branch 5 taken 510 times.
|
510 | boost::optional<double> testArea = boost::geometry::area(unionResult[0]); |
| 713 |
3/6✓ Branch 1 taken 510 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 510 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 510 times.
|
510 | if (!testArea || unionVertices.empty()) { |
| 714 | ✗ | LOG_FREE(Info, "utilities.geometry.join", "Cannot compute area of union"); | |
| 715 | ✗ | return boost::none; | |
| 716 |
2/3✓ Branch 1 taken 510 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 510 times.
|
510 | } else if (*testArea < tol * tol) { |
| 717 | ✗ | LOG_FREE(Info, "utilities.geometry.join", "Union has very small area of " << *testArea << " m^2"); | |
| 718 | ✗ | return boost::none; | |
| 719 | } | ||
| 720 | |||
| 721 | try { | ||
| 722 |
1/1✓ Branch 2 taken 510 times.
|
510 | has_self_intersections(unionResult[0]); |
| 723 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 724 | ✗ | LOG_FREE(Error, "utilities.geometry.join", "Union is self intersecting"); | |
| 725 | ✗ | return boost::none; | |
| 726 | ✗ | } | |
| 727 | |||
| 728 |
1/1✓ Branch 1 taken 510 times.
|
510 | unionVertices = reorderULC(unionVertices); |
| 729 |
1/1✓ Branch 1 taken 510 times.
|
510 | unionVertices = removeCollinearLegacy(unionVertices); |
| 730 | |||
| 731 |
1/1✓ Branch 1 taken 510 times.
|
510 | return unionVertices; |
| 732 | 13465 | } | |
| 733 | |||
| 734 | 26050 | std::vector<std::vector<Point3d>> joinAll(const std::vector<std::vector<Point3d>>& polygons, double tol) { | |
| 735 | 26050 | std::vector<std::vector<Point3d>> result; | |
| 736 | |||
| 737 | 26050 | const size_t N = polygons.size(); | |
| 738 |
2/2✓ Branch 0 taken 25652 times.
✓ Branch 1 taken 398 times.
|
26050 | if (N <= 1) { |
| 739 |
1/1✓ Branch 1 taken 25652 times.
|
25652 | return polygons; |
| 740 | } | ||
| 741 | |||
| 742 |
1/1✓ Branch 1 taken 398 times.
|
398 | std::vector<double> polygonAreas(N, 0.0); |
| 743 |
2/2✓ Branch 0 taken 2081 times.
✓ Branch 1 taken 398 times.
|
2479 | for (unsigned i = 0; i < N; ++i) { |
| 744 |
1/1✓ Branch 2 taken 2081 times.
|
2081 | auto area = getArea(polygons[i]); |
| 745 |
1/2✓ Branch 0 taken 2081 times.
✗ Branch 1 not taken.
|
2081 | if (area) { |
| 746 |
1/1✓ Branch 1 taken 2081 times.
|
2081 | polygonAreas[i] = *area; |
| 747 | } | ||
| 748 | } | ||
| 749 | |||
| 750 | // compute adjacency matrix | ||
| 751 |
1/1✓ Branch 1 taken 398 times.
|
398 | Matrix A(N, N, 0.0); |
| 752 |
2/2✓ Branch 0 taken 2081 times.
✓ Branch 1 taken 398 times.
|
2479 | for (unsigned i = 0; i < N; ++i) { |
| 753 |
1/1✓ Branch 1 taken 2081 times.
|
2081 | A(i, i) = 1.0; |
| 754 |
2/2✓ Branch 0 taken 13302 times.
✓ Branch 1 taken 2081 times.
|
15383 | for (unsigned j = i + 1; j < N; ++j) { |
| 755 |
3/3✓ Branch 3 taken 13302 times.
✓ Branch 6 taken 385 times.
✓ Branch 7 taken 12917 times.
|
26604 | if (join(polygons[i], polygons[j], tol)) { |
| 756 |
1/1✓ Branch 1 taken 385 times.
|
385 | A(i, j) = 1.0; |
| 757 |
1/1✓ Branch 1 taken 385 times.
|
385 | A(j, i) = 1.0; |
| 758 | } | ||
| 759 | } | ||
| 760 | } | ||
| 761 | |||
| 762 |
1/1✓ Branch 1 taken 398 times.
|
398 | const std::vector<std::vector<unsigned>> connectedComponents = findConnectedComponents(A); |
| 763 |
2/2✓ Branch 5 taken 1964 times.
✓ Branch 6 taken 398 times.
|
2362 | for (const std::vector<unsigned>& component : connectedComponents) { |
| 764 |
1/1✓ Branch 1 taken 1964 times.
|
1964 | std::vector<unsigned> orderedComponent(component); |
| 765 | // #4831 - Use a stable_sort to produce consistent results between Windows and Unix in case you have polygons with the same area | ||
| 766 |
1/1✓ Branch 3 taken 1964 times.
|
1964 | std::stable_sort(orderedComponent.begin(), orderedComponent.end(), |
| 767 | 429 | [&polygonAreas](int ia, int ib) { return polygonAreas[ia] > polygonAreas[ib]; }); | |
| 768 | |||
| 769 | 1964 | std::vector<Point3d> points; | |
| 770 | 1964 | std::set<unsigned> joinedComponents; | |
| 771 | |||
| 772 | // try to join at most component.size() times | ||
| 773 |
1/2✓ Branch 1 taken 1970 times.
✗ Branch 2 not taken.
|
1970 | for (unsigned n = 0; n < component.size(); ++n) { |
| 774 | |||
| 775 | // loop over polygons to join in order | ||
| 776 |
2/2✓ Branch 5 taken 2152 times.
✓ Branch 6 taken 1970 times.
|
4122 | for (const unsigned i : orderedComponent) { |
| 777 |
2/2✓ Branch 1 taken 1964 times.
✓ Branch 2 taken 188 times.
|
2152 | if (points.empty()) { |
| 778 |
1/1✓ Branch 2 taken 1964 times.
|
1964 | points = polygons[i]; |
| 779 |
1/1✓ Branch 1 taken 1964 times.
|
1964 | joinedComponents.insert(i); |
| 780 | } else { | ||
| 781 | // if not already joined | ||
| 782 |
3/3✓ Branch 2 taken 188 times.
✓ Branch 5 taken 137 times.
✓ Branch 6 taken 51 times.
|
188 | if (joinedComponents.find(i) == joinedComponents.end()) { |
| 783 |
1/1✓ Branch 2 taken 137 times.
|
137 | boost::optional<std::vector<Point3d>> joined = join(points, polygons[i], tol); |
| 784 |
2/2✓ Branch 0 taken 117 times.
✓ Branch 1 taken 20 times.
|
137 | if (joined) { |
| 785 |
2/2✓ Branch 1 taken 117 times.
✓ Branch 4 taken 117 times.
|
117 | points = *joined; |
| 786 |
1/1✓ Branch 1 taken 117 times.
|
117 | joinedComponents.insert(i); |
| 787 | } | ||
| 788 | 137 | } | |
| 789 | } | ||
| 790 | } | ||
| 791 | |||
| 792 | // if all polygons have been joined then we are done | ||
| 793 |
2/2✓ Branch 2 taken 1964 times.
✓ Branch 3 taken 6 times.
|
1970 | if (joinedComponents.size() == component.size()) { |
| 794 | 1964 | break; | |
| 795 | } | ||
| 796 | } | ||
| 797 | |||
| 798 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 1964 times.
|
1964 | if (joinedComponents.size() != component.size()) { |
| 799 | ✗ | LOG_FREE(Error, "utilities.geometry.joinAll", "Could not join all connected components"); | |
| 800 | } | ||
| 801 |
1/1✓ Branch 1 taken 1964 times.
|
1964 | result.push_back(points); |
| 802 | 1964 | } | |
| 803 | |||
| 804 | 398 | return result; | |
| 805 | 26050 | } | |
| 806 | |||
| 807 | 26746 | boost::optional<IntersectionResult> intersect(const std::vector<Point3d>& polygon1, const std::vector<Point3d>& polygon2, double tol) { | |
| 808 | |||
| 809 | 26746 | constexpr bool extraLogging = false; | |
| 810 | //std::cout << "Initial polygon1 area " << getArea(polygon1).get() << '\n'; | ||
| 811 | //std::cout << "Initial polygon2 area " << getArea(polygon2).get() << '\n'; | ||
| 812 | |||
| 813 | // convert vertices to boost rings | ||
| 814 | 26746 | std::vector<Point3d> allPoints; | |
| 815 | |||
| 816 |
1/1✓ Branch 1 taken 26746 times.
|
26746 | boost::optional<BoostRing> boostPolygon1 = nonIntersectingBoostRingFromVertices(polygon1, allPoints, tol); |
| 817 |
2/2✓ Branch 1 taken 17 times.
✓ Branch 2 taken 26729 times.
|
26746 | if (!boostPolygon1) { |
| 818 | 17 | return boost::none; | |
| 819 | } | ||
| 820 | |||
| 821 |
1/1✓ Branch 1 taken 26729 times.
|
26729 | boost::optional<BoostRing> boostPolygon2 = nonIntersectingBoostRingFromVertices(polygon2, allPoints, tol); |
| 822 |
2/2✓ Branch 1 taken 15 times.
✓ Branch 2 taken 26714 times.
|
26729 | if (!boostPolygon2) { |
| 823 | 15 | return boost::none; | |
| 824 | } | ||
| 825 | |||
| 826 | 26714 | BoostMultiPolygon polys; | |
| 827 | if constexpr (extraLogging) { | ||
| 828 | boost::optional<BoostPolygon> poly1 = boostPolygonFromVertices(polygon1, allPoints, tol); | ||
| 829 | if (poly1.has_value()) { | ||
| 830 | polys.push_back(*poly1); | ||
| 831 | } | ||
| 832 | boost::optional<BoostPolygon> poly2 = boostPolygonFromVertices(polygon2, allPoints, tol); | ||
| 833 | if (poly2.has_value()) { | ||
| 834 | polys.push_back(*poly2); | ||
| 835 | } | ||
| 836 | } | ||
| 837 | |||
| 838 | // intersect the points in face coordinates, | ||
| 839 | 26714 | std::vector<BoostPolygon> intersectionResult; | |
| 840 | try { | ||
| 841 |
3/3✓ Branch 1 taken 26714 times.
✓ Branch 4 taken 26714 times.
✓ Branch 7 taken 26714 times.
|
26714 | boost::geometry::intersection(*boostPolygon1, *boostPolygon2, intersectionResult); |
| 842 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 843 | ✗ | LOG_FREE(Error, "utilities.geometry.intersect", "overlay_invalid_input_exception"); | |
| 844 | ✗ | return boost::none; | |
| 845 | ✗ | } | |
| 846 | |||
| 847 | if constexpr (extraLogging) { | ||
| 848 | polys.push_back(intersectionResult[0]); | ||
| 849 | } | ||
| 850 | |||
| 851 | // check if intersection is empty | ||
| 852 |
2/2✓ Branch 1 taken 19105 times.
✓ Branch 2 taken 7609 times.
|
26714 | if (intersectionResult.empty()) { |
| 853 | //LOG_FREE(Info, "utilities.geometry.intersect", "Intersection is empty"); | ||
| 854 | 19105 | return boost::none; | |
| 855 | } | ||
| 856 | |||
| 857 |
1/1✓ Branch 1 taken 7609 times.
|
7609 | intersectionResult = removeSpikes(intersectionResult); |
| 858 |
2/2✓ Branch 1 taken 77 times.
✓ Branch 2 taken 7532 times.
|
7609 | if (intersectionResult.empty()) { |
| 859 | 77 | return boost::none; | |
| 860 | } | ||
| 861 | if constexpr (extraLogging) { | ||
| 862 | polys.push_back(intersectionResult[0]); | ||
| 863 | LOG_FREE(Debug, "intersection result", polys); | ||
| 864 | } | ||
| 865 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | intersectionResult = removeHoles(intersectionResult); |
| 866 | |||
| 867 | // check for multiple intersections | ||
| 868 |
2/2✓ Branch 1 taken 1 time.
✓ Branch 2 taken 7531 times.
|
7532 | if (intersectionResult.size() > 1) { |
| 869 |
7/7✓ Branch 1 taken 1 time.
✓ Branch 4 taken 1 time.
✓ Branch 8 taken 1 time.
✓ Branch 11 taken 1 time.
✓ Branch 14 taken 1 time.
✓ Branch 17 taken 1 time.
✓ Branch 20 taken 1 time.
|
3 | LOG_FREE(Info, "utilities.geometry.intersect", "Intersection has " << intersectionResult.size() << " elements"); |
| 870 |
1/1✓ Branch 3 taken 1 time.
|
1 | std::sort(intersectionResult.begin(), intersectionResult.end(), BoostPolygonAreaGreater()); |
| 871 | } | ||
| 872 | |||
| 873 | // check that largest intersection is ok | ||
| 874 |
1/1✓ Branch 2 taken 7532 times.
|
7532 | std::vector<Point3d> intersectionVertices = verticesFromBoostPolygon(intersectionResult[0], allPoints, tol, false); |
| 875 |
2/2✓ Branch 2 taken 7532 times.
✓ Branch 5 taken 7532 times.
|
7532 | boost::optional<double> testArea = boost::geometry::area(intersectionResult[0]); |
| 876 |
3/6✓ Branch 1 taken 7532 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 7532 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 7532 times.
|
7532 | if (!testArea || intersectionVertices.empty()) { |
| 877 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of largest intersection"); | |
| 878 | ✗ | return boost::none; | |
| 879 |
2/3✓ Branch 1 taken 7532 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 7532 times.
|
7532 | } else if (*testArea < tol * tol) { |
| 880 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", "Largest intersection has very small area of " << *testArea << " m^2"); | |
| 881 | ✗ | return boost::none; | |
| 882 | } | ||
| 883 | try { | ||
| 884 |
1/1✓ Branch 2 taken 7532 times.
|
7532 | has_self_intersections(intersectionResult[0]); |
| 885 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 886 | ✗ | LOG_FREE(Error, "utilities.geometry.intersect", "Largest intersection is self intersecting"); | |
| 887 | ✗ | return boost::none; | |
| 888 | ✗ | } | |
| 889 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 7532 times.
|
7532 | if (!intersectionResult[0].inners().empty()) { |
| 890 | ✗ | LOG_FREE(Error, "utilities.geometry.intersect", "Largest intersection has inner loops"); | |
| 891 | ✗ | return boost::none; | |
| 892 | }; | ||
| 893 | |||
| 894 | 7532 | std::vector<std::vector<Point3d>> newPolygons1; | |
| 895 |
1/1✓ Branch 2 taken 7532 times.
|
7532 | newPolygons1.reserve(intersectionResult.size() - 1); |
| 896 | |||
| 897 | // create new polygon for each **remaining** intersection (all but the largest one) | ||
| 898 |
2/2✓ Branch 1 taken 1 time.
✓ Branch 2 taken 7532 times.
|
7533 | for (unsigned i = 1; i < intersectionResult.size(); ++i) { |
| 899 | |||
| 900 |
1/1✓ Branch 2 taken 1 time.
|
1 | std::vector<Point3d> newPolygon = verticesFromBoostPolygon(intersectionResult[i], allPoints, tol, false); |
| 901 | |||
| 902 |
2/2✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
|
1 | testArea = boost::geometry::area(intersectionResult[i]); |
| 903 |
3/6✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 time.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 time.
|
1 | if (!testArea || newPolygon.empty()) { |
| 904 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of intersection, result will not include this polygon, " << newPolygon); | |
| 905 | ✗ | continue; | |
| 906 |
2/3✓ Branch 1 taken 1 time.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 time.
|
1 | } else if (*testArea < tol * tol) { |
| 907 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", | |
| 908 | "Intersection has very small area of " << *testArea << " m^2, result will not include this polygon, " << newPolygon); | ||
| 909 | ✗ | continue; | |
| 910 | ✗ | } | |
| 911 | try { | ||
| 912 |
1/1✓ Branch 2 taken 1 time.
|
1 | has_self_intersections(intersectionResult[i]); |
| 913 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 914 | ✗ | LOG_FREE(Error, "utilities.geometry.intersect", "Intersection is self intersecting, result will not include this polygon, " << newPolygon); | |
| 915 | ✗ | continue; | |
| 916 | ✗ | } | |
| 917 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 1 time.
|
1 | if (!intersectionResult[i].inners().empty()) { |
| 918 | ✗ | LOG_FREE(Error, "utilities.geometry.intersect", "Intersection has inner loops, result will not include this polygon, " << newPolygon); | |
| 919 | ✗ | continue; | |
| 920 | ✗ | }; | |
| 921 | |||
| 922 |
1/1✓ Branch 2 taken 1 time.
|
1 | newPolygons1.push_back(std::move(newPolygon)); |
| 923 | 1 | } | |
| 924 | |||
| 925 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | std::vector<std::vector<Point3d>> newPolygons2 = newPolygons1; |
| 926 | |||
| 927 | // polygon1 minus polygon2 | ||
| 928 | 7532 | std::vector<BoostPolygon> differenceResult1; | |
| 929 |
3/3✓ Branch 1 taken 7532 times.
✓ Branch 4 taken 7532 times.
✓ Branch 7 taken 7532 times.
|
7532 | boost::geometry::difference(*boostPolygon1, *boostPolygon2, differenceResult1); |
| 930 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | differenceResult1 = removeSpikes(differenceResult1); |
| 931 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | differenceResult1 = removeHoles(differenceResult1); |
| 932 | |||
| 933 |
1/1✓ Branch 3 taken 7532 times.
|
7532 | newPolygons1.reserve(newPolygons1.size() + differenceResult1.size()); |
| 934 | |||
| 935 | // create new polygon for each difference | ||
| 936 |
2/2✓ Branch 5 taken 1948 times.
✓ Branch 6 taken 7532 times.
|
9480 | for (auto& pp : differenceResult1) { |
| 937 |
1/1✓ Branch 1 taken 1948 times.
|
1948 | std::vector<Point3d> newPolygon1 = verticesFromBoostPolygon(pp, allPoints, tol, false); |
| 938 | |||
| 939 |
2/2✓ Branch 1 taken 1948 times.
✓ Branch 4 taken 1948 times.
|
1948 | testArea = boost::geometry::area(pp); |
| 940 |
3/6✓ Branch 1 taken 1948 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1948 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1948 times.
|
1948 | if (!testArea || newPolygon1.empty()) { |
| 941 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of face difference, result will not include this polygon, " << newPolygon1); | |
| 942 | ✗ | continue; | |
| 943 |
2/3✓ Branch 1 taken 1948 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1948 times.
|
1948 | } else if (*testArea < tol * tol) { |
| 944 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", | |
| 945 | "Face difference has very small area of " << *testArea << " m^2, result will not include this polygon, " << newPolygon1); | ||
| 946 | ✗ | continue; | |
| 947 | ✗ | } | |
| 948 | try { | ||
| 949 |
1/1✓ Branch 1 taken 1942 times.
|
1948 | has_self_intersections(pp); |
| 950 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
6 | } catch (const boost::geometry::overlay_invalid_input_exception&) { |
| 951 |
6/6✓ Branch 1 taken 6 times.
✓ Branch 4 taken 6 times.
✓ Branch 7 taken 6 times.
✓ Branch 10 taken 6 times.
✓ Branch 13 taken 6 times.
✓ Branch 16 taken 6 times.
|
18 | LOG_FREE(Error, "utilities.geometry.intersect", "Face difference is self intersecting, result will not include this polygon, " << newPolygon1); |
| 952 | 6 | continue; | |
| 953 | 6 | } | |
| 954 | |||
| 955 |
1/1✓ Branch 2 taken 1942 times.
|
1942 | newPolygons1.push_back(std::move(newPolygon1)); |
| 956 | 1948 | } | |
| 957 | |||
| 958 | // polygon2 minus polygon1 | ||
| 959 | 7532 | std::vector<BoostPolygon> differenceResult2; | |
| 960 |
3/3✓ Branch 1 taken 7532 times.
✓ Branch 4 taken 7532 times.
✓ Branch 7 taken 7532 times.
|
7532 | boost::geometry::difference(*boostPolygon2, *boostPolygon1, differenceResult2); |
| 961 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | differenceResult2 = removeSpikes(differenceResult2); |
| 962 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | differenceResult2 = removeHoles(differenceResult2); |
| 963 | |||
| 964 |
1/1✓ Branch 3 taken 7532 times.
|
7532 | newPolygons2.reserve(newPolygons2.size() + differenceResult2.size()); |
| 965 | |||
| 966 | // create new polygon for each difference | ||
| 967 |
2/2✓ Branch 5 taken 3276 times.
✓ Branch 6 taken 7532 times.
|
10808 | for (auto& pp : differenceResult2) { |
| 968 |
1/1✓ Branch 1 taken 3276 times.
|
3276 | std::vector<Point3d> newPolygon2 = verticesFromBoostPolygon(pp, allPoints, tol, false); |
| 969 | |||
| 970 |
2/2✓ Branch 1 taken 3276 times.
✓ Branch 4 taken 3276 times.
|
3276 | testArea = boost::geometry::area(pp); |
| 971 |
5/6✓ Branch 1 taken 3276 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✓ Branch 5 taken 3256 times.
✓ Branch 6 taken 20 times.
✓ Branch 7 taken 3256 times.
|
3276 | if (!testArea || newPolygon2.empty()) { |
| 972 |
6/6✓ Branch 1 taken 20 times.
✓ Branch 4 taken 20 times.
✓ Branch 7 taken 20 times.
✓ Branch 10 taken 20 times.
✓ Branch 13 taken 20 times.
✓ Branch 16 taken 20 times.
|
60 | LOG_FREE(Info, "utilities.geometry.intersect", "Cannot compute area of face difference, result will not include this polygon, " << newPolygon2); |
| 973 | 20 | continue; | |
| 974 |
2/3✓ Branch 1 taken 3256 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 3256 times.
|
3276 | } else if (*testArea < tol * tol) { |
| 975 | ✗ | LOG_FREE(Info, "utilities.geometry.intersect", | |
| 976 | "Face difference has very small area of " << *testArea << " m^2, result will not include this polygon, " << newPolygon2); | ||
| 977 | ✗ | continue; | |
| 978 | ✗ | } | |
| 979 | try { | ||
| 980 |
1/1✓ Branch 1 taken 3256 times.
|
3256 | has_self_intersections(pp); |
| 981 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 982 | ✗ | LOG_FREE(Error, "utilities.geometry.intersect", "Face difference is self intersecting, result will not include this polygon, " << newPolygon2); | |
| 983 | ✗ | continue; | |
| 984 | ✗ | } | |
| 985 | |||
| 986 |
1/1✓ Branch 2 taken 3256 times.
|
3256 | newPolygons2.push_back(std::move(newPolygon2)); |
| 987 | 3276 | } | |
| 988 | |||
| 989 | // intersections are the same | ||
| 990 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | std::vector<Point3d> resultPolygon1 = intersectionVertices; |
| 991 |
1/1✓ Branch 9 taken 7532 times.
|
7532 | IntersectionResult result(std::move(resultPolygon1), std::move(intersectionVertices), std::move(newPolygons1), std::move(newPolygons2)); |
| 992 | |||
| 993 | //std::cout << "Result area1 " << result.area1() << '\n'; | ||
| 994 | //std::cout << "Result area2 " << result.area2() << '\n'; | ||
| 995 | |||
| 996 |
1/1✓ Branch 1 taken 7532 times.
|
7532 | return result; |
| 997 | 26746 | } | |
| 998 | |||
| 999 | 423 | std::vector<std::vector<Point3d>> subtract(const std::vector<Point3d>& polygon, const std::vector<std::vector<Point3d>>& holes, double tol) { | |
| 1000 | 423 | std::vector<std::vector<Point3d>> result; | |
| 1001 | |||
| 1002 | // convert vertices to boost rings | ||
| 1003 | 423 | std::vector<Point3d> allPoints; | |
| 1004 | |||
| 1005 |
1/1✓ Branch 1 taken 423 times.
|
423 | boost::optional<BoostPolygon> initialBoostPolygon = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol); |
| 1006 |
2/2✓ Branch 1 taken 11 times.
✓ Branch 2 taken 412 times.
|
423 | if (!initialBoostPolygon) { |
| 1007 | 11 | return result; | |
| 1008 | } | ||
| 1009 | |||
| 1010 | 412 | std::vector<BoostPolygon> boostPolygons; | |
| 1011 |
2/2✓ Branch 1 taken 412 times.
✓ Branch 4 taken 412 times.
|
412 | boostPolygons.push_back(*initialBoostPolygon); |
| 1012 | |||
| 1013 |
2/2✓ Branch 5 taken 573 times.
✓ Branch 6 taken 410 times.
|
983 | for (const auto& hole : holes) { |
| 1014 |
1/1✓ Branch 1 taken 573 times.
|
573 | boost::optional<BoostPolygon> boostHole = nonIntersectingBoostPolygonFromVertices(hole, allPoints, tol); |
| 1015 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 571 times.
|
573 | if (!boostHole) { |
| 1016 | 2 | return result; | |
| 1017 | } | ||
| 1018 | |||
| 1019 | 571 | std::vector<BoostPolygon> newBoostPolygons; | |
| 1020 | |||
| 1021 |
2/2✓ Branch 5 taken 573 times.
✓ Branch 6 taken 571 times.
|
1144 | for (const BoostPolygon& boostPolygon : boostPolygons) { |
| 1022 | 573 | std::vector<BoostPolygon> diffResult; | |
| 1023 |
2/2✓ Branch 1 taken 573 times.
✓ Branch 4 taken 573 times.
|
573 | boost::geometry::difference(boostPolygon, *boostHole, diffResult); |
| 1024 |
1/1✓ Branch 3 taken 573 times.
|
573 | newBoostPolygons.reserve(newBoostPolygons.size() + diffResult.size()); |
| 1025 |
3/3✓ Branch 2 taken 573 times.
✓ Branch 6 taken 573 times.
✓ Branch 11 taken 573 times.
|
573 | newBoostPolygons.insert(newBoostPolygons.end(), std::make_move_iterator(diffResult.begin()), std::make_move_iterator(diffResult.end())); |
| 1026 | 573 | } | |
| 1027 | 571 | boostPolygons = std::move(newBoostPolygons); | |
| 1028 | 573 | } | |
| 1029 | |||
| 1030 | // Remove the holes and spikes and convert back to our data types | ||
| 1031 |
2/2✓ Branch 5 taken 437 times.
✓ Branch 6 taken 410 times.
|
847 | for (const BoostPolygon& boostPolygon : boostPolygons) { |
| 1032 |
1/1✓ Branch 1 taken 437 times.
|
437 | const BoostPolygon removedSpikes = removeSpikes(boostPolygon); |
| 1033 |
1/1✓ Branch 1 taken 437 times.
|
437 | const std::vector<BoostPolygon>& removedHoles = removeHoles(removedSpikes); |
| 1034 |
1/1✓ Branch 3 taken 437 times.
|
437 | result.reserve(result.size() + removedHoles.size()); |
| 1035 |
2/2✓ Branch 4 taken 2046 times.
✓ Branch 5 taken 437 times.
|
2483 | for (const BoostPolygon& removedHole : removedHoles) { |
| 1036 |
2/2✓ Branch 1 taken 2046 times.
✓ Branch 4 taken 2046 times.
|
2046 | result.push_back(verticesFromBoostPolygon(removedHole, allPoints, tol)); |
| 1037 | } | ||
| 1038 | 437 | } | |
| 1039 | |||
| 1040 | 410 | return result; | |
| 1041 | 423 | } | |
| 1042 | |||
| 1043 | 5 | bool selfIntersects(const std::vector<Point3d>& polygon, double tol) { | |
| 1044 | // convert vertices to boost rings | ||
| 1045 | 5 | std::vector<Point3d> allPoints; | |
| 1046 | |||
| 1047 |
1/1✓ Branch 1 taken 5 times.
|
5 | const boost::optional<BoostPolygon> bp = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol); |
| 1048 | // if bp has a value, we're able to get a non intersecting polygon, so does not self intersect | ||
| 1049 | 10 | return !bp.has_value(); | |
| 1050 | 5 | } | |
| 1051 | |||
| 1052 | ✗ | bool intersects(const std::vector<Point3d>& polygon1, const std::vector<Point3d>& polygon2, double tol) { | |
| 1053 | // convert vertices to boost rings | ||
| 1054 | ✗ | std::vector<Point3d> allPoints; | |
| 1055 | |||
| 1056 | ✗ | boost::optional<BoostPolygon> bp1 = boostPolygonFromVertices(polygon1, allPoints, tol); | |
| 1057 | ✗ | boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol); | |
| 1058 | |||
| 1059 | ✗ | if (bp1 && bp2) { | |
| 1060 | ✗ | return boost::geometry::intersects(*bp1, *bp2); | |
| 1061 | } | ||
| 1062 | |||
| 1063 | ✗ | return false; | |
| 1064 | ✗ | } | |
| 1065 | |||
| 1066 | 1464 | bool within(const Point3d& point1, const std::vector<Point3d>& polygon2, double tol) { | |
| 1067 |
3/5✓ Branch 1 taken 1464 times.
✓ Branch 3 taken 1464 times.
✓ Branch 4 taken 1464 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
4392 | const std::vector<Point3d> geometry1 = {point1}; |
| 1068 |
1/1✓ Branch 1 taken 1464 times.
|
2928 | return within(geometry1, polygon2, tol); |
| 1069 | 2928 | } | |
| 1070 | |||
| 1071 | 4195 | bool within(const std::vector<Point3d>& geometry1, const std::vector<Point3d>& polygon2, double tol) { | |
| 1072 | // convert vertices to boost rings | ||
| 1073 | 4195 | std::vector<Point3d> allPoints; | |
| 1074 | |||
| 1075 |
2/2✓ Branch 1 taken 1464 times.
✓ Branch 2 taken 2731 times.
|
4195 | if (geometry1.size() == 1) { |
| 1076 |
3/3✓ Branch 2 taken 1464 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 1462 times.
|
1464 | if (geometry1[0].z() > tol) { |
| 1077 | 2 | return false; | |
| 1078 | } | ||
| 1079 | |||
| 1080 |
1/1✓ Branch 2 taken 1462 times.
|
1462 | boost::tuple<double, double> p = boostPointFromPoint3d(geometry1[0], allPoints, tol); |
| 1081 |
3/3✓ Branch 1 taken 1462 times.
✓ Branch 4 taken 1462 times.
✓ Branch 7 taken 1462 times.
|
1462 | const BoostPoint boostPoint(p.get<0>(), p.get<1>()); |
| 1082 | |||
| 1083 |
1/1✓ Branch 1 taken 1462 times.
|
1462 | boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol); |
| 1084 | |||
| 1085 |
2/2✓ Branch 0 taken 1409 times.
✓ Branch 1 taken 53 times.
|
1462 | if (bp2) { |
| 1086 |
2/2✓ Branch 1 taken 1409 times.
✓ Branch 4 taken 1409 times.
|
1409 | return boost::geometry::within(boostPoint, *bp2); |
| 1087 | } | ||
| 1088 | |||
| 1089 | 53 | return false; | |
| 1090 | 1462 | } | |
| 1091 | |||
| 1092 | /* | ||
| 1093 | // DLM: this is the better implementation, requires boost 1.57 | ||
| 1094 | boost::optional<BoostPolygon> bp1 = boostPolygonFromVertices(geometry1, allPoints, tol); | ||
| 1095 | boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol); | ||
| 1096 | if (bp1 && bp2){ | ||
| 1097 | return boost::geometry::within(*bp1, *bp2); | ||
| 1098 | } | ||
| 1099 | */ | ||
| 1100 | |||
| 1101 | // DLM: temp code | ||
| 1102 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2731 times.
|
2731 | if (geometry1.size() < 3) { |
| 1103 | ✗ | return false; | |
| 1104 | } | ||
| 1105 |
1/1✓ Branch 1 taken 2731 times.
|
2731 | boost::optional<BoostPolygon> bp2 = boostPolygonFromVertices(polygon2, allPoints, tol); |
| 1106 |
1/2✓ Branch 0 taken 2731 times.
✗ Branch 1 not taken.
|
2731 | if (bp2) { |
| 1107 |
2/2✓ Branch 5 taken 10254 times.
✓ Branch 6 taken 2382 times.
|
12636 | for (const Point3d& point : geometry1) { |
| 1108 |
1/1✓ Branch 1 taken 10254 times.
|
10254 | boost::tuple<double, double> p = boostPointFromPoint3d(point, allPoints, tol); |
| 1109 |
3/3✓ Branch 1 taken 10254 times.
✓ Branch 4 taken 10254 times.
✓ Branch 7 taken 10254 times.
|
10254 | const BoostPoint boostPoint(p.get<0>(), p.get<1>()); |
| 1110 | |||
| 1111 |
4/4✓ Branch 1 taken 10254 times.
✓ Branch 4 taken 10254 times.
✓ Branch 6 taken 349 times.
✓ Branch 7 taken 9905 times.
|
10254 | if (!boost::geometry::within(boostPoint, *bp2)) { |
| 1112 | 349 | return false; | |
| 1113 | } | ||
| 1114 | } | ||
| 1115 | } else { | ||
| 1116 | ✗ | return false; | |
| 1117 | } | ||
| 1118 | |||
| 1119 | 2382 | return true; | |
| 1120 | 4195 | } | |
| 1121 | |||
| 1122 | 2615 | boost::optional<double> getLinearAlpha(const Point3d& point0, const Point3d& point1, const Point3d& test) { | |
| 1123 | // test = point0 + a*(point1 - point0) | ||
| 1124 |
1/1✓ Branch 1 taken 2615 times.
|
2615 | Vector3d diff1 = point1 - point0; |
| 1125 |
1/1✓ Branch 1 taken 2615 times.
|
2615 | const Vector3d diffTest = test - point0; |
| 1126 | |||
| 1127 |
1/1✓ Branch 1 taken 2615 times.
|
2615 | const double length = diff1.length(); |
| 1128 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2615 times.
|
2615 | if (length < 0.001) { |
| 1129 | ✗ | return boost::none; | |
| 1130 | } | ||
| 1131 | |||
| 1132 | 2615 | double a = 0.0; | |
| 1133 |
4/4✓ Branch 1 taken 2615 times.
✓ Branch 5 taken 2615 times.
✓ Branch 8 taken 1222 times.
✓ Branch 9 taken 1393 times.
|
2615 | if (std::abs(diff1.x()) > std::abs(diff1.y())) { |
| 1134 |
3/4✓ Branch 1 taken 1222 times.
✓ Branch 5 taken 1222 times.
✓ Branch 8 taken 1222 times.
✗ Branch 9 not taken.
|
1222 | if (std::abs(diff1.x()) > std::abs(diff1.z())) { |
| 1135 |
2/2✓ Branch 1 taken 1222 times.
✓ Branch 4 taken 1222 times.
|
1222 | a = diffTest.x() / diff1.x(); |
| 1136 | } else { | ||
| 1137 | ✗ | a = diffTest.z() / diff1.z(); | |
| 1138 | } | ||
| 1139 | } else { | ||
| 1140 |
3/4✓ Branch 1 taken 1393 times.
✓ Branch 5 taken 1393 times.
✓ Branch 8 taken 1393 times.
✗ Branch 9 not taken.
|
1393 | if (std::abs(diff1.y()) > std::abs(diff1.z())) { |
| 1141 |
2/2✓ Branch 1 taken 1393 times.
✓ Branch 4 taken 1393 times.
|
1393 | a = diffTest.y() / diff1.y(); |
| 1142 | } else { | ||
| 1143 | ✗ | a = diffTest.z() / diff1.z(); | |
| 1144 | } | ||
| 1145 | } | ||
| 1146 | |||
| 1147 |
1/1✓ Branch 1 taken 2615 times.
|
2615 | diff1.setLength(a * length); |
| 1148 |
1/1✓ Branch 1 taken 2615 times.
|
2615 | const Point3d test2 = point0 + diff1; |
| 1149 |
1/1✓ Branch 1 taken 2615 times.
|
2615 | const double d = getDistance(test, test2); |
| 1150 |
2/2✓ Branch 0 taken 783 times.
✓ Branch 1 taken 1832 times.
|
2615 | if (d < 0.001) { |
| 1151 |
4/4✓ Branch 0 taken 779 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 702 times.
✓ Branch 3 taken 77 times.
|
783 | if (a > 0 && a < 1) { |
| 1152 |
1/1✓ Branch 1 taken 702 times.
|
702 | return a; |
| 1153 | } | ||
| 1154 | } | ||
| 1155 | |||
| 1156 | 1913 | return boost::none; | |
| 1157 | 2615 | } | |
| 1158 | |||
| 1159 | 1605 | std::vector<Point3d> simplify(const std::vector<Point3d>& vertices, bool removeCollinear, double tol) { | |
| 1160 | 1605 | std::vector<Point3d> allPoints; | |
| 1161 | |||
| 1162 | 1605 | bool reversed = false; | |
| 1163 |
1/1✓ Branch 1 taken 1605 times.
|
1605 | boost::optional<Vector3d> outwardNormal = getOutwardNormal(vertices); |
| 1164 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1603 times.
|
1605 | if (!outwardNormal) { |
| 1165 | 2 | return {}; | |
| 1166 |
4/4✓ Branch 1 taken 1603 times.
✓ Branch 4 taken 1603 times.
✓ Branch 6 taken 992 times.
✓ Branch 7 taken 611 times.
|
1603 | } else if (outwardNormal->z() > 0) { |
| 1167 | 992 | reversed = true; | |
| 1168 | } | ||
| 1169 | |||
| 1170 | 1603 | boost::optional<BoostPolygon> bp; | |
| 1171 |
2/2✓ Branch 0 taken 992 times.
✓ Branch 1 taken 611 times.
|
1603 | if (reversed) { |
| 1172 |
3/3✓ Branch 1 taken 992 times.
✓ Branch 4 taken 992 times.
✓ Branch 7 taken 992 times.
|
992 | bp = boostPolygonFromVertices(reorderULC(reverse(vertices)), allPoints, tol); |
| 1173 | } else { | ||
| 1174 |
2/2✓ Branch 1 taken 611 times.
✓ Branch 4 taken 611 times.
|
611 | bp = boostPolygonFromVertices(reorderULC(vertices), allPoints, tol); |
| 1175 | } | ||
| 1176 | |||
| 1177 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1603 times.
|
1603 | if (!bp) { |
| 1178 | ✗ | return {}; | |
| 1179 | } | ||
| 1180 | |||
| 1181 |
2/2✓ Branch 1 taken 1603 times.
✓ Branch 4 taken 1603 times.
|
1603 | boost::geometry::remove_spikes(*bp); |
| 1182 | |||
| 1183 |
1/1✓ Branch 1 taken 1603 times.
|
1603 | 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 |
2/2✓ Branch 0 taken 1535 times.
✓ Branch 1 taken 68 times.
|
1603 | if (!removeCollinear) { |
| 1188 |
2/2✓ Branch 1 taken 1535 times.
✓ Branch 4 taken 1535 times.
|
1535 | boost::geometry::simplify(*bp, out, 0.0); |
| 1189 | } else { | ||
| 1190 |
2/2✓ Branch 1 taken 68 times.
✓ Branch 4 taken 68 times.
|
68 | boost::geometry::simplify(*bp, out, tol); // points within tol would already be merged |
| 1191 | } | ||
| 1192 | |||
| 1193 |
1/1✓ Branch 1 taken 1603 times.
|
1603 | std::vector<Point3d> tmp = verticesFromBoostPolygon(out, allPoints, tol, removeCollinear); |
| 1194 | |||
| 1195 |
2/2✓ Branch 0 taken 992 times.
✓ Branch 1 taken 611 times.
|
1603 | if (reversed) { |
| 1196 |
2/2✓ Branch 1 taken 992 times.
✓ Branch 4 taken 992 times.
|
992 | tmp = reorderULC(reverse(tmp)); |
| 1197 | } else { | ||
| 1198 |
1/1✓ Branch 1 taken 611 times.
|
611 | tmp = reorderULC(tmp); |
| 1199 | } | ||
| 1200 | |||
| 1201 |
2/2✓ Branch 0 taken 68 times.
✓ Branch 1 taken 1535 times.
|
1603 | if (removeCollinear) { |
| 1202 | // collinear points already removed | ||
| 1203 | 68 | return tmp; | |
| 1204 | } | ||
| 1205 | |||
| 1206 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1535 times.
|
1535 | 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 | 1535 | std::set<size_t> pointsToAdd; | |
| 1212 |
2/2✓ Branch 1 taken 10352 times.
✓ Branch 2 taken 1535 times.
|
11887 | for (size_t i = 0; i < allPoints.size(); ++i) { |
| 1213 | 10352 | bool found = false; | |
| 1214 |
2/2✓ Branch 5 taken 79062 times.
✓ Branch 6 taken 10352 times.
|
89414 | for (const auto& tmpPoint : tmp) { |
| 1215 |
3/3✓ Branch 2 taken 79062 times.
✓ Branch 4 taken 9648 times.
✓ Branch 5 taken 69414 times.
|
79062 | if (getDistance(tmpPoint, allPoints[i]) < tol) { |
| 1216 | 9648 | found = true; | |
| 1217 | } | ||
| 1218 | } | ||
| 1219 |
2/2✓ Branch 0 taken 704 times.
✓ Branch 1 taken 9648 times.
|
10352 | if (!found) { |
| 1220 |
1/1✓ Branch 1 taken 704 times.
|
704 | pointsToAdd.insert(i); |
| 1221 | } | ||
| 1222 | } | ||
| 1223 | |||
| 1224 | 1535 | std::vector<Point3d> result; | |
| 1225 |
1/1✓ Branch 2 taken 1535 times.
|
1535 | result.push_back(tmp[0]); |
| 1226 |
2/2✓ Branch 1 taken 8113 times.
✓ Branch 2 taken 1535 times.
|
9648 | for (size_t i = 1; i < tmp.size(); ++i) { |
| 1227 | // see which remaining points fit in this segment, double is index in allPoints, alpha along line | ||
| 1228 | 8113 | std::vector<std::pair<size_t, double>> pointsInSegment; | |
| 1229 |
2/2✓ Branch 5 taken 2487 times.
✓ Branch 6 taken 8113 times.
|
10600 | for (const size_t j : pointsToAdd) { |
| 1230 |
1/1✓ Branch 4 taken 2487 times.
|
2487 | boost::optional<double> alpha = getLinearAlpha(tmp[i - 1], tmp[i], allPoints[j]); |
| 1231 |
2/2✓ Branch 0 taken 576 times.
✓ Branch 1 taken 1911 times.
|
2487 | if (alpha) { |
| 1232 |
2/2✓ Branch 1 taken 576 times.
✓ Branch 4 taken 576 times.
|
576 | pointsInSegment.emplace_back(j, *alpha); |
| 1233 | } | ||
| 1234 | } | ||
| 1235 | |||
| 1236 |
1/1✓ Branch 3 taken 8113 times.
|
8113 | std::sort(pointsInSegment.begin(), pointsInSegment.end(), |
| 1237 | 218 | [](std::pair<size_t, double> a, std::pair<size_t, double> b) { return a.second < b.second; }); | |
| 1238 | |||
| 1239 |
2/2✓ Branch 5 taken 576 times.
✓ Branch 6 taken 8113 times.
|
8689 | for (const auto& pointInSegment : pointsInSegment) { |
| 1240 |
1/1✓ Branch 2 taken 576 times.
|
576 | result.push_back(allPoints[pointInSegment.first]); |
| 1241 |
1/1✓ Branch 1 taken 576 times.
|
576 | pointsToAdd.erase(pointInSegment.first); |
| 1242 | } | ||
| 1243 | |||
| 1244 | // push the next point in simplified polygon | ||
| 1245 |
1/1✓ Branch 2 taken 8113 times.
|
8113 | result.push_back(tmp[i]); |
| 1246 | 8113 | } | |
| 1247 | |||
| 1248 | // now check between last point and first point | ||
| 1249 | 1535 | std::vector<std::pair<size_t, double>> pointsInSegment; | |
| 1250 |
2/2✓ Branch 5 taken 128 times.
✓ Branch 6 taken 1535 times.
|
1663 | for (const size_t j : pointsToAdd) { |
| 1251 |
1/1✓ Branch 5 taken 128 times.
|
128 | boost::optional<double> alpha = getLinearAlpha(tmp[tmp.size() - 1], tmp[0], allPoints[j]); |
| 1252 |
2/2✓ Branch 0 taken 126 times.
✓ Branch 1 taken 2 times.
|
128 | if (alpha) { |
| 1253 |
2/2✓ Branch 1 taken 126 times.
✓ Branch 4 taken 126 times.
|
126 | pointsInSegment.emplace_back(j, *alpha); |
| 1254 | } | ||
| 1255 | } | ||
| 1256 | |||
| 1257 |
1/1✓ Branch 3 taken 1535 times.
|
1535 | std::sort(pointsInSegment.begin(), pointsInSegment.end(), |
| 1258 | 48 | [](std::pair<size_t, double> a, std::pair<size_t, double> b) { return a.second < b.second; }); | |
| 1259 | |||
| 1260 |
2/2✓ Branch 5 taken 126 times.
✓ Branch 6 taken 1535 times.
|
1661 | for (const auto& pointInSegment : pointsInSegment) { |
| 1261 |
1/1✓ Branch 2 taken 126 times.
|
126 | result.push_back(allPoints[pointInSegment.first]); |
| 1262 |
1/1✓ Branch 1 taken 126 times.
|
126 | pointsToAdd.erase(pointInSegment.first); |
| 1263 | } | ||
| 1264 | |||
| 1265 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1533 times.
|
1535 | if (!pointsToAdd.empty()) { |
| 1266 |
6/6✓ Branch 1 taken 2 times.
✓ Branch 5 taken 2 times.
✓ Branch 8 taken 2 times.
✓ Branch 11 taken 2 times.
✓ Branch 14 taken 2 times.
✓ Branch 17 taken 2 times.
|
6 | LOG_FREE(Warn, "utilities.geometry.simplify", pointsToAdd.size() << " unique vertices were not added back to the polygon"); |
| 1267 | } | ||
| 1268 | |||
| 1269 | 1535 | return result; | |
| 1270 | 1605 | } | |
| 1271 | |||
| 1272 | /// Converts a Polygon to a BoostPolygon | ||
| 1273 | 3686 | boost::optional<BoostPolygon> BoostPolygonFromPolygon(const Polygon3d& polygon, Point3dVector& allPoints, double tol) { | |
| 1274 |
1/1✓ Branch 1 taken 3686 times.
|
3686 | BoostPolygon boostPolygon; |
| 1275 | |||
| 1276 |
3/3✓ Branch 1 taken 3686 times.
✓ Branch 7 taken 19902 times.
✓ Branch 8 taken 3686 times.
|
23588 | for (const Point3d& vertex : polygon.getOuterPath()) { |
| 1277 | |||
| 1278 | // should all have zero z coordinate now | ||
| 1279 | //double z = vertex.z(); | ||
| 1280 | //if (std::abs(z) > tol) { | ||
| 1281 | // LOG_FREE(Error, "utilities.geometry.boostPolygonFromVertices", "All points must be on z = 0 plane"); | ||
| 1282 | // return boost::none; | ||
| 1283 | //} | ||
| 1284 |
2/2✓ Branch 1 taken 19902 times.
✓ Branch 4 taken 19902 times.
|
19902 | boost::geometry::append(boostPolygon, boostPointFromPoint3d(vertex, allPoints, tol)); |
| 1285 | 3686 | } | |
| 1286 | |||
| 1287 |
1/1✓ Branch 1 taken 3686 times.
|
3686 | const Point3dVector& path = polygon.getOuterPath(); |
| 1288 | 3686 | const Point3d& first = path.front(); | |
| 1289 |
2/2✓ Branch 1 taken 3686 times.
✓ Branch 4 taken 3686 times.
|
3686 | boost::geometry::append(boostPolygon, boostPointFromPoint3d(first, allPoints, tol)); |
| 1290 | |||
| 1291 |
1/1✓ Branch 1 taken 3686 times.
|
7372 | return boostPolygon; |
| 1292 | 3686 | } | |
| 1293 | |||
| 1294 | 499 | Polygon3d PolygonFromBoostPolygon(const BoostPolygon& boostPolygon, Point3dVector& allPoints, double tol) { | |
| 1295 | 499 | Polygon3d p; | |
| 1296 |
1/1✓ Branch 2 taken 499 times.
|
499 | BoostRing outer = boostPolygon.outer(); |
| 1297 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 499 times.
|
499 | if (outer.empty()) { |
| 1298 | ✗ | return p; | |
| 1299 | } | ||
| 1300 | |||
| 1301 | 499 | Point3dVector points; | |
| 1302 |
2/2✓ Branch 1 taken 4947 times.
✓ Branch 2 taken 499 times.
|
5446 | for (unsigned i = 0; i < outer.size() - 1; ++i) { |
| 1303 |
3/3✓ Branch 2 taken 4947 times.
✓ Branch 6 taken 4947 times.
✓ Branch 9 taken 4947 times.
|
4947 | const Point3d point3d(outer[i].x() / scaleBy, outer[i].y() / scaleBy, 0.0); |
| 1304 |
1/1✓ Branch 1 taken 4947 times.
|
4947 | Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol); |
| 1305 | // don't keep repeated vertices | ||
| 1306 |
5/7✓ Branch 0 taken 4448 times.
✓ Branch 1 taken 499 times.
✓ Branch 4 taken 4448 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 4448 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 4947 times.
|
4947 | if ((i > 0) && (points.back() == resultPoint)) { |
| 1307 | ✗ | continue; | |
| 1308 | } | ||
| 1309 |
1/1✓ Branch 2 taken 4947 times.
|
4947 | points.emplace_back(std::move(resultPoint)); |
| 1310 | 4947 | } | |
| 1311 | |||
| 1312 |
1/1✓ Branch 1 taken 499 times.
|
499 | points = removeCollinearLegacy(points); |
| 1313 |
2/2✓ Branch 5 taken 4947 times.
✓ Branch 6 taken 499 times.
|
5446 | for (const auto& point : points) { |
| 1314 |
1/1✓ Branch 1 taken 4947 times.
|
4947 | p.addPoint(point); |
| 1315 | } | ||
| 1316 | |||
| 1317 |
2/2✓ Branch 6 taken 19 times.
✓ Branch 7 taken 499 times.
|
518 | for (const auto& inner : boostPolygon.inners()) { |
| 1318 | 19 | Point3dVector hole; | |
| 1319 |
2/2✓ Branch 1 taken 76 times.
✓ Branch 2 taken 19 times.
|
95 | for (unsigned i = 0; i < inner.size() - 1; ++i) { |
| 1320 |
3/3✓ Branch 2 taken 76 times.
✓ Branch 6 taken 76 times.
✓ Branch 9 taken 76 times.
|
76 | Point3d point3d(inner[i].x() / scaleBy, inner[i].y() / scaleBy, 0.0); |
| 1321 |
1/1✓ Branch 1 taken 76 times.
|
76 | const Point3d resultPoint = getCombinedPoint(point3d, allPoints, tol); |
| 1322 | // don't keep repeated vertices | ||
| 1323 |
5/7✓ Branch 0 taken 57 times.
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 57 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 57 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 76 times.
|
76 | if ((i > 0) && (hole.back() == resultPoint)) { |
| 1324 | ✗ | continue; | |
| 1325 | } | ||
| 1326 |
1/1✓ Branch 2 taken 76 times.
|
76 | hole.emplace_back(std::move(resultPoint)); |
| 1327 | 76 | } | |
| 1328 |
1/1✓ Branch 1 taken 19 times.
|
19 | p.addHole(hole); |
| 1329 | 19 | } | |
| 1330 | |||
| 1331 | 499 | return p; | |
| 1332 | 499 | } | |
| 1333 | |||
| 1334 | // Non class member stuff | ||
| 1335 | 1843 | boost::optional<Polygon3d> join(const Polygon3d& polygon1, const Polygon3d& polygon2) { | |
| 1336 | 1843 | Point3dVector allPoints; | |
| 1337 | |||
| 1338 | 1843 | constexpr double tol = 0.01; | |
| 1339 | |||
| 1340 | // Convert polygons to boost polygon (not ring obvs) | ||
| 1341 |
1/1✓ Branch 1 taken 1843 times.
|
1843 | boost::optional<BoostPolygon> boostPolygon1 = BoostPolygonFromPolygon(polygon1, allPoints, tol); |
| 1342 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1843 times.
|
1843 | if (!boostPolygon1) { |
| 1343 | ✗ | return boost::none; | |
| 1344 | } | ||
| 1345 | |||
| 1346 |
1/1✓ Branch 1 taken 1843 times.
|
1843 | boost::optional<BoostPolygon> boostPolygon2 = BoostPolygonFromPolygon(polygon2, allPoints, tol); |
| 1347 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1843 times.
|
1843 | if (!boostPolygon2) { |
| 1348 | ✗ | return boost::none; | |
| 1349 | } | ||
| 1350 | |||
| 1351 | 1843 | std::vector<BoostPolygon> unionResult; | |
| 1352 | try { | ||
| 1353 |
3/3✓ Branch 1 taken 1843 times.
✓ Branch 4 taken 1843 times.
✓ Branch 7 taken 1843 times.
|
1843 | boost::geometry::union_(*boostPolygon1, *boostPolygon2, unionResult); |
| 1354 | ✗ | } catch (const boost::geometry::overlay_invalid_input_exception&) { | |
| 1355 | ✗ | LOG_FREE(Error, "utilities.geometry.join", "overlay_invalid_input_exception"); | |
| 1356 | ✗ | return boost::none; | |
| 1357 | ✗ | } | |
| 1358 | |||
| 1359 | // Smooth the result | ||
| 1360 |
1/1✓ Branch 1 taken 1843 times.
|
1843 | unionResult = removeSpikes(unionResult); |
| 1361 | |||
| 1362 | // Check the result - we do not have to bail for holes but we bail for > 1 poly | ||
| 1363 |
6/6✓ Branch 1 taken 1768 times.
✓ Branch 2 taken 75 times.
✓ Branch 4 taken 1269 times.
✓ Branch 5 taken 499 times.
✓ Branch 6 taken 1344 times.
✓ Branch 7 taken 499 times.
|
1843 | if (unionResult.empty() or (unionResult.size() > 1)) { |
| 1364 | 1344 | return boost::none; | |
| 1365 | } | ||
| 1366 | |||
| 1367 | // Convert back to polygon | ||
| 1368 |
1/1✓ Branch 2 taken 499 times.
|
499 | Polygon3d p = PolygonFromBoostPolygon(unionResult.front(), allPoints, tol); |
| 1369 |
1/1✓ Branch 1 taken 499 times.
|
499 | return p; |
| 1370 | 1843 | } | |
| 1371 | |||
| 1372 | 13 | std::vector<Polygon3d> joinAllPolygons(const std::vector<std::vector<Point3d>>& polygons, double tol) { | |
| 1373 | 13 | std::vector<Polygon3d> inputPolygons; | |
| 1374 | |||
| 1375 | // Create Polygon3d from point3dvectors | ||
| 1376 |
2/2✓ Branch 5 taken 189 times.
✓ Branch 6 taken 13 times.
|
202 | for (const auto& polygon : polygons) { |
| 1377 | 189 | Polygon3d inputPolygon; | |
| 1378 |
2/2✓ Branch 5 taken 883 times.
✓ Branch 6 taken 189 times.
|
1072 | for (const auto& point : polygon) { |
| 1379 |
1/1✓ Branch 1 taken 883 times.
|
883 | inputPolygon.addPoint(point); |
| 1380 | } | ||
| 1381 |
1/1✓ Branch 1 taken 189 times.
|
189 | inputPolygons.push_back(inputPolygon); |
| 1382 | 189 | } | |
| 1383 | |||
| 1384 |
1/1✓ Branch 1 taken 13 times.
|
26 | return joinAll(inputPolygons, tol); |
| 1385 | 13 | } | |
| 1386 | |||
| 1387 | 15 | std::vector<Polygon3d> joinAll(const std::vector<Polygon3d>& polygons, double /*tol*/) { | |
| 1388 | |||
| 1389 | 15 | std::vector<Polygon3d> result; | |
| 1390 | |||
| 1391 | 15 | const size_t N = polygons.size(); | |
| 1392 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 15 times.
|
15 | if (N <= 1) { |
| 1393 | ✗ | return polygons; | |
| 1394 | } | ||
| 1395 | |||
| 1396 |
1/1✓ Branch 1 taken 15 times.
|
15 | std::vector<double> polygonAreas(N, 0.0); |
| 1397 |
2/2✓ Branch 0 taken 197 times.
✓ Branch 1 taken 15 times.
|
212 | for (unsigned i = 0; i < N; ++i) { |
| 1398 |
2/2✓ Branch 2 taken 197 times.
✓ Branch 5 taken 197 times.
|
197 | auto area = getArea(polygons[i].getOuterPath()); |
| 1399 |
1/2✓ Branch 0 taken 197 times.
✗ Branch 1 not taken.
|
197 | if (area) { |
| 1400 |
1/1✓ Branch 1 taken 197 times.
|
197 | polygonAreas[i] = *area; |
| 1401 | } | ||
| 1402 | } | ||
| 1403 | |||
| 1404 | // compute adjacency matrix | ||
| 1405 |
1/1✓ Branch 1 taken 15 times.
|
15 | Matrix A(N, N, 0.0); |
| 1406 |
2/2✓ Branch 0 taken 197 times.
✓ Branch 1 taken 15 times.
|
212 | for (unsigned i = 0; i < N; ++i) { |
| 1407 |
1/1✓ Branch 1 taken 197 times.
|
197 | A(i, i) = 1.0; |
| 1408 |
2/2✓ Branch 0 taken 1571 times.
✓ Branch 1 taken 197 times.
|
1768 | for (unsigned j = i + 1; j < N; ++j) { |
| 1409 |
3/3✓ Branch 3 taken 1571 times.
✓ Branch 6 taken 320 times.
✓ Branch 7 taken 1251 times.
|
3142 | if (join(polygons[i], polygons[j] /*,tol*/)) { |
| 1410 |
1/1✓ Branch 1 taken 320 times.
|
320 | A(i, j) = 1.0; |
| 1411 |
1/1✓ Branch 1 taken 320 times.
|
320 | A(j, i) = 1.0; |
| 1412 | } | ||
| 1413 | } | ||
| 1414 | } | ||
| 1415 | |||
| 1416 |
1/1✓ Branch 1 taken 15 times.
|
15 | const std::vector<std::vector<unsigned>> connectedComponents = findConnectedComponents(A); |
| 1417 |
2/2✓ Branch 5 taken 15 times.
✓ Branch 6 taken 15 times.
|
30 | for (const std::vector<unsigned>& component : connectedComponents) { |
| 1418 | |||
| 1419 |
1/1✓ Branch 1 taken 15 times.
|
15 | std::vector<unsigned> orderedComponent(component); |
| 1420 | // #4831 - Use a stable_sort to produce consistent results between Windows and Unix in case you have polygons with the same area | ||
| 1421 |
1/1✓ Branch 3 taken 15 times.
|
15 | std::stable_sort(orderedComponent.begin(), orderedComponent.end(), |
| 1422 | 652 | [&polygonAreas](int ia, int ib) { return polygonAreas[ia] > polygonAreas[ib]; }); | |
| 1423 | |||
| 1424 | 15 | Polygon3d polygon; | |
| 1425 | 15 | std::set<unsigned> joinedComponents; | |
| 1426 | // try to join at most component.size() times | ||
| 1427 |
2/2✓ Branch 1 taken 44 times.
✓ Branch 2 taken 3 times.
|
47 | for (unsigned n = 0; n < component.size(); ++n) { |
| 1428 | |||
| 1429 | // loop over polygons to join in order | ||
| 1430 |
2/2✓ Branch 5 taken 522 times.
✓ Branch 6 taken 44 times.
|
566 | for (const unsigned i : orderedComponent) { |
| 1431 |
3/3✓ Branch 1 taken 522 times.
✓ Branch 5 taken 15 times.
✓ Branch 6 taken 507 times.
|
522 | if (polygon.getOuterPath().empty()) { |
| 1432 |
1/1✓ Branch 2 taken 15 times.
|
15 | polygon = polygons[i]; |
| 1433 |
1/1✓ Branch 1 taken 15 times.
|
15 | joinedComponents.insert(i); |
| 1434 | } else { | ||
| 1435 | // if not already joined | ||
| 1436 |
3/3✓ Branch 2 taken 507 times.
✓ Branch 5 taken 269 times.
✓ Branch 6 taken 238 times.
|
507 | if (joinedComponents.find(i) == joinedComponents.end()) { |
| 1437 |
1/1✓ Branch 2 taken 269 times.
|
269 | boost::optional<Polygon3d> joined = join(polygon, polygons[i] /*, tol*/); |
| 1438 |
2/2✓ Branch 0 taken 176 times.
✓ Branch 1 taken 93 times.
|
269 | if (joined) { |
| 1439 |
2/2✓ Branch 1 taken 176 times.
✓ Branch 4 taken 176 times.
|
176 | polygon = *joined; |
| 1440 |
1/1✓ Branch 1 taken 176 times.
|
176 | joinedComponents.insert(i); |
| 1441 | } | ||
| 1442 | 269 | } | |
| 1443 | } | ||
| 1444 | } | ||
| 1445 | |||
| 1446 | // if all polygons have been joined then we are done | ||
| 1447 |
2/2✓ Branch 2 taken 12 times.
✓ Branch 3 taken 32 times.
|
44 | if (joinedComponents.size() == component.size()) { |
| 1448 | 12 | break; | |
| 1449 | } | ||
| 1450 | } | ||
| 1451 | |||
| 1452 |
2/2✓ Branch 2 taken 3 times.
✓ Branch 3 taken 12 times.
|
15 | if (joinedComponents.size() != component.size()) { |
| 1453 |
5/5✓ Branch 1 taken 3 times.
✓ Branch 4 taken 3 times.
✓ Branch 7 taken 3 times.
✓ Branch 10 taken 3 times.
✓ Branch 13 taken 3 times.
|
9 | LOG_FREE(Error, "utilities.geometry.joinAll", "Could not join all connected components"); |
| 1454 | } | ||
| 1455 |
1/1✓ Branch 1 taken 15 times.
|
15 | result.push_back(polygon); |
| 1456 | 15 | } | |
| 1457 | |||
| 1458 | 15 | return result; | |
| 1459 | 15 | } | |
| 1460 | |||
| 1461 | ✗ | std::vector<Polygon3d> bufferAll(const std::vector<Polygon3d>& polygons, double tol) { | |
| 1462 | ✗ | BoostMultiPolygon source; | |
| 1463 | ✗ | std::vector<Point3d> allPoints; | |
| 1464 | |||
| 1465 | ✗ | for (const Polygon3d& polygon : polygons) { | |
| 1466 | ✗ | boost::optional<BoostPolygon> boostPolygon = BoostPolygonFromPolygon(polygon, allPoints, tol); | |
| 1467 | ✗ | source.push_back(*boostPolygon); | |
| 1468 | ✗ | } | |
| 1469 | |||
| 1470 | ✗ | const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> expand(tol * scaleBy); | |
| 1471 | ✗ | const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> shrink(-tol * scaleBy); | |
| 1472 | ✗ | const boost::geometry::strategy::buffer::join_miter join_strategy; | |
| 1473 | const boost::geometry::strategy::buffer::end_flat end_strategy; | ||
| 1474 | const boost::geometry::strategy::buffer::side_straight side_strategy; | ||
| 1475 | ✗ | const boost::geometry::strategy::buffer::point_circle point_strategy; | |
| 1476 | |||
| 1477 | ✗ | BoostMultiPolygon resultExpand; | |
| 1478 | ✗ | BoostMultiPolygon resultShrink; | |
| 1479 | ✗ | boost::geometry::buffer(source, resultExpand, expand, side_strategy, join_strategy, end_strategy, point_strategy); | |
| 1480 | ✗ | boost::geometry::buffer(resultExpand, resultShrink, shrink, side_strategy, join_strategy, end_strategy, point_strategy); | |
| 1481 | |||
| 1482 | ✗ | std::vector<Polygon3d> result; | |
| 1483 | ✗ | result.reserve(resultShrink.size()); | |
| 1484 | ✗ | for (const auto& boostPolygon : resultShrink) { | |
| 1485 | ✗ | BoostPolygon simplified; | |
| 1486 | ✗ | boost::geometry::simplify(boostPolygon, simplified, tol); | |
| 1487 | ✗ | result.push_back(PolygonFromBoostPolygon(simplified, allPoints, tol)); | |
| 1488 | ✗ | } | |
| 1489 | |||
| 1490 | ✗ | return result; | |
| 1491 | ✗ | } | |
| 1492 | |||
| 1493 | 31 | boost::optional<std::vector<Point3d>> buffer(const std::vector<Point3d>& polygon1, double amount, double tol) { | |
| 1494 | 31 | std::vector<Point3d> allPoints; | |
| 1495 |
1/1✓ Branch 1 taken 31 times.
|
31 | boost::optional<BoostPolygon> boostPolygon1 = nonIntersectingBoostPolygonFromVertices(polygon1, allPoints, tol); |
| 1496 | |||
| 1497 |
2/2✓ Branch 1 taken 15 times.
✓ Branch 2 taken 16 times.
|
31 | if (!boostPolygon1) { |
| 1498 | 15 | return boost::none; | |
| 1499 | } | ||
| 1500 | |||
| 1501 | 16 | constexpr double miterLimit = 15; | |
| 1502 | //const double buffer_distance = 1.0; | ||
| 1503 | //const int points_per_circle = 36; | ||
| 1504 | 16 | const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> distance_strategy(amount * scaleBy); | |
| 1505 |
1/1✓ Branch 1 taken 16 times.
|
16 | const boost::geometry::strategy::buffer::join_miter join_strategy(miterLimit * scaleBy); |
| 1506 | const boost::geometry::strategy::buffer::end_flat end_strategy; | ||
| 1507 | const boost::geometry::strategy::buffer::side_straight side_strategy; | ||
| 1508 | 16 | const boost::geometry::strategy::buffer::point_circle point_strategy; | |
| 1509 | |||
| 1510 | 16 | BoostMultiPolygon polygons; | |
| 1511 |
2/2✓ Branch 1 taken 16 times.
✓ Branch 4 taken 16 times.
|
16 | polygons.push_back(*boostPolygon1); |
| 1512 | |||
| 1513 | 16 | BoostMultiPolygon buffered; | |
| 1514 | 16 | BoostMultiPolygon result; | |
| 1515 | |||
| 1516 |
1/1✓ Branch 1 taken 16 times.
|
16 | boost::geometry::buffer(polygons, buffered, distance_strategy, side_strategy, join_strategy, end_strategy, point_strategy); |
| 1517 |
1/1✓ Branch 1 taken 16 times.
|
16 | boost::geometry::simplify(buffered, result, 0.0005); |
| 1518 | |||
| 1519 |
1/1✓ Branch 2 taken 16 times.
|
16 | std::vector<Point3d> vertices = verticesFromBoostPolygon(result[0], allPoints, tol); |
| 1520 |
1/1✓ Branch 1 taken 16 times.
|
16 | return vertices; |
| 1521 | 31 | } | |
| 1522 | |||
| 1523 | 8 | boost::optional<std::vector<std::vector<Point3d>>> buffer(const std::vector<std::vector<Point3d>>& polygons, double amount, double tol) { | |
| 1524 | 8 | std::vector<Point3d> allPoints; | |
| 1525 | |||
| 1526 | 8 | BoostMultiPolygon boostPolygons; | |
| 1527 |
1/1✓ Branch 2 taken 8 times.
|
8 | boostPolygons.reserve(polygons.size()); |
| 1528 |
2/2✓ Branch 5 taken 21 times.
✓ Branch 6 taken 8 times.
|
29 | for (const auto& polygon : polygons) { |
| 1529 |
1/1✓ Branch 1 taken 21 times.
|
21 | boost::optional<BoostPolygon> boostPolygon = nonIntersectingBoostPolygonFromVertices(polygon, allPoints, tol); |
| 1530 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 21 times.
|
21 | if (!boostPolygon) { |
| 1531 | ✗ | return boost::none; | |
| 1532 | } | ||
| 1533 |
2/2✓ Branch 1 taken 21 times.
✓ Branch 4 taken 21 times.
|
21 | boostPolygons.push_back(boostPolygon.get()); |
| 1534 | 21 | } | |
| 1535 | |||
| 1536 | 8 | constexpr double miterLimit = 15; | |
| 1537 | 8 | const boost::geometry::strategy::buffer::distance_symmetric<coordinate_type> distance_strategy(amount * scaleBy); | |
| 1538 |
1/1✓ Branch 1 taken 8 times.
|
8 | const boost::geometry::strategy::buffer::join_miter join_strategy(miterLimit * scaleBy); |
| 1539 | const boost::geometry::strategy::buffer::end_flat end_strategy; | ||
| 1540 | const boost::geometry::strategy::buffer::side_straight side_strategy; | ||
| 1541 | 8 | const boost::geometry::strategy::buffer::point_circle point_strategy; | |
| 1542 | |||
| 1543 | 8 | BoostMultiPolygon offset; | |
| 1544 | 8 | BoostMultiPolygon result; | |
| 1545 |
1/1✓ Branch 1 taken 8 times.
|
8 | boost::geometry::buffer(boostPolygons, offset, distance_strategy, side_strategy, join_strategy, end_strategy, point_strategy); |
| 1546 |
1/1✓ Branch 1 taken 8 times.
|
8 | boost::geometry::simplify(offset, result, 0.0005); |
| 1547 | |||
| 1548 | 8 | std::vector<Point3dVector> results; | |
| 1549 |
1/1✓ Branch 2 taken 8 times.
|
8 | results.reserve(result.size()); |
| 1550 |
2/2✓ Branch 4 taken 9 times.
✓ Branch 5 taken 8 times.
|
17 | for (const auto& boostPolygon : result) { |
| 1551 |
2/2✓ Branch 1 taken 9 times.
✓ Branch 4 taken 9 times.
|
9 | results.push_back(verticesFromBoostPolygon(boostPolygon, allPoints, tol)); |
| 1552 | } | ||
| 1553 |
1/1✓ Branch 1 taken 8 times.
|
8 | return results; |
| 1554 | 8 | } | |
| 1555 | |||
| 1556 | // buffers the polygons to increase reliability of joining | ||
| 1557 | ✗ | std::vector<std::vector<Point3d>> joinAllWithBuffer(const std::vector<std::vector<Point3d>>& polygons, double offset, double tol) { | |
| 1558 | ✗ | std::vector<std::vector<Point3d>> result; | |
| 1559 | |||
| 1560 | ✗ | const size_t N = polygons.size(); | |
| 1561 | ✗ | if (N <= 1) { | |
| 1562 | ✗ | return polygons; | |
| 1563 | } | ||
| 1564 | |||
| 1565 | ✗ | std::vector<double> polygonAreas(N, 0.0); | |
| 1566 | ✗ | for (unsigned i = 0; i < N; ++i) { | |
| 1567 | ✗ | auto area = getArea(polygons[i]); | |
| 1568 | ✗ | if (area) { | |
| 1569 | ✗ | polygonAreas[i] = *area; | |
| 1570 | } | ||
| 1571 | } | ||
| 1572 | |||
| 1573 | ✗ | std::vector<std::vector<Point3d>> modifiedPolygons; | |
| 1574 | |||
| 1575 | ✗ | for (unsigned i = 0; i < N; i++) { | |
| 1576 | ✗ | modifiedPolygons.push_back(*buffer(polygons[i], offset, tol)); | |
| 1577 | } | ||
| 1578 | |||
| 1579 | // compute adjacency matrix | ||
| 1580 | ✗ | Matrix A(N, N, 0.0); | |
| 1581 | ✗ | for (unsigned i = 0; i < N; ++i) { | |
| 1582 | ✗ | A(i, i) = 1.0; | |
| 1583 | ✗ | for (unsigned j = i + 1; j < N; ++j) { | |
| 1584 | ✗ | if (join(modifiedPolygons[i], modifiedPolygons[j], tol)) { | |
| 1585 | ✗ | A(i, j) = 1.0; | |
| 1586 | ✗ | A(j, i) = 1.0; | |
| 1587 | } | ||
| 1588 | } | ||
| 1589 | } | ||
| 1590 | |||
| 1591 | ✗ | const std::vector<std::vector<unsigned>> connectedComponents = findConnectedComponents(A); | |
| 1592 | ✗ | for (const std::vector<unsigned>& component : connectedComponents) { | |
| 1593 | ✗ | std::vector<unsigned> orderedComponent(component); | |
| 1594 | ✗ | std::sort(orderedComponent.begin(), orderedComponent.end(), [&polygonAreas](int ia, int ib) { return polygonAreas[ia] > polygonAreas[ib]; }); | |
| 1595 | |||
| 1596 | ✗ | std::vector<Point3d> points; | |
| 1597 | ✗ | std::set<unsigned> joinedComponents; | |
| 1598 | |||
| 1599 | // try to join at most component.size() times | ||
| 1600 | ✗ | for (unsigned n = 0; n < component.size(); ++n) { | |
| 1601 | |||
| 1602 | // loop over polygons to join in order | ||
| 1603 | ✗ | for (const unsigned i : orderedComponent) { | |
| 1604 | ✗ | if (points.empty()) { | |
| 1605 | ✗ | points = modifiedPolygons[i]; | |
| 1606 | ✗ | joinedComponents.insert(i); | |
| 1607 | } else { | ||
| 1608 | // if not already joined | ||
| 1609 | ✗ | if (joinedComponents.find(i) == joinedComponents.end()) { | |
| 1610 | ✗ | boost::optional<std::vector<Point3d>> joined = join(points, modifiedPolygons[i], tol); | |
| 1611 | ✗ | if (joined) { | |
| 1612 | ✗ | points = *joined; | |
| 1613 | ✗ | joinedComponents.insert(i); | |
| 1614 | } | ||
| 1615 | ✗ | } | |
| 1616 | } | ||
| 1617 | } | ||
| 1618 | |||
| 1619 | // if all polygons have been joined then we are done | ||
| 1620 | ✗ | if (joinedComponents.size() == component.size()) { | |
| 1621 | ✗ | break; | |
| 1622 | } | ||
| 1623 | } | ||
| 1624 | |||
| 1625 | ✗ | if (joinedComponents.size() != component.size()) { | |
| 1626 | ✗ | LOG_FREE(Error, "utilities.geometry.joinAll", "Could not join all connected components"); | |
| 1627 | } | ||
| 1628 | ✗ | points = simplify(points, true, tol); | |
| 1629 | ✗ | result.push_back(points); | |
| 1630 | ✗ | } | |
| 1631 | |||
| 1632 | ✗ | return result; | |
| 1633 | ✗ | } | |
| 1634 | } // namespace openstudio | ||
| 1635 |