| 11 | { |
| 12 | |
| 13 | bool isPointInsidePolyline( const Polyline2& polyline, const Vector2f& point ) |
| 14 | { |
| 15 | const auto& tree = polyline.getAABBTree(); |
| 16 | if ( tree.nodes().size() == 0 ) |
| 17 | return false; |
| 18 | |
| 19 | // we consider plusX ray here |
| 20 | auto rayBoxIntersect = [] ( const Box2f& box, const Vector2f& plusXRayStart )->bool |
| 21 | { |
| 22 | if ( box.max.x <= plusXRayStart.x ) |
| 23 | return false; |
| 24 | if ( box.max.y <= plusXRayStart.y ) |
| 25 | return false; |
| 26 | if ( box.min.y > plusXRayStart.y ) |
| 27 | return false; |
| 28 | return true; |
| 29 | }; |
| 30 | if ( !rayBoxIntersect( tree[tree.rootNodeId()].box, point ) ) |
| 31 | return false; |
| 32 | |
| 33 | InplaceStack<NoInitNodeId, 32> nodesStack; |
| 34 | nodesStack.push( tree.rootNodeId() ); |
| 35 | |
| 36 | int intersectionCounter = 0; |
| 37 | while ( !nodesStack.empty() ) |
| 38 | { |
| 39 | const auto& node = tree[nodesStack.top()]; |
| 40 | nodesStack.pop(); |
| 41 | if ( node.leaf() ) |
| 42 | { |
| 43 | if ( node.box.min.x >= point.x ) |
| 44 | ++intersectionCounter; |
| 45 | else |
| 46 | { |
| 47 | auto uEId = node.leafId(); |
| 48 | const auto& org = polyline.orgPnt( uEId ); |
| 49 | const auto& dest = polyline.destPnt( uEId ); |
| 50 | |
| 51 | double yLength = ( double( dest.y ) - double( org.y ) ); |
| 52 | if ( yLength != 0.0f ) |
| 53 | { |
| 54 | double ratio = ( double( point.y ) - double( org.y ) ) / yLength; |
| 55 | float x = float( ratio * double( dest.x ) + ( 1.0 - ratio ) * double( org.x ) ); |
| 56 | if ( x >= point.x ) |
| 57 | ++intersectionCounter; |
| 58 | } |
| 59 | } |
| 60 | } |
| 61 | else |
| 62 | { |
| 63 | if ( rayBoxIntersect( tree[node.l].box, point ) ) |
| 64 | nodesStack.push( node.l ); |
| 65 | if ( rayBoxIntersect( tree[node.r].box, point ) ) |
| 66 | nodesStack.push( node.r ); |
| 67 | } |
| 68 | } |
| 69 | return ( intersectionCounter % 2 ) == 1; |
| 70 | } |