The Real Complexity of Point in Polygon

Introduction

Look at a map and drop a pin. Is it inside the city limits or not? Your eye answers instantly. A computer has no eyes — it only has a list of corner coordinates and the pin's (x, y). So how does it decide?

For a circle the test is trivial: compare the distance to the radius. But real shapes are polygons — countries, sales territories, the hit-box of a sprite, a fenced-off zone on a drone map — and they can be wildly irregular, with hundreds or thousands of corners and even concave dents that fold back on themselves.

The surprise is that one of the oldest tricks in geometry settles it with almost no math: fire a ray from the point off to infinity and count how many edges it crosses. The answer to inside-or-out is hiding in whether that count is odd or even.

Drag the Point

Below is a polygon and a movable dot. A horizontal ray shoots to the right from the dot. Drag the dot around — through the shape, into a concave notch, back out — and watch the crossing counter.

<p class="hint">Drag the <b>blue dot</b> anywhere. A ray shoots to the right and counts how many polygon edges it crosses. <b>Odd</b> crossings &rarr; inside, <b>even</b> &rarr; outside. Watch the verdict flip as you cross a boundary.</p>
<canvas id="cv" width="360" height="300"></canvas>
<div class="readout">
  <span class="pill" id="count">Crossings: 0</span>
  <span class="pill verdict" id="verdict">OUTSIDE</span>
</div>
<button id="reset" type="button" class="ghost">Reset point</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f7fafc;
         touch-action: none; display: block; max-width: 100%; }
