Issue with Shape.containsPoint

[jessegreenberg]

In https://github.com/phetsims/quadrilateral/issues/39 I found an issue with Shape.containsPoint. If the point being tested is perfectly vertically aligned with the start or end point of one of the shape segments an intersection with that segment will be undefined. This breaks the "winding intersection" algorithm that determines if a point is within a shape.

For example, we have this shape

Vertex 1 is perfectly aligned with vertex 3. Vertex 3 is the end point for the first shape segment (from 2 to 3) and the start point of the second shape segment (from 3 to 5).

Since cointainsPoint uses this Ray2 to determine the winding number, the ray perfectly intersects with point 3 so an intersection with those two segments is not well defined.

    // we pick a ray, and determine the winding number over that ray. if the number of segments crossing it CCW == number of segments crossing it CW, then the point is contained in the shape
    const ray = new Ray2( point, Vector2.X_UNIT );

We tried changing the ray direction to something random and it fixed my problem case in quadrilateral.

@jonathanolson suggested that the fix for this is for Shape.containsPoint to detect this and try another ray in this case.

[jessegreenberg]

In sim code I am going to use this function to workaround. It may or may not be a reasonable fix for this issue in Kite.

  /**
   * A workaround for https://github.com/phetsims/kite/issues/94. Shape.containsPoint implementation does not work
   * if both the provided point and one of the shape segment vertices lie along the test ray used in the
   * winding intersection algorithm. This function looks for a different ray to use in the test if that is the case.
   *
   * This solution has been proposed in https://github.com/phetsims/kite/issues/94. If it is absorbed or fixed a
   * different way in kite this function could be removed and replaced with shape.containsPoint.
   */
  private customShapeContainsPoint( shape: Shape, point: Vector2 ): boolean {
    const rayDirectionVector = new Vector2( 1, 0 ); // unit x Vector, but we may mutate it
    let ray = new Ray2( point, rayDirectionVector );

    // Put a limit on attempts so we don't try forever
    let count = 0;
    while ( count < 5 ) {
      count++;

      // Look for cases where the proposed ray will intersect with one of the vertices of a shape segment - in this case
      // the intersection in windingIntersection is not well-defined and won't be counted so we need a different ray
      const rayIntersectsSegmentVertex = _.some( shape.subpaths, subpath => {
        return _.some( subpath.segments, segment => {
          return segment.start.minus( point ).normalize().equals( rayDirectionVector );
        } );
      } );

      if ( rayIntersectsSegmentVertex ) {

        // the proposed ray will not work because it intersects with a segment Vertex - try another one
        rayDirectionVector.rotate( dotRandom.nextDouble() );
      }
      else {

        // Should be safe to use this Ray for windingIntersection
        ray = new Ray2( point, rayDirectionVector );
        break;
      }
    }

    return shape.windingIntersection( ray ) !== 0;
  }

[jonathanolson]

Moved over a variation. There's the possibility it might compute things incorrectly still at cusps or other extrema, however it seems almost all of those cases that were problematic before involve the endpoints, so avoiding endpoints works really nicely here. Thus I don't really feel like a more complicated solution is warranted at the moment, unless we're picking up a specific case where it's broken.