How to pick points inside grids?

Question

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()

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.

You want to pick random value inside this grid, e.g., red points within the boundaries of blue points? — Hamzah, Jun 17 '22 at 13:23
I think it is more dependent on the shape of the blue grid. What is the shape? — Hamzah, Jun 17 '22 at 15:24
@Phoenix Every four blue points are one satellite pixel. So, the shape depends on the satellite data which can be accessed from [here](https://data-portal.s5p-pal.com/browser/BXADeFDHwTQ3o8nrrhTDZSMwnfrWHe16d/2JM1fiAU7vaLzQZSRP3o4uRznddN4VH4NGpp4dfkKSnZV4hzrZifph/eX91ZTvd7bADysky6BArSuuZDRDyS1Va6ZSSSaUkw4PxEXiYyc3ZYZ1vNcwo/xdDvwjHCFDzMnS3V2LdCjo3DPbiMR3LiLiz79gzQibo1eZFqP9tRcKY61ufpJgW9/KgetR5YwayM5bxhmeo9EyBvzxERkFsxvu4RcgssWj7r13XWNEPaJ9VFyD2JsjNuhvNR?t=2). When you click one file link, you can see the shape on the right panel. — zxdawn, Jun 17 '22 at 15:53
[This](https://stackoverflow.com/a/43564754/2912349) is probably the best approach, but the convex hull approaches discussed in the other answers on that thread are fine, too. — Paul Brodersen, Jun 17 '22 at 15:59
@PaulBrodersen Thanks a lot. The "whether a point can be expressed as a convex combination of another set of points can be formulated as a linear programming problem" is interesting. Could you add your answer using the simple example above if that's possible? — zxdawn, Jun 17 '22 at 16:12

score 1 · Answer 1 · answered Jun 17 '22 at 16:33

 #!/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

How to pick points inside grids?

1 Answers1