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:
- 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.
- 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.
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).
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):
- For a convex polygon with CCW vertex order, what sign should isLeft(Vi,Vi+1,P) have for P strictly inside?
- In the even-odd rule, what parity of crossings means the point is inside?
- 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?