d3 / d3-delaunay Goto Github PK
View Code? Open in Web Editor NEWCompute the Voronoi diagram of a set of two-dimensional points.
Home Page: https://d3js.org/d3-delaunay
License: ISC License
Compute the Voronoi diagram of a set of two-dimensional points.
Home Page: https://d3js.org/d3-delaunay
License: ISC License
If we want to apply Liang–Barsky clipping, the Voronator will also need to know the clip extent.
Not sure if this is intended, but it looks like "delaunator" might need to be added as a production dependency to not get this error.
Delaunator uses counterclockwise triangles, so we should probably be consistent.
What if voronoi.index pointed to the first triangle vertex for a given cell, and then we used the halfedge traversal algorithm lazily? Then we wouldn’t need to precompute voronoi.edges.
d3-voronoi has an edge object with edge.left
and edge.right
properties to get the index of the cell on either side.
Is there any chance you'd consider adding something similar to d3-delaunay? I've been trying to figure it out for the last while without success.
As it was mentioned use this new module instead d3-voronoi since its faster I tried to upgrade turf js voronoi to use this feature.
But it seems cellPolygons doesn't preserve the order.
import { collectionOf } from '@turf/invariant';
import { Delaunay } from 'd3-delaunay';
import * as turf from '@turf/helpers';
function coordsToPolygon(coords) {
coords = coords.slice();
coords.push(coords[0]);
return turf.polygon([coords]);
}
function voronoi(points, options) {
// Optional params
options = options || {};
const bbox = options.bbox || [-180, -85, 180, 85];
// Input Validation
if (!points) { throw new Error('points is required'); }
if (!Array.isArray(bbox)) { throw new Error('bbox is invalid'); }
collectionOf(points, 'Point', 'points');
const delaunay = Delaunay.from(points.features,
feature => feature.geometry.coordinates[0],
feature => feature.geometry.coordinates[1]);
const voronator = delaunay.voronoi([bbox[0], bbox[1], bbox[2], bbox[3]]);
const fc = turf.featureCollection(
Array.from(voronator.cellPolygons()).map(coordsToPolygon)
);
if (options.keepProperties) {
fc.features.forEach((polygon, i) => polygon.properties = JSON.parse(JSON.stringify(points.features[i].properties));
}
return fc;
}
export default voronoi;
Will keep properties will work for this package?
I'm looking to use Voronoi cells to represent movement for a game. I have a starting point/cell i, and a neighboring point/cell j - I'd like to use the edges for movement cost, walls, etc.
If I understand correctly, my ij pair is a half edge common to two adjacent triangles. The cell edge I'm looking for is the line connecting the circumcenter of these two triangles, but I can't find a way to determine the connections to get there. I think I'm missing how to find which half edge connects i and j, but maybe I'm missing something. Is there a simpler way that I'm not seeing?
We’re computing the polygon edges correctly (although we haven’t yet implemented clipping), but we’re not yet stitching them together into rings. #2
The current way of associating cells with their triangles brings a high performance and memory footprint cost, because we have to create a new Cell object and a triangles array for every input vertex.
A more efficient way to store cell triangles would be to keep a single Uint32Array
holding all the triangles, with cells only keeping offsets for looking into this array (e.g. index
and length
). Like this:
for (let i = 0; i < cellLength; i++) {
console.log(cellTriangles.subarray(cellIndex, cellIndex + cellLength));
}
Moreover, we could ditch Cell
class altogether and keep associated data in a flat typed array too. This would make Voronoi
data structures optimal in terms of performance and memory footprint and make the API consistent with that of Delaunator. However, this would require breaking the API — e.g. replacing methods like cell.contains(x, y)
with voronoi.cellContains(cellIndex, x, y)
.
cc @mbostock
Instead of delaunay.renderHull(context). Would require forking Delaunator to create a Node prototype.
voronoi._clipFinite currently always makes a copy, but it only needs to if clipping is needed.
Delaunator v4 got an update method to update triangulation after editing coordinates in place, avoiding a lot of new memory allocations for use cases like the Lloyd's algorithm (see mapbox/delaunator#36).
It would be great to make a corresponding change in d3-delaunay
as well. The Delaunay
class would have to hold on to the whole delaunator
object then (instead of just triangles
, halfedges
and hull
), and update inedges/outedges
after calling delaunator.update
in a potential update
method.
i found few edge cases,
when points provided to Delaunay are on one line (x or y axis) delaunay is not able to produce correct result, and it throwing error with
Error: No Delaunay triangulation exists for this input.
that's a case even no matter how many points there in single line.
this was not a case with d3-voronoi
points
[20,0,107.24319391634981,0,188.8577946768061,0,275.9837262357414,0,360.4126235741445,0,447.6558174904943,0,532.0847148288974,0,619.3279087452472,0,706.5711026615969,0,791,0]
How is delaunay.update supposed to interact with delaunay.voronoi? I assume you are expected to call delaunay.voronoi again after calling delaunay.update, but it’d be nice if there were an equivalent voronoi.update method.
I'm working with a set of lines that sometimes have coincident start points. I use d3-delaunay to find the nearest point to the cursor in order to highlight the line this point belongs to.
If it occurs that there is a point coincident to the first point of the first line, inedges[0]
will be -1. Therefore, find(x, y, i = 0)
will return -1 independent of x
and y
(because of how the _step
function is implemented) — but find(x, y, i = 1)
will not return -1 (or maybe only for i = 2, 3,...
).
Question:
i
and calling find(x, y, i)
) or by d3-delaunay?See demo at https://observablehq.com/d/b31c2945b6082f94
I'm creating these test points with a linear formula, so it's just rounding errors that make the points "almost collinear". But the consequence is that Delaunator finds triangles — which could OK except that d3-delaunay then fails when it computes the Voronoi (rounding errors in the circumcenters I suspect).
I'm not sure if this should be dealt with upstream or here. I managed to fix it by changing the test on minRadius from minRadius === Infinity
to minRadius < 1e30
, so that the second chance of #64 (jittering) kicks in. It might be the solution, but then it breaks the Delaunator tests.
Currently we throw an error from Delaunator:
Error: No Delaunay triangulation exists for this input.
There is a valid Voronoi diagram for n = 1 and n = 2, so we should allow an empty Delaunay triangulation with no triangles in these cases. And similarly for n = 0, we can have an empty Voronoi diagram with no cells.
More performance!
See also #49 ;)
Currently, the voronoi()
method is much slower than it could be — 2.3x slower on a million-point sample than the Delaunay pass, despite the fact that Delaunay is O(n log n) and getting its dual should in theory be only O(n).
It's slow due to the way cell edges are connected in Cell.js
. Each cell keeps an array of disjoint connected components which it attempts to join with each incoming half-edge, having to loop through all components constantly, allocate tons of small arrays, and connect with very expensive concat
/splice
array operations.
Instead, I believe cells can be connected with a simple linear-time algorithm. Each half-edge belongs to only one cell. So we'll go through each half-edge whose cell hasn't yet been connected and connect it through other half-edges of the cell at once. Here's a rough illustration:
cc @mbostock
Not sure if this is a bug per se, but it would be nice to avoid them.
Is there a way to find the voronoi cell covering a point? And once you have a cell, is there a way of getting all the neighboring cells?
Since cells are in sorted order we need a way to match up with the original input site. Is delaunay.ids sufficient?
A lot faster than [[x0, y0], [x1, y1], …].
In d3-voronoi voronoi.find accepts a third argument, radius, which returns the nearest point from that distance. In this case the third argument i, specifies the index where the search starts.
I find the radius useful for creating distance-limited interactions. Is this something that you may consider adding?
The red Voronoi edge that should be pointing diagonally down and to the right is missing here:
The input is:
Delaunay.from([[100, 100], [200, 100], [100, 200]])
The issue is that the circumcenter of the triangle [150, 150] is coincident with the midpoint of the triangle vertexes on the convex hull [200, 100] and [100, 200], so we’re not able to compute the direction of the vector.
These are still marked as TODO in the README.
See this section in my "Lloyd’s Algorithm With Velocities" notebook.
As far as I can tell I inlined all of Delaunator + d3-delaunay. Then I added caching of the typed arrays used in the constructor, plus an update
method on each. The idea is to re-use those arrays and reduce allocation/GC pressure.
However, trying to use this version fails because... well, I'm not sure? I can't see anything that am I missing from the original libraries.
It breaks on line 35 of delaunay.js. The problem, as far as I can tell, is that hull
is a typed array. Yet somehow, in this library, it has been extended with a next
, i
and t
property. But I can't actually find any of that in the original Delaunator code so I guess I must be missing something?
constructor(points) {
const { halfedges, hull, triangles } = this.delaunator = new Delaunator(points);
/* ... */
// For points on the hull, index both the incoming and outgoing halfedges.
let node0, node1 = hull;
do {
node0 = node1, node1 = node1.next;
inedges[node1.i] = node0.t;
outedges[node0.i] = node1.t;
} while (node1 !== hull);
}
Currently voronoi.find only traverses internal edges of the Delaunay triangulation; it doesn’t traverse edges on the convex hull.
In Delaunator, the convex hull is kept as a circular doubly linked list internally for convenience/performance during the Delaunay sweep phase, but I think there's no point in exposing it like this in a public API — it would be simpler to flatten it after Delaunay construction and remove the "Node" section in Voronator API reference.
The only question is whether we should do this in Delaunator (and expose hull
as a Uint32Array
publicly), or Voronator.
Now that mapbox/delaunator#17 is fixed, we should support the same API for the Delaunay constructor. Or, if we want to retain the current private copy constructor API, we’d need to expose a new factory method. Delaunay.of(array) comes to mind, but that seems like a bad idea—that should be reserved for Delaunay.of(…values) for consistency with Array.of. So some options:
Remove the copy constructor and just do new Delaunay(array). Pros: simple. Cons: copying a Delaunay instance would then require Object.create, but I don’t really anticipate this being a common pattern anyway; requires the new
operator.
Rename Delaunay.from to Delaunay.fromPoints and introduce a new Delaunay.from that takes the flat array. Pros: retains copy constructor. Cons: confusing terminology, as both constructors accept “points”.
Add Delaunay.fromFlat(array), and keep existing constructor and Delaunay.from. Pros: does everything. Cons: fromFlat is the ugliest name for the use case we want to encourage.
Detect in Delaunay.from whether the given array is flat or not. Pros: “just works”. Cons: sometimes it doesn’t, and overloading by type is icky.
Feels like the first option is the “obvious” choice, but wanted to consider the others.
It’s already implemented; we might as well expose it.
For convenience.
Maybe also delaunay.renderPoint(i, context).
I get the following error when I try to use this library on Linux:
Module not found: Can't resolve './polygon' in '/home/brent/git/terrain3/node_modules/d3-delaunay/src'
This is because the file is named Polygon.js, but gets imported as "polygon".
https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js#L3
Renaming the file to "polygon.js" in my node_modules fixes the issue.
This throws an error (No Delaunay triangulation exists for this input):
Delaunay.from([[0, 0], [1, 1], [2, 2]])
But like #19, there is a valid Voronoi diagram for this input! The problem is that all the cells have infinite sides and no points. Hrm.
https://beta.observablehq.com/d/3b28638926bcac75 fixes the last part of https://beta.observablehq.com/@mbostock/the-delaunays-dual
(sorry for the weird alignments, they're prettier)
Delaunay.from([[0,171],[0,62],[0,15]])
complains with:
index.js:91 Uncaught Error: No Delaunay triangulation exists for this input.
at new Delaunator (index.js:91)
at new Delaunay (delaunay.js:18)
Some wrong voronoi.cellPolygon
results maybe related to floating points precision.
Hi! I've tried to reproduce the famous @mbostock Mike & Mario sketch rotating-voronoi.
But I noticed some problems. Talking with @Fil in the d3 slack he came up with a observable nootbook to reproduce the problem.
https://observablehq.com/d/bd8a95abd9a01c79
I've tried with both d3-delaunay version 5.0.2 and 4.0.2
@Fil added this note:
change 253.74999999999997 to 253.75
Thanks!
My library currently depends on d3-voronoi
, and I'm trying to upgrade to d3-delaunay
for performance improvements. Unfortunately, the lack of a transpiled target is a blocker. Transpiling it myself with webpack works for publishing the dist
version of my library, but I'm currently also providing a transpiled lib
which is how most of my users consume my library. At the moment, including this package would force all of those people to alter their builds to accommodate the change.
If you modify this notebook so that the voronoi extent is [0, 0, width, height], it will crash shortly:
https://beta.observablehq.com/@mbostock/voronoi-particles
Edit: It seems to hang even with a larger extent. Just less often. Hmmm.
Because of d3-delaunay
uses a lot of ECMAScript new and experimental feature (e.g. class, exponential operator) for production build, it causes issues for production use.
Do you have a plan to use transpiler like babel to build a production module?
Currently, cell.triangles is undefined.
We should probably change cell.render(context) to be a no-op in this case, too.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.