Skip to content

Rewrite line-intersect module#2033

Merged
mfedderly merged 28 commits intomasterfrom
line-intersect-update
Apr 2, 2022
Merged

Rewrite line-intersect module#2033
mfedderly merged 28 commits intomasterfrom
line-intersect-update

Conversation

@rowanwins
Copy link
Copy Markdown
Member

@rowanwins rowanwins commented Feb 13, 2021 •
edited
Loading

Please fill in this template.

  • Use a meaningful title for the pull request. Include the name of the package modified.
  • Have read How To Contribute.
  • Run npm test at the sub modules where changes have occurred.
  • Run npm run lint to ensure code style at the turf module level.

This PR provides an overhaul of the line-intersect module primarily to make it more performant for larger geometries. The previous implementation used a fairly brute force approach while this PR make uses a sweepline.

I did have to comment out one test for handling GeometryCollection as I couldn't make typescript happy.

The benchmark shows the improvement, the only exception is the first case which i only a single segment.

// CURRENT
2-vertex-segment x 4,123,821 ops/sec ±12.92% (74 runs sampled)
double-intersect x 53,118 ops/sec ±4.22% (72 runs sampled)
multi-linestring x 16,417 ops/sec ±2.31% (77 runs sampled)
polygons-with-holes x 9,739 ops/sec ±2.55% (85 runs sampled)
same-coordinates x 51,303 ops/sec ±4.23% (71 runs sampled)

// PROPOSED
2-vertex-segment x 1,467,485 ops/sec ±1.74% (89 runs sampled)
double-intersect x 307,665 ops/sec ±1.70% (91 runs sampled)
multi-linestring x 81,337 ops/sec ±0.67% (94 runs sampled)
polygons-with-holes x 27,711 ops/sec ±0.70% (92 runs sampled)
same-coordinates x 521,277 ops/sec ±0.75% (92 runs sampled)

Resolves #2024
Resolves #2029

@rowanwins rowanwins mentioned this pull request Feb 13, 2021
Closed
mfedderly
mfedderly previously requested changes Feb 13, 2021
View reviewed changes
@rowanwins rowanwins requested a review from mfedderly June 17, 2021 11:57
@mfedderly mfedderly mentioned this pull request Aug 4, 2021
Closed
@mfedderly
Copy link
Copy Markdown
Collaborator

mfedderly commented Aug 5, 2021

Any chance you can change this back to your npm sweeplines-intersections package and get it to pass the build that way like with point-in-polygon-hao? The lack of licensing header and babeled code breaking eslint makes me feel bad.

@mfedderly mfedderly mentioned this pull request Aug 5, 2021
Merged
4 tasks
@mfedderly
Copy link
Copy Markdown
Collaborator

mfedderly commented Jan 17, 2022

@rowanwins I think the build will pass if you go back to depending on your npm package now that we started targeting es2017? We should also add that package name to https://github.com/Turfjs/turf/blob/master/README.md#browser-support

@rowanwins rowanwins mentioned this pull request Mar 17, 2022
Open
@twelch twelch mentioned this pull request Mar 20, 2022
Merged
@twelch
line-intersect additional type cleanup (#2273)
472f471 
* some cleanup

* clarify Intersection type
twelch
twelch approved these changes Mar 20, 2022
View reviewed changes
Copy link
Copy Markdown
Collaborator

@twelch twelch left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I have one comment to remove geojson-rbush dep if no longer needed. approving otherwise.

mfedderly
mfedderly reviewed Mar 20, 2022
View reviewed changes
Copy link
Copy Markdown
Collaborator

@mfedderly mfedderly left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks awesome. Can you publish the typescript defs in the package itself? I made two PRs to accomplish this:
rowanwins/sweepline-intersections#12
#2274

mfedderly
mfedderly reviewed Mar 21, 2022
View reviewed changes
@mfedderly
Copy link
Copy Markdown
Collaborator

mfedderly commented Apr 2, 2022

I'm going to go ahead and merge this

@mfedderly mfedderly merged commit b3076e7 into master Apr 2, 2022
@mfedderly mfedderly deleted the line-intersect-update branch April 2, 2022 16:37
@matthiasfeist
Copy link
Copy Markdown

matthiasfeist commented Apr 30, 2022

Hi quick question as this PR is merged but it's not released yet to npm. When and how is that gonna happen?

@diogormsf
Copy link
Copy Markdown

diogormsf commented Nov 4, 2022 •
edited
Loading

Hi quick question as this PR is merged but it's not released yet to npm. When and how is that gonna happen?

@matthiasfeist +1 on your comment. I would love to see this being merged to npm, it would allow me to remove an intersection algorithm created as a workaround.

@pm0u
Copy link
Copy Markdown
Contributor

pm0u commented Sep 24, 2024 •
edited
Loading

I believe this PR introduced a breaking change that means that self intersections are checked by default where previously they were not checked at all / did not have the option to be checked.

#2707
#2722

I believe this has further sweeping changes than just booleanIntersects. For instance, booleanCrosses does not call out this option in its implementation but I think it would be expected that if checking if 2 geometries cross, a self intersection is not a helpful result.

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

Line 104 in 68915ee

var doLinesIntersect = lineIntersect(lineString1, lineString2);

@pm0u pm0u mentioned this pull request Sep 24, 2024
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@twelch twelch twelch approved these changes

@mfedderly mfedderly mfedderly left review comments

+1 more reviewer

@matthiasfeist matthiasfeist matthiasfeist approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

lineStringsIntersect in geojson-utils a lot faster than turf.lineIntersect useless comparison inside line intersection algorithm

6 participants

@rowanwins @mfedderly @matthiasfeist @diogormsf @pm0u @twelch