algorithm to define a geofence and see if a point is inside/outside it

Question

I am looking for an algorithm through I can create a geofence and check if a device is entering/leaving the fence. I have looked at point in polygon algorithms (ray casting and winding number) but are there any algorithms which can be applied to circle and any irregular shapes as well? The important constraint is time efficiency.

Thank you.

Answer 1

Well circles are pretty easy (at least if you are assuming a locally flat surface) - just absolute distance from a point.

The normal way if you need speed is a cascade where you check a circle first, or a square around the point, then a convex polygon, then a more detailed polygon if necessary.

How are you defining the irregular shape - if it's not a polygon?

ps see How to test if a point is inside of a convex polygon in 2D integer coordinates?

Answer 2

Here is the c code algorithm that is simple to understand:

http://alienryderflex.com/polygon/

Answer 3

I found this solution for python. This worked as far as I know.

from shapely.geometry import Point, Polygon
import matplotlib.path as mpltPath
from functools import reduce
import operator
import math
coords = [[ 12.934158,77.609316], [ 12.934796,77.609852],[ 12.934183,77.610646], [ 12.933551,77.610100], [12.934158,77.609316]]

#sorting the geofence coords in clockwise direction
center = tuple(map(operator.truediv, reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
coords = sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360)

#Testing if a point inside or outside
poly = Polygon(coords)
point = Point(12.933556,77.609854)
print(coords)
if(point.within(poly)):
    print("Inside")
else:
    print("Outside")

Thank You!

Answer 4

Take a look at quadtrees, spatial index, quadkeys and r-trees.

Answer 5

Winding Number Method

But the bottom line is that for both geometric correctness and efficiency reasons, the Winding Number algorithm should always be preferred for determining the inclusion of a point in a polygon.