Test intersection vertices for whether they are inside a limited angle for field of vision

[aaclayton]

Originally in GitLab by @caewok

Environment Details

Please share the following basic details about your setup.

• Foundry VTT Version: 9.235
• Operating System: Mac OS X 10.15.7 running Foundry in NodeJS/Linux version
• How Are You Using Foundry: Chrome 96.0.4664.55
• Which Game System: dnd5e 1.5.5
• Modules Enabled?: no

Issue Description

I spotted a potential bug in ClockwiseSweepPolygon.prototype._identifyIntersections: This method adds vertices at overlapping wall intersections, but if the vertex is new, _identifyIntersections does not check set a value for _inLimitedAngle for that vertex. In the very next step after _inLimitedAngle, the parent method _identifyVertices deletes any vertices that do not have _inLimitedAngle set to true. As a result, the newly added vertex will be immediately removed. (In the case of a limited angle field of vision.)

This does not usually present as a bug, because in at least most instances, _identifyIntersections adds an intersection vertex that already exists in the set of vertices and thus will already have _inLimitedAngle set previously. I would not assume this to always be the case, however, as intersections are a bit fickle and, due to floating point errors, can be slightly off their exact location. So it may be possible to have a new keyed vertex at an intersection point not previously seen.

I found this potential bug because I am adding temporary walls to ClockwiseSweepPolygon. In this case, any overlapping intersection with the temporary wall will not have been previously processed, and so the vertex at the overlap is definitely new. I can confirm that this results in ClockwiseSweepPolygon removing the vertex at the overlap intersection, causing field-of-vision to display incorrectly. I would expect the same behavior if, as I said above, the overlapping intersection is not in the existing set of vertices.

Proposed solution

A fairly simple check can avoid this potential issue in _identifyIntersections:

if ( this.vertices.has(v.key) ) v = this.vertices.get(v.key);
        else {
          
          // if limited angle, test for inclusion
          if(hasLimitedAngle) {      
            v._inLimitedAngle = this.constructor.pointBetweenRays(v, rMin, rMax);
          } 
          this.vertices.set(v.key, v);                  
        }

For your reference, here is what the full method would look like:

 /**
  * Add additional vertices for intersections between edges.
  * @param {Map<string,PolygonEdge>} wallEdgeMap    A mapping of wall IDs to PolygonEdge instances
  * @private
  */
  _identifyIntersections(wallEdgeMap) {
    const { hasLimitedAngle, rMin, rMax } = this.config;
  
    const processed = new Set();
    const o = this.origin;
    for ( let edge of this.edges ) {

      // If the edge has no intersections, skip it
      if ( !edge.intersectsWith.size ) continue;

      // Check each intersecting wall
      for ( let [id, i] of edge.intersectsWith.entries() ) {

        // Some other walls may not be included in this polygon
        const other = wallEdgeMap.get(id);
        if ( !other || processed.has(other) ) continue;

        // Verify that the intersection point is still contained within the radius
        const r2 = Math.pow(i.x - o.x, 2) + Math.pow(i.y - o.y, 2);
        if ( r2 > this.config.radius2 ) continue;

        // Register the intersection point as a vertex
        let v = PolygonVertex.fromPoint(i);
        if ( this.vertices.has(v.key) ) v = this.vertices.get(v.key);
        else {
          
          // if limited angle, test for inclusion
          if(hasLimitedAngle) {      
            v._inLimitedAngle = this.constructor.pointBetweenRays(v, rMin, rMax);
          } 
          this.vertices.set(v.key, v);                  
        }
        if ( !v.edges.has(edge) ) v.attachEdge(edge, 0);
        if ( !v.edges.has(other) ) v.attachEdge(other, 0);
      }
      processed.add(edge);
    }
  }