Python GeoPandas - if distance between each point and its neighbor(s) is less than 20m, delete all but the most recent point

Question

I have a GeoDataframe that contains thousands of points with a corresponding timestamp (milliseconds), which is an amalgamation of many gps trajectories.

I must check the distance between each point and its neighbors. If their geometries are the same or nearby (e.g. within 20 metres), delete all but the most recent point. This will remove all 'superceded' points where newer data is available.

In the example GeoDataframe below, points #2, #3 and #4 are definitely within 20m of one another (same geometry). But only #4 should remain in the dataframe because it has the most recent timestamp.

Example GeoDataframe:

  id    captured_at     geometry
    0   1632410217000   POINT (-525919.001 7186220.048)
    1   1632410219000   POINT (-525950.054 7186212.882)
    2   1632410221000   POINT (-526009.173 7186211.688)
    3   1632410223000   POINT (-526009.173 7186211.688)
    4   1632410225000   POINT (-526009.173 7186211.688)

Full replicable example:

import geopandas as gpd
import pandas as pd

df = pd.DataFrame(
    {'captured_at': [1632410217000, 1632410219000, 1632410221000, 1632410223000, 1632410225000],
      'geometry': ['POINT (-525919.001 7186220.048)', 'POINT (-525950.054 7186212.882)',
                      'POINT (-526009.173 7186211.688)', 'POINT (-526009.173 7186211.688)',
                      'POINT (-526009.173 7186211.688)']})
df['geometry'] = gpd.GeoSeries.from_wkt(df['geometry'])
gdf = gpd.GeoDataFrame(df, geometry='geometry')
gdf

How might I go about this problem?

Answer 1

Pretty sure this is what you're looking for. I used clustering from the sklearn package since this is essentially the same problem as this question: Split polygons in a shapefile based on distance

import pandas as pd
import geopandas as gpd
import shapely

from sklearn.cluster import AgglomerativeClustering

def cluster_shapes_by_distance(geodf, distance, check_crs=False):
    """
    Make groups for all shapes within a defined distance. For a shape to be 
    excluded from a group, it must be greater than the defined distance
    from *all* shapes in the group.
    Distances are calculated using shape centroids.

    Parameters
    ----------
    geodf : data.frame
        A geopandas data.frame of polygons. Should be a projected CRS where the
        unit is in meters. 
    distance : float
        Maximum distance between elements. In meters.
    check_crs : bool
        Confirm that the CRS of the geopandas dataframe is projected. This 
        function should not be run with lat/lon coordinates. 

    Returns
    -------
    np.array
        Array of numeric labels assigned to each row in geodf.

    """
    if check_crs:
        assert geodf.crs.is_projected, 'geodf should be a projected crs with meters as the unit'
        
    centers = [p.centroid for p in geodf.geometry]
    centers_xy = [[c.x, c.y] for c in centers]
    
    cluster = AgglomerativeClustering(n_clusters=None, 
                                      linkage='single',
                                      affinity='euclidean',
                                      distance_threshold=distance)
    cluster.fit(centers_xy)
    
    return cluster.labels_

#---------------------------

geoms =  ['POINT (-525919.001 7186220.048)', 'POINT (-525950.054 7186212.882)',
          'POINT (-526009.173 7186211.688)', 'POINT (-526009.173 7186211.688)',
          'POINT (-526009.173 7186211.688)']
geoms = [shapely.wkt.loads(s) for s in geoms]

df = gpd.GeoDataFrame(
    {'captured_at': [1632410217000, 1632410219000, 1632410221000, 1632410223000, 1632410225000]},
    geometry = gpd.GeoSeries(geoms),
    )

df['group'] = cluster_shapes_by_distance(df, distance=20) # 20m

# Within each group keep the most recent.
df = df.groupby('group').apply(lambda x: x.iloc[x.captured_at.argmax()])

Answer 2

I had a similar situation, where I wanted to fuse a bunch of location if they were close together. Essentially clustering points. In my case (railroad crossings) the points to be fused were very close together and very far away from other clusters...and I had no idea how many clusters the results should be. I thought about using something like hierarchical clustering, but I decided to use a network-based approach.

Here is the algorithm I used

###=== Input a GeoDataFrame and return a GeoDataFrame with nearby (distance < X meters) elements groups together.
def clusterLocations(gdf, distThreshold=10):
    gdf = gdf.to_crs(distCalcCRS) #- convert to the distance-preserving CRS of your choice (obviously skip if already in an appropriate CRS)
    G = nx.Graph()
    G.add_nodes_from(list(gdf.index))
    nx.set_node_attributes(G, gdf.to_dict('index'))
    nearbyPairs = [(u, v) for i,u in enumerate(list(G.nodes)) for v in list(G.nodes)[i + 1:] if G.nodes[u]['geometry'].distance(G.nodes[v]['geometry']) < distThreshold ]
    G.add_edges_from(nearbyPairs) #- creates edges only when the pairwise distance is less than the threshold
    comps = [[idx,i] for i,c in enumerate(sorted(nx.connected_components(G), key=len, reverse=True)) for idx in c]  #- a list of pairs holding the node id and its component number
    for comp in comps:
        gdf.at[comp[0],'comp'] = comp[1] #- assign comp num to each row
    
    #- Choose what information you want to keep from each cluster, OP wants to keep the one with the most recent time, but I got modal values and centroid location
    gdf = gdf.groupby('comp').agg({'name':lambda x: max(list(x), key=list(x).count), 'captured_at':lambda x: max(list(x)), 'geometry':lambda x: MultiPoint(list(x)).centroid})
    gdf.reset_index(inplace=True, drop=True)
    gdf = gpd.GeoDataFrame(gdf, geometry='geometry', crs=distCalcCRS)
    gdf = gdf.to_crs(standardCRS) #- change back to your original CRS
    ##-- redo the lat and lon from the new geometry, if desired
    gdf[['lon','lat']] = gdf.apply(lambda row: [row['geometry'].x, row['geometry'].y], axis=1, result_type='expand')
    return gdf

This is not the most efficient algorithm because it evaluates the distance of every pair of points in a list comprehension, but it's not the worst either.

Probably it could be sped up by using an STRtree to reduce the number of distance comparisons.