How to search point inside polygon without GeoDjango

Question

The situation follows:

• Each supplier has some service areas, which the user have defined using GoogleMaps (polygons).
• I need to store this data in the DB and make simple (but fast) queries over this.
• Queries should looks like: "List all suppliers with service area containing x,y" or "In which polygons (service areas) x,y are inside?"

At this time, I've found GeoDjango which looks a very complex solution to this problem. To use it, I need a quite complex setup and I couldn't find any recent (and good) tutorial.

I came with this solution:

• Store every polygon as a Json into the database
• Apply a method to determine if some x,y belongs to any polygon

The problem with this solution is quite obvious: Queries may take too long to execute, considering I need to evaluate every polygon.

Finally: I'm looking for another solution for this problem, and I hope find something that doesn't have setup GeoDjango in my currently running server

Determine wheter some point is inside a polygon is not a problem (I found several examples); the problem is that retrieve every single polygon from DB and evaluate it does not scale. To solve that, I need to store the polygon in such way I can query it fast.

Answer 1

My approach.

1. Find centroid of polygon C++ code.
2. Store in database
3. Find longest distance from vertex to centroid (pythag)
4. Store as radius
5. Search database using centroid & radius as bounding box
6. If 1 or more result use point in polygon on resultant polygons

Answer 2

This solution enables you to store polygons outside of GeoDjango to dramatically speed up point in polygon queries.

In my case, I needed to find whether the coordinates of my numpy arrays where inside a polygon stored in my geodjango db (land/water masking). This required iterating over every coordinate combination in my arrays to test if it was inside or outside the polygon. As my arrays are large, this was taking a very long time using geodjango.

Using django's GEOSGeometry.contains my command looked something like this:

import numpy as np
from django.contrib.gis.geos import Point

my_polygon = model.geometry  # get model multipolygon field
lat_lon = zip(latitude.flat, longitude.flat)  # zip coordinate arrays to tuple
mask = np.array([my_polygon.contains(Point(l)) for l in lon_lat])  # boolean mask

This was taking 20 s or more on large arrays. I tried different ways of applying the geometry.contains() function over the array (e.g. np.vectorize) but this did not lead to any improvements. I then realised it was the Django contains lookup which was taking too long. I also converted the geometry to a shapely polygon and tested shapely's polygon.contains function - no difference or worse.

The solution lay in bypassing GeoDjango by using Polygon isInside method. First I created a function to create a Polygon object from my Geos Multipolygon.

from Polygon import Polygon

def multipolygon_to_polygon(multipolygon):
    """
    Convert a Geos Multipolygon to python Polygon
    """

    polygon = multipolygon[0] # select first polygon object
    nrings = polygon.num_interior_rings # get number of rings in polygon

    poly = Polygon()  
    poly.addContour(polygon[0].coords)  # Add first ring coordinates tuple

    # Add subsequent rings
    if nrings > 0:
        for i in range(nrings):
            print("Adding ring %s" % str(i+1))
            hole = True
            poly.addContour(polygon[i+1].coords, hole)

    return poly

Applying this to my problem

my_polygon = model.geometry  # get model multipolygon field
polygon = multipolygon_to_polygon(my_polygon)  # convert to python Polygon
lat_lon = zip(bands['latitude'].flat, bands['longitude'].flat)  # points tuple
land_mask = array([not polygon.isInside(ll[1], ll[0]) for ll in lat_lon])

This resulted in a roughly 20X improvement in speed. Hope this helps someone.

Python 2.7.