| 71 | |
| 72 | template<typename T> |
| 73 | void rayPolylineIntersectAll_( const Polyline2& polyline, const Line2<T>& line, const PolylineIntersectionCallback2<T>& callback, |
| 74 | T rayStart, T rayEnd, const IntersectionPrecomputes2<T>& prec ) |
| 75 | { |
| 76 | if ( !callback ) |
| 77 | { |
| 78 | assert( false ); |
| 79 | return; |
| 80 | } |
| 81 | |
| 82 | const auto& tree = polyline.getAABBTree(); |
| 83 | if ( tree.nodes().empty() ) |
| 84 | return; |
| 85 | |
| 86 | // we `insignificantlyExpand` boxes to avoid leaks due to float errors |
| 87 | // (small intersection of neighbor boxes guarantee that both of them will be considered as candidates of connection area) |
| 88 | |
| 89 | auto rayExpBoxIntersect = [] ( const auto& box, const auto& point, auto& t0, auto& t1, const auto& rayPrec ) |
| 90 | { |
| 91 | return rayBoxIntersect( box.insignificantlyExpanded(), point, t0, t1, rayPrec ); |
| 92 | }; |
| 93 | |
| 94 | T s = rayStart, e = rayEnd; |
| 95 | if( !rayExpBoxIntersect( Box2<T>{ tree[tree.rootNodeId()].box }, line.p, s, e, prec ) ) |
| 96 | return; |
| 97 | |
| 98 | constexpr int maxTreeDepth = 32; |
| 99 | std::pair< NodeId,T> nodesStack[maxTreeDepth]; |
| 100 | int currentNode = 0; |
| 101 | nodesStack[0] = { tree.rootNodeId(), rayStart }; |
| 102 | |
| 103 | while( currentNode >= 0 ) |
| 104 | { |
| 105 | if( currentNode >= maxTreeDepth ) // max depth exceeded |
| 106 | { |
| 107 | assert( false ); |
| 108 | break; |
| 109 | } |
| 110 | |
| 111 | const auto& node = tree[nodesStack[currentNode].first]; |
| 112 | if( nodesStack[currentNode--].second < rayEnd ) |
| 113 | { |
| 114 | if( node.leaf() ) |
| 115 | { |
| 116 | EdgeId edge = node.leafId(); |
| 117 | auto segm = polyline.edgeSegment( edge ); |
| 118 | T segmPos = 0, rayPos = 0; |
| 119 | if ( doSegmentLineIntersect( LineSegm2<T>{ segm }, line, &segmPos, &rayPos ) |
| 120 | && rayPos < rayEnd && rayPos > rayStart ) |
| 121 | { |
| 122 | if ( callback( EdgePoint{ edge, float( segmPos ) }, rayPos, rayStart, rayEnd ) == Processing::Stop ) |
| 123 | return; |
| 124 | } |
| 125 | } |
| 126 | else |
| 127 | { |
| 128 | T lStart = rayStart, lEnd = rayEnd; |
| 129 | T rStart = rayStart, rEnd = rayEnd; |
| 130 | if( rayExpBoxIntersect( Box2<T>{ tree[node.l].box }, line.p, lStart, lEnd, prec ) ) |
nothing calls this directly
no test coverage detected