mapbox / delaunator

An incredibly fast JavaScript library for Delaunay triangulation of 2D points
https://mapbox.github.io/delaunator/
ISC License
2.24k stars 139 forks source link

Add a failing test showing issue #61 #69

Closed mcwhittemore closed 3 years ago

mcwhittemore commented 3 years ago

@mourner currently this test fail on the triangles has the number of vertices equal to 4 triangles assert in the main body of the test and on the triangulation is broken assert in the validate suite. This is taken from the failing case I mentioned in #61.

mourner commented 3 years ago

@mcwhittemore It appears that the test case is not actually a proper triangle — it's actually three nearly collinear points. Adding midpoints produces more collinear points. Here's how it looks in the demo viz:

image

The results are expected for such a sample — connectivity is not broken, number of triangles being different is expected due to different topology, and triangulation validation by area fails because of floating point errors in validation itself as far as I understand. Not sure if Delaunator could do better in this case. As a workaround when dealing with data like this, I'd suggest calculating the area of a polygon first and throwing it out if it's below certain value (e.g.g < 2e-14).

mcwhittemore commented 3 years ago

Hmmm... maybe I'm picking a bad example. I'm doing an area check on geojson to make sure the triangle is > 100sq/m and still seeing this problem. Here is an image of it in geojson.io and the geojson. Its very possible I'm doing something else wrong here though. I'll keep poking and if I find a way to better show the problem I'll cut a new ticket. Thanks @mourner.

image

{
  "type": "FeatureCollection",
  "features": [{
  "type": "Feature",
  "properties": {},
  "geometry": {
    "type": "Polygon",
    "coordinates": [
      [
        [
          31.980857849121094,
          -27.32083985541714
        ],
        [
          31.96918487548828,
          -27.319467192847057
        ],
        [
          31.97021484375,
          -27.319314674783715
        ],
        [
          31.980857849121094,
          -27.32083985541714
        ]
      ]
    ]
  }
}]
}