Overview
Point in Polygon methods often cast a ray from the point and count how many polygon edges it crosses.
FoundationSource checked
Point in Polygon
Tests whether a point lies inside a polygon.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Geometry
- Difficulty
- Beginner
- Family
- Geometric Predicate
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 5
- Code example
- Not ready
- Visualization
- Ready
Core Concepts
ray crossingpolygon boundaryinside-outside testedge intersectiongeometric calculationgeometric predicatespatial relationshipcoordinate calculation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use it to classify a point relative to a polygon boundary.
- Use it for hit testing, geographic containment, and polygon selection.
- Use a boundary convention that matches the application.
When Not to Use
- Avoid it on self-intersecting polygons unless the winding rule is defined.
- Avoid ignoring points that lie exactly on an edge or vertex.
- Avoid planar assumptions for spherical or geographic coordinates without projection care.
What It Does
- Checks containment inside a polygon
- Counts boundary crossings
Use Cases
- Geofencing
- Hit testing
- Polygon selection
Inputs
- Point
- Polygon vertices
Outputs
- Inside, outside, or boundary result
Key Formulas (1)
Crossing parity
inside = crossingcount mod 2 = 1
inside = crossing_count mod 2 == 1Classifies a point by whether a ray crosses polygon edges an odd number of times.
Pseudocode
- 1.Cast a ray from the point
- 2.Count polygon edges that cross the ray
- 3.Handle points on the boundary separately
- 4.Return inside if the crossing count is odd
- 5.Return outside if the crossing count is even
Canonical Example
- Input
- square = [(0,0), (2,0), (2,2), (0,2)], point = (1,1)
- Output
- inside
- Explanation
- A ray from the point crosses the square boundary once.
Implementation Notes
- Use ray casting or winding number depending on the desired inside rule.
- Handle edge and vertex hits before counting crossings.
- Keep polygon orientation and coordinate system assumptions explicit.
Common Pitfalls
- Double-counting ray crossings at polygon vertices.
- Leaving boundary points undefined.
- Using a rule for simple polygons on self-intersecting polygons without defining semantics.
Interactive Mechanism Walkthrough
Spatial Primitive & Sweep-Line CanvasShow a ray from the point crossing polygon edges.
Step 1 of 5: Cast a ray from the point
ray-crossingNotes
Boundary handling should be specified as part of the predicate's contract.
Sources (1)
What each reference supports for this entry.
Computational Geometry
BookComputational geometry reference for convex hulls, point location, triangulations, and geometric predicates.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesKirkpatrick Point Location
Geometry · Specialized
Kirkpatrick Point Location and Point in Polygon are practical alternatives within planar point location, with different assumptions and tradeoffs.
Compare with thisUsed byEar Clipping Triangulation
Geometry · Core
Ear clipping checks whether candidate ears contain other polygon vertices.
Compare with thisOften paired withRay Tracing
Rendering · Foundation
Ray crossing tests for point-in-polygon are conceptually similar to ray intersection counts.
Compare with thisRelationships
View full relationship pageConceptual neighborLine Segment Intersection
Point-in-polygon tests often intersect a ray with polygon edges.
Often paired withRay Tracing
Ray crossing tests for point-in-polygon are conceptually similar to ray intersection counts.
Related Algorithms
Tags
GeometryPolygonsComputational Geometry