Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

#

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Jump to bottom

booleanIntersects false positive #195

Open
ristiisa opened this issue Feb 11, 2025 · 2 comments · May be fixed by #196
Open

booleanIntersects false positive #195

ristiisa opened this issue Feb 11, 2025 · 2 comments · May be fixed by #196

Comments

@ristiisa
Copy link

ristiisa commented Feb 11, 2025 •
edited
Loading

The following geojson has 2 polygons that by visual inspection do not intersect but booleanIntersects reports otherwise. The same geojson with turf.js seems to work correctly https://www.jdoodle.com/ia/1Cl2.

I'm using turf 0.0.10.

{
    "type": "FeatureCollection",
    "features": [
      {
        "type": "Feature",
        "properties": {},
        "geometry": {
          "type": "Polygon",
          "coordinates": [[
            [24.603832926513377, 59.31365641519804],
            [24.839352333388916, 59.31365641519804],
            [24.839352333388916, 59.47725847796798],
            [24.603832926513377, 59.47725847796798],
            [24.603832926513377, 59.31365641519804]
          ]]
        }
      },
      {
        "type": "Feature",
        "properties": {},
        "geometry": {
          "type": "Polygon",
          "coordinates": [[
            [24.567369012152085, 8.229187933785468],
            [23.805813429466752, 8.666318874542426],
            [23.459012892355986, 8.954285793488893],
            [23.394779087017184, 9.265067857292223],
            [23.55724979014283, 9.681218166538684],
            [23.554304233502194, 10.089255275915308],
            [22.97754357269261, 10.71446259199854],
            [22.864165480244225, 11.142395127807546],
            [22.87622, 11.384610000000123],
            [22.50869, 11.67936],
            [22.49762, 12.26024],
            [22.28801, 12.64605],
            [21.93681, 12.588180000000136],
            [22.03759, 12.95546],
            [22.29658, 13.37232],
            [22.18329, 13.78648],
            [22.51202, 14.09318],
            [22.30351, 14.32682],
            [22.56795000000011, 14.944290000000137],
            [23.024590000000103, 15.68072],
            [23.886890000000108, 15.61084],
            [23.837660000000142, 19.580470000000105],
            [23.850000000000136, 20.0],
            [25.000000000000114, 20.00304],
            [25.0, 22.0],
            [29.02, 22.0],
            [32.9, 22.0],
            [36.86623, 22.0],
            [37.188720000000103, 21.01885],
            [36.96941, 20.837440000000129],
            [37.114700000000141, 19.80796],
            [37.481790000000103, 18.61409],
            [37.86276, 18.36786],
            [38.410089959473225, 17.998307399970315],
            [37.90400000000011, 17.42754],
            [37.16747, 17.263140000000135],
            [36.852530000000115, 16.95655],
            [36.75389, 16.29186],
            [36.32322, 14.82249],
            [36.42951, 14.42211],
            [36.27022, 13.563330000000121],
            [35.86363, 12.57828],
            [35.26049, 12.08286],
            [34.831630000000132, 11.318960000000118],
            [34.731150000000127, 10.910170000000107],
            [34.25745, 10.63009],
            [33.96162, 9.58358],
            [33.97498, 8.68456],
            [33.963392794971185, 9.464285229420625],
            [33.824963480907513, 9.484060845715362],
            [33.842130853028152, 9.981914637215993],
            [33.721959248183111, 10.325262079630193],
            [33.206938084561784, 10.720111638406593],
            [33.086766479716744, 11.441141267476496],
            [33.206938084561784, 12.179338268667095],
            [32.743419037302544, 12.248007757149992],
            [32.674749548819648, 12.02483191958072],
            [32.073891524594785, 11.973329803218519],
            [32.314234734284753, 11.681484477166521],
            [32.400071594888345, 11.080626452941488],
            [31.850715687025513, 10.531270545078826],
            [31.352861895524882, 9.810240916008695],
            [30.837840731903384, 9.70723668328452],
            [29.996639497988554, 10.290927335388687],
            [29.618957311332849, 10.084918869940225],
            [29.515953078608618, 9.793073543888056],
            [29.000931914987177, 9.604232450560289],
            [28.966597170745786, 9.398223985111656],
            [27.970889587744352, 9.398223985111656],
            [27.833550610778786, 9.604232450560289],
            [27.112520981708883, 9.638567194801624],
            [26.752006167173818, 9.466893473594496],
            [26.477328213242515, 9.552730334198088],
            [25.962307049621018, 10.136420986302426],
            [25.790633328413946, 10.411098940233728],
            [25.069603699343986, 10.273759963267992],
            [24.794925745412684, 9.810240916008695],
            [24.53741516360202, 8.91753756573172],
            [24.19406772118765, 8.728696472403897],
            [23.886979580860668, 8.619729712933065],
            [24.567369012152085, 8.229187933785468]
          ]]
        }
      }
    ]
  }
Loading 
import 'dart:convert';
import 'package:turf/turf.dart';

void main() {
  var geoJson = GeoJSONObject.fromJson(jsonDecode(geoJsonString));
  var featureCollection = geoJson as FeatureCollection;

  var feature1 = featureCollection.features[0];
  var feature2 = featureCollection.features[1];

  var intersects = booleanIntersects(feature1, feature2);

  print("Do the features intersect? $intersects");
}

