Add support for turf-line-intersect

[riastrad]

What kind of issue is this?

• [ ] Questions are better to ask on Stack Overflow. We are actively monitoring the questions there and oftentimes, others have already asked a similar question.
• [x] Feature request should start off by describing the problem the feature will resolve. Please open a GitHub ticket beforehand with information about the feature to spark some discussion about the topic and once you have our support.
• [ ] Bug Report can be reported using the provided template below:

Expected Behavior

I want to detect which roads intersect the route line I've drawn on the map and the coordinate pairs for these intersections.

Current Behavior

Currently there is no way to do this that's doesn't require a lot customer math on the part of the developer. This is because our Java Turf library does not support turf-line-intersect.

Possible Implementation

Porting Turf's lineIntersect would be the most consistent, straightforward way to handle the above use case.

[langsmith]

lineIntersect logic: https://github.com/Turfjs/turf/blob/master/packages/turf-intersect/index.ts

As is the case with many Turf methods, this method depends on other Turf methods and/or non-Turf libraries. This method uses "martinez-polygon-clipping". https://github.com/w8r/martinez

We'd need to consider is how to deal with bringing this math logic into our port of this method. A similar conversation is happening at https://github.com/mapbox/mapbox-java/issues/987#issuecomment-479028863.

[langsmith]

Soooo, looks like we already have lineIntersect or logic that could help create the port https://github.com/mapbox/mapbox-java/blob/master/services-turf/src/main/java/com/mapbox/turf/TurfMisc.java#L294 . 🤔 🎊 👏

Returns a LineIntersectsResult object: https://github.com/mapbox/mapbox-java/blob/master/services-turf/src/main/java/com/mapbox/turf/models/LineIntersectsResult.java

[langsmith]

Well we don't have the exact method, because it's private, not documented, etc. But the logic linked above is a great headstart.

[1ec5]

Indeed, LineIntersectsResult is functionally equivalent to turf-line-intersect, except that it operates on individual line segments instead of LineStrings. A turf-line-intersect workalike could be implemented easily by brute-forcing calls to this method.

https://github.com/mapbox/mapbox-java/blob/a86a6148b87ff3e4a9bd1096eaed5715b80db5e1/services-turf/src/main/java/com/mapbox/turf/TurfMisc.java#L314-L320

The JavaScript implementation of turf-line-intersect is more efficient for longer lines, because it relies on a JavaScript implementation of the RBush algorithm, which isn’t available as part of mapbox-java yet. (But there may be Java implementations out there.)

When we originally started porting Turf to Swift, we exposed LineIntersectsResult publicly as a stopgap solution. mapbox/turf-swift#167 implemented a turf-line-intersect method that’s functionally equivalent to the JavaScript function, but based on LineIntersectsResult. mapbox/turf-swift#171 tracks reimplementing it atop RBush for performance parity with JavaScript. I would suggest taking the same approach for now in Java, because LineIntersectsResult’s performance hit is not a problem for some use cases that involve short LineStrings.

/cc @LukasPaczos

[OttyLab]

@1ec5 @LukasPaczos

I opened the double for loop implementation PR here as a short-term solution.

[ghost]

Hi @OttyLab , @1ec5 , @LukasPaczos ,

May we have some updates please.

Best, Colin Tan

[OttyLab]

@762caliber

The PR was merged. Next, it should be released.

@LukasPaczos

Is there any plan for the next release on mapbox-java ?

[LukasPaczos]

We don't have any additional changes in the pipeline, so we'll release a mapbox-java v6.3.0-beta.1 today. Anyone could test it out independently or wait for it to be available in the Nav SDK v2.3.0 by the end of February (or in earlier v2.3 pre-releases).