Geo Fencing - a point inside / outside the polygon

Question

I would like to define a polygon and implement an algorithm that would check if a point is inside or outside the polygon.

Does anyone know if there is any example of any such algorithm?

Answer 1

Just consider the problem of the problem with the point in the polygon (PIP) .

Answer 2

If I remember correctly, the algorithm should draw a horizontal line through the test point. Count how many lines of the polygon you cross to reach your point.

If the answer is odd, you're inside. If the answer is even, you are outside.

Edit: Yes, what did he say ( Wikipedia ):

Answer 3

C # code

bool IsPointInPolygon(List<Loc> poly, Loc point) { int i, j; bool c = false; for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) { if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg)) c = !c; } } return c; } 

Local class

 public class Loc { private double lt; private double lg; public double Lg { get { return lg; } set { lg = value; } } public double Lt { get { return lt; } set { lt = value; } } public Loc(double lt, double lg) { this.lt = lt; this.lg = lg; } } 

Answer 4

After searching the Internet and testing various implementations and porting them from C ++ to C #, I finally got my code:

  public static bool PointInPolygon(LatLong p, List<LatLong> poly) { int n = poly.Count(); poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon }); LatLong[] v = poly.ToArray(); int wn = 0; // the winding number counter // loop through all edges of the polygon for (int i = 0; i < n; i++) { // edge from V[i] to V[i+1] if (v[i].Lat <= p.Lat) { // start y <= Py if (v[i + 1].Lat > p.Lat) // an upward crossing if (isLeft(v[i], v[i + 1], p) > 0) // P left of edge ++wn; // have a valid up intersect } else { // start y > Py (no test needed) if (v[i + 1].Lat <= p.Lat) // a downward crossing if (isLeft(v[i], v[i + 1], p) < 0) // P right of edge --wn; // have a valid down intersect } } if (wn != 0) return true; else return false; } private static int isLeft(LatLong P0, LatLong P1, LatLong P2) { double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat) - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat)); if (calc > 0) return 1; else if (calc < 0) return -1; else return 0; } 

The isLeft function gave me rounding problems, and I spent hours not realizing that I was doing the wrong conversion, so forgive me for being lame if the block is at the end of this function.

By the way, this is the original code and article: http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 5

I think there is a simpler and more efficient solution.

Here is the code in C ++. I should just convert it to C #.

 int pnpoly(int npol, float *xp, float *yp, float x, float y) { int i, j, c = 0; for (i = 0, j = npol-1; i < npol; j = i++) { if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) && (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) c = !c; } return c; } 

Answer 6

Our best explanation and implementation can be found at Point in the inclusion of the number of polygon windings.

At the end of a well-explained article, there is a C ++ implementation. This site also contains some excellent algorithms / solutions for other geometry-based tasks.

I changed and used a C ++ implementation, and also created a C # implementation. You definitely want to use the Winding Number algorithm as it is more accurate than the border crossing algorithm and it is very fast.

Answer 7

Just a head (using the answer, since I can’t comment), if you want to use point-in-polygon for geofencing, you need to change your algorithm to work with spherical coordinates. -180 longitude is the same as 180 longitude, and the point-to-polygon will break in this situation.

Answer 8

Complete solution in asp.Net C #, you can see the full information here, you can see how to find the point (lat, lon), whether inside or outside the polygon, using latitude and longitude? Link article links

