Invalid Intersection result after upgrading to GeoSwift 7.0.0+

[india2sarthak]

I'm using GeoSwift for performing geospatial operations in a mobile app. Prior to v7.0.0, the intersection operation used to work as expected, however, after upgrading to v7.0.0 from 6.2.0, the same method returned a different result. Please find the attached geoJson files in the zip file for reproducing the error.

Parent: polygon.json (polygon)
LineString: multiLinestring.json (multiLineString)

And here is the code I am using for the same

  do {
             for lineString in multiLineString.lineStrings {
                if try lineString.intersects(polygon) {
                    let intersectingGeometry = try lineString.intersection(with: polygon)
                    // Handle Intersection here
                }
            } 
   } catch {
            DDLogError("Unable to get the intersection of line string with the geometry. \(error.localizedDescription)")
            return nil
        }

Essentially I am getting a different result when I run the intersection operation on GeoSwift v6.2.0 (Expected) and GeoSwift v7.1.0 (Possibly Incorrect)

Is there something else I need to do to find an intersection in the newer versions of GeoSwift?
Thanks a lot for helping :)

Here is the environment I am using
Xcode : 12.2
GeoSwift: 7.1.0
GEOS: 5.1.0

Apologies for not being able to find a simpler example to illustrate the problem 😅

// Zip containing the geojson files
TestData.zip

[macdrevx]

Thanks for reporting this. I'll take a look in the next few days.

[macdrevx]

The only differences I'm seeing in the output are with the results of the line strings at indexes 22, 24, and 26. GEOSwift v6 is on the left, v7 on the right. It seems like the difference is in the order in which the line strings are included in the multilinestrings.

This must be a difference between GEOS 3.7.1 (packaged for SPM as GEOSwift/geos 4.1.0) and GEOS 3.9.0 (packaged for SPM as GEOSwift/geos 5.1.0)

As far as I'm aware these two results would be considered topologically equivalent. You can check for topological equivalence between 2 geometries using the method .isTopologicallyEquivalent(to:)

Let me know if this helps.

[india2sarthak]

Thanks a lot for the quick reply! Yeah, I guess they would be topologically equivalent. However, the order of the intersection points is quite critical to us. I also believe that the order of the intersection points in the previous version of GEOS was in sync with that of other GeoSpatial libraries like Shapely, ArcGIS, etc. Can you suggest a workaround for this? Like maybe a way to sort the coordinates or something to retain the previous order. Thanks.

[macdrevx]

I think we'll need to bubble this up to the GEOS folks to get their perspective. I'll ask for guidance on their mailing list.

[macdrevx]

@india2sarthak in the mean time, one option you have is to downgrade geos to 5.0.0. This will likely resolve this issue for you.

[dr-jts]

I also believe that the order of the intersection points in the previous version of GEOS was in sync with that of other GeoSpatial libraries like Shapely, ArcGIS, etc.

Shapely uses GEOS as well, so that is probably why it is consistent (and why it will also change with GEOS 3.9).

There is no relationship to ArcGIS - any similarity is purely coincidental. In general there is no "defined" ordering to the output from Overlay. In fact Overlay avoids imposing any ordering, in order to minimize processing time.

Can you suggest a workaround for this? Like maybe a way to sort the coordinates or something to retain the previous order.

GEOS provides a normalize operation which does a lexicographical sort of geometries in a collection. That is the usual way to enforce a consistent ordering for geometries.

[india2sarthak]

@dr-jts Thanks for the suggestion, will try it out! @macdrevx Do we have a method similar to the normalize method of GEOS in GeoSwift?

[macdrevx]

I just checked. Looks like we haven't exposed it yet, but we can add it.

[macdrevx]

@india2sarthak I've pushed a branch with this change. Please test it out and let us know whether it meets your needs.

The branch is named normalize and it adds a method normalized() -> Geometry that can be used on any type conforming to GeometryConvertible.

[india2sarthak]

Thanks so much! Will test it out and get back to you.

[macdrevx]

This is now available in version 8.0

[india2sarthak]

Hey. Thanks a lot for pushing the experimental branch (normalize) and a new release. I tried using the generalzed() method on the geometries as @dr-jts suggested. However, unfortunately, it does not solve the issue. I was wondering if there was any way for me to only downgrade GEOS and yet use the latest version of GEOSwift so that I can continue to use the newest exposed methods of geos in my app.

[macdrevx]

I've pushed a new branch issue212 which contains a variant of the latest GEOSwift modified to run against an older geos version. I don't think it makes sense for this to be an officially supported part of GEOSwift since we want to keep up with the evolution of geos, but what you could do is maintain a fork that tracks upstream and maintains compatibility with the older geos version.

