nearestPointOnLine returns invalid segmentIndex when result is at the end of the last segment of the lineString

[smallsaucepan]

When calling nearestPointOnLine and the result is at the end of a segment, there is legacy behaviour that sets the segmentIndex to that of the next segment (end point of one segment being the same as the start point of the next). Unsure why this is the behaviour.

Unfortunately, if the original segment was the last in the lineString the segmentIndex is still incremented meaning it now refers to a non-existent segment.

After fixing #2946 with PR #2951, it became apparent in #3008 some users were using the overflowing segmentIndex as an indicator for whether the nearest point was found at the end of the line. Although undocumented, this caused backwards compatibility issues and will be reverted.

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)

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. With the already returned lineStringIndex and segmentIndex it should be possible to test that condition in user code if required. Happy to hear examples though if there are other capabilities that would become impossible.

[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.