var geoJsonString = '''{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "Polygon",
        "coordinates": [[
          [24.603832926513377, 59.31365641519804],
          [24.839352333388916, 59.31365641519804],
          [24.839352333388916, 59.47725847796798],
          [24.603832926513377, 59.47725847796798],
          [24.603832926513377, 59.31365641519804]
        ]]
      }
    },
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "Polygon",
        "coordinates": [[
          [24.567369012152085, 8.229187933785468],
          [23.805813429466752, 8.666318874542426],
          [23.459012892355986, 8.954285793488893],
          [23.394779087017184, 9.265067857292223],
          [23.55724979014283, 9.681218166538684],
          [23.554304233502194, 10.089255275915308],
          [22.97754357269261, 10.71446259199854],
          [22.864165480244225, 11.142395127807546],
          [22.87622, 11.384610000000123],
          [22.50869, 11.67936],
          [22.49762, 12.26024],
          [22.28801, 12.64605],
          [21.93681, 12.588180000000136],
          [22.03759, 12.95546],
          [22.29658, 13.37232],
          [22.18329, 13.78648],
          [22.51202, 14.09318],
          [22.30351, 14.32682],
          [22.56795000000011, 14.944290000000137],
          [23.024590000000103, 15.68072],
          [23.886890000000108, 15.61084],
          [23.837660000000142, 19.580470000000105],
          [23.850000000000136, 20.0],
          [25.000000000000114, 20.00304],
          [25.0, 22.0],
          [29.02, 22.0],
          [32.9, 22.0],
          [36.86623, 22.0],
          [37.188720000000103, 21.01885],
          [36.96941, 20.837440000000129],
          [37.114700000000141, 19.80796],
          [37.481790000000103, 18.61409],
          [37.86276, 18.36786],
          [38.410089959473225, 17.998307399970315],
          [37.90400000000011, 17.42754],
          [37.16747, 17.263140000000135],
          [36.852530000000115, 16.95655],
          [36.75389, 16.29186],
          [36.32322, 14.82249],
          [36.42951, 14.42211],
          [36.27022, 13.563330000000121],
          [35.86363, 12.57828],
          [35.26049, 12.08286],
          [34.831630000000132, 11.318960000000118],
          [34.731150000000127, 10.910170000000107],
          [34.25745, 10.63009],
          [33.96162, 9.58358],
          [33.97498, 8.68456],
          [33.963392794971185, 9.464285229420625],
          [33.824963480907513, 9.484060845715362],
          [33.842130853028152, 9.981914637215993],
          [33.721959248183111, 10.325262079630193],
          [33.206938084561784, 10.720111638406593],
          [33.086766479716744, 11.441141267476496],
          [33.206938084561784, 12.179338268667095],
          [32.743419037302544, 12.248007757149992],
          [32.674749548819648, 12.02483191958072],
          [32.073891524594785, 11.973329803218519],
          [32.314234734284753, 11.681484477166521],
          [32.400071594888345, 11.080626452941488],
          [31.850715687025513, 10.531270545078826],
          [31.352861895524882, 9.810240916008695],
          [30.837840731903384, 9.70723668328452],
          [29.996639497988554, 10.290927335388687],
          [29.618957311332849, 10.084918869940225],
          [29.515953078608618, 9.793073543888056],
          [29.000931914987177, 9.604232450560289],
          [28.966597170745786, 9.398223985111656],
          [27.970889587744352, 9.398223985111656],
          [27.833550610778786, 9.604232450560289],
          [27.112520981708883, 9.638567194801624],
          [26.752006167173818, 9.466893473594496],
          [26.477328213242515, 9.552730334198088],
          [25.962307049621018, 10.136420986302426],
          [25.790633328413946, 10.411098940233728],
          [25.069603699343986, 10.273759963267992],
          [24.794925745412684, 9.810240916008695],
          [24.53741516360202, 8.91753756573172],
          [24.19406772118765, 8.728696472403897],
          [23.886979580860668, 8.619729712933065],
          [24.567369012152085, 8.229187933785468]
        ]]
      }
    }
  ]
}''';
@lukas-h
Copy link
Member

lukas-h commented Feb 17, 2025

Dear @ristiisa thank you a lot for providing this detailed bug report!

Were you able to figure out a bug fix? We are highly appreciative of merge requests if you would like to contribute.

Otherwise we'll try to figure out the false positive soon, but with no guaranteed timeline as our maintenance is a bit limited

@ristiisa ristiisa linked a pull request Feb 17, 2025 that will close this issue
Open
@ristiisa
Copy link
Author

This morning I was ready to write "as a workaround I added some extra checks":

bool intersects(f1, f2) => booleanIntersects(f1, f2) && (booleanOverlap(f1, f2) || booleanContains(f1, f2) || booleanContains(f2, f1));

But then I got curious and took a look at how the dart and js implementations differ and I was able to find a key difference in omition of self-intersection check. And after taking a closer look at my data, it seems that the "sudan" border definitions does self-intersect at some points.

I created PR with the fix #196

@lukas-h lukas-h moved this to Backlog in TurfDart RMIT Project Mar 10, 2025
# for free to join this conversation on GitHub. Already have an account? # to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

fixes booleanIntersects false positive ristiisa/turf_dart
2 participants
@ristiisa @lukas-h