pythonpandasnumpyscipypyproj

How to pick points inside grids?

I have one grid that consists of two boundary arrays: lon_bnds and lat_bnds. The goal is to pick the points inside the grid.

Here's an example:

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd


lon_bnds = np.array([[-77.9645  , -77.56074 , -77.162025, -76.76827 , -76.37937 ],
                    [-77.88815 , -77.48613 , -77.08915 , -76.69711 , -76.30993 ],
                    [-77.811676, -77.41139 , -77.01614 , -76.62582 , -76.24034 ],
                    [-77.73638 , -77.337814, -76.944275, -76.55565 , -76.17186 ],
                    [-77.66197 , -77.265114, -76.87326 , -76.48632 , -76.1042  ]])

lat_bnds = np.array([[-77.34674 , -77.35804 , -77.36858 , -77.378395, -77.38752 ],
                    [-77.28847 , -77.299614, -77.31001 , -77.31969 , -77.328674],
                    [-77.23022 , -77.24122 , -77.25147 , -77.26101 , -77.26986 ],
                    [-77.17193 , -77.182785, -77.192894, -77.20229 , -77.211006],
                    [-77.11363 , -77.12434 , -77.13431 , -77.14357 , -77.15215 ]])

plt.scatter(lon_bnds, lat_bnds, label='corner')

d = {'longitude': [-79, -77.2, -77, -75.5], 'latitude': [-77.4, -77.2, -77.3, -77.3]}
df_points = pd.DataFrame(data=d)
plt.scatter(df_points['longitude'], df_points['latitude'], c='r', label='points')

plt.legend()

example

The results should be the DataFrame which have the two inside points.

I also find this useful question but they used the kdTree to search points around instead of using the exact boundary arrays like my example.

Solution 
  •  #!/usr/bin/env python
 """
 Test if query points are inside the convex hull of another set of points.
 """
 
 import numpy as np
 import pandas as pd
 
 from scipy.optimize import linprog
 
 def in_hull(points, x):
     # https://stackoverflow.com/a/43564754/2912349
     n_points = len(points)
     n_dim = len(x)
     c = np.zeros(n_points)
     A = np.r_[points.T,np.ones((1,n_points))]
     b = np.r_[x, np.ones(1)]
     lp = linprog(c, A_eq=A, b_eq=b)
     return lp.success
 
 
 if __name__ == '__main__':
     lon_bnds = np.array([[-77.9645  , -77.56074 , -77.162025, -76.76827 , -76.37937 ],
                         [-77.88815 , -77.48613 , -77.08915 , -76.69711 , -76.30993 ],
                         [-77.811676, -77.41139 , -77.01614 , -76.62582 , -76.24034 ],
                         [-77.73638 , -77.337814, -76.944275, -76.55565 , -76.17186 ],
                         [-77.66197 , -77.265114, -76.87326 , -76.48632 , -76.1042  ]])
 
     lat_bnds = np.array([[-77.34674 , -77.35804 , -77.36858 , -77.378395, -77.38752 ],
                         [-77.28847 , -77.299614, -77.31001 , -77.31969 , -77.328674],
                         [-77.23022 , -77.24122 , -77.25147 , -77.26101 , -77.26986 ],
                         [-77.17193 , -77.182785, -77.192894, -77.20229 , -77.211006],
                         [-77.11363 , -77.12434 , -77.13431 , -77.14357 , -77.15215 ]])
 
     points = np.c_[lon_bnds.ravel(), lat_bnds.ravel()]
 
     d = {'longitude': [-79, -77.2, -77, -75.5], 'latitude': [-77.4, -77.2, -77.3, -77.3]}
     df = pd.DataFrame(d)
     df['in hull'] = df[['longitude', 'latitude']].apply(lambda x : in_hull(points, x.values), axis=1)
     print(df)
 
     #    longitude  latitude  in hull
     # 0      -79.0     -77.4    False
     # 1      -77.2     -77.2     True
     # 2      -77.0     -77.3     True
     # 3      -75.5     -77.3    False