Why this matters when you build with AI
Ask an AI tool for "is this point inside this polygon" and you will often get a ray casting function that uses double division for the crossing x coordinate. It passes random tests, because random points almost never land on an edge. Judge data does land on edges, since test writers put points on vertices and on grid lines. The function then answers "inside" or "outside" for points that should be "on the boundary", and nothing in the output says it is wrong.
The second common gap is direction. A polygon can list its vertices clockwise or counterclockwise. A winding number test written for one direction returns "outside" for every point of a polygon given in the other direction. The shoelace formula, which many tools write as a sum divided by 2, has the same sign issue, and dividing by 2 turns an exact integer into a half-integer that a long long cannot hold.
This lesson uses integers only. It gives the shoelace formula with the doubled area, the two standard ways to decide inside or outside, a boundary test that runs first, and a set of broken versions with their real outputs. Two terms first. A polygon here is a closed chain of straight edges through vertices given in order. It is simple if no two edges cross and no vertex repeats.
The idea: the shoelace formula
Take a polygon with vertices p0, p1, ..., p(n-1) in order, where the last vertex connects back to the first. Write cross(u, v) = u.x * v.y - u.y * v.x, as in the earlier lessons. The doubled signed area is
2A = sum over i of cross(p_i, p_(i+1))
with indices taken modulo n. Each term is twice the signed area of the triangle formed by the origin and one edge. The origin can lie outside the polygon. The signs of the terms cancel the parts that lie outside, so the sum is still the polygon's area, with sign.
Worked example: the triangle (0, 0), (4, 0), (0, 3). The three terms are cross((0, 0), (4, 0)) = 0 * 0 - 0 * 4 = 0, then cross((4, 0), (0, 3)) = 4 * 3 - 0 * 0 = 12, then cross((0, 3), (0, 0)) = 0 * 0 - 3 * 0 = 0. The sum is 12. The area is 12 / 2 = 6, which matches the right triangle with legs 4 and 3, since 4 * 3 / 2 = 6.
The sign gives the direction. A positive 2A means the vertices go counterclockwise, which is the direction most texts use as the standard. A negative 2A means clockwise. For the triangle above, going from (0, 0) to (4, 0) to (0, 3) turns left at each corner, which is counterclockwise, and 2A is +12.
The sample polygon of the worked problem below has five vertices. Its 2A is 40, so its area is 20, and it is counterclockwise.
Keep 2A, not A, as the integer answer. Coordinates up to 10^9 give 2A up to about 8 * 10^18, which fits in a signed 64-bit integer. The area itself can be a half-integer, and printing it as an integer would lose the half. The reference program prints 2A and the direction.
Winding direction and normalizing
Some problems give the vertices in either direction, and some algorithms need counterclockwise order. The fix is short: compute 2A, and if it is negative, reverse the vertex list. Reversing does not change which points are inside, so the answers to queries stay the same. The reference program does not reverse, because the point tests below work for both directions. It reports the direction only.
The idea: inside, outside or boundary
For a simple polygon, every point of the plane is in one of three places. It is on the boundary, which is the union of the edges, including the vertices. It is strictly inside. Or it is strictly outside. The three answers must be decided in that order, because the ray tests do not handle points on an edge reliably, so the boundary needs its own test.
Step 1: the boundary
A point q is on the segment from a to b if and only if cross(b - a, q - a) = 0 and q lies inside the bounding box of a and b. The cross product is zero exactly when q is on the line through a and b. The box test then keeps the part of the line between the two endpoints. Run this test on every edge first. If any edge says yes, the answer is BOUNDARY and no other test is needed.
Step 2: a ray to the right
For points that are not on the boundary, cast a ray from q going to the right, along the line y = q.y. Count how many edges it crosses, and how they cross. Two standard methods use that count.
The crossing number method counts crossings only. A point is inside if the count is odd. A crossing is counted for an edge that has one endpoint strictly above the ray and one at or below it. That half-open rule means a vertex on the ray is counted once, not twice.
The winding number method counts crossings with a sign. An edge going upward, from below the ray to above it, adds 1 if the point is to the left of the edge. An edge going downward, from above to below, subtracts 1 if the point is to the right of it. The point is inside if the total is not zero. Dan Sunday described this method in his web article "Inclusion of a Point in a Polygon". Secondary sources date it to 2001. It avoids angles and trigonometry. The reference program uses it.
For a simple polygon both methods give the same answer. They differ for a polygon that winds around a point twice, which is not simple, as the next section shows.
Worked example by hand: the point q = (3, 2) in the sample polygon (0, 0), (4, 0), (4, 4), (2, 6), (0, 4). Walk the edges in order. The edge (0, 0) to (4, 0) has both endpoints at height 0 or lower, so it does not cross the upward or downward rule. The edge (4, 0) to (4, 4) goes up across y = 2. The cross product cross((0, 4), (3, 2) - (4, 0)) = cross((0, 4), (-1, 2)) = 0 * 2 - 4 * (-1) = 4, which is positive, so the point is to the left of this upward edge. The winding total becomes 1. The edge (4, 4) to (2, 6) is entirely above the ray. The edge (2, 6) to (0, 4) is entirely above it too. The last edge (0, 4) to (0, 0) goes down across y = 2. The cross product cross((0, -4), (3, -2)) is 0 * (-2) - (-4) * 3 = 12, which is positive, so the point is to the left of the downward edge, and the rule for downward edges subtracts only when the point is to the right. Nothing is subtracted. The total is 1, not zero, so the point is inside. The crossing method agrees: the ray crosses one edge, the upward edge at x = 4, and one is odd.
The reference program
The code below is the reference. It is C++17, compiled with g++ -O2 -std=c++17 -Wall -Wextra with no warnings. The program takes an optional argument crossing that switches to the crossing number method. The argument exists only so the two methods can be compared in the tests.
// poly.cpp: doubled area (shoelace) and point location in a polygon with integer vertices.
// Input: N, then N lines "x y" (polygon vertices in order), then Q, then Q lines "x y".
// Output: first line "2A <doubled area> <CCW|CW>", then one line per query: INSIDE | OUTSIDE | BOUNDARY.
// Optional argument "crossing" uses the even-odd ray rule instead of the winding number (for testing).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
struct P { ll x, y; };
// cross(b - a, q - a): positive when q is left of the directed line a -> b.
ll isLeft(P a, P b, P q) {
return (b.x - a.x) * (q.y - a.y) - (b.y - a.y) * (q.x - a.x);
}
// Is q on the closed segment ab? (Exact: zero cross product and inside the bounding box.)
bool onSegment(P q, P a, P b) {
return isLeft(a, b, q) == 0 &&
min(a.x, b.x) <= q.x && q.x <= max(a.x, b.x) &&
min(a.y, b.y) <= q.y && q.y <= max(a.y, b.y);
}
// Shoelace formula: twice the signed area. Positive means counterclockwise.
i128 doubledArea(const vector<P>& p) {
i128 s = 0;
size_t n = p.size();
for (size_t i = 0; i < n; i++) {
const P& a = p[i];
const P& b = p[(i + 1) % n];
s += (i128)a.x * b.y - (i128)b.x * a.y; // products up to 1e18 each: keep the running sum in 128 bits
}
return s;
}
// Winding number (Dan Sunday's method): counts signed crossings of a rightward ray from q.
int windingNumber(const vector<P>& p, P q) {
int wn = 0;
size_t n = p.size();
for (size_t i = 0; i < n; i++) {
P a = p[i], b = p[(i + 1) % n];
if (a.y <= q.y) {
if (b.y > q.y && isLeft(a, b, q) > 0) wn++; // upward crossing, q on the left
} else {
if (b.y <= q.y && isLeft(a, b, q) < 0) wn--; // downward crossing, q on the right
}
}
return wn;
}
// Crossing number (even-odd rule): parity of the rightward ray crossings.
int crossingParity(const vector<P>& p, P q) {
int cnt = 0;
size_t n = p.size();
for (size_t i = 0; i < n; i++) {
P a = p[i], b = p[(i + 1) % n];
if ((a.y > q.y) != (b.y > q.y)) {
ll s = isLeft(a, b, q); // never 0 here: q is not on the edge
if ((s > 0) == (b.y > a.y)) cnt ^= 1;
}
}
return cnt;
}
string toStr(i128 v) {
if (v == 0) return "0";
bool neg = v < 0;
if (neg) v = -v;
string s;
while (v > 0) { s += char('0' + (int)(v % 10)); v /= 10; }
if (neg) s += '-';
reverse(s.begin(), s.end());
return s;
}
int main(int argc, char** argv) {
bool useCrossing = argc > 1 && string(argv[1]) == "crossing";
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<P> poly(n);
for (auto& v : poly) cin >> v.x >> v.y;
i128 a2 = doubledArea(poly);
cout << "2A " << toStr(a2) << " " << (a2 > 0 ? "CCW" : "CW") << "\n";
int q;
cin >> q;
while (q--) {
P z;
cin >> z.x >> z.y;
bool boundary = false;
for (int i = 0; i < n && !boundary; i++)
boundary = onSegment(z, poly[i], poly[(i + 1) % n]);
if (boundary) { cout << "BOUNDARY\n"; continue; }
bool inside = useCrossing ? crossingParity(poly, z) == 1 : windingNumber(poly, z) != 0;
cout << (inside ? "INSIDE" : "OUTSIDE") << "\n";
}
return 0;
}The input is N, then N vertices, then Q, then Q query points. The first output line is 2A, its value and CCW or CW. Then one line per query.
Worked example: courtyard check
Statement, written for this lesson. A courtyard is a simple polygon given by its N corners in order, clockwise or counterclockwise. A guard asks Q questions, each a point. For each question, print INSIDE if the point is strictly inside the courtyard, BOUNDARY if it is on a wall, and OUTSIDE otherwise. First print the doubled area and the direction. Limits: 3 <= N <= 1000, 1 <= Q <= 1000, and each coordinate has absolute value at most 10^9. The polygon is guaranteed to be simple.
Sample input and the output of the reference program:
5
0 0
4 0
4 4
2 6
0 4
6
0 3
2 1
1 5
1 6
6 0
3 22A 40 CCW
BOUNDARY
INSIDE
BOUNDARY
OUTSIDE
OUTSIDE
INSIDECheck the answers. (0, 3) lies on the wall from (0, 4) to (0, 0), so BOUNDARY. (2, 1) is in the middle, so INSIDE. (1, 5) lies on the slanted wall from (2, 6) to (0, 4), since that wall is the line y = x + 4 and 5 = 1 + 4, so BOUNDARY. (1, 6) is above the top, so OUTSIDE. (6, 0) is to the right, so OUTSIDE. (3, 2) is the hand example, so INSIDE.
A polygon that winds twice. The next input is a square listed twice in a row, which makes a polygon with eight vertices that is not simple. Its doubled area is 64, twice the square's 32. Three queries show that the two methods disagree on it.
8
0 0
4 0
4 4
0 4
0 0
4 0
4 4
0 4
3
2 2
5 5
6 1Output of the winding number method, the default:
2A 64 CCW
INSIDE
OUTSIDE
OUTSIDEOutput of the crossing method, crossing argument:
2A 64 CCW
OUTSIDE
OUTSIDE
OUTSIDEThe point (2, 2) is inside the square, and the winding number is 2. The crossing method counts two crossings of the right edge, once per traversal, which is even, so it says outside. For a polygon that is not simple, the crossing method can be wrong about the question "inside the region this polygon encloses", and the winding method is the one that matches the usual meaning. The problem statement guarantees a simple polygon, so either method is correct on the contest data.
How this was tested
The random tester built 400 simple polygons with 3 to 9 vertices and coordinates from -5 to 5. A polygon was accepted only if it passed a simplicity check: no two non-adjacent edges meet, and no vertex repeats. The tester checked 16,000 query points, 40 per polygon, with coordinates from -6 to 6. Each answer was compared with two references: an exact brute force that uses Fraction numbers for the crossing x coordinate, and the shapely 2.2.0 library, installed with pip into a scratch virtual environment. shapely is a geometry library that answers "is this point inside the polygon, or on its boundary" without any code of this lesson. The reference program agreed with both on all 16,000 answers, with 0 mismatches against each.
A second test ran the winding method and the crossing method on 300 simple polygons with 40 queries each, 12,300 answers. They differed in 0 answers. This supports the claim that the two methods agree on simple polygons. It is a test on random small polygons, not a proof.
The broken variants below were run on the same inputs. Their outputs are shown in the mistakes section.
Complexity
The shoelace formula takes O(N) time and O(1) memory. A point query takes O(N) time, because the boundary test and the winding test each look at every edge once. For Q queries on one polygon the total is O(N * Q). With N and Q both 1000 that is about 10^6 edge checks, which is fast. If a problem allows N and Q near 10^5, the total is about 10^10, too slow, and a different method such as sorting or a binary search over a decomposition is needed. This lesson does not cover that method, and the problem above does not need it.
Common mistakes
Mistake 1: no boundary test. A ray casting function that starts with the crossing count puts boundary points on one side or the other. The variant below is the reference with the boundary check removed, run on the sample:
2A 40 CCW
INSIDE expected BOUNDARY for (0, 3)
INSIDE
INSIDE expected BOUNDARY for (1, 5)
OUTSIDE
OUTSIDE
INSIDETwo of the six answers are wrong, and both are on walls. The symptom is a wrong line in the output for the few queries that land on an edge, while random tests with points off the edges pass.
Mistake 2: a sign test that only works for one direction. A winding test that returns INSIDE only when the total is greater than zero works for counterclockwise polygons. The variant below is the reference with > 0 in place of != 0, run on the sample given in clockwise order (the same five corners, reversed):
2A -40 CW
BOUNDARY
OUTSIDE expected INSIDE for (2, 1)
BOUNDARY
OUTSIDE
OUTSIDE
OUTSIDE expected INSIDE for (3, 2)The symptom is that every interior point of a clockwise polygon is reported as outside.
Mistake 3: skipping the closing edge. The last vertex must connect back to the first. A loop that runs i + 1 < n misses that edge. On the sample it changes no answer, because the sample queries are all to the right of the closing edge. On the points (-1, 2) and (-1, 5), which are to the left of the polygon, the variant gives:
2A 40 CCW
INSIDE expected OUTSIDE for (-1, 2)
OUTSIDEThe closing edge is crossed by the ray from these points, and the sign of its crossing cancels the crossing of the right wall. Without it the total stays at 1.
Mistake 4: printing the area as an integer after dividing by 2. A triangle with vertices (0, 0), (1, 0), (0, 1) has 2A = 1 and area 1/2. The integer division gives 0. Print 2A.
Mistake 5: a double in the boundary test. The cross product is exact in integers. A double cross product can round a small nonzero value to zero or the reverse, so a point on the line can be misclassified. Keep the test integer, as the reference does.
Mistake 6: trusting one method on a non-simple polygon. The square listed twice is the example above. The methods disagree, so a test case that is not simple can expose the wrong method. The statement decides which property is promised, and the test tells you whether it holds.
Checklist to keep
- Compute
2Awith the shoelace formula and keep it as an integer. - Read the sign of
2Afor the direction, and do not divide by 2 until the end, if at all. - Run the boundary test on every edge before any inside test.
- Include the closing edge from the last vertex back to the first.
- Use the winding test with
!= 0, not> 0, so both directions work. - Keep all tests in integers, with
long longfor the cross products and__int128for sums of2A. - Test with query points on vertices, on edges, and outside the bounding box.
- Compare with an independent reference, such as an exact brute force, on random simple polygons.
Hands-on exercise
Write the program on your own machine in C++17, from the description above, without copying the reference. Build a Python generator with a fixed seed that makes 400 simple polygons and 40 query points for each. A polygon is simple if no two non-adjacent edges share a point. Use the segment test from the previous lesson for that check, or write a version of your own. Compare your program with a Python brute force that uses Fraction numbers. Record the number of mismatches. Then, if you can install it in a scratch virtual environment, compare the same answers with shapely and record that count too.
Then run the three broken variants from the mistakes section on the same inputs and confirm that each one fails in the way described.
Prompt to try with an AI tool
Use this prompt, then check the answer with the steps above:
Write a C++17 function that classifies a point as INSIDE, OUTSIDE or BOUNDARY
for a simple polygon with integer vertices (coordinates up to 1e9 in absolute
value). The vertices may be listed clockwise or counterclockwise. Use integer
arithmetic only, with no double and no atan2. Also write a function that
returns twice the signed area with a sign that shows the direction. Then give
one polygon and one point where a ray casting test that ignores the boundary
gives the wrong answer, with the expected answer.A good answer checks the boundary first, uses a sign rule that works for both directions, and keeps the area doubled. Its counterexample should be a point on an edge. Check the answer by running it on the sample of the worked example and on the reversed sample. Reject an answer that uses atan2 to sum angles, since that is slow and can be wrong at the boundary, or one that divides the area by 2 with integer division.
Summary
A point in a simple polygon is on the boundary, inside, or outside, and the boundary test comes first. The shoelace formula gives twice the area as an exact integer, and its sign gives the winding direction. The winding number and the crossing number both answer the inside question for simple polygons, and they differ on polygons that wind more than once. Every test in this lesson uses integers, so the boundary cases come out exact.
Practice
These take a few minutes each. Try them on paper or in your scratch folder before you open the answers.
Practice 1: shoelace by hand
Find 2A and the direction for the rectangle (0, 0), (5, 0), (5, 2), (0, 2) in that order.
Hint: Write the four terms cross(p_i, p_(i+1)), and add them.
Show the answer
The terms are 0, 5 * 2 - 0 * 0 = 10, 5 * 2 - 0 * 2 = 10, and 0. The sum is 20, so 2A = 20 and the area is 10. The direction is counterclockwise. The reference program prints 2A 20 CCW for this rectangle.
Practice 2: boundary before inside
For the triangle (0, 0), (4, 0), (0, 3), classify the points (1, 1), (2, 1), (4, 0) and (3, 3).
Hint: First check whether each point is on an edge. The hypotenuse runs from (4, 0) to (0, 3), so the points on it satisfy x / 4 + y / 3 = 1.
Show the answer
The program prints INSIDE, INSIDE, BOUNDARY and OUTSIDE for these four points, in that order. The point (4, 0) is a vertex, so it is on the boundary. The point (2, 1) satisfies 2 / 4 + 1 / 3 < 1, so it is strictly inside. The point (3, 3) is above the hypotenuse.
Practice 3: count the crossings
Use the crossing number method by hand on the point (1, 5) of the sample polygon (0, 0), (4, 0), (4, 4), (2, 6), (0, 4). Say whether the point is inside, and why the answer is decided without a count.
Hint: Check whether the point is on an edge first.
Show the answer
The point (1, 5) lies on the edge from (2, 6) to (0, 4), because 5 = 1 + 4. So the answer is BOUNDARY, and no crossing count is needed. The reference program prints BOUNDARY. A ray casting function that skips this check prints INSIDE here, as the variant in the mistakes section does.
Practice 4: the closing edge
Write the list of edges for the square (0, 0), (4, 0), (4, 4), (0, 4). Then say which edge a loop that runs over i + 1 < n would miss, and which query point would show it.
Hint: The last vertex connects back to the first. A query point to the left of the square is crossed by the edge that connects the last vertex to the first.
Show the answer
The edges are (0, 0) to (4, 0), (4, 0) to (4, 4), (4, 4) to (0, 4), and (0, 4) to (0, 0). The loop misses the last one, from (0, 4) back to (0, 0). The point (-1, 2) is to the left of the square and outside, and the ray from it crosses the missed edge and the right wall. Without the missed edge the winding total is 1 and the answer is INSIDE, which is wrong.
Practice 5: why the two methods differ
Explain why the crossing number method says OUTSIDE for (2, 2) in the square listed twice. Then say what the winding number is at that point and why it is 2.
Hint: Count the crossings of the ray to the right of (2, 2) with the edge from (4, 0) to (4, 4), once for each time the square is listed.
Show the answer
The ray from (2, 2) to the right crosses the wall at x = 4 once for each traversal of the square, so it crosses twice. Two is even, so the parity says outside. Both traversals go counterclockwise, so each adds 1 to the winding number, and the total is 2. Two is not zero, so the winding method says inside. The reference program prints INSIDE for the winding method and OUTSIDE for the crossing method.
Sources
- Dan Sunday, "Inclusion of a Point in a Polygon" (web article on geomalgorithms.com; secondary sources date it to 2001). It describes the winding number method used in the reference program.
shapely2.2.0, the geometry library used as a second reference in the tests. It was installed with pip in a scratch environment on 2026-11-08.