Efficient Point‑in‑Polygon Determination for Geo‑fencing Using Ray Casting and R‑Tree Indexing

Geo‑fencing is a location‑based service that defines a virtual boundary; when a mobile device enters, leaves, or moves within this area, it can receive automatic notifications such as promotional coupons. Major mobile apps like Meituan, Dianping, and Taobao use this technique.

The core problem of geo‑fencing is determining whether a user’s location lies inside a polygonal fence. This article introduces practical solutions used in real applications.

1. Determining Whether a Point Is Inside a Polygon

Most geo‑fences are polygons. The ray‑casting algorithm tests a point by drawing a ray along the X‑axis and counting how many times the ray intersects polygon edges; an odd count means the point is inside, an even count means it is outside. This method works for convex and concave polygons and runs in O(N) time, where N is the number of edges. A reference implementation can be found at alienryderflex.com/polygon .

When the number of polygons is small, a simple brute‑force loop combined with ray‑casting is sufficiently fast. However, with a large number of polygons (e.g., 100,000), performing ray‑casting for each one takes about 3.9 seconds, which is unacceptable for online services. A performance test on 7‑edge polygons is shown below.

2. Accelerating the Check with R‑Tree Indexing

The inefficiency of brute‑force comes from invoking ray‑casting for every polygon. By first filtering out most polygons with a coarse spatial index, the number of expensive ray‑casting calls can be dramatically reduced. For one‑dimensional data we use B‑tree indexes; for two‑dimensional spatial data we use an R‑tree.

2.1 Bounding‑Box Approximation

Polygons of arbitrary shape are approximated by their Minimum Bounding Rectangle (MBR), which provides a uniform, simple representation.

2.2 Building an R‑Tree on the Bounding Boxes

2.3 Query Process

a) Use the R‑tree to quickly test whether the user’s point (red dot) is covered by any MBR (average query complexity O(log N)).

b) If no MBR covers the point, the user is outside all geo‑fences.

c) If one or more MBRs cover the point, apply the ray‑casting algorithm to the corresponding polygons for a precise result.

3. Handling Polygons with a Very Large Number of Edges

Some geo‑fences consist of extremely complex polygons with tens of thousands of edges. Running ray‑casting on such polygons is costly because its complexity is O(N) with N being the edge count.

To speed this up, each edge is also wrapped in an MBR and an R‑tree is built on those edge MBRs. During a query, the ray first checks intersection with edge MBRs via the R‑tree, then only the remaining candidate edges are processed precisely, reducing the complexity from O(N) to O(log N).

4. Practical Results

In a production system with 300,000 geo‑fence polygons, building an in‑memory R‑tree reduced the average real‑time query latency to under 1 ms, compared with roughly 9 seconds for a naïve brute‑force approach.

5. R‑Tree Source Code Links

Rtree (Python)

R‑tree implementation (Java)

R‑tree (JavaScript)

R‑tree (C#)