How to find a point inside an irregular polygon

Question

I have a function that takes latitude and longitude coordinates, and returns information related to the polygon which contains the coordinates. In other words:

def coords_to_info(lat, lng):
    #check in which polygon the point lies
    return polyName

to check if the point is inside the polygon, I have tried two different functions:

def point_in_poly(x,y,poly):
    """
    function to check if a point is in a 2D polygon
    """
    n = len(poly)
    inside = False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xints:
                        inside = not inside
        p1x,p1y = p2x,p2y

    return inside

print point_in_poly(lat, lng, lBoundary)

and

from shapely.geometry import Point
from shapely.geometry.polygon import Polygon

coordPoint = Point(lat, lng)
coordPolygon = Polygon(lBoundary)

print coordPolygon.contains(coordPoint)

lBoundary is a list of tuples that is closed (first and last points are equal): [(a,b), (c,d), (e,f), (a,b)]

Both approaches work perfectly for test data and small convex data, but return false for most real data polygons.

I have tested both functions rather extensively with mock data (I tested all these types of polygons ), but when I apply it to most of my real data the functions cease working.

Are there any factors that would affect these functions to give false negatives, such as polygon size, decimal places of coordinates, or other such trivialities?

who are your real polygons? Are there zero length segments, duplicate points, crossing lines, etc.? — Daniel, Jul 13 '14 at 08:21
To my mind the easiest way to do this would be to either manually separate the polygon into triangles - you could write an algorithm to do that I think : you can then detect which of your defined triangles your long/lat sits in - this is rather easy I think. — Tony Suffolk 66, Jul 13 '14 at 08:37
I would just like to say that the problem resolved itself. There was a quirk in the data that I had overseen. I am leaving the question up because I quite like those two functions. — Roman, Jul 14 '14 at 09:26

score 0 · Answer 1 · edited May 23 '17 at 10:33

One of the most common approach to find if a point is inside a polygon is to test how many times a line that starts at the point and goes in any direction crosses the boundaries of the polygons. Check this question in stackoverflow for more information and concrete examples.

BTW, Shapely is a well tested library. I don't think that it will work incorrectly, probably there is a problem with your polygons or the way you are using it.

score 0 · Answer 2 · answered Jul 13 '14 at 08:53

Here is an algorithm I have used with success.

Find a point outside your polygon - just choose an x or y greater than your max.

Draw a line, in your head, from your point to the point outside your polygon..

Count the number of intersections of this line with the line segments that make up the perimeter of your polygon. If it is odd, the point is inside. If even, it is outside.

Another approach is to use a graphics polygon flood-fill function to fill a red polygon on a white background and then see what colour your point is...

score 0 · Answer 3 · answered Jul 13 '14 at 09:10

You can alternatively use QHull. The Python implementation comes with Scipy (http://docs.scipy.org/doc/scipy-0.13.0/reference/generated/scipy.spatial.ConvexHull.html#scipy.spatial.ConvexHull)

You can simply supply the coordiantes of your polygon along with the point you are looking at to ConvexHull and it will return the set of vertices that form the outer boundary of all the points. If your point is one of these vertices, then you know that your point like outside. Otherwsie, it lies inside. Nevertheless, scipy.spatial has a lot of functions for the type of things that you are doing, and you might want to take a look at that.

How to find a point inside an irregular polygon

3 Answers3