When saving points with latitude and longitude in a pandas data frame, it’s pretty easy and fast to choose all points within a rectangle block between a pair of latitude and a pair of longitude, but pandas data frame cannot choose points within a irregular polygon.
GeoPandas can help with this, believe me, GeoPandas is just too slow. Using shapely’s built-in function such as object.within() or ojbect.contains() over all points is not better than using GeoPandas. Here we introduce 2 ways to make a fast selection through a mass amount of points.
Method 1: Katana
This article inspired me to divide an irregular Polygon into several rectangles, some of them are all within this polygon, and some of them covers the edge of the polygon.
For rectangles within the polygon, points within these rectangles are sure within the polygon, and they can be selected in the fast way we introduced in paragraph 1.
For rectangles covers the edge of the polygon, points within these rectangles are candidates of being within the polygon, we can then iterate shapely’s built-in function such as object.within() over these points.
Method 2: KDTree
KDTree is an amazing fast spacial index which can find nearest points in no second. My another article introduced a way to do reverse geocode using KDTree, which can be used to classify points into inside or outside of the polygon.