File indexing completed on 2025-07-05 08:33:00
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
0016
0017 #include <cstddef>
0018 #include <algorithm>
0019 #include <map>
0020 #include <set>
0021 #include <vector>
0022
0023 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0024 # include <iostream>
0025 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0026 # include <boost/geometry/io/wkt/wkt.hpp>
0027 # if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
0028 # define BOOST_GEOMETRY_DEBUG_IDENTIFIER
0029 #endif
0030 #endif
0031
0032 #include <boost/range/begin.hpp>
0033 #include <boost/range/end.hpp>
0034 #include <boost/range/value_type.hpp>
0035
0036 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
0037 #include <boost/geometry/algorithms/detail/overlay/discard_duplicate_turns.hpp>
0038 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
0039 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
0040 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0041 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
0042 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0043 #include <boost/geometry/policies/robustness/robust_type.hpp>
0044 #include <boost/geometry/util/constexpr.hpp>
0045 #include <boost/geometry/util/for_each_with_index.hpp>
0046
0047 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0048 # include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
0049 #endif
0050
0051
0052 namespace boost { namespace geometry
0053 {
0054
0055 #ifndef DOXYGEN_NO_DETAIL
0056 namespace detail { namespace overlay
0057 {
0058
0059 template <typename Turns>
0060 struct discarded_indexed_turn
0061 {
0062 discarded_indexed_turn(Turns const& turns)
0063 : m_turns(turns)
0064 {}
0065
0066 template <typename IndexedTurn>
0067 inline bool operator()(IndexedTurn const& indexed) const
0068 {
0069 return m_turns[indexed.turn_index].discarded;
0070 }
0071
0072 Turns const& m_turns;
0073 };
0074
0075
0076
0077
0078
0079
0080 template
0081 <
0082 bool Reverse1, bool Reverse2,
0083 typename Operations,
0084 typename Turns,
0085 typename Geometry1, typename Geometry2,
0086 typename RobustPolicy,
0087 typename Strategy
0088 >
0089 inline void enrich_sort(Operations& operations,
0090 Turns const& turns,
0091 Geometry1 const& geometry1,
0092 Geometry2 const& geometry2,
0093 RobustPolicy const& robust_policy,
0094 Strategy const& strategy)
0095 {
0096 std::sort(std::begin(operations),
0097 std::end(operations),
0098 less_by_segment_ratio
0099 <
0100 Turns,
0101 typename boost::range_value<Operations>::type,
0102 Geometry1, Geometry2,
0103 RobustPolicy,
0104 Strategy,
0105 Reverse1, Reverse2
0106 >(turns, geometry1, geometry2, robust_policy, strategy));
0107 }
0108
0109
0110
0111 template <typename Operations, typename Turns>
0112 inline void enrich_assign(Operations& operations, Turns& turns,
0113 bool check_consecutive_turns)
0114 {
0115 for_each_with_index(operations, [&](std::size_t index, auto const& indexed)
0116 {
0117 auto& turn = turns[indexed.turn_index];
0118 auto& op = turn.operations[indexed.operation_index];
0119
0120 std::size_t next_index = index + 1 < operations.size() ? index + 1 : 0;
0121 auto advance = [&operations](auto index)
0122 {
0123 std::size_t const result = index + 1;
0124 return result >= operations.size() ? 0 : result;
0125 };
0126
0127 auto next_turn = [&operations, &turns, &next_index]()
0128 {
0129 return turns[operations[next_index].turn_index];
0130 };
0131 auto next_operation = [&operations, &turns, &next_index]()
0132 {
0133 auto const& next_turn = turns[operations[next_index].turn_index];
0134 return next_turn.operations[operations[next_index].operation_index];
0135 };
0136
0137 if (check_consecutive_turns
0138 && indexed.turn_index == operations[next_index].turn_index
0139 && op.seg_id == next_operation().seg_id)
0140 {
0141
0142
0143
0144
0145
0146
0147
0148
0149
0150
0151
0152
0153
0154
0155
0156
0157
0158
0159
0160
0161
0162 next_index = advance(next_index);
0163 }
0164
0165
0166
0167
0168 while (turn.is_clustered()
0169 && turn.cluster_id == next_turn().cluster_id
0170 && op.seg_id == next_operation().seg_id
0171 && indexed.turn_index != operations[next_index].turn_index)
0172 {
0173 next_index = advance(next_index);
0174 }
0175
0176 op.enriched.travels_to_ip_index
0177 = static_cast<signed_size_type>(operations[next_index].turn_index);
0178 op.enriched.travels_to_vertex_index
0179 = operations[next_index].subject->seg_id.segment_index;
0180
0181 auto const& next_op = next_operation();
0182 if (op.seg_id.segment_index == next_op.seg_id.segment_index
0183 && op.fraction < next_op.fraction)
0184 {
0185
0186 op.enriched.next_ip_index = static_cast<signed_size_type>(operations[next_index].turn_index);
0187 }
0188 });
0189
0190 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0191 for (auto const& indexed_op : operations)
0192 {
0193 auto const& op = turns[indexed_op.turn_index].operations[indexed_op.operation_index];
0194
0195 std::cout << indexed_op.turn_index
0196 << " cl=" << turns[indexed_op.turn_index].cluster_id
0197 << " meth=" << method_char(turns[indexed_op.turn_index].method)
0198 << " seg=" << op.seg_id
0199 << " dst=" << op.fraction
0200 << " op=" << operation_char(turns[indexed_op.turn_index].operations[0].operation)
0201 << operation_char(turns[indexed_op.turn_index].operations[1].operation)
0202 << " (" << operation_char(op.operation) << ")"
0203 << " nxt=" << op.enriched.next_ip_index
0204 << " / " << op.enriched.travels_to_ip_index
0205 << " [vx " << op.enriched.travels_to_vertex_index << "]"
0206 << (turns[indexed_op.turn_index].discarded ? " [discarded]" : "")
0207 << (op.enriched.startable ? "" : " [not startable]")
0208 << std::endl;
0209 }
0210 #endif
0211 }
0212
0213 template <typename Operations, typename Turns>
0214 inline void enrich_adapt(Operations& operations, Turns& turns)
0215 {
0216
0217
0218 if (operations.size() < 3)
0219 {
0220 return;
0221 }
0222
0223 bool next_phase = false;
0224 std::size_t previous_index = operations.size() - 1;
0225
0226 for_each_with_index(operations, [&](std::size_t index, auto const& indexed)
0227 {
0228 auto& turn = turns[indexed.turn_index];
0229 auto& op = turn.operations[indexed.operation_index];
0230
0231 std::size_t const next_index = index + 1 < operations.size() ? index + 1 : 0;
0232 auto const& next_turn = turns[operations[next_index].turn_index];
0233 auto const& next_op = next_turn.operations[operations[next_index].operation_index];
0234
0235 if (op.seg_id.segment_index == next_op.seg_id.segment_index)
0236 {
0237 auto const& prev_turn = turns[operations[previous_index].turn_index];
0238 auto const& prev_op = prev_turn.operations[operations[previous_index].operation_index];
0239 if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
0240 {
0241 op.enriched.startable = false;
0242 next_phase = true;
0243 }
0244 }
0245 previous_index = index;
0246 });
0247
0248 if (! next_phase)
0249 {
0250 return;
0251 }
0252
0253
0254 next_phase = false;
0255 for (auto& turn : turns)
0256 {
0257 if (! turn.operations[0].enriched.startable
0258 && ! turn.operations[1].enriched.startable)
0259 {
0260 turn.discarded = true;
0261 next_phase = true;
0262 }
0263 }
0264
0265 if (! next_phase)
0266 {
0267 return;
0268 }
0269
0270
0271 discarded_indexed_turn<Turns> const predicate(turns);
0272 operations.erase(std::remove_if(std::begin(operations),
0273 std::end(operations), predicate), std::end(operations));
0274 }
0275
0276 struct enriched_map_default_include_policy
0277 {
0278 template <typename Operation>
0279 static inline bool include(Operation const& )
0280 {
0281
0282 return true;
0283 }
0284 };
0285
0286
0287
0288
0289 template <typename Turns, typename MappedVector, typename IncludePolicy>
0290 inline void create_map(Turns const& turns, MappedVector& mapped_vector,
0291 IncludePolicy const& include_policy)
0292 {
0293 for_each_with_index(turns, [&](std::size_t index, auto const& turn)
0294 {
0295 if (! turn.discarded)
0296 {
0297 for_each_with_index(turn.operations, [&](std::size_t op_index, auto const& op)
0298 {
0299 if (include_policy.include(op.operation))
0300 {
0301 ring_identifier const ring_id
0302 (
0303 op.seg_id.source_index,
0304 op.seg_id.multi_index,
0305 op.seg_id.ring_index
0306 );
0307 mapped_vector[ring_id].emplace_back
0308 (
0309 index, op_index, op, turn.operations[1 - op_index].seg_id
0310 );
0311 }
0312 });
0313 }
0314 });
0315 }
0316
0317 template <typename Point1, typename Point2>
0318 inline typename geometry::coordinate_type<Point1>::type
0319 distance_measure(Point1 const& a, Point2 const& b)
0320 {
0321
0322
0323 using ctype = typename geometry::coordinate_type<Point1>::type;
0324 ctype const dx = get<0>(a) - get<0>(b);
0325 ctype const dy = get<1>(a) - get<1>(b);
0326 return dx * dx + dy * dy;
0327 }
0328
0329 template <typename Turns>
0330 inline void calculate_remaining_distance(Turns& turns)
0331 {
0332 for (auto& turn : turns)
0333 {
0334 auto& op0 = turn.operations[0];
0335 auto& op1 = turn.operations[1];
0336
0337 static decltype(op0.remaining_distance) const zero_distance = 0;
0338
0339 if (op0.remaining_distance != zero_distance
0340 || op1.remaining_distance != zero_distance)
0341 {
0342 continue;
0343 }
0344
0345 auto const to_index0 = op0.enriched.get_next_turn_index();
0346 auto const to_index1 = op1.enriched.get_next_turn_index();
0347 if (to_index0 >= 0
0348 && to_index1 >= 0
0349 && to_index0 != to_index1)
0350 {
0351 op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
0352 op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
0353 }
0354 }
0355 }
0356
0357
0358 }}
0359 #endif
0360
0361
0362
0363
0364
0365
0366
0367
0368
0369
0370
0371
0372
0373
0374
0375
0376
0377
0378
0379 template
0380 <
0381 bool Reverse1, bool Reverse2,
0382 overlay_type OverlayType,
0383 typename Turns,
0384 typename Clusters,
0385 typename Geometry1, typename Geometry2,
0386 typename RobustPolicy,
0387 typename IntersectionStrategy
0388 >
0389 inline void enrich_intersection_points(Turns& turns,
0390 Clusters& clusters,
0391 Geometry1 const& geometry1, Geometry2 const& geometry2,
0392 RobustPolicy const& robust_policy,
0393 IntersectionStrategy const& strategy)
0394 {
0395 constexpr detail::overlay::operation_type target_operation
0396 = detail::overlay::operation_from_overlay<OverlayType>::value;
0397 constexpr detail::overlay::operation_type opposite_operation
0398 = target_operation == detail::overlay::operation_union
0399 ? detail::overlay::operation_intersection
0400 : detail::overlay::operation_union;
0401 constexpr bool is_dissolve = OverlayType == overlay_dissolve;
0402 constexpr bool is_buffer = OverlayType == overlay_buffer;
0403
0404 using turn_type = typename boost::range_value<Turns>::type;
0405 using indexed_turn_operation = detail::overlay::indexed_turn_operation
0406 <
0407 typename turn_type::turn_operation_type
0408 > ;
0409
0410 using mapped_vector_type = std::map
0411 <
0412 ring_identifier,
0413 std::vector<indexed_turn_operation>
0414 >;
0415
0416
0417
0418
0419 bool has_cc = false;
0420 bool has_colocations = false;
0421
0422 if BOOST_GEOMETRY_CONSTEXPR (! is_buffer)
0423 {
0424
0425 has_colocations = detail::overlay::handle_colocations
0426 <
0427 Reverse1, Reverse2, OverlayType, Geometry1, Geometry2
0428 >(turns, clusters, robust_policy);
0429
0430
0431 detail::overlay::gather_cluster_properties
0432 <
0433 Reverse1,
0434 Reverse2,
0435 OverlayType
0436 >(clusters, turns, target_operation,
0437 geometry1, geometry2, strategy);
0438 }
0439 else
0440 {
0441
0442 has_colocations = ! clusters.empty();
0443 }
0444
0445 discard_duplicate_start_turns(turns, geometry1, geometry2);
0446
0447
0448 for (auto& turn : turns)
0449 {
0450 if (turn.both(detail::overlay::operation_none)
0451 || turn.both(opposite_operation)
0452 || turn.both(detail::overlay::operation_blocked)
0453 || (detail::overlay::is_self_turn<OverlayType>(turn)
0454 && ! turn.is_clustered()
0455 && ! turn.both(target_operation)))
0456 {
0457
0458
0459
0460
0461
0462
0463
0464
0465
0466
0467 turn.discarded = true;
0468 turn.cluster_id = -1;
0469 continue;
0470 }
0471
0472 if (! turn.discarded
0473 && turn.both(detail::overlay::operation_continue))
0474 {
0475 has_cc = true;
0476 }
0477 }
0478
0479 if (! is_dissolve)
0480 {
0481 detail::overlay::discard_closed_turns
0482 <
0483 OverlayType,
0484 target_operation
0485 >::apply(turns, clusters, geometry1, geometry2,
0486 strategy);
0487 detail::overlay::discard_open_turns
0488 <
0489 OverlayType,
0490 target_operation
0491 >::apply(turns, clusters, geometry1, geometry2,
0492 strategy);
0493 }
0494
0495
0496
0497 mapped_vector_type mapped_vector;
0498
0499 detail::overlay::create_map(turns, mapped_vector,
0500 detail::overlay::enriched_map_default_include_policy());
0501
0502 for (auto& pair : mapped_vector)
0503 {
0504 detail::overlay::enrich_sort<Reverse1, Reverse2>(
0505 pair.second, turns,
0506 geometry1, geometry2,
0507 robust_policy, strategy);
0508 }
0509
0510 if (has_colocations)
0511 {
0512 detail::overlay::cleanup_clusters(turns, clusters);
0513 detail::overlay::colocate_clusters(clusters, turns);
0514 }
0515
0516
0517
0518 for (auto& pair : mapped_vector)
0519 {
0520 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0521 std::cout << "ENRICH-assign Ring " << pair.first << std::endl;
0522 #endif
0523 if (is_dissolve)
0524 {
0525 detail::overlay::enrich_adapt(pair.second, turns);
0526 }
0527
0528 detail::overlay::enrich_assign(pair.second, turns, ! is_dissolve);
0529 }
0530
0531 if (has_cc)
0532 {
0533 detail::overlay::calculate_remaining_distance(turns);
0534 }
0535
0536 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
0537
0538 #endif
0539
0540 }
0541
0542 }}
0543
0544 #endif