pythonperformancegispolygongreat-circle

Fast python GIS library that supports Great Circle Distance and polygon

I was looking for a geographical library for python. I need to be able to do the following:

  1. Get the distance between 2 points (in meters) using Great-circle distance (not liner distance calculation)
  2. Check if a point is inside a polygon
  3. Perform 1 and 2 couple of thousands times per seconds

At start I've looked at this post: Python module for storing and querying geographical coordinates and started to use geopy. I've encountered 2 problems:

  1. Geopy doesn't support polygons
  2. High CPU usage of geoPy (it takes about 140ms of CPU to calculate distance between a point and relative 5000 points)

I've continued looking and found Best Python GIS library? and https://gis.stackexchange.com/ . It looked promising as geos is using complied C code which should be faster and shapely supports polygons. The problem is that geos/OGR performs linear distance calculations instead of sphere. This eliminates all other geos based modules (like GEODjango and shapely). Am I missing something here? I don't think that I'm the first person who is using python to perform GIS calculations and wants to get accurate results.

Solution

  • UPDATE

    Moving on now to finishing out the other 576 functions in that library not including the two polygon functions that are finished, the three sphere distance algorithms that are done, and two new ones, an angle_box_2d and angle_contains_ray_2d. Also, I switched to the C version so that externs are not needed, simplifies the work. Put the old C++ version in directory old_c++, so its still there.

    Tested performance, it is identical as listed at the bottom of the answer.

    UPDATE 2

    So just a quick update, I haven't finished the whole library yet (I'm only about 15% of the way through), but I've added these untested functions, in case you need them right away, on github, to add to the old point in polygon and sphere distance algorithms.

    angle_box_2d
angle_contains_ray_2d
angle_deg_2d
angle_half_2d # MLM: double *
angle_rad_2d
angle_rad_3d
angle_rad_nd
angle_turn_2d
anglei_deg_2d
anglei_rad_2d
annulus_area_2d
annulus_sector_area_2d
annulus_sector_centroid_2d # MLM: double *
ball_unit_sample_2d # MLM: double *
ball_unit_sample_3d # MLM: double *
ball_unit_sample_nd # MLM; double *
basis_map_3d #double *
box_01_contains_point_2d
box_01_contains_point_nd
box_contains_point_2d
box_contains_point_nd
box_ray_int_2d
box_segment_clip_2d
circle_arc_point_near_2d
circle_area_2d
circle_dia2imp_2d
circle_exp_contains_point_2d
circle_exp2imp_2d
circle_imp_contains_point_2d
circle_imp_line_par_int_2d
circle_imp_point_dist_2d
circle_imp_point_dist_signed_2d
circle_imp_point_near_2d
circle_imp_points_2d # MlM: double *
circle_imp_points_3d # MLM: double *
circle_imp_points_arc_2d
circle_imp_print_2d
circle_imp_print_3d
circle_imp2exp_2d
circle_llr2imp_2d # MLM: double *
circle_lune_area_2d
circle_lune_centroid_2d # MLM; double *
circle_pppr2imp_3d

    The ones that I've commented above probably won't work, the others might, but again - polygon & sphere distances definitely do. And you can specify meters, kilometers, miles, nautical miles, it doesn't really matter on the spherical distance ones, the output is in the same units as the input - the algorithms are agnnostic to the units.

    I put this together this morning so it currently only provides the point in polygon, point in convex polygon, and three different types of spherical distance algorithms, but at least those ones that you requested are there for you to use now. I don't know if there is a name conflict with any other python library out there, I only get peripherally involved with python these days, so if there's a better name for it I'm open to suggestions.

    On github: https://github.com/hoonto/pygeometry

    It is just a python bridge to the functions described and implemented here:

    http://people.sc.fsu.edu/~jburkardt/cpp_src/geometry/geometry.html

    The GEOMETRY library is pretty good actually, so I think it'll be useful to bridge all of those functions for python, which I'll do probably tonight.

    Edit: a couple other things

    1. Because the math functions are actually compiled C++, you do of course need to make sure that the shared library is in the path. You can modify the geometry.py to point at wherever you want to put that shared library though.
    2. Only compiled for linux, the .o and .so were compiled on x86_64 fedora.
    3. The spherical distance algorithms expect radians so you need to convert decimal lat/lon degrees for example to radians, as shown in geometry.py.

    If you do need this on Windows let me know, it should only take a couple minutes to get it worked out in Visual Studio. But unless someone asks I'll probably just leave it alone for now.

    Hope this helps!

    Rgds....Hoonto/Matt

    (new commit: SHA: 4fa2dbbe849c09252c7bd931edfe8db478de28e6 - fixed some things, like radian conversions and also the return types for the py functions. Also added some basic performance tests to make sure the library performs appropriately.)

    Test Results In each iteration, one call to sphere_distance1 and one call polygon_contains_point_2d so 2 calls to the library total.