In addition, could you share a bit more about your use case? I'm curious whether we could help you come up with another approach if we knew a bit more about what you're building.

[india2sarthak]

So we use GeoSwift in a drone-based mapping application wherein we obtain the drone path for mapping a geometry.

1.) For this, we first find the bounding box of the geometry using the envelope method of GeoSwift that needs to surveyed like this

2.) We then draw lines inside the bounding box at equal intervals using the interpolatedPoint(withFraction: ) method of a line string.

3.) Finally, we find the intersection of these lines with the original geometry using the intersection method. We then reverse the alternate lines while joining these intersection points to create a lawn-mover pattern. These joined lines finally determine the path the drone is going to take while surveying the region.

Hence, the order of the intersecting points is critical to us as a change in the order of the intersecting points changes the path of the drone completely.

[india2sarthak]

Also, I noticed that this issue is only present for concave geometries. We don't face this issue with convex geometries as such. The order changes if the line intersects the geometry at more than 2 points (convex geometries).

[dr-jts]

Ok, I understand the problem now, and I can reproduce it in GEOS and JTS. And I agree that it is desirable that the order of results from polygon-linestring intersections be faithful to the ordering of the original lines. I'm looking in to whether this is possible to do as an improvement to the OverlayNG code.

I do note that the direction of each result line is consistent with the input line. So this provides a workaround - sort the output lines by the distance of their start point along the input line.

[dr-jts]

@india2sarthak Are you computing the intersection one line at a time? Or for the whole ensemble (in which case how do you determine the ordering within the output?)

It would be nice to preserve the total ordering of the input line ensemble in the result (which is not done now in OverlayNG, but seems to be the case in the previous overlay). This should be feasible to do for OverlayNG. That would allow matching result lines to the input lines in an efficient way, by scanning both lists and computing the nearest input line to each result line start point. Is this what you are doing now?

[dr-jts]

It looks like there is a fairly simple fix to this ordering problem. I will add that to JTS, and we'll work through the pipeline to land in GEOS too.

[macdrevx]

Sounds great! Thanks @dr-jts.

@india2sarthak I'm not sure when we should expect this to land in a GEOS release, but when it does, we can update our CocoaPods & SPM packages accordingly so you'll have access to it and won't need to maintain a fork. We can leave this issue open until then.

[india2sarthak]

Sounds great! @macdrevx @dr-jts. Will wait for it to land into GEOS.

[india2sarthak]

@dr-jts Any updates on the fix landing in the GEOS?

[dr-jts]

This has been fixed in GEOS. See GEOS 1093.

[india2sarthak]

That's great! Thanks so much for the update. Any update on when the next version of GEOS would be released?

[dr-jts]

No timeline for next GEOS release at the moment.

[macdrevx]

GEOS 3.9.1 has been released with this fix. I've tagged a new version of GEOSwift/geos that includes the update.

@india2sarthak could you please update your geos dependency and verify the fix? (There's not a new GEOSwift version since the current version is already compatible with the new geos.)

[india2sarthak]

Wow, that's great! I will get back to you on this

[india2sarthak]

I tried upgrading geos on my end. However, I am getting this error Specs satisfying the `geos (= 6.0.2), geos (~> 5.0)` dependency were found, but they required a higher minimum deployment target..

I am currently targeting iOS 13.0 in my app, even tried increasing it to 14.2, it still resulted in the same error on running pod install or pod update.

Here is a copy of my Podfile

project 'DMC.xcodeproj'
platform :ios, '13.0'

# ignore all warnings from all pods
inhibit_all_warnings!

target 'App' do
  use_frameworks!

  # Geospatial Analysis
  pod 'GEOSwift', '7.2.0'  
  pod 'geos', '6.0.2'
end

Any idea where I am going wrong? Thanks!

[macdrevx]

You'll want GEOSwift 8.0.1

[india2sarthak]

That worked! However, I had to set it to 8.0.0, setting it to 8.0.1 resulted in the following error

[!] CocoaPods could not find compatible versions for pod "GEOSwift":
  In Podfile:
    GEOSwift (= 8.0.1)

None of your spec sources contain a spec satisfying the dependency: `GEOSwift (= 8.0.1)`.

You have either:
 * mistyped the name or version.
 * not added the source repo that hosts the Podspec to your Podfile.

Additionally, I was able to test the fix and I can confirm that the issue has indeed been resolved in the latest version of GEOS (3.9.1)

[macdrevx]

Thanks! I realize now that 8.0.1 was never published to CocoaPods because the only change was to the Swift Package Manager configuration. Glad it's working!