Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Polygons and the inside test

How to decide whether a point lies inside, outside or on the boundary of a polygon: definitions, theorems, the even-odd (ray-casting) and winding-number rules, half-plane test for convex polygons, point-in-triangle by barycentric coordinates, formulas, algorithms and a working C++ implementation.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Two or three sentences: where an engineer uses this.

Knowing whether a point is inside a polygon is a basic building block in computer graphics: it is used in polygon filling, hit-testing for user interaction, collision detection, visibility, clipping, and rasterization (e.g., scan-line fill). An engineer must choose an inside-test that is correct, robust for boundary cases (points on edges or vertices), and efficient enough for many points / large polygons.

Key ideas

Explain simply; define terms before using them. Give exact statements, assumptions, and derivations universities ask for.

  • Point: a pair (x, y) in the 2D plane. Units depend on the coordinate system (pixels, metres). I will use coordinates as numbers; mention units when needed.

  • Polygon: a finite ordered list of vertices V0, V1, ..., Vn-1 joined by straight edges (segments) Ei = Vi -> V{i+1} (index arithmetic modulo n). Assumption: polygon vertices are given in order (clockwise or counter-clockwise).

  • Simple polygon: a polygon whose edges do not cross except at shared vertices. Most standard inside-tests assume the polygon is simple.

  • Convex polygon: a polygon where every line segment between two points of the polygon lies entirely inside the polygon. Equivalent test: all interior angles <= 180 degrees; or the signed cross product of successive edges has the same sign for all edges (assuming no collinear consecutive edges).

  • Concave polygon: not convex; it has at least one interior angle > 180 degrees.

  • Inside, Outside, Boundary (On-edge): For point P, we want to classify it as either INSIDE, OUTSIDE or ON_EDGE (including vertices). A robust algorithm must explicitly decide what to do with ON_EDGE cases.

Two main classes of tests used in graphics and exams:

  1. Even–odd (ray-casting) rule. Exact statement: Cast a ray from point P in any fixed direction (commonly positive X direction). Count how many times this ray crosses polygon edges. If the count is odd then P is inside; if even then P is outside. Assumptions: polygon is simple; ray does not pass through any vertex except if handled carefully (see edge cases).

Detailed procedure universities expect you to write step-by-step:

  • Draw ray R from P horizontally to x = +infinity.
  • For each polygon edge (A -> B): check whether the vertical range of A and B straddles P.y (i.e., (A.y > P.y) != (B.y > P.y)). If not, the edge cannot cross the ray.
  • If straddling, compute intersection X coordinate x_int = A.x + (P.y - A.y) * (B.x - A.x) / (B.y - A.y). If x_int > P.x count one crossing.
  • If the ray passes exactly through a vertex, treat by standard tie-breaking: consider edges as half-open intervals [A,B) so each vertex belongs to only one of the incident edges; this avoids double counting.
  • After counting, odd => INSIDE, even => OUTSIDE. If any test finds that P lies exactly on an edge (orientation zero and P within the segment bounding box), return ON_EDGE.

Describe exactly what to draw and label for a diagram: draw polygon (simple, labelled V0..V5), point P inside, draw horizontal ray to right from P, mark intersections with edges, label count.

  1. Winding-number rule. Exact statement: Compute the algebraic number of times the polygon winds around P. If winding number != 0, P is inside; if 0, outside. This is orientation-aware and works for polygons whose edges may self-intersect (non-simple), and for oriented contours (useful in fill rules).

