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.

score 4 · Answer 1 · answered Oct 09 '12 at 13:02

4

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

http://alienryderflex.com/polygon/

answered Oct 09 '12 at 13:02

Josh C

89
1
11

score 3 · Answer 2 · edited May 23 '17 at 12:15

3

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?

edited May 23 '17 at 12:15

Community

1
1

answered Jun 01 '12 at 21:00

Martin Beckett

94,801
28
188
263

N.B. Rather than a square, it is usually a rectangle and often called a "bounding box". – David Conrad Jun 01 '12 at 21:54
@DavidConrad - yes, I oversimplified. Alternatively it IS a square you just change your coordinates ;-) – Martin Beckett Jun 01 '12 at 22:42
1

Sure. :) I just wanted to give the OP the term "bounding box" and a little more info, which might be useful to search for, and didn't feel it was worth a separate answer, so I put it here, as a comment to your answer. Cheers! – David Conrad Jun 01 '12 at 23:13

score 2 · Answer 3 · answered Jul 19 '20 at 04:23

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!

score 1 · Answer 4 · answered Mar 06 '18 at 17:20

1

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.

answered Mar 06 '18 at 17:20

LucasM

431
4
11

score 0 · Answer 5 · answered Oct 09 '12 at 13:11

0

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

answered Oct 09 '12 at 13:11

Micromega

12,486
7
35
72

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

5 Answers5