Basically I have DataFrame
with a huge amount of boxes which are defined with xmin
ymin
xmax
ymax
tuples.
JavaScript
x
8
1
xmin ymin xmax ymax
2
0 66 88 130 151
3
1 143 390 236 468
4
2 77 331 143 423
5
3 289 112 337 157
6
4 343 282 405 352
7
..
8
My task is to remove all nested boxes. (I.e. any box which is within
another box has to be removed)
My current method:
- construct GeoDataFrame with box geometry
- sort by box size (descending)
- iteratively find smaller boxes within a larger box.
Sandbox: https://www.kaggle.com/code/easzil/remove-nested-bbox/
JavaScript
1
29
29
1
def remove_nested_bbox(df):
2
# make an extra unique 'id'
3
df['__id'] = range(0, len(df))
4
# create geometry
5
df['__geometry'] = df.apply(lambda x: shapely.geometry.box(x.xmin, x.ymin, x.xmax, x.ymax), axis=1)
6
gdf = gpd.GeoDataFrame(df, geometry='__geometry')
7
# sort by area
8
gdf['__area'] = gdf.__geometry.area
9
gdf.sort_values('__area', ascending=False, inplace=True)
10
11
nested_id = set()
12
for iloc in range(len(gdf)):
13
# skip aready identifed one
14
if gdf.iloc[iloc]['__id'] in nested_id:
15
continue
16
bbox = gdf.iloc[iloc] # current target larger bbox
17
tests = gdf.iloc[iloc+1:] # all bboxes smaller than the urrent target
18
tests = tests[~tests['__id'].isin(nested_id)] # skip aready identifed one
19
nested = tests[tests['__geometry'].within(bbox['__geometry'])]
20
nested_id.update(list(nested['__id']))
21
22
df = df[~df['__id'].isin(nested_id)]
23
24
del df['__id']
25
del df['__geometry']
26
del df['__area']
27
28
return df
29
Is there any better way to optimize the task to make it faster? The current method is pretty slow to handle large dataset.
I would also consider other methods such as implementing in C or CUDA.
Advertisement
Answer
- your sample data is not large and has no instances of boxes within boxes. Have generated some randomly
- have used approach of using
loc
checking dimensions are bigger - not sure if this is faster than your approach, timing details
JavaScript
1
5
1
%timeit gdf["within"] = gdf.apply(within, args=(gdf,), axis=1)
2
print(f"""number of polygons: {len(gdf)}
3
number kept: {len(gdf.loc[lambda d: ~d["within"]])}
4
""")
5
JavaScript
1
4
1
2.37 s ± 118 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
2
number of polygons: 2503
3
number kept: 241
4
visuals
full code
JavaScript
1
48
48
1
import pandas as pd
2
import numpy as np
3
import geopandas as gpd
4
import io
5
import shapely
6
7
df = pd.read_csv(
8
io.StringIO(
9
""" xmin ymin xmax ymax
10
0 66 88 130 151
11
1 143 390 236 468
12
2 77 331 143 423
13
3 289 112 337 157
14
4 343 282 405 352"""
15
),
16
sep="s+",
17
)
18
19
# randomly generate some boxes, check they are valid
20
df = pd.DataFrame(
21
np.random.randint(1, 200, [10000, 4]), columns=["xmin", "ymin", "xmax", "ymax"]
22
).loc[lambda d: (d["xmax"] > d["xmin"]) & (d["ymax"] > d["ymin"])]
23
24
gdf = gpd.GeoDataFrame(
25
df, geometry=df.apply(lambda r: shapely.geometry.box(*r), axis=1)
26
)
27
28
gdf.plot(edgecolor="black", alpha=0.6)
29
30
# somewhat optimised by limiting polygons that are considered by looking at dimensions
31
def within(r, gdf):
32
for g in gdf.loc[
33
~(gdf.index == r.name)
34
& gdf["xmin"].lt(r["xmin"])
35
& gdf["ymin"].lt(r["ymin"])
36
& gdf["xmax"].gt(r["xmax"])
37
& gdf["ymax"].gt(r["ymax"]),
38
"geometry",
39
]:
40
if r["geometry"].within(g):
41
return True
42
return False
43
44
45
gdf["within"] = gdf.apply(within, args=(gdf, ), axis=1)
46
47
gdf.loc[lambda d: ~d["within"]].plot(edgecolor="black", alpha=0.6)
48
approach 2
- using sample data you provided on kaggle
- this returns in about half the time (5s) compared to previous version
- concept is similar, a box is within another box if xmin & ymin are greater than that of another box and max & ymax are less
JavaScript
1
15
15
1
import functools
2
3
df = pd.read_csv("https://storage.googleapis.com/kagglesdsdata/datasets/2015126/3336994/sample.csv?X-Goog-Algorithm=GOOG4-RSA-SHA256&X-Goog-Credential=gcp-kaggle-com%40kaggle-161607.iam.gserviceaccount.com%2F20220322%2Fauto%2Fstorage%2Fgoog4_request&X-Goog-Date=20220322T093633Z&X-Goog-Expires=259199&X-Goog-SignedHeaders=host&X-Goog-Signature=3cc7824afe45313fe152858a6b8d79f93b0d90237ad82737fcf28949b9314df4be2f247821934a371d09cff4b463d69fc2422d8d7f746d6fccf014605b2e0f2cba54c23fba012c2531c4cd714436545bd83db0e880072fa049b116106ba4e296c259c32bc19267a15b9b9af78494bb6859cb53ffe4388c3b8c375a330e09008bb1d9c839f8ab4c14a8f01c38179ba31dc9f4ea9fa11f5ecc7e6ba87757edbe48577d60988349b948ceb70e885be5d6ebc36abe438a5275fa683ee4e318e21661ea032af7d8e2f488020288a1a2ff15af8aa153bb8ac33a0b827dd53c928ddf3abb024f2972ba6ef21bc9a0034e504706a2b3fc78be9ea3bb9190437d98a8ab35")
4
5
def within_np(df):
6
d = {}
7
for c in df.columns[0:4]:
8
a = np.tile(df[c].values.T ,(len(df),1))
9
d[c] = a.T > a if c[1:] == "min" else a.T < a
10
11
aa = functools.reduce(np.logical_and, (aa for aa in d.values()))
12
return aa.sum(axis=1)>0
13
14
df.loc[~within_np(df)]
15