Document nearestPointOnLine behaviour for v8

[smallsaucepan]

Discussion to document from the ground up the behaviour of nearestPointOnLine for the next major release.

Function purpose: given a MultiLineString and a Point, identify the closed point on the input line to the input point.

Inputs:

• line LineString | MultiLineString | Feature<LineString | MultiLineString>
• point Point | Feature<Point>
• options {...}

Returns:

Feature<Point, {
    lineStringIndex: number;
    segmentIndex: number;
    totalDistance: number;
    lineDistance: number;
    segmentDistance: number;
    pointDistance: number;
}>

In addition to the position of the nearest point, for convenience the function returns some meta data about where in the input line the point was found. For example, on which segment of which LineString the point was found on.

In the case of ambiguity, such as when the nearest point lies on multiple line segments, the behaviour will be:

• ...

[smallsaucepan]

@EmilJunker

[EmilJunker]

I am happy that the regression introduced in v7.3.2 will be fixed in the short term. I am also happy that a long term solution to fix and improve the behavior of the nearestPointOnLine function is being discussed for v8.

This issue aims to fix the problem properly as a breaking change aligned with a major release. Current plan is to:
1. ensure segmentIndex always refers to a valid segment
2. stop favouring the start point of the next segment instead (unless a valid reason becomes clear)

I support the goal of making sure that the nearestPointOnLine function never returns points with a segmentIndex of a non-existent line segment. This bug should definitely be fixed in v8.

I also support the plan to change the behavior for all line points (not just for the last one like it was done in v7.3.2). When the nearest point falls on the line point at the end of a line segment at index i, the next major version of Turf should always interpret this as segmentIndex = i. No more "index progresses to start of next segment because legacy behavior" shenanigans. 👍

This would also preserve a really useful aspect of the nearestPointOnLine function that I have come to appreciate. In all Turf versions up to v7.3.1, there is a nice symbiosis between the lineStringIndex and segmentIndex properties when the input line is represented as a MultiLineString vs. a LineString. Turf v7.3.2 broke this symbiosis, but if Turf v8 would change the behavior for all line points in the way discussed above, then this symbiosis would be restored.

Expand for detailed explanation of symbiosis

Consider a LineString with six points [P, Q, R, S, T, U].

Given an input point, we want to know the nearest point to the input point that lies on the line. In particular, I want to focus on the cases when the nearest point lies on any line point as well as when it lies in between any two line points. Here is a visualization of possible positions for the nearest point:

This example nicely covers all the interesting cases.

If the behavior change discussed above was implemented in v8, we would get:

	segmentIndex
nearA	0
nearB	0
nearC	0
nearD	1
nearE	1
nearF	2
nearG	2
nearH	3
nearJ	3
nearK	4
nearL	4

But as we all know, the nearestPointOnLine function also accepts MultiLineStrings as input. And the above line with six points can also be represented as a MultiLineString. For example, one way to do this would be to chop it up into three sub-lines [P, Q, R], [R, S] and [S, T, U].

If you ask why someone would chop up a LineString into a MultiLineString, let me just say that there can be various reasons to do this. For example, it lets you color different parts of a route with different colors on a map, e.g. to represent route parts with congested traffic. Also, it lets you filter out certain line segments that you don't want to consider in the nearest-point-on-line calculation.

The symbiosis I'm talking about allows me to easily switch the line representation between a LineString and a MultiLineString back and forth without much effort. The lineStringIndex and segmentIndex properties returned by the nearestPointOnLine function provide all the information I need. The only additional ingredient I need is to consider the different lengths of the sub-lines in the MultiLineString (because I chopped it up irregularly). For my example, this would be the following:

let segmentIndexOffset = {
  0: 0, // there is no offset before the line [P, Q, R] because it's the first
  1: 2, // there are two line segments before the line [R, S]
  2: 3 // there are three line segments before the line [S, T, U]
};

If the behavior was changed in v8 and we passed this MultiLineString [[P, Q, R], [R, S], [S, T, U]] into the nearestPontOnLine function, we would get:

	lineStringIndex	segmentIndex	segmentIndexOffset[lineStringIndex] + segmentIndex
nearA	0	0	0
nearB	0	0	0
nearC	0	0	0
nearD	0	1	1
nearE	0	1	1
nearF	1	0	2
nearG	1	0	2
nearH	2	0	3
nearJ	2	0	3
nearK	2	1	4
nearL	2	1	4

Notice how the index sum for the MultiLineString is the same as the segmentIndex for the LineString. This is the symbiosis I'm talking about. It is a really useful property that I have come to appreciate and rely on in my code.

(Detailed explanation ends here)

The only point I disagree with is this:

There have been requests to add additional meta data to the response properties to make up for the removal of the inferred "end of line" overflow. We're currently leaning away from that to avoid bloating the response.

I would argue that whenever the nearest point falls exactly on the line point at the end of a line segment at index i, it is an edge case and leaves room for two possible interpretations:

1. The point is at the end of said line segment, i.e. segmentIndex = i.
2. The point is at the start of the next line segment, i.e. segmentIndex = i + 1.

