The Central Idea
A region divides space into different kinds of locations.
For a typical closed planar region, a point may be:
- strictly inside the region;
- strictly outside the region;
- on the boundary.
A robust point-in-region algorithm should make these cases explicit rather than treating every input as only true or false.
Classification as a Computational Output
Instead of returning only
\[ \text{inside}=\text{true or false}, \]many systems use a three-way classification:
\[ \boxed{ \{\text{outside},\text{boundary},\text{inside}\} }. \]This avoids ambiguity when later computations need to distinguish a point touching an edge from a point strictly contained in the region.
The Region Must Have a Representation
A point-in-region test depends on how the region is represented.
Common representations include:
- axis-aligned rectangles;
- circles and ellipses;
- convex polygons;
- general simple polygons;
- polygons with holes;
- implicit inequalities;
- meshes and higher-dimensional solids.
Different representations support different algorithms.
The Simplest Region: An Axis-Aligned Rectangle
Suppose a rectangle is described by
\[ x_{\min}\le x\le x_{\max} \]and
\[ y_{\min}\le y\le y_{\max}. \]Then the point
\[ P=(x,y) \]lies inside or on the rectangle exactly when
\[ \boxed{ x_{\min}\le x\le x_{\max} \quad\text{and}\quad y_{\min}\le y\le y_{\max} }. \]Strict Interior versus Boundary for a Rectangle
The strict interior uses strict inequalities:
\[ \boxed{ x_{\min}Bounding Boxes as an Early Filter
Before performing a more expensive point-in-polygon test, first compare the point with the polygon's axis-aligned bounding box.
If the point lies outside that box, it cannot lie inside the polygon.
This provides a quick rejection:
\[ \boxed{ P\notin\operatorname{AABB}(R) \implies P\notin R }. \]Passing the bounding-box test does not prove that the point is inside.
Point-in-Circle Test
Let a circle have center
\[ C=(c_x,c_y) \]and radius \(r\).
A point
\[ P=(x,y) \]lies inside or on the circle when
\[ \boxed{ (x-c_x)^2+(y-c_y)^2\le r^2 }. \]Squared Distance Avoids an Unnecessary Square Root
The point-in-circle test could be written as
\[ \|P-C\|\le r. \]But this would require computing a square root.
Since both sides are nonnegative, it is equivalent to compare squared quantities:
\[ \boxed{ \|P-C\|^2\le r^2 }. \]This is usually the simpler computational test.
Interior, Boundary, and Exterior of a Circle
Define
\[ d^2=(x-c_x)^2+(y-c_y)^2. \]Then:
- if \(d^2
- if \(d^2=r^2\), the point is on the boundary;
- if \(d^2>r^2\), the point is outside.
Regions Defined by Inequalities
Some regions are naturally described directly by inequalities.
For example,
\[ x^2+y^2\le 25 \]describes the disk of radius \(5\) centered at the origin.
A point-in-region test is then simply evaluation of the defining inequality.
Half-Planes
A line
\[ ax+by=c \]divides the plane into two half-planes:
\[ ax+byTherefore, evaluating
\[ ax+by-c \]tells us which side of the line contains a point.
Orientation as a Side-of-Line Test
For a directed edge from \(A\) to \(B\), the orientation value
\[ \operatorname{orient}(A,B,P) \]classifies the side containing \(P\).
- A positive value places \(P\) to the left of the directed line.
- A negative value places \(P\) to the right.
- Zero means \(P\) is collinear with \(A\) and \(B\).
Convex Regions as Intersections of Half-Planes
A convex polygon can be viewed as the intersection of the interior half-planes determined by its edges.
If the vertices are listed counterclockwise, a point lies inside or on the polygon when it never lies strictly to the right of any directed boundary edge.
Thus a convex-polygon membership test can repeatedly evaluate
\[ \operatorname{orient}(V_i,V_{i+1},P). \]Convex Polygon Test
Suppose the vertices
\[ V_0,V_1,\ldots,V_{n-1} \]are listed counterclockwise.
For each edge
\[ V_iV_{i+1}, \]with indices taken cyclically, compute
\[ o_i=\operatorname{orient}(V_i,V_{i+1},P). \]If every \(o_i\ge0\), the point lies inside or on the boundary.
Why the Convex Test Works
A convex polygon contains every segment joining two of its points.
Equivalently, its interior is contained consistently on the same side of every directed edge when the vertices are ordered consistently.
This property does not hold for general concave polygons, so the same simple all-edges test cannot be used there without modification.
Example: Point in a Convex Triangle
Let
\[ A=(0,0),\qquad B=(6,0),\qquad C=(2,5) \]be listed counterclockwise, and test
\[ P=(2,2). \]Compute
\[ \operatorname{orient}(A,B,P)=12, \] \[ \operatorname{orient}(B,C,P)=14, \] \[ \operatorname{orient}(C,A,P)=6. \]All are positive, so
\[ \boxed{P\text{ lies inside the triangle}.} \]Boundary Detection for a Polygon
Before classifying a point as strictly inside or outside, it is often useful to test whether it lies on any polygon edge.
For each segment \(V_iV_{i+1}\), test:
\[ \operatorname{orient}(V_i,V_{i+1},P)=0 \]together with the coordinate bounds for the segment.
If both conditions hold, classify the point as
\[ \boxed{\text{boundary}}. \]General Polygons Need a Different Strategy
A concave polygon may turn inward.
A point inside such a polygon can lie on different sides of different directed edges.
Two widely used general methods are:
- the ray-casting or crossing-number method;
- the winding-number method.
The Ray-Casting Idea
Start at the test point \(P\) and imagine a ray extending indefinitely in one direction, commonly to the right.
Count how many times this ray crosses the polygon boundary.
For a simple polygon:
\[ \boxed{ \text{odd crossings}\Rightarrow\text{inside} } \]and
\[ \boxed{ \text{even crossings}\Rightarrow\text{outside}. } \]Why Crossing Parity Works
Far away from a bounded polygon, the ray is outside the region.
Each ordinary boundary crossing switches between outside and inside:
\[ \text{outside} \leftrightarrow \text{inside}. \]After an odd number of switches, the starting point lies inside. After an even number, it lies outside.
Ray Casting with a Horizontal Ray
Let the test point be
\[ P=(x_P,y_P). \]For each polygon edge from
\[ A=(x_A,y_A) \]to
\[ B=(x_B,y_B), \]determine whether the edge crosses the horizontal level
\[ y=y_P. \]Only edges that straddle that level can produce a crossing.
A Useful Straddle Test
One common convention treats an edge as crossing the horizontal level when
\[ \boxed{ (y_A>y_P)\ne(y_B>y_P) }. \]This logical test says exactly one endpoint lies above the ray's horizontal level.
The asymmetric convention is important because it avoids counting a shared polygon vertex twice.
Finding the Crossing Coordinate
If the edge straddles \(y=y_P\), the horizontal coordinate where the edge reaches that level is
\[ \boxed{ x_{\text{cross}} = x_A+ \frac{(y_P-y_A)(x_B-x_A)} {y_B-y_A} }. \]If
\[ x_{\text{cross}}>x_P, \]then the crossing lies to the right of the test point and contributes to the ray count.
A Standard Ray-Casting Predicate
For an edge \(AB\), toggle the inside/outside state when both of the following are true:
\[ (y_A>y_P)\ne(y_B>y_P) \]and
\[ x_P< x_A+ \frac{(y_P-y_A)(x_B-x_A)} {y_B-y_A}. \]After all edges are processed, the final parity determines the result, provided boundary cases were handled separately.
Why Vertices Require Care
Suppose the ray passes exactly through a polygon vertex shared by two edges.
Naively counting both incident edges would count one geometric crossing twice.
Correct implementations adopt a consistent endpoint convention, such as treating one endpoint of an edge as included and the other as excluded.
Horizontal Edges Require Care
If an edge is horizontal,
\[ y_A=y_B, \]then a horizontal test ray may overlap its vertical level.
The usual straddle rule automatically excludes ordinary horizontal edges from the crossing count.
Boundary membership should be checked separately before ray casting.
Ray Direction Is Arbitrary in Principle
The ray does not have to point rightward.
It may extend left, upward, downward, or in another direction, provided the crossing rules are implemented consistently and degenerate alignments are handled.
Horizontal rays are popular because their arithmetic is convenient.
The Winding-Number Idea
Instead of counting crossings only by parity, the winding-number method tracks how the polygon boundary winds around the test point.
For a simple consistently oriented polygon:
\[ \boxed{ \text{winding number}=0 \Rightarrow \text{outside} } \]while a nonzero winding number indicates that the point is enclosed.
Signed Crossings in the Winding Number
As polygon edges cross a horizontal level through \(P\), upward and downward crossings are treated differently.
Orientation tests determine whether a crossing passes on the appropriate side of the point.
The accumulated signed count measures how many net times the boundary wraps around \(P\).
Crossing Number versus Winding Number
For ordinary simple polygons, both methods can correctly distinguish inside from outside.
The crossing-number method asks whether the number of crossings is odd or even.
The winding-number method retains directional information and is especially useful when orientation or more general winding behavior matters.
Simple Polygons
A simple polygon has boundary edges that meet only at adjacent shared endpoints.
In particular, the boundary does not cross itself.
Standard inside/outside intuition is clearest for simple polygons because the boundary separates the plane into a well-defined interior and exterior.
Self-Intersecting Polygons Need a Filling Rule
If a polygonal path crosses itself, the word inside becomes convention-dependent.
Common filling rules include:
- the even-odd rule;
- the nonzero winding rule.
These rules can classify some self-intersecting configurations differently.
Therefore, the algorithm must match the intended region definition.
The Even-Odd Filling Rule
The even-odd rule uses crossing parity.
A point is treated as filled when a ray from the point crosses the boundary an odd number of times.
Direction does not matter; only parity matters.
The Nonzero Winding Rule
The nonzero winding rule uses the signed winding of the boundary around the point.
A point is filled when the net winding number is nonzero.
Because direction matters, different boundary orientations can affect the result.
Polygons with Holes
A region may have an outer boundary and one or more inner boundaries representing holes.
One strategy is:
- test whether the point lies inside the outer boundary;
- test whether it lies inside any hole;
- classify it as part of the region only if it is inside the outer boundary and outside every hole.
Boundary conventions must still be specified for both outer and inner boundaries.
Orientation Conventions for Holes
In winding-based systems, boundary orientation can encode region structure.
A common convention lists:
- outer boundaries counterclockwise;
- hole boundaries clockwise.
The opposite convention may also be used. Consistency is what matters.
Triangles Have Specialized Tests
Because a triangle has only three edges, several efficient membership tests are available.
One uses orientation signs.
Another uses barycentric coordinates.
These specialized tests are common in computer graphics, mesh processing, and interpolation.
Barycentric Coordinates
For a nondegenerate triangle with vertices \(A\), \(B\), and \(C\), a point \(P\) can be represented as
\[ \boxed{ P=\alpha A+\beta B+\gamma C } \]with
\[ \boxed{ \alpha+\beta+\gamma=1. } \]The values \(\alpha,\beta,\gamma\) are the barycentric coordinates of \(P\) relative to the triangle.
Barycentric Point-in-Triangle Test
A point lies inside or on a nondegenerate triangle when
\[ \boxed{ \alpha\ge0,\qquad \beta\ge0,\qquad \gamma\ge0 }. \]It lies strictly inside when all three values are positive.
A zero barycentric coordinate places the point on the edge opposite the corresponding vertex.
Area Interpretation of Barycentric Coordinates
The barycentric coordinates may be interpreted through signed triangle areas.
For example,
\[ \alpha = \frac{ \operatorname{area}(PBC) }{ \operatorname{area}(ABC) }, \]with analogous formulas for \(\beta\) and \(\gamma\), using a consistent signed-area convention.
Thus point-in-triangle testing is closely connected to the orientation determinant introduced earlier.
Convex Polygon Testing Can Be Accelerated
The straightforward half-plane method checks every edge, requiring work proportional to the number of vertices.
For a fixed convex polygon with many repeated queries, the polygon can also be organized into angular sectors from one reference vertex.
A binary search can locate the relevant triangle fan sector, after which a point-in-triangle test completes the query.
This is an example of preprocessing geometry to make later queries faster.
Many Queries Change the Best Algorithm
If only one point will be tested against one polygon, a simple linear scan may be ideal.
If millions of points will be tested against the same region, it may be worthwhile to build:
- spatial indexes;
- hierarchical bounding regions;
- triangulations;
- grid accelerators;
- specialized convex-query structures.
Algorithm choice depends not only on geometry but also on workload.
Broad Phase and Narrow Phase
As with intersection problems, point-in-region systems often use a two-stage design.
The broad phase rejects points using inexpensive bounds.
The narrow phase applies the exact region-specific test.
For a polygon:
\[ \boxed{ \text{bounding-box test} \rightarrow \text{polygon test} }. \]Boundary Policy Is Part of the Problem Definition
Applications do not always want the same treatment of boundary points.
A geographic database may treat a boundary location as belonging to both adjacent regions.
A tiling algorithm may deliberately assign shared boundaries to only one cell to avoid duplication.
Therefore, the inclusion convention should be defined before the algorithm is implemented.
Open, Closed, and Half-Open Regions
A closed region includes its boundary.
An open region excludes its boundary.
Computational partitions sometimes use half-open conventions so that neighboring regions do not both claim the same boundary point.
These are mathematical design choices as well as implementation choices.
Numerical Boundary Ambiguity
In exact mathematics, a point may satisfy
\[ \operatorname{orient}(A,B,P)=0 \]exactly.
In floating-point arithmetic, the computed value may instead be a very small positive or negative number.
This can cause a boundary point to be misclassified as inside or outside.
Using a Tolerance for Boundary Tests
A practical approximate test may classify a value \(r\) as effectively zero when
\[ \boxed{ |r|\le\varepsilon. } \]For example, a near-collinearity test may use
\[ |\operatorname{orient}(A,B,P)| \le\varepsilon. \]The tolerance must be chosen with attention to coordinate scale and the needs of the application.
Exact Predicates
Some geometric applications require guaranteed topological consistency.
In such cases, approximate floating-point predicates may be replaced or supplemented with:
- integer arithmetic when coordinates permit it;
- rational arithmetic;
- extended precision;
- adaptive exact predicates.
The goal is to prevent numerical noise from changing discrete geometric decisions.
Degenerate Polygons
A polygonal input may contain:
- repeated consecutive vertices;
- zero-length edges;
- collinear neighboring edges;
- too few distinct vertices to enclose area;
- self-intersections when a simple polygon was expected.
Robust software should either normalize these cases or reject them explicitly.
Repeated Vertices
If two consecutive polygon vertices are identical, the edge between them has zero length.
This usually contributes no useful boundary geometry and may interfere with algorithms that assume every edge has distinct endpoints.
Preprocessing may remove repeated consecutive vertices.
Collinear Adjacent Edges
A polygon may contain three consecutive vertices
\[ A,\ B,\ C \]with
\[ \operatorname{orient}(A,B,C)=0. \]If \(B\) lies between \(A\) and \(C\), then \(B\) does not change the geometric boundary.
Some systems keep such vertices; others simplify them away.
Example: Point in a Rectangle
Consider the rectangle
\[ -2\le x\le5 \]and
\[ 1\le y\le7. \]Test
\[ P=(3,4). \]Since
\[ -2<3<5 \]and
\[ 1<4<7, \]the point lies strictly inside.
Example: Point on a Rectangle Boundary
Using the same rectangle, consider
\[ Q=(5,3). \]The point satisfies the inclusive bounds, but
\[ x=5=x_{\max}. \]Therefore,
\[ \boxed{Q\text{ lies on the boundary}.} \]Example: Point in a Circle
Let the circle have center
\[ C=(1,2) \]and radius
\[ r=5. \]Test
\[ P=(4,6). \]The squared distance is
\[ (4-1)^2+(6-2)^2 = 9+16 = 25. \]Since
\[ 25=r^2, \]the point lies on the circle boundary.
Example: A Concave Polygon
Consider a polygon with an inward indentation.
A point can pass the polygon's bounding-box test and still lie in the indentation outside the actual region.
This demonstrates why bounding boxes are filters rather than complete point-in-polygon tests.
Ray casting or winding-number methods are needed for the full boundary.
Common Error: Treating the Bounding Box as the Region
A polygon's axis-aligned bounding box generally contains points that are not in the polygon.
Therefore,
\[ P\in\operatorname{AABB}(R) \]does not imply
\[ P\in R. \]The bounding box is an early rejection tool, not a universal membership test.
Common Error: Using the Convex Test on a Concave Polygon
The all-edges same-side test relies on convexity.
A concave polygon may contain valid interior points that lie on different sides of different supporting edge lines.
For general simple polygons, use a method such as ray casting or winding number instead.
Common Error: Counting a Vertex Twice
A ray may pass through a polygon vertex shared by two edges.
Counting both edges as separate crossings can flip the parity incorrectly.
Use a consistent half-open crossing convention so that a shared vertex contributes correctly.
Common Error: Ignoring Boundary Cases
A point that lies exactly on a polygon edge is neither an ordinary interior point nor an ordinary exterior point.
If boundary membership matters, test for it explicitly before applying the inside/outside rule.
Common Error: Assuming Every Polygon Is Simple
A self-intersecting polygon does not have a unique inside/outside interpretation without a filling rule.
The even-odd and nonzero winding rules can disagree.
Therefore, the region definition must specify how self-intersections are to be interpreted.
Common Error: Comparing Floating-Point Values to Zero Blindly
Tests such as
\[ \operatorname{orient}(A,B,P)=0 \]are mathematically exact statements.
Floating-point arithmetic may require a tolerance or a more robust exact predicate, depending on the application.
A Reliable Procedure for Point-in-Rectangle Testing
- Compare \(x\) with \(x_{\min}\) and \(x_{\max}\).
- Compare \(y\) with \(y_{\min}\) and \(y_{\max}\).
- If any coordinate is outside its range, return outside.
- If the point lies on any limiting coordinate and boundary is included, return boundary.
- Otherwise return inside.
A Reliable Procedure for Point-in-Circle Testing
- Subtract the center from the point.
- Compute the squared distance \(d^2\).
- Compare \(d^2\) with \(r^2\).
- Return inside, boundary, or outside according to the comparison.
- Use a suitable numerical policy when approximate arithmetic is involved.
A Reliable Procedure for Point-in-Convex-Polygon Testing
- Confirm the polygon orientation or use a sign-consistent formulation.
- Optionally reject the point using the polygon bounding box.
- Test whether the point lies on any boundary edge.
- Evaluate orientation against every directed edge.
- If the signs are consistent with the polygon interior, return inside.
- If one sign violates the interior half-plane condition, return outside.
A Reliable Procedure for Ray Casting
- Reject with the bounding box when possible.
- Test polygon edges for exact or approximate boundary membership.
- Choose a consistent ray direction.
- Process each edge with a half-open endpoint convention.
- Count or toggle only genuine ray crossings.
- Return inside for odd parity and outside for even parity.
- Apply the application's chosen boundary policy.
A Reliable Procedure for Repeated Region Queries
- Analyze the region type and expected number of queries.
- Precompute the region bounding box.
- Remove or classify degenerate boundary data if appropriate.
- Choose a specialized test for circles, rectangles, or convex polygons when available.
- Use a general polygon method only when the geometry requires it.
- Consider spatial indexing or preprocessing when query volume is large.
- Keep boundary and numerical conventions consistent across all queries.
Practice 1: Rectangle
Classify
\[ P=(3,5) \]relative to
\[ 0\le x\le6, \qquad 1\le y\le8. \]Practice 2: Rectangle Boundary
Classify
\[ P=(6,4) \]relative to the same rectangle.
Practice 3: Circle
A circle has center
\[ C=(2,-1) \]and radius \(5\). Classify
\[ P=(5,3). \]Practice 4: Outside a Circle
Using the same circle, classify
\[ Q=(8,3). \]Practice 5: Half-Plane
Determine the sign of
\[ 2x-y-3 \]at
\[ P=(4,2), \]and state which side of the line
\[ 2x-y=3 \]contains the point.
Practice 6: Orientation Side Test
Let
\[ A=(0,0), \qquad B=(5,0), \qquad P=(2,3). \]Determine whether \(P\) lies to the left, right, or on the directed line from \(A\) to \(B\).
Practice 7: Triangle Boundary
Let
\[ A=(0,0), \qquad B=(6,0), \qquad C=(0,6). \]Classify
\[ P=(3,3). \]Practice 8: Ray-Casting Parity
A horizontal ray from a point crosses a simple polygon boundary \(5\) times. Classify the point.
Practice 9: Ray-Casting Parity
A horizontal ray from another point crosses the boundary \(4\) times. Classify the point.
Practice 10: Polygon with a Hole
A point lies inside the outer polygon boundary and also inside one of the polygon's holes. Is the point part of the filled region?
Practice Answers
Practice 1
Since
\[ 0<3<6 \]and
\[ 1<5<8, \]the point is
\[ \boxed{\text{inside}}. \]Practice 2
The point satisfies the inclusive bounds, and
\[ x=6=x_{\max}. \]Therefore,
\[ \boxed{\text{boundary}}. \]Practice 3
Compute
\[ d^2=(5-2)^2+(3-(-1))^2. \] \[ d^2=3^2+4^2=25. \]Since
\[ r^2=25, \]the point is
\[ \boxed{\text{boundary}}. \]Practice 4
\[ d^2=(8-2)^2+(3-(-1))^2 = 36+16 = 52. \]Since
\[ 52>25, \]the point is
\[ \boxed{\text{outside}}. \]Practice 5
\[ 2(4)-2-3=3. \]The result is positive, so \(P\) lies in the half-plane
\[ \boxed{2x-y>3}. \]Practice 6
\[ \operatorname{orient}(A,B,P) = 5(3)-0(2) = 15. \]Since the value is positive,
\[ \boxed{P\text{ lies to the left of }A\to B.} \]Practice 7
The hypotenuse from \(B\) to \(C\) satisfies
\[ x+y=6. \]For \(P=(3,3)\),
\[ 3+3=6. \]Therefore,
\[ \boxed{P\text{ lies on the boundary}.} \]Practice 8
Five is odd, so under the even-odd rule,
\[ \boxed{\text{the point is inside}.} \]Practice 9
Four is even, so
\[ \boxed{\text{the point is outside}.} \]Practice 10
A hole is excluded from the filled region.
Therefore, a point inside both the outer boundary and a hole is
\[ \boxed{\text{outside the filled region}}. \]What to Remember
Point-in-region tests translate spatial containment into computational predicates.
- rectangles use coordinate-range tests;
- circles use squared-distance comparisons;
- half-planes use signs of linear expressions or orientation values;
- convex polygons can be tested by consistent edge-side predicates;
- general simple polygons can use ray casting or winding numbers;
- ray casting requires careful endpoint and vertex conventions;
- self-intersecting boundaries require an explicit filling rule;
- holes require additional region logic;
- triangles support efficient orientation and barycentric tests;
- bounding boxes provide fast early rejection;
- boundary policy and numerical tolerance are part of the algorithm design.
The key computational question is not merely whether a point satisfies an equation, but how the entire boundary partitions space and how the application wants that partition interpreted.
Where We Go Next
Point-in-region tests determine whether a location belongs to an existing spatial boundary. The next lesson asks how to construct an important boundary directly from a collection of points.
Convex Hulls develops methods for finding the smallest convex region that contains a point set and introduces one of the central constructive problems of computational geometry.