Algorithm (standard incremental form):

  • Initialize wn = 0.
  • For each edge Vi -> Vj: if Vi.y <= P.y:
    • if Vj.y > P.y and isLeft(Vi, Vj, P) > 0 then wn++
  • Else (Vi.y > P.y):
    • if Vj.y <= P.y and isLeft(Vi, Vj, P) < 0 then wn--
  • where isLeft(A,B,P) = (B.x - A.x)(P.y - A.y) - (P.x - A.x)(B.y - A.y) (signed area * 2).
  • If wn != 0 => INSIDE. As with ray-casting, test ON_EDGE first.
  1. Half-plane (edge-sign) test for convex polygons. Exact statement: For a convex polygon with vertices ordered consistently (say counter-clockwise), a point P is inside iff for all edges Vi->V{i+1}, the signed cross product is non-negative: isLeft(Vi,V{i+1},P) >= 0 (use > 0 for strict inside and allow =0 for on-edge). This is O(n) but can be improved to O(log n) if vertices are preprocessed and binary-search is used (advanced topic).

  2. Point-in-triangle by barycentric coordinates (or areas). Exact theorem: For triangle A,B,C, P is inside (including boundary) iff there exist scalars u,v,w >= 0 with u+v+w = 1 such that P = uA + vB + w*C. Computation by areas or cross-products is standard and stable.

Derivation universities ask for (barycentric via cross products):

  • Compute denom = isLeft(A,B,C).
  • u = isLeft(B,C,P) / denom, v = isLeft(C,A,P) / denom, w = isLeft(A,B,P) / denom.
  • If denom == 0 triangle is degenerate. If u,v,w >= 0 and u+v+w = 1 then P inside (include equality for boundary). Show algebraic steps: start from linear combination, rearrange and solve the 2×2 system.

Edge cases and robustness: collinear edges, point on vertex, ray exactly through vertex, numerical precision (floating point epsilon). For exams, state how you will treat ON_EDGE and choose an epsilon.

Complexity: naive tests are O(n) per point for n-vertex polygon. Many points or real-time needs require acceleration (spatial indexing, bounding boxes, triangulation, scan-line fill).

Formulas

Each formula on its own line; define symbols and units.

isLeft(A,B,P) = (B.x - A.x)*(P.y - A.y) - (P.x - A.x)*(B.y - A.y)

  • A,B,P are points with coordinates in same units (e.g., metres or pixels). isLeft is twice the signed area of triangle A-B-P. Positive if P is left of directed AB (assuming screen y up), negative if right, zero if collinear.

x_int = A.x + (P.y - A.y) * (B.x - A.x) / (B.y - A.y)

  • Intersection X coordinate of horizontal line at P.y with edge A->B. Valid when B.y != A.y.

wn = sum of upward/downward crossings (algorithmic, see Key ideas)

  • wn is integer winding number (dimensionless).

For triangle barycentric: denom = isLeft(A,B,C) u = isLeft(B,C,P) / denom v = isLeft(C,A,P) / denom w = isLeft(A,B,P) / denom

  • u, v, w are dimensionless barycentric coordinates.

Complexity: time = O(n) per point for ray-casting or winding-number on n-vertex polygon.

Worked examples

Three exam-standard worked examples: numeric, program, and theory-model answer.

Example 1 — Numerical: point-in-triangle using barycentric coordinates Given triangle A(0,0), B(4,0), C(1,3). Test P(1,1). Step 1: compute isLeft values (using formula): denom = isLeft(A,B,C) = (4-0)(3-0) - (1-0)(0-0) = 43 - 10 = 12. isLeft(B,C,P) = (1-4)(1-0) - (1-4)(3-0) = (-3)1 - (-3)3 = -3 - (-9) = 6. isLeft(C,A,P) = (0-1)(1-3) - (1-1)(0-3) = (-1)(-2) - (0)(-3) = 2. isLeft(A,B,P) = (4-0)(1-0) - (1-0)(0-0) = 41 - 10 = 4. Compute barycentrics: u = isLeft(B,C,P)/denom = 6/12 = 0.5 v = isLeft(C,A,P)/denom = 2/12 = 0.1666667 w = isLeft(A,B,P)/denom = 4/12 = 0.3333333 Check u+v+w = 1.0 (0.5+0.1666667+0.3333333 = 1.0). All are >= 0 so P is inside. Final answer: P is INSIDE the triangle.

Example 2 — C++ program: ray-casting with ON_EDGE detection Complete program (single-file). It reads n, then n vertices (x y) in order, then point Px Py, and prints INSIDE, OUTSIDE or ON_EDGE.

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct P{double x,y;};
const double EPS = 1e-9;

