Rolling back ignoreSelfIntersections to 6.5.0 behaviour

[smallsaucepan]

Discussion to prepare for a PR that will revert ignoreSelfIntersections behaviour to what is in 6.5.0. With the release of v7 we seem to have introduced multiple breaking changes to this area and they should be reverted ASAP.

Some questions to answer:

1. What was the ignore self intersections behaviour in 6.5.0?
2. Can we trace to some degree where / why that changed? Not to blame anyone. More to understand how we got here and to ensure we aren't missing something.
3. Roughly what will we have to change as part of a PR?

Covers issues:

#2722
#2707
#2700
#2633
#2585

[smallsaucepan]

History as I understand it. Will amend as comments and corrections are suggested.

6.5.0 (mid-2021) shipped with an in house algorithm for line-intersect. There is no mention of self intersections and no way to override the behaviour. The (to be confirmed) belief is this implementation always ignored self intersections.

In 2022 line-intersect was rewritten to use the third party sweepline-intersections library. This included the function changing to recognise self intersections by default. It's not clear yet why this change was made or if it was intended.

Over the ensuing couple of years the ignoreSelfIntersections option has been added in a few more places. The default value chosen may have been based on an incorrect assumption that recognising self intersections was the default in 6.5.0 because that was what was in the development branch.

Eventually, releasing 7.0.0 (mid-2024) shipped an undocumented breaking change to line-intersect (and other packages).

Possibly impacted packages:

boolean-crosses
boolean-disjoint
boolean-intersects
line-intersect
line-split

To do

• Confirm 6.5.0 and 7.1.0 behaviour for each possibly affected package
• Confirm we've covered all the packages that might be effected
• Flesh out a PR

Behaviour matrix - lines

Package	6.5.0	7.1.0	dev
boolean-crosses	ignores false	🟢 ignores
boolean-disjoint	ignores true	🔴 recognises
boolean-intersects	ignores false	🔴 recognises
line-intersect	ignores [ ]	🔴 recognises
line-split	ignores [ ]	🟢 ignores

Behaviour matrix - polygons

Package	6.5.0	7.1.0	dev
boolean-crosses	n/a	n/a
boolean-disjoint	ignores true	🔴 recognises
boolean-intersects	ignores false	🔴 recognises
line-intersect	ignores [ ]	🔴 recognises
line-split	n/a	n/a

[pm0u]

To support of the point 6.5.0 did not check self intersections - this is the relevant implementation https://github.com/Turfjs/turf/blob/v6.5.0/packages/turf-line-intersect/index.ts#L69-L83

turf/packages/turf-line-intersect/index.ts

Lines 69 to 83 in 5375941

	const tree = rbush();
	tree.load(lineSegment(line2));
	featureEach(lineSegment(line1), (segment) => {
	featureEach(tree.search(segment), (match) => {
	const intersect = intersects(segment, match);
	if (intersect) {
	// prevent duplicate points https://github.com/Turfjs/turf/issues/688
	const key = getCoords(intersect).join(",");
	if (!unique[key]) {
	unique[key] = true;
	results.push(intersect);
	}
	}
	});
	});

My understanding of the above is that one geometry (line2) is loaded into an Rbush index (line 70).
Then the other feature (line1) is split (line 71) and checked for intersections against the RBush tree (line 72), with the resulting featureCollection of the result for each segment fed into featureEach. The actual point of intersection for an intersection pair (components of pair are line2, line1) is then computed on line 74 and added to a feature collection if it is not already computed. This feature collection is returned once all iterations are complete.

I don't see a way that this could have accounted for a self intersection. If separate consumers of this did something like lineIntersects(line1, line2) || lineIntersects(line1, line1) || lineIntersects(line2, line2) then those consumers would be checking for a self intersection, but I don't think that check is performed anywhere.

[smallsaucepan]

Hi @pm0u. Would you mind taking a look at the above? Can you think of any other packages we should check?

