A diagram suggests which side of an edge a point occupies, but a program needs an exact decision. The cross product supplies that decision; summing the same determinant over a polygon gives its oriented area. This chapter separates three questions: whether the vertex order is clockwise, whether a point is on the boundary, and whether the arithmetic can represent the answer.
1. Orientation without slopes
Definition 8.1.1
(Cross product test of a point against a directed line)
For points , and define
It is positive when lies to the left of the directed line , negative on the right and zero on the line.
This works for vertical edges, where a slope formula would divide by zero. Zero alone says that is collinear with the edge; it does not say that it lies on the finite segment. For a segment test, also check both coordinates against the endpoint intervals.
Worked example 8.1.2
(A collinear point outside the segment)
Take and . Then , and the three points , and give
The first point is on the left, the second on the right. The last cross is zero, so is collinear with the line, but its coordinate is outside the interval , so it is not on the segment.
Quick check
(For , and , compute . Is on the segment ?)
Substitute and .
Solution · Answer
, so lies on the line . But is outside , so is not on the segment.
2. Twice the signed area
Definition 8.1.3
(Twice the signed area (shoelace sum))
For vertices of a simple polygon in boundary order, with and , define
The area is . With the usual Cartesian orientation, a counterclockwise boundary gives and a clockwise one gives . Reversing the list reverses every directed edge and changes the sign of , not its absolute value. The formula is a sum of signed triangle contributions relative to the origin: when the boundary is decomposed into triangles, internal directed edges appear in opposite directions and cancel. Signed contributions are essential when the origin is outside the polygon. The input must be a simple polygon; applying to an arbitrary self-intersecting walk gives an algebraic signed area rather than necessarily the area of its filled region.
Worked example 8.1.4
(Shoelace sum of a pentagon)
Take the counterclockwise vertices , closed by . The forward products are , which sum to . The backward products are , which sum to . Hence and the area is .
Keeping as an integer preserves half-integer areas exactly: compute |S| / 2 and append .5 exactly when |S| % 2 == 1. Ensure the chosen type can represent as well as ; taking the absolute value of the most negative signed value can overflow.
Worked example 8.1.5
(A half-integer area and a clockwise list)
For the triangle the summands are , and , so . Since is odd, the area is , printed as 1.5. Listing the same triangle clockwise as gives summands , so : same area, opposite sign.
Quick check
(Compute and the area for the clockwise square .)
Close the list with and evaluate the four summands.
Solution · Answer
The summands are , , and . So : negative because the list is clockwise. The area is , as expected for a square of side .
Quick check
(What are and the area of the pentagon above if its vertex list is reversed?)
Reversing every directed edge changes the sign of every summand pair.
Solution · Answer
, because reversing the list negates the sum. The area is unchanged.
3. Convexity turns every edge into a constraint
Suppose the input is already known to be a nondegenerate, simple, convex polygon listed counterclockwise. Its closed region, including boundary, is the intersection of the closed left half-planes of its directed boundary edges; its interior is the intersection of the corresponding open half-planes. Thus compute every cross with .
Theorem 8.1.6
(Edge-test classification of a point)
Let be a nondegenerate simple convex polygon with vertices in counterclockwise order, , and for a point write . Then:
- if some , is outside ;
- if no is negative and at least one is zero, is on the boundary of ;
- if all , is strictly inside .
Proof
(Half-planes give the three cases)
Let be the closed left half-plane of the -th edge. We use the standard half-plane description of a convex polygon: with counterclockwise edges, . (One direction is easy: each edge supports , so every point of lies in every . The converse is the part that requires convexity.)
Hence exactly when every , which proves the first case by contraposition: a negative puts outside .
The interior of a finite intersection is the intersection of the interiors, and the interior of is the open half-plane . So is in the interior of exactly when all , which is the third case.
The boundary of the closed set is minus its interior. So is on the boundary exactly when all but not all , that is, when no is negative and at least one is zero. This is the second case.
Proof X-ray
Where convexity and the zero case enter
Only one step of the proof uses convexity: the identity . For a convex polygon each edge supports , which gives the inclusion ; the reverse inclusion is the half-plane theorem. For a concave polygon the identity fails, and the counterexample below exhibits a point of that lies outside one . After the identity, the argument concerns half-planes only: the interior of a finite intersection equals the intersection of the interiors (finiteness matters), and the boundary of a closed set is the set minus its interior. A single zero cross is therefore not a boundary certificate by itself. It counts only because every other cross is nonnegative, which has already placed in .
Convexity is not a formality, as a concrete concave polygon shows.
Counterexample mode
The one-sided test needs convexity
It is tempting to apply the same all-crosses test to any simple counterclockwise polygon. Take the concave polygon . Its shoelace sum is , so it is counterclockwise, and its area is (the square minus the notch triangle of area ). The point is inside the polygon: it lies in the square, and the notch meets the line only at . For the edge we have and , so the cross is . The test would declare an interior point outside. The statement is repaired by the hypothesis of convexity: for a concave polygon the intersection of the left half-planes is smaller than the polygon.
Worked example 8.1.7
(Classifying three points against the pentagon)
Use the five-vertex example. For the five crosses are , all positive, so is strictly inside. For the first two crosses are and , and the third is , so is outside. For the crosses are : none is negative and the first is zero, so is on the boundary (it lies on the edge from to ).
Worked example 8.1.8
(A vertex is a boundary point)
Take the vertex of the same pentagon. It lies on the two edges meeting there. Edge gives , and edge gives . The other three crosses are computed in the same way. Edge with gives ; edge with gives ; edge with gives . Two zeros and three positives: no negative cross and a zero, so is on the boundary, as it must be.
Common mistake
(Treating a zero cross as being on the boundary)
Take and the first edge of the pentagon: the cross is , yet is not on the polygon. The second edge gives , so is outside. A zero is a boundary certificate only when no other cross is negative.
Common mistake
(Feeding a clockwise list to the counterclockwise rule)
List the pentagon in reverse, . Each reversed edge negates the cross, so gets the five crosses and the rule as written reports an outside point for a point that is strictly inside. Compute first and reverse the list when .
The input convention matters: for a clockwise polygon the signs reverse. Compute the signed area and reverse a clockwise vertex list before using this rule. A zero signed area is rejected under the nondegenerate-polygon precondition; the sign alone does not prove that an arbitrary input is simple or convex.
Quick check
(For the pentagon above, classify using the edge crosses.)
Compute the cross against each of the five directed edges, stopping at the first negative one.
Solution · Answer
Edge : . Edge : , so . Edge : , so . Edge : , so . Edge : , so . All five are positive, so is strictly inside.
4. Cost and exact arithmetic
Proposition 8.1.9
(Linear cost of one pass)
For a polygon with vertices, one signed-area computation or one point query evaluates exactly summands or crosses, so it uses arithmetic operations and extra scalars.
Proof
(One loop over the edges)
Each of the edges , , is visited once, and each visit does a constant number of subtractions, multiplications and one comparison or addition into a running value. Only the loop counter, the running sum and the current cross need to be stored beyond the input.
A single signed-area pass or point query visits edges and costs arithmetic operations. Repeating the query for points costs ; this analysis does not claim a faster preprocessing method. The polygon requires storage if retained for multiple queries; a scan uses extra scalars.
Proposition 8.1.10
(Integer range bounds)
If every integer coordinate has magnitude at most , then every coordinate difference has magnitude at most , every cross value has magnitude at most , every shoelace summand has magnitude at most , and every running sum of summands has magnitude at most .
Proof
(Triangle inequality on each term)
A difference of two numbers in lies in . Each of the two products in a cross multiplies two such differences, so it has magnitude at most , and their difference has magnitude at most . In a shoelace summand each product has magnitude at most , so the summand is at most , and of them sum to at most .
These are safe upper bounds, not promises that every input attains them simultaneously. Select a signed type that can represent the required intermediate values and promote coordinates before subtraction or multiplication. Taking a remainder or widening after an overflow cannot recover the lost value. The simple running-sum bound can exceed the range of a type sufficient for one orientation test. Either use a wider accumulator or prove a tighter bound on every partial sum. Although the final is at most for a simple polygon in the box, that final-value bound does not by itself bound partial sums.
Concept lensGeometric
The same sum as a triangle fan
Fix the vertex and cut the polygon into triangles . Then ; for the pentagon the terms are , again . For a counterclockwise convex polygon every term is positive, so the partial sums increase to and the accumulator never exceeds the final bound.
Worked example 8.1.11
(Does 64-bit arithmetic suffice at one billion?)
Let . Then differences are at most , a product at most and a cross at most . Because , one cross fits in signed 64-bit integers, provided the coordinates are promoted to 64 bits before subtracting. For the shoelace sum with the bound exceeds , so the simple bound does not certify a 64-bit accumulator; one would need a wider accumulator or a tighter argument.
Common mistake
(Letting the final bound stand in for partial sums)
For a simple polygon the final is at most , but is computed by adding summands one at a time, and the certified bound for the partial sums is only after summands. Declaring that a type holding is safe for the accumulator skips this gap.
Quick check
(With and all arithmetic done in signed 64-bit integers after promoting the coordinates, can a single cross overflow?)
Compare the bound with .
Solution · Answer
No. The cross magnitude is at most , which is less than . If the coordinates were multiplied as 32-bit values before promotion, the product could already overflow, so the promotion must come first.
Checklist. Confirm simple, convex and nondegenerate input before applying the edge test. Establish boundary orientation, preserve the signed area until orientation is known, distinguish a line from a segment, and derive an overflow bound for the actual input limits.