Suppose you gotta setup drawing and saving of geofences on your website with Google Maps API.
You say, hey that shouldn’t take much time. Boy oh boy are you wrong.
Suppose that there are just two types of shapes you have to handle, polygon and circle geofences.
You have to handle the following cases,
Polygon drawn must not be self intersecting. There is something called Bentley–Ottmann algorithm to check if a polygon is self intersecting, it is hard to implement and should only be used if the number of points in the polygon is very large. Otherwise you can just check if any two set of lines in a polygon are intersecting. Run it in a loop in such a way that each line segment is checked with every other line segment in the polygon exactly once.
Ref : https://math.stackexchange.com/a/80806
Futher reading : http://geomalgorithms.com/algorithms.html
- Polygon/Circle drawn must not intersect with any other geofences.
- New Polygon
- Must not intersect with another polygon. Loop through all the points in new polygon, check if this point falls inside the stored polygons.
- Must not intersect with another circle. Find the distance of each point in new polygon from the centre of the older circle. If the distance is lesser than the radius, we have an intersection.
- New Circle
- Must not intersect with another circle. Distance between the two circle’s centre must be greater than the sum of the two respective radii.
- Must not intersect with another polygon.
Following the same method as mentioned before in this article for polygon-circle intersection.
- New Polygon
- New polygon intesects with another geofence, but no vertex of it is contained inside the other geofence.
This case is where an edge of the new polygon passes over a geofence’s boundary. The only way I’ve thought of to manually validate this case is to split the edges of the polygon and check for each point whether it falls inside any other geofence. The splitting distance will be the tolerance of how much intersection is allowed. If you set the splitting distance too low, your frontend might hang doing this validation.
Now you can go ahead store this as GeoJSON object in whatever database you’re using.
If you’ve got a better way to handle the 3rd case, ping me.