Also, you mention on #2722 there is no workaround for booleanCrosses (agreed). I don't see booleanCrosses misbehaving for the test cases above though. Nor any existing issues along those lines. Do you have a test case where it is being affected by this ignores issue?

[pm0u]

Do you have the source for this reproduction? This was the reproduction I created: https://codesandbox.io/p/sandbox/turfjs-7-1-0-s8x273

I think the difference may be that my example is using line-poly crossing check - we may want to add some test cases for that as well.

[pm0u]

Based on the source, the line-line example should (assuming we are looking at the correct geo in the image provided) return as crossing - line-line and line-poly both use the lineIntersect package without ignoring self intersections

turf/packages/turf-boolean-crosses/index.ts

Lines 103 to 135 in 90e91a3

	function doLineStringsCross(lineString1: LineString, lineString2: LineString) {
	var doLinesIntersect = lineIntersect(lineString1, lineString2);
	if (doLinesIntersect.features.length > 0) {
	for (var i = 0; i < lineString1.coordinates.length - 1; i++) {
	for (var i2 = 0; i2 < lineString2.coordinates.length - 1; i2++) {
	var incEndVertices = true;
	if (i2 === 0 || i2 === lineString2.coordinates.length - 2) {
	incEndVertices = false;
	}
	if (
	isPointOnLineSegment(
	lineString1.coordinates[i],
	lineString1.coordinates[i + 1],
	lineString2.coordinates[i2],
	incEndVertices
	)
	) {
	return true;
	}
	}
	}
	}
	return false;
	}
	function doLineStringAndPolygonCross(lineString: LineString, polygon: Polygon) {
	const line: any = polygonToLine(polygon);
	const doLinesIntersect = lineIntersect(lineString, line);
	if (doLinesIntersect.features.length > 0) {
	return true;
	}
	return false;
	}

[pm0u]

I added a test case to my example of line-line comparison and there does not seem to be an issue in my test case either. I am wondering if this isPointOnLine check that happens for line-line is the reason why there is a difference. I think this is somewhat diverging behavior - I would think for consistency it could make sense to perform the same check here, eg convert poly to line and then use doLineStringsCross within doLineStringAndPolygonCross?

turf/packages/turf-boolean-crosses/index.ts

Lines 113 to 118 in 90e91a3

	isPointOnLineSegment(
	lineString1.coordinates[i],
	lineString1.coordinates[i + 1],
	lineString2.coordinates[i2],
	incEndVertices
	)

[smallsaucepan]

Thankyou, that's great. I'd missed those tests. Have added them to mine and confirm seeing the same results.

the line-line example should [...] return as crossing

Hmm. line-line only seems to use lineIntersect as a short circuit method. Even though lineIntersect is returning a false positive, the nested loops still check each segment with isPointOnLineSegment.

line-poly on the other hand uses lineIntersect verbatim so I reckon that same false positive (which line-line neutralises by looping all segments as well) is why it's only the *-poly combos are failing. What do you think?

[smallsaucepan]

Hi @01100100. Copying you in on this issue because it touches on #2633. It looks like we are going to be changing ignoreSelfIntersections to default to true - Turf wide. Within the context of your PR I think this is ok as that was all about letting people override ignore to true. If true becomes the default they're not affected.

Please have a read of the above and let me know if I've got anything wrong. Thanks!

[01100100]

Hello Mr Saucepan,

Sounds good with me, happy the changes helped.

Best regards,
Dave

[01100100]

If I remember correctly, the default pre 6.5.0 behaviour was that it was ignored, hence false. Just so your aware.

Maybe this change will need some tests updating... 🧪

[smallsaucepan]

If I remember correctly, the default pre 6.5.0 behaviour was that it was ignored, hence false. Just so your aware

You mean true here though right? 6.5.0 ignored self intersections yes?

[01100100]

Let me know if you want me to implement any changes here and I would be happy to help ⛑️