Repository: mie-lab/trackintel (python)

Issue:
ENH: _split_overlap() function does not deal with miliseconds
The splitting of records implemented in the `_split_overlap()` function only replaces the time larger than 1 second, causing the newly created records not to start exactly at 12 midnight. The codes [here](https://github.com/mie-lab/trackintel/blob/1ff2323c868cfb82c0d0497cf57281c821e044d1/trackintel/analysis/tracking_quality.py#L253) and [here](https://github.com/mie-lab/trackintel/blob/1ff2323c868cfb82c0d0497cf57281c821e044d1/trackintel/analysis/tracking_quality.py#L257) need to be changed.

![image](https://user-images.githubusercontent.com/17105123/151533803-8f9f3079-04eb-4356-a7ef-c7455220d2ef.png)


Pull request description:
ENH: `_split_overlap` splits now exactly on border
This PR does quite a lot because some changes where necessary to generalize this method.
- use `dt.ceil()` and `dt.floor()` to handle the splits more generally.
- fixed multiple bugs that come from using `.date`/`.hour` (if on same date on different months it wouldn't be recongized)
- wrote test for corner cases in `_split_overlap`
- wrote test for helpfunction `_get_split_index`.
- some cleanup and speedup here and there

closes #369 

Patch:
diff --git a/trackintel/analysis/tracking_quality.py b/trackintel/analysis/tracking_quality.py
index 254b9c6..20e3e3a 100644
--- a/trackintel/analysis/tracking_quality.py
+++ b/trackintel/analysis/tracking_quality.py
@@ -1,8 +1,8 @@
-import datetime
+import warnings
 
-import pandas as pd
+import geopandas as gpd
 import numpy as np
-import warnings
+import pandas as pd
 
 
 def temporal_tracking_quality(source, granularity="all", max_iter=60):
@@ -238,35 +238,31 @@ def _split_overlaps(source, granularity="day", max_iter=60):
     GeoDataFrame (as trackintel datamodels)
         The GeoDataFrame object after the splitting
     """
-    df = source.copy()
-    change_flag = __get_split_index(df, granularity=granularity)
+    if granularity == "hour":
+        # every split over hour splits also over day
+        # this way to split of an entry over a month takes 30+24 iterations instead of 30*24.
+        df = _split_overlaps(source, granularity="day", max_iter=max_iter)
+    else:
+        df = source.copy()
 
+    change_flag = _get_split_index(df, granularity=granularity)
     iter_count = 0
 
+    freq = "D" if granularity == "day" else "H"
     # Iteratively split one day/hour from multi day/hour entries until no entry spans over multiple days/hours
     while change_flag.sum() > 0:
-
         # calculate new finished_at timestamp (00:00 midnight)
-        finished_at_temp = df.loc[change_flag, "finished_at"].copy()
-        if granularity == "day":
-            df.loc[change_flag, "finished_at"] = df.loc[change_flag, "started_at"].apply(
-                lambda x: x.replace(hour=23, minute=59, second=59) + datetime.timedelta(seconds=1)
-            )
-        elif granularity == "hour":
-            df.loc[change_flag, "finished_at"] = df.loc[change_flag, "started_at"].apply(
-                lambda x: x.replace(minute=59, second=59) + datetime.timedelta(seconds=1)
-            )
+        new_df = df.loc[change_flag].copy()
+        df.loc[change_flag, "finished_at"] = (df.loc[change_flag, "started_at"] + pd.Timestamp.resolution).dt.ceil(freq)
 
         # create new entries with remaining timestamp
-        new_df = df.loc[change_flag].copy()
         new_df.loc[change_flag, "started_at"] = df.loc[change_flag, "finished_at"]
-        new_df.loc[change_flag, "finished_at"] = finished_at_temp
 
         df = pd.concat((df, new_df), ignore_index=True, sort=True)
 
-        change_flag = __get_split_index(df, granularity=granularity)
+        change_flag = _get_split_index(df, granularity=granularity)
         iter_count += 1
-        if iter_count > max_iter:
+        if iter_count >= max_iter:
             warnings.warn(
                 f"Maximum iteration {max_iter} reached when splitting the input dataframe by {granularity}. "
                 "Consider checking the timeframe of the input or parsing a higher 'max_iter' parameter."
@@ -275,11 +271,10 @@ def _split_overlaps(source, granularity="day", max_iter=60):
 
     if "duration" in df.columns:
         df["duration"] = df["finished_at"] - df["started_at"]
-
     return df
 
 
-def __get_split_index(df, granularity="day"):
+def _get_split_index(df, granularity="day"):
     """
     Get the index that needs to be splitted.
 
@@ -297,10 +292,8 @@ def __get_split_index(df, granularity="day"):
     change_flag: pd.Series
         Boolean index indicating which records needs to be splitted
     """
-    change_flag = df["started_at"].dt.date != (df["finished_at"] - pd.to_timedelta("1s")).dt.date
-    if granularity == "hour":
-        hour_flag = df["started_at"].dt.hour != (df["finished_at"] - pd.to_timedelta("1s")).dt.hour
-        # union of day and hour change flag
-        change_flag = change_flag | hour_flag
-
-    return change_flag
+    freq = "D" if granularity == "day" else "H"
+    cond1 = df["started_at"].dt.floor(freq) != (df["finished_at"] - pd.Timedelta.resolution).dt.floor(freq)
+    # catch corner case where both on same border and subtracting would lead to error
+    cond2 = df["started_at"] != df["finished_at"]
+    return cond1 & cond2


Test patch:
diff --git a/tests/analysis/test_tracking_quality.py b/tests/analysis/test_tracking_quality.py
index c22f42b..4511ec4 100644
--- a/tests/analysis/test_tracking_quality.py
+++ b/tests/analysis/test_tracking_quality.py
@@ -7,6 +7,7 @@ import geopandas as gpd
 from shapely.geometry import Point
 
 import trackintel as ti
+from trackintel.analysis.tracking_quality import _get_split_index
 
 
 @pytest.fixture
@@ -279,7 +280,7 @@ class TestSplit_overlaps:
         splitted = ti.analysis.tracking_quality._split_overlaps(sp_tpls, granularity="day")
 
         # no record spans several days after the split
-        multi_day_records = (splitted["finished_at"] - pd.to_timedelta("1s")).dt.day - splitted["started_at"].dt.day
+        multi_day_records = (splitted["finished_at"] - pd.Timestamp.resolution).dt.day - splitted["started_at"].dt.day
         assert (multi_day_records == 0).all()
 
     def test_split_overlaps_hours(self, testdata_sp_tpls_geolife_long):
@@ -295,23 +296,22 @@ class TestSplit_overlaps:
         splitted = ti.analysis.tracking_quality._split_overlaps(sp_tpls, granularity="hour")
 
         # no record spans several hours after the split
-        hour_diff = (splitted["finished_at"] - pd.to_timedelta("1s")).dt.hour - splitted["started_at"].dt.hour
+        hour_diff = (splitted["finished_at"] - pd.Timestamp.resolution).dt.hour - splitted["started_at"].dt.hour
         assert (hour_diff == 0).all()
 
     def test_split_overlaps_hours_case2(self, testdata_sp_tpls_geolife_long):
         """Test if _split_overlaps() function can split record that have the same hour but different days."""
-        sp_tpls = testdata_sp_tpls_geolife_long
-
         # get the first two records
-        head2 = sp_tpls.head(2).copy()
+        head2 = testdata_sp_tpls_geolife_long.head(2)
+
         # construct the finished_at exactly one day after started_at
-        head2["finished_at"] = head2.apply(lambda x: x["started_at"].replace(day=x["started_at"].day + 1), axis=1)
+        head2["finished_at"] = head2["started_at"] + pd.Timedelta("1d")
 
         # the records have the same hour
-        hour_diff = (head2["finished_at"] - pd.to_timedelta("1s")).dt.hour - head2["started_at"].dt.hour
+        hour_diff = (head2["finished_at"] - pd.Timestamp.resolution).dt.hour - head2["started_at"].dt.hour
         assert (hour_diff == 0).all()
         # but have different days
-        day_diff = (head2["finished_at"] - pd.to_timedelta("1s")).dt.day - head2["started_at"].dt.day
+        day_diff = (head2["finished_at"] - pd.Timestamp.resolution).dt.day - head2["started_at"].dt.day
         assert (day_diff > 0).all()
 
         # split the records according to hour
@@ -319,7 +319,7 @@ class TestSplit_overlaps:
         splitted = ti.analysis.tracking_quality._split_overlaps(head2, granularity="hour")
 
         # no record has different days after the split
-        day_diff = (splitted["finished_at"] - pd.to_timedelta("1s")).dt.day - splitted["started_at"].dt.day
+        day_diff = (splitted["finished_at"] - pd.Timestamp.resolution).dt.day - splitted["started_at"].dt.day
         assert (day_diff == 0).all()
 
     def test_split_overlaps_duration(self, testdata_sp_tpls_geolife_long):
@@ -354,3 +354,46 @@ class TestSplit_overlaps:
 
         with pytest.warns(UserWarning):
             ti.analysis.tracking_quality._split_overlaps(sp, granularity="day")
+
+    def test_exact_midnight_split(self):
+        """Test if split finishes and starts on midnight on the ns (pandas resolution)."""
+        midnight = pd.Timestamp("2022-03-18 00:00:00", tz="utc")
+        start = midnight - pd.Timestamp.resolution
+        end = midnight + pd.Timestamp.resolution
+        data = [
+            {"user_id": 0, "started_at": start, "finished_at": end, "geom": Point(0.0, 0.0)},
+            {"user_id": 1, "started_at": start, "finished_at": midnight, "geom": Point(0.0, 0.0)},
+            {"user_id": 2, "started_at": midnight, "finished_at": end, "geom": Point(0.0, 0.0)},
+            {"user_id": 3, "started_at": midnight, "finished_at": midnight, "geom": Point(0.0, 0.0)},
+        ]
+        sp = gpd.GeoDataFrame(data=data, geometry="geom", crs="EPSG:4326")
+        sp_res = ti.analysis.tracking_quality._split_overlaps(sp, granularity="hour")
+        sp_res.sort_values(by="user_id", inplace=True, kind="stable")
+        assert (sp_res["started_at"] == [start, midnight, start, midnight, midnight]).all()
+        assert (sp_res["finished_at"] == [midnight, end, midnight, end, midnight]).all()
+
+
+class TestGet_split_index:
+    """Test if __get_split_index splits correctly"""
+
+    def test_midnight_ns(self):
+        """Test datetimes 1 ns around midnight."""
+        # 9 possibilities, 3 per starts before, on and after an hour point
+        #     h1          h2
+        # --  | -- ... -- |  --
+        # s1 s2 s3 ... e1 e2 e3
+        midnight = pd.Timestamp("2022-03-18 00:00:00", tz="utc")
+        start1 = midnight - pd.Timestamp.resolution
+        start2 = midnight
+        start3 = midnight + pd.Timestamp.resolution
+        starts = [start1, start2, start3]
+        ends = [s + pd.Timedelta("1h") for s in starts]
+
+        data = [
+            {"started_at": start, "finished_at": end, "res": (start == starts[0]) or (end == ends[2])}
+            for start in starts
+            for end in ends
+        ]
+        df = pd.DataFrame(data=data)
+        calculated_result = _get_split_index(df, "hour")
+        assert (calculated_result == df["res"]).all()