private static bool checkPointExistsInGeofencePolygon (latlnglist string, lat string, lng string) {

  List<Loc> objList = new List<Loc>(); // sample string should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|"; string[] arr = latlnglist.Split('|'); for (int i = 0; i <= arr.Length - 1; i++) { string latlng = arr[i]; string[] arrlatlng = latlng.Split(','); Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1])); objList.Add(er); } Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng)); if (IsPointInPolygon(objList, pt) == true) { return true; } else { return false; } } private static bool IsPointInPolygon(List<Loc> poly, Loc point) { int i, j; bool c = false; for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) { if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) | ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) / (poly[j].Lt - poly[i].Lt) + poly[i].Lg)) c = !c; } return c; } 

Answer 9

Check if the point is inside the polygon or not -

Consider a polygon that has vertices a1, a2, a3, a4, a5. The following set of steps should help determine if point P is inside the polygon or outside.

Calculate the vector region of the triangle formed by the edge a1-> a2, and the vectors connecting a2 with P and P with a1. Similarly, calculate the vector region of each of the possible triangles having one side as the side of the polygon, and the other two connect P to this side.

For a point to be inside the polygon, each of the triangles must have a positive area. Even if one of the triangles has a negative region, the point P stands out from the polygon.

To calculate the area of ​​a triangle defined by a vector representing its 3 edges, refer to http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

Answer 10

The problem is simpler if your polygon is convex. If so, you can do a simple test for each line to see if the point is inside or outside the line (to infinity in both directions). Otherwise, for concave polygons, draw an imaginary ray from your point to infinity (in any direction). Indicate how many times he crosses the border. Odd means that the point is inside, even means that the point is outside.

This last algorithm is more complicated than it sounds. You have to be very careful about what happens when your imaginary ray exactly hits one of the vertices of the polygon.

If your imaginary ray goes in the -x direction, you can only choose to count lines containing at least one point whose y-coordinate is strictly less than the y-coordinate of your point. Here's how you can work with most weird edge cases.

Answer 11

If you have a simple polygon (none of the lines intersect) and you have no holes, you can also triangulate the polygon, which you are probably going to do in the GIS application to draw a TIN, and then check the points in each triangle. If you have a small number of edges of a polygon, but a large number of points is fast.

For an interesting point in the triangle see link text

Otherwise, definitely use the winding rule, rather than crossing edges, crossing edges has real problems with points on the edges, which if your data is generated from GPS with limited accuracy is very likely.

Answer 12

a polygon is defined as a sequential list of pairs of points A, B, C .... A. no side AB, BC ... intersects the other side

Define the field Xmin, Xmax, Ymin, Ymax

case 1 control point P is out of field

case 2, the control point P lies inside the box:

Define the "diameter" D of the window {[Xmin, Ymin] - [Xmax, Ymax]} (and add a little extra to avoid possible confusion with D on the side)

Define the gradients M of all sides

Find a gradient Mt different from all gradients M

The test line runs from P in a gradient of Mt to a distance D.

Set the number of intersections to zero.

For each of the sides AB, BC, the test is for the PD to intersect with the side from its launch to, but NOT including its end. Increase the number of intersections if necessary. Note that the zero distance from P to the intersection indicates that P is on the side

An odd number indicates that P is inside the polygon

Answer 13

I translated the C # method into Php and I added a lot of comments to understand the code.

PolygonHelps Description:
Check if the point is inside or outside the polygon. This procedure uses gps coordinates, and it works when the polygon has a small geographic area.
INPUT:
$ poly: array of points: list of polygon vertices; [{Point}, {Point}, ...];
$ point: point to check; Point: {"lat" => "x.xxx", "lng" => "y.yyy"}


When $ c is false, the number of intersections with the polygon is even, so the point is outside the polygon;
When $ c is true, the number of intersections with the polygon is odd, so the point is inside the polygon;
$ n - the number of vertices in the polygon,
For each vertex in the polygon, the method calculates a line through the current vertex and the previous vertex and checks if there are two lines at the intersection point.
$ c changes when the intersection exists.
Thus, the method can return true if the point is inside the polygon, otherwise returns false.

 class PolygonHelps { public static function isPointInPolygon(&$poly, $point){ $c = false; $n = $j = count($poly); for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){ if ( ( ( ( $poly[$i]->lat <= $point->lat ) && ( $point->lat < $poly[$j]->lat ) ) || ( ( $poly[$j]->lat <= $point->lat ) && ( $point->lat < $poly[$i]->lat ) ) ) && ( $point->lng < ( $poly[$j]->lng - $poly[$i]->lng ) * ( $point->lat - $poly[$i]->lat ) / ( $poly[$j]->lat - $poly[$i]->lat ) + $poly[$i]->lng ) ){ $c = !$c; } } return $c; } } 

Answer 14

I add one detail to help people who live in ... the south of the earth! If you are in Brazil (this is my business), our GPS coordination is all the negatives. And all these algos give wrong results.

The easiest way to use the absolute Lat and Long values ​​of the whole point. And in this case, Jan Kobersky algo is perfect.

Answer 15

Jan's answer is excellent.

Here is the same code using the GeoCoordinate class.

 using System.Device.Location; 

...

 public static bool IsPointInPolygon(List<GeoCoordinate> poly, GeoCoordinate point) { int i, j; bool c = false; for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) { if ((((poly[i].Latitude <= point.Latitude) && (point.Latitude < poly[j].Latitude)) || ((poly[j].Latitude <= point.Latitude) && (point.Latitude < poly[i].Latitude))) && (point.Longitude < (poly[j].Longitude - poly[i].Longitude) * (point.Latitude - poly[i].Latitude) / (poly[j].Latitude - poly[i].Latitude) + poly[i].Longitude)) c = !c; } return c; }