Codingame Solution: Dead men's shot

Solution

The classical solution to check if a point falls into a polygon is putting an infinite horizontal line to the point and count the number of intersections with edges of the polygon. If the number is odd, the point must be within the polygon.

Here we will do it differently since we know the polygon is convex. This means that when taking a random starting point and follow the path all around the polygon, we have made a perfect circular tour. It is obvious that when doing that tour, the point will always be on one side. Testing if this side changes even once therefore solves the test of a point being in a convex polygon. To check if the side changes, we calculate the 2D cross-product of the vector from a starting point \(A\) to a successive point \(B\) and the vector from \(A\) to the target point \(P\). The 2D cross-product is defined as \(\mathbf{u}\times\mathbf{v}=det(\mathbf{u}\mathbf{v})\) and the sign of the resulting scalar desides the direction. As such the problem can be solved with the following implementation:

function inPoly(Px, Py, poly) {

  let flag = 0;

  for (let i = 0; i < poly.length; i++) {

    const j = (i + 1) % poly.length;

    // Current point A
    const Ax = poly[i][0];
    const Ay = poly[i][1];

    // Successive point B
    const Bx = poly[j][0];
    const By = poly[j][1];

    // 2D Cross product
    const d = (Px - Ax) * (By - Ay) - (Py - Ay) * (Bx - Ax);

    // Flag the sign in a bitmap
    flag|= 1 << (d <= 0);

    if (flag === 3) {
      return false;
    }
  }
  return true;
}

const E = [];
const N = +readline();
for (let i = 0; i < N; i++) {
  E.push(readline().split(' ').map(Number));
}

const M = +readline();
for (let i = 0; i < M; i++) {
  const [x, y] = readline().split(' ').map(Number);
  print(inPoly(x, y, E) ? "hit" : "miss");
}