double isLeft(const P &A,const P &B,const P &Pp){
    return (B.x - A.x)*(Pp.y - A.y) - (Pp.x - A.x)*(B.y - A.y);
}

bool onSegment(const P &A,const P &B,const P &Pp){
    if (fabs(isLeft(A,B,Pp)) > EPS) return false;
    return (min(A.x,B.x)-EPS <= Pp.x && Pp.x <= max(A.x,B.x)+EPS &&
            min(A.y,B.y)-EPS <= Pp.y && Pp.y <= max(A.y,B.y)+EPS);
}

int rayCrossing(const vector<P>& poly,const P &Pp){
    int n = poly.size();
    int count = 0;
    for(int i=0;i<n;i++){
        P A = poly[i];
        P B = poly[(i+1)%n];
        if (onSegment(A,B,Pp)) return -1; // signal ON_EDGE
        bool cond = ((A.y > Pp.y) != (B.y > Pp.y));
        if (cond){
            double xint = A.x + (Pp.y - A.y)*(B.x - A.x)/(B.y - A.y);
            if (xint > Pp.x) count++;
        }
    }
    return count%2; // 1 => inside, 0 => outside
}

int main(){
    int n; if(!(cin>>n)) return 0;
    vector<P> poly(n);
    for(int i=0;i<n;i++) cin>>poly[i].x>>poly[i].y;
    P p; cin>>p.x>>p.y;
    int res = rayCrossing(poly,p);
    if (res == -1) cout<<"ON_EDGE\n";
    else if (res==1) cout<<"INSIDE\n";
    else cout<<"OUTSIDE\n";
}

Sample input:

4
0 0
4 0
4 4
0 4
1 1

Exact output:

INSIDE

Example 3 — Theory model answer: difference between even-odd and winding-number rules Answer: The even-odd rule counts crossings modulo 2 and decides inside if odd; it is simple and works for simple polygons. The winding-number method counts oriented crossings and decides inside if winding != 0; it distinguishes holes and orientation, and works for complex/non-simple polygons and for fill rules where orientation matters. In exams give algorithm steps and mention complexity O(n) and discuss handling of boundary cases.

Common mistakes

  • Wrong sign convention for isLeft or mixing screen coordinates (y downward) without adjusting sign. Always state coordinate orientation.
  • Division by zero when computing x_int for horizontal edges; first check B.y != A.y and use the y-straddle test.
  • Using equality of floating-point doubles directly instead of an EPS threshold (1e-9). But don't pick EPS blindly for integer grid coordinates; state EPS.
  • Applying convex half-plane test on concave polygons.

For your exam

Kinds of questions and what full-marks answers include:

  • Definitions: define polygon, simple, convex, inside/outside/boundary.
  • Short notes: explain ray-casting and winding-number rules, their assumptions, and complexity.
  • Derivations: derive barycentric coordinate formula for triangle point test (show algebra or cross-product form) and derive half-plane test from signed area.
  • Numericals: compute barycentric coordinates for a given triangle and point (carry units if present). Show all arithmetic and final classification.
  • Programs: implement ray-casting or winding-number with ON_EDGE checks in C++ and show sample input/output.
  • Diagrams: draw polygon labeled vertices, draw point P and a horizontal ray, label intersections and count.

Full-marks answers explicitly state how boundary cases are handled, show step-by-step arithmetic or code, and discuss complexity.

Quick check

Three short questions (answers given in final line):

  1. For a convex polygon with CCW vertex order, what sign should isLeft(Vi,Vi+1,P) have for P strictly inside?
  2. In the even-odd rule, what parity of crossings means the point is inside?
  3. For triangle A(0,0), B(2,0), C(0,2), compute barycentric coordinates of P(0.5,0.5).

Answers: 1) Positive (>0) for CCW order. 2) Odd crossings => inside. 3) denom = 4, u = isLeft(B,C,P)/4 = 2/4 = 0.5; v = isLeft(C,A,P)/4 = 1/4 = 0.25; w = isLeft(A,B,P)/4 = 1/4 = 0.25.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?