search

mapbox / delaunator

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

Different results between 1.0.0 and 1.0.3 #8

Closed mcwhittemore closed 7 years ago

mcwhittemore commented 7 years ago

@mourner - I'm seeing different results for the same set of points when upgrading from 1.0.0 to 1.0.3. My use case is a bit weird as I'm iteratively adding points, but it's a deterministic process and upgrading has resulted in a change. Is this expected?

Reading through the commits I don't see anything that seems to imply an intentional change. If this is unexpected, I'll spend some time to create a dataset that reproduces the result.

mourner commented 7 years ago

@mcwhittemore yes, that's expected! Sorry, should have mentioned that in the readme. Visually the result should be the same (except for cases where there are multiple points on the same circle, such as grids), but the order can be different after the hash edge table optimization.

mcwhittemore commented 7 years ago

yes, that's expected!

👍

except for cases where there are multiple points on the same circle, such as grids

Sorry, I'm not 100% sure what you mean by on the same circle. Can you explain this a bit more?

order can be different after the hash edge table optimization

The order can be different after each run or the order can be different compared to previous versions?

mourner commented 7 years ago

@mcwhittemore different order compared to previous versions. As for points on a circle: a point set can have multiple Delaunay triangulations in cases like this:

image