All Turf versions up to v7.3.1 were always imposing the second interpretation onto everyone. If the behavior was changed as discussed above, Turf v8 would switch to the first interpretation. But I think it would be good if Turf still offered the user an easy way to revert to the v7.3.1 behavior. Both interpretations are valid and have their use cases. Turf shouldn't impose either of them onto everyone.

I am therefore in favor of adding a isSegmentEnd property that is true if and only if the nearest point is located at the end of the line segment. With this change, the user could decide for themselves how to handle this edge case. By default, it would be interpreted as being at the end of the previous line segment. But if the user wants to interpret it as being at the start of the next line segment, all they would need to do is increment the segmentIndex by 1 whenever isSegmentEnd is true.

I am aware that adding yet another property to the points returned by the nearestPointOnLine function is not ideal. And it is of course true that one could manually check if the point is at the end of its line segment by using only the the existing lineStringIndex and segmentIndex properties. But this is cumbersome and I would very much appreciate it if this was handled by Turf itself.

The reason why I prefer the second interpretation is because it simply makes more sense for my use case. I'm using the nearestPointOnLine function to map the user position onto a route to provide a sort of turn-by-turn navigation experience. Depending on where the user is on the route, I will show them information what to do next. When the user is mapped exactly on a line point (often happens for example at street corners), it simply makes more sense to show them the information for the route part ahead of them instead of the one behind them.

[smallsaucepan]

The reason why I prefer the second interpretation is because it simply makes more sense for my use case. I'm using the nearestPointOnLine function to map the user position onto a route to provide a sort of turn-by-turn navigation experience. Depending on where the user is on the route, I will show them information what to do next. When the user is mapped exactly on a line point (often happens for example at street corners), it simply makes more sense to show them the information for the route part ahead of them instead of the one behind them.

Then this is probably why it was coded that way in the first place. In light of what seems like a useful, real world convention we can just leave that behaviour as is. If the point can be on the either segment, Turf will continue to indicate the segment most likely to be used "next".

What will still be fixed (this issue) is the segmentIndex pointing beyond the end of the lineString to a non-existent segment. Will update the description to reflect that.

[EmilJunker]

First of all, thank you for the swift handling of the regression, I just saw that v7.3.4 was released yesterday. I appreciate it 🙏

In light of what seems like a useful, real world convention we can just leave that behaviour as is. If the point can be on the either segment, Turf will continue to indicate the segment most likely to be used "next".

Please not that again, this was the behavior in v7.3.2 and it broke the symbiosis (sorry, I just can't think of a better word) between the lineStringIndex and segmentIndex that I've been writing about so much. Maybe this overview will help to make it clear:

	progress to next segment after last line point	progress to next segment after intermediate line points	no non-existent line segments	symbiosis between lineStringIndex and segmentIndex
Turf v7.3.1 and v7.3.4	yes	yes	❌	✅
Turf v7.3.2 and your proposal for v8	no	yes	✅	❌
My proposal for v8	no	no (but indicate via isSegmentEnd)	✅	✅

[smallsaucepan]

You'll need to explain more what you mean by "symbiosis". I'm not following. Perhaps a couple of labelled diagrams to illustrate the relationship.

[smallsaucepan]

With the indices returning consistently + correctly, it would be possible to check for end of segment even without a flag though, right? Comparing the returned point with the point in the input line referenced by the indices.

[EmilJunker]

With the indices returning consistently + correctly, it would be possible to check for end of segment even without a flag though, right? Comparing the returned point with the point in the input line referenced by the indices.

Yes, that would be possible. But the exact way to check this would differ slightly depending on whether you passed in a LineString or a MultiLineString (or just a geometry which I think is also supported):

// LineString segment end coordinates:
lineString.geometry.coordinates[nearestPoint.properties.segmentIndex + 1]

// MultiLineString segment end coordinates:
multiLineString.geometry.coordinates[nearestPoint.properties.lineStringIndex][nearestPoint.properties.segmentIndex + 1]

Therefore, I would appreciate it if Turf simply handled this check itself, so I don't need to worry about what format the passed line has. I think many other users would also find this useful, especially if they (like me) prefer to move to the next segment when the nearest point is at the end of a segment.

[smallsaucepan]

Before you proceed to the next segment though you'd still need to check there is another segment to come. I get what you're saying about the flag being convenient, however it doesn't imply there is another segment yet to come. You're still going to have to get your hands dirty in the coords array/s.

Taking a step back, there might be value in adding general purpose segment checks you can use. atEndOfSegment, atEndOfLineString, hasNextSegment. That would fit in better with a Turf building block approach, and also wrap that functionality for non-nearestPointOnLine users.

[EmilJunker]

For my particular use case, I actually don't need to check if there is a next segment. But for users who need that, we could in theory also add a isLineEnd flag that tells you whether the nearest point is at the end of the line (meaning there is no segment after it).

But I understand your concern about adding too many properties. Maybe we could make the additional properties optional via the options parameter of the nearestPointOnLine function? By default, they wouldn't be included. But if the user wants them, they are added 🤔

On the other hand, you are right that a general purpose Turf function to check this would probably make more sense. So I'm definitely not opposed to that.

[EmilJunker]

@smallsaucepan I would be willing to help with the creation of the general purpose functions atEndOfSegment, atEndOfLineString, hasNextSegment. I just need some instructions how to get started. Should they be added to an existing turf module or should I create a new module for them?