Turfjs / Turfjs/turf

turf-difference creating holes instead of cutouts when input polys share an edge

Open
#2,887 3 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

polyclip-ts
Dominant language
TypeScript
Stars
10.5k
Forks
1k
Avg merge
1h 11m
Merged PRs (30d)
4

Description

Copied, as requested by @smallsaucepan, from original issue #2836.
Issue title isn't great, not sure how best to concisely describe it ¯_(ツ)_/¯

Original issue denotes problems between v5.16 and v6.5, however, the issue described here changes were tested on 6.5 to 7+. In original issue, Mr. Pan suggests the underlying issue is likely related to a myriad of polygon clipping library switches that turf has undergone across the versions to address other problems.

const targetBody = {
type: "Feature",
properties: {},
geometry: {
type: "Polygon",
coordinates: [[[-97.21939, 47.192546], [-97.219274, 47.192509], [-97.219274, 47.192416], [-97.219311, 47.192354], [-97.219428, 47.192352], [-97.219512, 47.192469], [-97.21939, 47.192546]]],
},
};

const shapeToRemove = {
type: "Feature",
properties: {},
geometry: {
type: "Polygon",
coordinates: [
[[-97.21946286472821, 47.192500011605965], [-97.21936021525944, 47.192446501553235], [-97.2193683023461, 47.1925390791966], [-97.21939, 47.192546], [-97.21946286472821, 47.192500011605965]]],
},
};
Shapes look like this where we want to remove the orange chunk from the yellow section.

Image

// Turf 6.5

const diff = turf.difference(targetBody, shapeToremove);

{
"type": "Feature",
"properties": {},
"geometry": {
"type": "Polygon",
"coordinates": [[[-97.219512,47.192469], [-97.219428,47.192352], [-97.219311,47.192354], [-97.219274,47.192416], [-97.219274,47.192509], [-97.2193683023461,47.1925390791966], [-97.21936021525944,47.192446501553235], [-97.21946286472821,47.192500011605965], [-97.219512,47.192469]]]
}
}
Expected results. The orange segment is removed

Image

// Turf 7+

const diff = turf.difference(turf.featureCollection([targetBody, shapeToremove]));

{
"type": "Feature",
"properties": {},
"geometry": {
"type": "Polygon",
"coordinates": [
[[-97.219512,47.192469], [-97.219428,47.192352], [-97.219311,47.192354], [-97.219274,47.192416], [-97.219274,47.192509], [-97.21939,47.192546], [-97.219512,47.192469]],
[[-97.21939,47.192546], [-97.2193683023461,47.1925390791966], [-97.21936021525944,47.192446501553235], [-97.21946286472821,47.192500011605965], [-97.21939,47.192546]]
]
}
}
Very unexpected results. Get back a polygon containing two rings

The first/exterior ring of the original yellow section
An interior ring which closely resembles the original orange section (being interpreted as a hole)
The outputs suggest that the diff decided that I was just cutting a hole out of the original shape instead of an entire segment.

This rendering is a little odd but the result is that same convex yellow shape with a hole that is extremely close the edges

Image

You might say: "The shapeToRemove geometry here is just off a bit. Use something that aligns better with the edges of the target shape, or better yet, extends beyond them"

To which I would reply: "The shapeToRemove here comes directly from the result of a turf.intersect between the targettBody and an original shape. The orange section is the result of that intersect and I would expect it to be as 'best-est' a shape as I can get for this kind of diff"

I've seen loads of examples of likely related issues where diff leaves behind these thin tails or slivers that it didn't in 6.5.
Something changed in the 7+ release that adjusted this. Idk if this is a wholly unexpected bug or if the changes made things 'too precise' comparatively and so all of these little things that were truncated are started to show up.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reproducing the supplied targetBody and shapeToRemove with turf.difference, comparing Turf 6.5 with 7+. Inspect the turf.difference entry point and the polygon-clipping changes mentioned in the issue. Add a regression test showing that a shape sharing an edge removes the segment without leaving an unintended interior hole or sliver.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript, typescript
Domain
computer-graphics
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.