[BUG]: Bad results returned from pairwise_linestring_intersection on large self-equal LineStrings.

[thomcom]

Version

23.08

On which installation method(s) does this occur?

Rapids-Compose

Describe the issue

Hiya! I found a new issue with pairwise_linestring_intersection today working on the Watershed Demo Notebook for Release 23.06.

When pairwise_linestring_intersection is called using the same linestring for the left and right hand sides, results are unpredictable and eventually fail as the linestring size increases. The API fails because the second element returned by pairwise_linestring_intersection eventually creates an invalid GeoSeries object with bad offsets.

For the reproducer, I created a LineString comprised of diagonal segments of length $sqrt(2)$ originating at the origin and rising by 1 in x and y. The LineString then connects the highest point along the diagonal with a point directly beneath it $(x, 0)$, and that returns to the origin making a closed LineString.

With this specific example, valid (though strange) results are returned up to a LineString of length 129. At 130 the API returns a broken GeoSeries for geoms. The results are strange because the first n of the segments get grouped into a single segment semi-randomly, say, ((0, 0), (32, 32)), and then the subsequent segments all are returned separately: ((32, 32), (33, 33)), ((33, 33), (34, 34)), etc.

Is this a valid error? There are two constraints that maybe make this invalid:

1. The LineStrings in the pairwise comparison are identical
2. The LineStrings are closed with the same start and end vertex.

I can see from the result returned here:

    geoms, look_back_ids = c_pairwise_linestring_intersection(
        linestrings1.lines.column(), linestrings2.lines.column()
    )

    (
        geometry_collection_offset,
        types_buffer,
        offset_buffer,
        points,
        segments,
    ) = geoms

That types_buffer when the length of the LineString is 130 all come back as points, that is, type = 0. When the length of the LineString is 129, they are returned correctly as type = 2. look_back_ids are also corrupt at length 130 and apparently valid at length 129 in this case.

Minimum reproducible example

    import cuspatial
    import cupy as cp
    from cuspatial.core.binops.intersection import pairwise_linestring_intersection

    size = 130.0
    xy = cp.concatenate([
        cp.arange(size - 2).repeat(2),
        cp.array([size - 3, 0, 0, 0])
    ])
    s1 = cuspatial.GeoSeries.from_linestrings_xy(
        xy,
        [0, len(xy)/2],
        [0, 1]
    )
    s2 = cuspatial.GeoSeries.from_linestrings_xy(
        xy,
        [0, len(xy)/2],
        [0, 1]
    )

    offset, geoms, ids = pairwise_linestring_intersection(s1, s2)
    print(offset)
    print(geoms._column._meta.input_types)
    print(geoms._column.lines._column)
    print(geoms.to_geopandas())

Relevant log output

>>>>>>>>>>>>>>>>>>>>>> captured stdout >>>>>>>>>>>>>>>>>>>>>>
<cudf.core.column.numerical.NumericalColumn object at 0x7f90b195e4c0>
[
  0,
  354
]
dtype: int32
0     0
1     0
2     0
3     0
4     0
     ..
93    0
94    0
95    0
96    0
97    0
Length: 98, dtype: int8
<cudf.core.column.lists.ListColumn object at 0x7f90b195e5c0>
[
  [
    [
      [
        0,
        0
      ],
      [
        32,
        32
      ]
    ]
  ],
  [
    [
      [
        32,
        32
      ],
      [
        33,
        33
      ]
    ]
  ],
  ...
  [
    [
      [
        126,
        126
      ],
      [
        127,
        127
      ]
    ]
  ],
  [
    [
      [
        127,
        0
      ],
      [
        127,
        127
      ]
    ]
  ]
]
dtype: list
>>>>>>>>>>>>>>>>>>>>>>>>> traceback >>>>>>>>>>>>>>>>>>>>>>>>>

    def test_same_linestring():
        size = 130.0
        xy = cp.concatenate([
            cp.arange(size - 2).repeat(2),
            cp.array([size - 3, 0, 0, 0])
        ])
        s1 = cuspatial.GeoSeries.from_linestrings_xy(
            xy,
            [0, len(xy)/2],
            [0, 1]
        )
        s2 = cuspatial.GeoSeries.from_linestrings_xy(
            xy,
            [0, len(xy)/2],
            [0, 1]
        )
    
        offset, geoms, ids = pairwise_linestring_intersection(s1, s2)
        print(offset)
        print(geoms._column._meta.input_types)
        print(geoms._column.lines._column)
>       print(geoms.to_geopandas())

tests/basicpreds/test_intersections.py:261: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
core/geoseries.py:474: in to_geopandas
    final_union_slice.to_shapely(),
core/geoseries.py:540: in to_shapely
    shapely_serialization_fn(union[result_index].as_py())
pyarrow/array.pxi:1295: in pyarrow.lib.Array.__getitem__
    ???
pyarrow/array.pxi:1298: in pyarrow.lib.Array.getitem
    ???
pyarrow/error.pxi:144: in pyarrow.lib.pyarrow_internal_check_status
    ???
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

>   ???
E   pyarrow.lib.ArrowIndexError: index with value of 0 is out-of-bounds for array of length 0

pyarrow/error.pxi:127: ArrowIndexError
>>>>>>>>>>>>>>>>>>>>>>> entering PDB >>>>>>>>>>>>>>>>>>>>>>>>

>>>>>>>>> PDB post_mortem (IO-capturing turned off) >>>>>>>>>
> /home/coder/cuspatial/python/cuspatial/cuspatial/pyarrow/error.pxi(127)pyarrow.lib.check_status()

Environment details

No response

Other/Misc.

No response

[isVoid]

The LineStrings in the pairwise comparison are identical
The LineStrings are closed with the same start and end vertex.

Definitely sounds like a valid input. This pattern that the bug only emerge with large input makes me think if this is the same error as last time - misusing the thrust API where input and output must not overlap.

[isVoid]

Confirmed reproducible in C++.