Point-in-Polygon Collision

polygon_collision.dnh

// `poly` is an array of points like [[x1,y1], [x2,y2], [x3,y3], [x4,y4]] where edges connect between two adjacent points
// `bounds` is the bounding box returned by `get_bounding_box`

function is_collided_polygon(x, y, poly, bounds){
  if(x < bounds[0] || y < bounds[1] || x > bounds[2] || y > bounds[3]){ return false; }

  let wn = 0;
  poly = poly ~ [poly[0]]; // connect edge from last to first vertex
  ascent(i in 0..length(poly)-1){
    if(poly[i][1] > y){
      if(poly[i+1][1] <= y){ // ascending edge crossing point
        if(point_edge_side(x, y, poly[i][0], poly[i][1], poly[i+1][0], poly[i+1][1]) < 0){ // point left-hand of edge
          wn--;
        }
      }
    }else{
      if(poly[i+1][1] > y){ // descending edge crossing point
        if(point_edge_side(x, y, poly[i][0], poly[i][1], poly[i+1][0], poly[i+1][1]) > 0){ // point right-hand of edge
          wn++;
        }
      }
    }
  }
  // winding number of 0 iff point outside polygon
  return (wn != 0);

  function point_edge_side(px, py, ax, ay, bx, by){
    // AB.x * AP.y - AB.y * AP.x
    return ( (bx - ax) * (py - ay) - (by - ay) * (px - ax) );
  }
}


function is_collided_rect(x, y, poly, bounds){
  if(x < bounds[0] || y < bounds[1] || x > bounds[2] || y > bounds[3]){ return false; }

  return is_point_projected_line(x, y, poly[0][0], poly[0][1], poly[1][0], poly[1][1])
      && is_point_projected_line(x, y, poly[1][0], poly[1][1], poly[2][0], poly[2][1]);

  function is_point_projected_line(px, py, ax, ay, bx, by){
    let abx = bx-ax;
    let aby = by-ay;
    let proj = (px-ax)*abx + (py-ay)*aby;
    let magn = abx*abx + aby*aby;
    //    0 < (ap . ab) / |ab| < |ab|
    // => 0 < (ap . ab) < |ab|^2 = (ab . ab)
    return (proj > 0 && proj < magn);
  }
}


function get_bounding_box(poly){
  let minx =  1/0; // +inf
  let maxx = -1/0; // -inf
  let miny =  1/0; // +inf
  let maxy = -1/0; // -inf
  ascent(i in 0..length(poly)){
    minx = min(minx, poly[i][0]);
    maxx = max(maxx, poly[i][0]);
    miny = min(miny, poly[i][1]);
    maxy = max(maxy, poly[i][1]);
  }
  return [minx, miny, maxx, maxy];
}