.readout { display: flex; gap: .5rem; margin: .7rem 0; flex-wrap: wrap; }
.pill { font: 700 14px ui-monospace, monospace; padding: .4rem .8rem; border-radius: 999px;
        background: #e8eef3; color: #1d3557; }
.verdict.in  { background: #0a7d33; color: #fff; }
.verdict.out { background: #c92f3c; color: #fff; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Point-in-polygon by ray casting (even-odd rule). We shoot a horizontal ray
// from the test point to +infinity and count how many polygon edges it crosses.
// Odd count => inside, even => outside. This is O(n) per query (PNPOLY, Franklin).
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
// A deliberately concave polygon (an arrow-like notch) to show the rule still holds.
const POLY = [
  [60,40],[300,40],[300,140],[180,140],[300,200],[300,260],[60,260],[60,160],[150,150],[60,120]
];
let P = { x: 130, y: 110 };

// Count crossings of the rightward ray from (px,py) with each edge.
// Returns { count, segments } where segments are the edges actually crossed.
function rayCross(px, py) {
  let count = 0; const hit = [];
  for (let i = 0, n = POLY.length; i < n; i++) {
    const [ax, ay] = POLY[i];
    const [bx, by] = POLY[(i + 1) % n];
    // Edge straddles the horizontal line y = py?
    if ((ay > py) !== (by > py)) {
      // x of the intersection of the edge with y = py
      const xCross = ax + (py - ay) * (bx - ax) / (by - ay);
      if (xCross > px) { count++; hit.push(i); }
    }
  }
  return { count, hit };
}
const isInside = (px, py) => rayCross(px, py).count % 2 === 1;

function draw() {
  ctx.clearRect(0, 0, cv.width, cv.height);
  const { count, hit } = rayCross(P.x, P.y);
  const inside = count % 2 === 1;
  // polygon
  ctx.beginPath();
  POLY.forEach(([x, y], i) => i ? ctx.lineTo(x, y) : ctx.moveTo(x, y));
  ctx.closePath();
  ctx.fillStyle = inside ? 'rgba(10,125,51,.12)' : 'rgba(201,47,60,.08)';
  ctx.fill();
  ctx.lineWidth = 2; ctx.strokeStyle = '#1d3557'; ctx.stroke();
  // the ray
  ctx.beginPath(); ctx.moveTo(P.x, P.y); ctx.lineTo(cv.width, P.y);
  ctx.strokeStyle = '#e6a800'; ctx.lineWidth = 2;
  ctx.setLineDash([5, 4]); ctx.stroke(); ctx.setLineDash([]);
  // crossing markers
  hit.forEach(i => {
    const [ax, ay] = POLY[i]; const [bx, by] = POLY[(i + 1) % POLY.length];
    const xc = ax + (P.y - ay) * (bx - ax) / (by - ay);
    ctx.beginPath(); ctx.arc(xc, P.y, 4, 0, 7); ctx.fillStyle = '#e6a800'; ctx.fill();
  });
  // the point
  ctx.beginPath(); ctx.arc(P.x, P.y, 7, 0, 7);
  ctx.fillStyle = '#1d6fe6'; ctx.fill();
  ctx.lineWidth = 2; ctx.strokeStyle = '#fff'; ctx.stroke();
  // readouts
  document.getElementById('count').textContent = fmt('Crossings: %count%', { count: count });
  const v = document.getElementById('verdict');
  v.textContent = inside ? 'INSIDE' : 'OUTSIDE';
  v.className = 'pill verdict ' + (inside ? 'in' : 'out');
}

let dragging = false;
function pos(e) {
  const r = cv.getBoundingClientRect();
  const t = e.touches ? e.touches[0] : e;
  return { x: (t.clientX - r.left) * cv.width / r.width, y: (t.clientY - r.top) * cv.height / r.height };
}
function down(e) { dragging = true; P = pos(e); draw(); e.preventDefault(); }
function move(e) { if (dragging) { P = pos(e); draw(); e.preventDefault(); } }
function up() { dragging = false; }
cv.addEventListener('mousedown', down); cv.addEventListener('mousemove', move);
window.addEventListener('mouseup', up);
cv.addEventListener('touchstart', down); cv.addEventListener('touchmove', move);
window.addEventListener('touchend', up);
document.getElementById('reset').addEventListener('click', () => { P = { x: 130, y: 110 }; draw(); });
draw();

<p class="hint">Drag the <b>blue dot</b> anywhere. A ray shoots to the right and counts how many polygon edges it crosses. <b>Odd</b> crossings &rarr; inside, <b>even</b> &rarr; outside. Watch the verdict flip as you cross a boundary.</p>
<canvas id="cv" width="360" height="300"></canvas>
<div class="readout">
  <span class="pill" id="count">Crossings: 0</span>
  <span class="pill verdict" id="verdict">OUTSIDE</span>
</div>
<button id="reset" type="button" class="ghost">Reset point</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f7fafc;
         touch-action: none; display: block; max-width: 100%; }
.readout { display: flex; gap: .5rem; margin: .7rem 0; flex-wrap: wrap; }
.pill { font: 700 14px ui-monospace, monospace; padding: .4rem .8rem; border-radius: 999px;
        background: #e8eef3; color: #1d3557; }
.verdict.in  { background: #0a7d33; color: #fff; }
.verdict.out { background: #c92f3c; color: #fff; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Point-in-polygon by ray casting (even-odd rule). We shoot a horizontal ray
// from the test point to +infinity and count how many polygon edges it crosses.
// Odd count => inside, even => outside. This is O(n) per query (PNPOLY, Franklin).
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
// A deliberately concave polygon (an arrow-like notch) to show the rule still holds.
const POLY = [
  [60,40],[300,40],[300,140],[180,140],[300,200],[300,260],[60,260],[60,160],[150,150],[60,120]
];
let P = { x: 130, y: 110 };

// Count crossings of the rightward ray from (px,py) with each edge.
// Returns { count, segments } where segments are the edges actually crossed.
function rayCross(px, py) {
  let count = 0; const hit = [];
  for (let i = 0, n = POLY.length; i < n; i++) {
    const [ax, ay] = POLY[i];
    const [bx, by] = POLY[(i + 1) % n];
    // Edge straddles the horizontal line y = py?
    if ((ay > py) !== (by > py)) {
      // x of the intersection of the edge with y = py
      const xCross = ax + (py - ay) * (bx - ax) / (by - ay);
      if (xCross > px) { count++; hit.push(i); }
    }
  }
  return { count, hit };
}
const isInside = (px, py) => rayCross(px, py).count % 2 === 1;

function draw() {
  ctx.clearRect(0, 0, cv.width, cv.height);
  const { count, hit } = rayCross(P.x, P.y);
  const inside = count % 2 === 1;
  // polygon
  ctx.beginPath();
  POLY.forEach(([x, y], i) => i ? ctx.lineTo(x, y) : ctx.moveTo(x, y));
  ctx.closePath();
  ctx.fillStyle = inside ? 'rgba(10,125,51,.12)' : 'rgba(201,47,60,.08)';
  ctx.fill();
  ctx.lineWidth = 2; ctx.strokeStyle = '#1d3557'; ctx.stroke();
  // the ray
  ctx.beginPath(); ctx.moveTo(P.x, P.y); ctx.lineTo(cv.width, P.y);
  ctx.strokeStyle = '#e6a800'; ctx.lineWidth = 2;
  ctx.setLineDash([5, 4]); ctx.stroke(); ctx.setLineDash([]);
  // crossing markers
  hit.forEach(i => {
    const [ax, ay] = POLY[i]; const [bx, by] = POLY[(i + 1) % POLY.length];
    const xc = ax + (P.y - ay) * (bx - ax) / (by - ay);
    ctx.beginPath(); ctx.arc(xc, P.y, 4, 0, 7); ctx.fillStyle = '#e6a800'; ctx.fill();
  });
  // the point
  ctx.beginPath(); ctx.arc(P.x, P.y, 7, 0, 7);
  ctx.fillStyle = '#1d6fe6'; ctx.fill();
  ctx.lineWidth = 2; ctx.strokeStyle = '#fff'; ctx.stroke();
  // readouts
  document.getElementById('count').textContent = fmt('Crossings: %count%', { count: count });
  const v = document.getElementById('verdict');
  v.textContent = inside ? 'INSIDE' : 'OUTSIDE';
  v.className = 'pill verdict ' + (inside ? 'in' : 'out');
}

let dragging = false;
function pos(e) {
  const r = cv.getBoundingClientRect();
  const t = e.touches ? e.touches[0] : e;
  return { x: (t.clientX - r.left) * cv.width / r.width, y: (t.clientY - r.top) * cv.height / r.height };
}
function down(e) { dragging = true; P = pos(e); draw(); e.preventDefault(); }
function move(e) { if (dragging) { P = pos(e); draw(); e.preventDefault(); } }
function up() { dragging = false; }
cv.addEventListener('mousedown', down); cv.addEventListener('mousemove', move);
window.addEventListener('mouseup', up);
cv.addEventListener('touchstart', down); cv.addEventListener('touchmove', move);
window.addEventListener('touchend', up);
document.getElementById('reset').addEventListener('click', () => { P = { x: 130, y: 110 }; draw(); });
draw();

Result

Console

The rule is the whole algorithm: odd number of crossings means the point is inside; even (including zero) means outside. Each time the ray pierces a boundary it flips you from out to in or in to out, so the parity of the count is exactly your status. Notice it works even for the concave dent — the ray simply crosses the boundary more times. Checking one point walks the edges once: $O(n)$ for an $n$ -vertex polygon.

The Real Complexity

Where does point-in-polygon sit on the difficulty map? Comfortably among the solved, easy problems.

One query is linear. The ray-casting (even-odd) test inspects each of the $n$ edges once, checking whether the horizontal ray crosses it. That is $O(n)$ time and $O(1)$ extra space — no cleverness required. The classic, battle-tested implementation is W. Randolph Franklin's PNPOLY (a handful of lines of C).
A robust cousin: the winding number. Instead of parity, sum the signed angle the polygon sweeps around the point; a nonzero total means inside. It is also $O(n)$ and handles self-overlapping polygons more gracefully than even-odd.
Many queries? Preprocess. If you will test millions of points against the same polygon, you can build a structure (slab decomposition, trapezoidal map) in $O(n \log n)$ once, then answer each query in $O(\log n)$ .
The only real subtlety is the boundary. Points exactly on an edge, or rays that graze a vertex, need careful tie-breaking — but these are precision details, not complexity barriers.

There is no exponential blowup, no open question, no hardness here. Unlike the art gallery problem, which asks the genuinely hard question of how few guards cover a polygon, simply testing one point is the friendly end of computational geometry.

Where It Matters

"Is this point inside that shape?" is one of the most-asked questions in all of computing, and the same little ray answers it:

Maps and GIS: which county, sales region or flood zone contains a given coordinate — the bread and butter of every spatial database.
Geofencing: phones and delivery drones decide whether they have entered or left a virtual fence drawn on the map.
Games and UI: did the cursor click inside this irregular button or sprite? Hit-testing is point-in-polygon at 60 frames per second.
Rendering and CAD: ray tracers ask whether a ray hits inside a face; design tools select every object that falls within a lasso you draw.

The same crossing idea generalizes the moment you go 3D, where ray casting decides whether a point is inside a mesh, and it pairs naturally with hull-based shortcuts like the convex hull for fast rejection tests.

Conclusion

Point-in-polygon is a small triumph of the right idea over brute force. There is no need to triangulate the shape or reason about its interior — you just shoot a ray, count the crossings, and read off a single bit of parity. Odd is in, even is out.

It is a reminder that not every geometry question is a monster. Some, like deciding how few guards watch a gallery, really are hard. But the everyday inside test that your phone runs millions of times a day is solved, linear, and elegant — proof that a clever observation can retire a problem for good. For the genuinely hard side of the same field, see the art gallery problem.

Comments

Loading comments...

https://www.kipuhub.com/en/article/point-in-polygon/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Point in Polygon

How a single ray decides inside from outside