Skip to content
New issue

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

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

Already on GitHub? Sign in to your account

SweepEvent comparison error thrown for infinitely thin input polygons #48

Closed
mfogel opened this issue Nov 14, 2018 · 2 comments
Closed
Labels
bug Something isn't working
Milestone

Comments

@mfogel
Copy link
Owner

mfogel commented Nov 14, 2018

If a polygon has an internal segment that is infinitely thin, polygon-clipping can crash. For example, performing a union on the following shapes results in a SweepEvent comparison failed at [-1, 0]... equal but not identical?

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "Polygon",
        "coordinates": [
          [[-2, -1], [-1, 0], [1, 0], [2, -1], [2, 1], [1, 0], [-1, 0], [-2, 1]]
        ]
      }
    },
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "Polygon",
        "coordinates": [[[-3, -3], [3, -3], [3, 3], [-3, 3], [-3, -3]]]
      }
    }
  ]
}

The polygon above polygon causing the problem looks like this:

screen shot 2018-11-14 at 14 09 26

What's going on here is that the algorithm doesn't know how to sort the two segments from the same ring that both go from [-1, 0] to [1, 0].

@mfogel mfogel added the bug Something isn't working label Nov 14, 2018
@mfogel mfogel changed the title Error thrown for infinitely thin input polygons SweepEvent comparison error thrown for infinitely thin input polygons Nov 14, 2018
@mfogel
Copy link
Owner Author

mfogel commented Nov 14, 2018

Other sets of coordinates that have appeared in the wild that appear to trigger this bug (pulled over from #41):

var coords = [
  [
    [-118.46571, 34.025348],
    [-118.465871, 34.025308],
    [-118.465936, 34.025348],
    [-118.467899, 34.025348],
    [-118.468194, 34.025197],
    [-118.468983, 34.025174],
    [-118.469245, 34.025348],
    [-118.46571, 34.025348]
  ]
];

polygonClipping.union(
  JSON.parse(JSON.stringify(coords)),
  JSON.parse(JSON.stringify(coords))
); // or `polygonClipping.union(coords, coords)`
polygonClipping.union(
  [
    [
      [-118.46571, 34.025348],
      [-118.465871, 34.025308],
      [-118.465936, 34.025348],
      [-118.467899, 34.025348],
      [-118.468194, 34.025197],
      [-118.468983, 34.025174],
      [-118.469245, 34.025348],
      [-118.46571, 34.025348]
    ]
  ],
  [
    [
      [-118.464605, 34.02561],
      [-118.465871, 34.025308],
      [-118.466413, 34.02565],
      [-118.467722, 34.025468],
      [-118.468194, 34.025197],
      [-118.468983, 34.025174],
      [-118.469433, 34.025494],
      [-118.470297, 34.025512],
      [-118.472282, 34.027219],
      [-118.464605, 34.02561]
    ]
  ]
);

@brianhearn
Copy link

Any luck with this one? I'm trying to use this with union operation on postal code polygons and running into it frequently

@mfogel mfogel added this to the v0.10 milestone Jan 7, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants